src/llist.c: Add a tail pointer

Adding a tail pointer to each list increases memory footprint by four
bytes, while reducing the runtime of llist_add() from O(n) to O(1). In
testing, the time required to append 100000 elements to a linked list
was reduced from 29.245s to 0.009s.

Our second main concern is to reduce the runtime of llist_add_sorted()
when inserting elements from a presorted list (this is reduced from O(n)
to O(1) as well), since the data files contain appointments in sorted
order and are always processed front to back.

Some local numbers show how this speeds up calcurse startup (test set
with 50000 appointments):

    0.22user 0.12system 0:00.35elapsed 99%CPU (0avgtext+0avgdata 5396maxresident)k
    0inputs+8outputs (0major+1398minor)pagefaults 0swaps

As opposed to the unpatched binary:

    21.97user 0.25system 0:22.23elapsed 99%CPU (0avgtext+0avgdata 5388maxresident)k
    0inputs+48outputs (0major+1396minor)pagefaults 0swaps

This is a ~10000% increase in speed. Timings for reading random input
files generated by a script stay the same (32.391s vs. 31.776s).

Signed-off-by: Lukas Fleischer <calcurse@cryptocrack.de>

1 files changed, 14 insertions, 6 deletions

diff --git a/src/llist.c b/src/llist.c
index eeded6b..7611595 100644
--- a/src/llist.c
+++ b/src/llist.c
@@ -43,6 +43,7 @@ void
 llist_init (llist_t *l)
 {
   l->head = NULL;
+  l->tail = NULL;
 }
 
 /*
@@ -60,6 +61,7 @@ llist_free (llist_t *l)
     }
 
   l->head = NULL;
+  l->tail = NULL;
 }
 
 /*
@@ -128,7 +130,6 @@ void
 llist_add (llist_t *l, void *data)
 {
   llist_item_t *o = mem_malloc (sizeof (llist_item_t));
-  llist_item_t *i;
 
   if (o)
     {
@@ -136,12 +137,11 @@ llist_add (llist_t *l, void *data)
       o->next = NULL;
 
       if (!l->head)
-        l->head = o;
+        l->head = l->tail = o;
       else
         {
-          for (i = l->head; i->next; i = i->next)
-            ;
-          i->next = o;
+          l->tail->next = o;
+          l->tail = o;
         }
     }
 }
@@ -161,7 +161,12 @@ llist_add_sorted (llist_t *l, void *data, llist_fn_cmp_t fn_cmp)
       o->next = NULL;
 
       if (!l->head)
-        l->head = o;
+        l->head = l->tail = o;
+      else if (fn_cmp(o->data, l->tail->data) >= 0)
+        {
+          l->tail->next = o;
+          l->tail = o;
+        }
       else if (fn_cmp(o->data, l->head->data) < 0)
         {
           o->next = l->head;
@@ -198,6 +203,9 @@ llist_remove (llist_t *l, llist_item_t *i)
     {
       if (j)
         j->next = i->next;
+      if (i == l->tail)
+        l->tail = j;
+
       mem_free (i);
     }
 }