vis

commit e3cf021629db7add2f78e0ea7ec3d6a79eae6e0d
parent b5f9c1a66569080fd5c8519f1f3b25f1ab23d60f
Author: Marc André Tanner <mat@brain-dump.org>
Date:   Tue, 31 Jan 2017 14:05:18 +0100

sam: optmize transcript insertion for common case

This esentially performs an insertion sort. Rather than iterating the list
from the start every time keep track of the latest change and optmize for
monotonically increasing file positions.

Diffstat:
M
sam.c
 | 
11
+++++++++--
M
vis-core.h
 | 
1
+

2 files changed, 10 insertions(+), 2 deletions(-)
diff --git a/sam.c b/sam.c
@@ -444,8 +444,14 @@ static void change_free(Change *c) {
 static Change *change_new(Transcript *t, enum ChangeType type, Filerange *range, Win *win, Cursor *cur) {
 	if (!text_range_valid(range))
 		return NULL;
-	// TODO optimize for common case
-	Change **prev = &t->changes, *next = t->changes;
+	Change **prev, *next;
+	if (t->latest && t->latest->range.end <= range->start) {
+		prev = &t->latest->next;
+		next = t->latest->next;
+	} else {
+		prev = &t->changes;
+		next = t->changes;
+	}
 	while (next && next->range.end <= range->start) {
 		prev = &next->next;
 		next = next->next;
@@ -462,6 +468,7 @@ static Change *change_new(Transcript *t, enum ChangeType type, Filerange *range,
 		new->win = win;
 		new->next = next;
 		*prev = new;
+		t->latest = new;
 	}
 	return new;
 }
diff --git a/vis-core.h b/vis-core.h
@@ -110,6 +110,7 @@ typedef struct {             /** collects all information until an operator is e
 typedef struct Change Change;
 typedef struct {
 	Change *changes;      /* all changes in monotonically increasing file position */
+	Change *latest;       /* most recent change */
 	enum SamError error;  /* non-zero in case something went wrong */
 } Transcript;