Slightly generalize case_to_values and case_from_values functions, and

[pspp] / src / libpspp / tower.c

diff --git a/src/libpspp/tower.c b/src/libpspp/tower.c
index ead91e61a7093beda05e3708256be0ed9222b7d0..0786bbbc2fd59212f847e5bc321c87bc5575d4c2 100644 (file)
--- a/src/libpspp/tower.c
+++ b/src/libpspp/tower.c
@@ -20,13 +20,18 @@
 
 #include <libpspp/tower.h>
 
+#include <limits.h>
+
 #include <libpspp/assertion.h>
 #include <libpspp/compiler.h>
 
 static struct tower_node *abt_to_tower_node (const struct abt_node *);
 static struct tower_node *first_node (const struct tower *);
+static struct tower_node *last_node (const struct tower *);
 static struct tower_node *next_node (const struct tower *,
                                      const struct tower_node *);
+static struct tower_node *prev_node (const struct tower *,
+                                     const struct tower_node *);
 static unsigned long int get_subtree_height (const struct abt_node *);
 static void reaugment_tower_node (struct abt_node *,
                                   const struct abt_node *,
@@ -38,6 +43,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 +70,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 +79,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 +91,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 +119,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 +128,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 +164,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 
@@ -168,6 +187,14 @@ tower_first (const struct tower *t)
   return first_node (t);
 }
 
+/* Returns the node at the top of tower T, or a null pointer if T
+   is empty. */
+struct tower_node *
+tower_last (const struct tower *t) 
+{
+  return last_node (t);
+}
+
 /* If NODE is nonnull, returns the node just above NODE in tower
    T, or a null pointer if NODE is the topmost node in T.
    If NODE is null, acts like tower_first. */
@@ -176,6 +203,15 @@ tower_next (const struct tower *t, const struct tower_node *node)
 {
   return node != NULL ? next_node (t, node) : first_node (t);
 }
+
+/* If NODE is nonnull, returns the node just below NODE in tower
+   T, or a null pointer if NODE is the bottommost node in T.
+   If NODE is null, acts like tower_last. */
+struct tower_node *
+tower_prev (const struct tower *t, const struct tower_node *node) 
+{
+  return node != NULL ? prev_node (t, node) : last_node (t);
+}
 \f
 /* Returns the tower node corresponding to the given ABT_NODE. */
 static struct tower_node *
@@ -184,20 +220,39 @@ abt_to_tower_node (const struct abt_node *abt_node)
   return abt_data (abt_node, struct tower_node, abt_node);
 }
 
+/* Returns the tower node corresponding to the given ABT_NODE. */
+static struct tower_node *
+abt_to_tower_node_null (const struct abt_node *abt_node) 
+{
+  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+}
+
 /* Returns the first node in TOWER. */
 static struct tower_node *
 first_node (const struct tower *t) 
 {
-  struct abt_node *abt_node = abt_first (&t->abt);
-  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+  return abt_to_tower_node_null (abt_first (&t->abt));
+}
+
+/* Returns the first node in TOWER. */
+static struct tower_node *
+last_node (const struct tower *t) 
+{
+  return abt_to_tower_node_null (abt_last (&t->abt));
 }
 
 /* Returns the next node in TOWER after NODE. */
 static struct tower_node *
 next_node (const struct tower *t, const struct tower_node *node) 
 {
-  struct abt_node *abt_node = abt_next (&t->abt, &node->abt_node);
-  return abt_node != NULL ? abt_to_tower_node (abt_node) : NULL;
+  return abt_to_tower_node_null (abt_next (&t->abt, &node->abt_node));
+}
+
+/* Returns the previous node in TOWER before NODE. */
+static struct tower_node *
+prev_node (const struct tower *t, const struct tower_node *node) 
+{
+  return abt_to_tower_node_null (abt_prev (&t->abt, &node->abt_node));
 }
 
 /* Returns the total height of the nodes in the subtree rooted at