[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Pspp-cvs] pspp/src/libpspp ChangeLog tower.c tower.h
From: |
Ben Pfaff |
Subject: |
[Pspp-cvs] pspp/src/libpspp ChangeLog tower.c tower.h |
Date: |
Mon, 04 Jun 2007 01:29:08 +0000 |
CVSROOT: /cvsroot/pspp
Module name: pspp
Changes by: Ben Pfaff <blp> 07/06/04 01:29:08
Modified files:
src/libpspp : ChangeLog tower.c tower.h
Log message:
* 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.
CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ChangeLog?cvsroot=pspp&r1=1.68&r2=1.69
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.c?cvsroot=pspp&r1=1.2&r2=1.3
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/tower.h?cvsroot=pspp&r1=1.2&r2=1.3
Patches:
Index: ChangeLog
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/ChangeLog,v
retrieving revision 1.68
retrieving revision 1.69
diff -u -b -r1.68 -r1.69
--- ChangeLog 4 Jun 2007 01:22:47 -0000 1.68
+++ ChangeLog 4 Jun 2007 01:29:08 -0000 1.69
@@ -1,5 +1,11 @@
2007-06-03 Ben Pfaff <address@hidden>
+ * 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.
Index: tower.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/tower.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -b -r1.2 -r1.3
--- tower.c 3 Apr 2007 22:55:07 -0000 1.2
+++ tower.c 4 Jun 2007 01:29:08 -0000 1.3
@@ -20,6 +20,8 @@
#include <libpspp/tower.h>
+#include <limits.h>
+
#include <libpspp/assertion.h>
#include <libpspp/compiler.h>
@@ -38,6 +40,7 @@
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 @@
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 @@
{
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 @@
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 @@
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 @@
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 @@
if (height < node_height)
{
/* Our goal height is in P. */
+ t->cache = node;
+ t->cache_bottom = *node_start;
return node;
}
else
Index: tower.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/tower.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -b -r1.2 -r1.3
--- tower.h 3 Apr 2007 22:55:07 -0000 1.2
+++ tower.h 4 Jun 2007 01:29:08 -0000 1.3
@@ -75,6 +75,8 @@
struct tower
{
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 *);
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Pspp-cvs] pspp/src/libpspp ChangeLog tower.c tower.h,
Ben Pfaff <=