From 8a419b7d67feaa587fe0b0b9c3d0521389a4d5ef Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Marc=20Andr=C3=A9=20Tanner?= Date: Tue, 31 Jan 2017 14:05:18 +0100 Subject: 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. --- sam.c | 11 +++++++++-- 1 file changed, 9 insertions(+), 2 deletions(-) (limited to 'sam.c') 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; } -- cgit v1.2.3