aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorLukas Fleischer <calcurse@cryptocrack.de>2011-09-28 16:13:17 +0200
committerLukas Fleischer <calcurse@cryptocrack.de>2011-10-05 12:25:48 +0200
commita0afb7ded2fba68e710afda1053dba2a20b4665f (patch)
tree3592e3b3def25a654a44790e41ca800946a3bcc4 /src
parent718a6cfee4916f347636215ee35313610793f9bd (diff)
downloadcalcurse-a0afb7ded2fba68e710afda1053dba2a20b4665f.tar.gz
calcurse-a0afb7ded2fba68e710afda1053dba2a20b4665f.zip
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>
Diffstat (limited to 'src')
-rw-r--r--src/llist.c20
-rw-r--r--src/llist.h1
-rw-r--r--src/llist_ts.h1
3 files changed, 16 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);
}
}
diff --git a/src/llist.h b/src/llist.h
index d7e4249..cdab18d 100644
--- a/src/llist.h
+++ b/src/llist.h
@@ -44,6 +44,7 @@ struct llist_item {
typedef struct llist llist_t;
struct llist {
struct llist_item *head;
+ struct llist_item *tail;
};
typedef int (*llist_fn_cmp_t) (void *, void *);
diff --git a/src/llist_ts.h b/src/llist_ts.h
index 0f90024..e7a6b3c 100644
--- a/src/llist_ts.h
+++ b/src/llist_ts.h
@@ -38,6 +38,7 @@
typedef struct llist_ts llist_ts_t;
struct llist_ts {
llist_item_t *head;
+ llist_item_t *tail;
pthread_mutex_t mutex;
};