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 +++++++++-- vis-core.h | 1 + 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; -- cgit v1.2.3