From de0ea5739d1b303ae5a2066802c84eaf55b42500 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Mon, 4 Jun 2007 01:29:08 +0000 Subject: [PATCH] * tower.c: Cache repeated lookups of a single tower element. This turns such lookups into O(1) operations without harming the big-O of other operations. * tower.h (struct tower): Add members for caching. --- src/libpspp/ChangeLog | 6 ++++++ src/libpspp/tower.c | 18 +++++++++++++++++- src/libpspp/tower.h | 4 +++- 3 files changed, 26 insertions(+), 2 deletions(-) diff --git a/src/libpspp/ChangeLog b/src/libpspp/ChangeLog index c125ac41..29acbae1 100644 --- a/src/libpspp/ChangeLog +++ b/src/libpspp/ChangeLog @@ -1,5 +1,11 @@ 2007-06-03 Ben Pfaff + * tower.c: Cache repeated lookups of a single tower element. This + turns such lookups into O(1) operations without harming the big-O + of other operations. + + * tower.h (struct tower): Add members for caching. + * range-set.c (range_set_clone): New function. * array.c (insert_range): New function. diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c index ead91e61..79801b3a 100644 --- a/src/libpspp/tower.c +++ b/src/libpspp/tower.c @@ -20,6 +20,8 @@ #include +#include + #include #include @@ -38,6 +40,7 @@ void tower_init (struct tower *t) { abt_init (&t->abt, NULL, reaugment_tower_node, NULL); + t->cache_bottom = ULONG_MAX; } /* Returns true if T contains no nodes, false otherwise. */ @@ -64,6 +67,7 @@ tower_insert (struct tower *t, unsigned long height, struct tower_node *new, new->height = height; abt_insert_before (&t->abt, under ? &under->abt_node : NULL, &new->abt_node); + t->cache_bottom = ULONG_MAX; } /* Deletes NODE from tower T. */ @@ -72,6 +76,7 @@ tower_delete (struct tower *t, struct tower_node *node) { struct tower_node *next = next_node (t, node); abt_delete (&t->abt, &node->abt_node); + t->cache_bottom = ULONG_MAX; return next; } @@ -83,6 +88,7 @@ tower_resize (struct tower *t, struct tower_node *node, assert (new_height > 0); node->height = new_height; abt_reaugmented (&t->abt, &node->abt_node); + t->cache_bottom = ULONG_MAX; } /* Removes nodes FIRST through LAST (exclusive) from tower SRC @@ -110,6 +116,7 @@ tower_splice (struct tower *dst, struct tower_node *under, abt_insert_before (&dst->abt, under ? &under->abt_node : NULL, &first->abt_node); } + dst->cache_bottom = src->cache_bottom = ULONG_MAX; } /* Returns the node at the given HEIGHT from the bottom of tower @@ -118,14 +125,21 @@ tower_splice (struct tower *dst, struct tower_node *under, of the returned node, which may be less than HEIGHT if HEIGHT refers to the middle of a node instead of its bottom. */ struct tower_node * -tower_lookup (const struct tower *t, +tower_lookup (const struct tower *t_, unsigned long height, unsigned long *node_start) { + struct tower *t = (struct tower *) t_; struct abt_node *p; assert (height < tower_height (t)); + if (height >= t->cache_bottom && height - t->cache_bottom < t->cache->height) + { + *node_start = t->cache_bottom; + return t->cache; + } + *node_start = 0; p = t->abt.root; for (;;) @@ -147,6 +161,8 @@ tower_lookup (const struct tower *t, if (height < node_height) { /* Our goal height is in P. */ + t->cache = node; + t->cache_bottom = *node_start; return node; } else diff --git a/src/libpspp/tower.h b/src/libpspp/tower.h index e0ee12a7..5a4c08e2 100644 --- a/src/libpspp/tower.h +++ b/src/libpspp/tower.h @@ -74,7 +74,9 @@ tower_node_get_height (const struct tower_node *node) /* A tower. */ struct tower { - struct abt abt; /* Tree. */ + struct abt abt; /* Tree. */ + struct tower_node *cache; /* Cache node. */ + unsigned long int cache_bottom; /* Height of cache's bottom. */ }; void tower_init (struct tower *); -- 2.30.2