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.

2 files changed, 10 insertions, 2 deletions

diff --git a/sam.c b/sam.c
index b232726..3238cb1 100644
--- 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
index 66c71c4..a1039a8 100644
--- 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;