[Pspp-cvs] pspp tests/libpspp/abt-test.c src/libpspp/abt.h... [simpler-proc]

[Ben Pfaff]

CVSROOT:        /cvsroot/pspp
Module name:    pspp
Branch:         simpler-proc
Changes by:     Ben Pfaff <blp> 07/03/28 05:16:13

Modified files:
        tests/libpspp  : abt-test.c 
        src/libpspp    : abt.h abt.c 

Log message:
        Allow ABTs to lack comparison function.
        Patch #5828.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/pspp/tests/libpspp/abt-test.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1&r2=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/abt.h?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1&r2=1.1.2.1
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/abt.c?cvsroot=pspp&only_with_tag=simpler-proc&r1=1.1&r2=1.1.2.1

Patches:
Index: tests/libpspp/abt-test.c
===================================================================
RCS file: /cvsroot/pspp/pspp/tests/libpspp/abt-test.c,v
retrieving revision 1.1
retrieving revision 1.1.2.1
diff -u -b -r1.1 -r1.1.2.1
--- tests/libpspp/abt-test.c    26 Jan 2007 03:34:01 -0000      1.1
+++ tests/libpspp/abt-test.c    28 Mar 2007 05:16:13 -0000      1.1.2.1
@@ -336,6 +336,8 @@
   order = xmemdup (data, cnt * sizeof *data);
   qsort (order, cnt, sizeof *order, compare_ints_noaux);
 
+  if (abt->compare != NULL) 
+    {
   for (i = 0; i < cnt; i++)
     {
       struct abt_node *p;
@@ -352,6 +354,7 @@
 
   e.data = -1;
   check (abt_find (abt, &e.node) == NULL);
+    }
 
   check_levels (abt->root);
   check_augmentations (abt->root);
@@ -381,12 +384,57 @@
   free (order);
 }
 
+/* Ways that nodes can be inserted. */
+enum insertion_method 
+  {
+    INSERT,             /* With abt_insert. */
+    INSERT_AFTER,       /* With abt_insert_after. */
+    INSERT_BEFORE       /* With abt_insert_before. */
+  };
+
+/* Inserts INSERT into ABT with the given METHOD. */
+static void
+insert_node (struct abt *abt, struct element *insert,
+             enum insertion_method method) 
+{
+  if (method == INSERT) 
+    check (abt_insert (abt, &insert->node) == NULL);
+  else 
+    {
+      struct abt_node *p = abt->root;
+      int dir = 0;
+      if (p != NULL)
+        for (;;) 
+          {
+            dir = insert->data > abt_node_to_element (p)->data;
+            if (p->down[dir] == NULL)
+              break;
+            p = p->down[dir];
+          }
+      if (method == INSERT_AFTER) 
+        {
+          if (p != NULL && (dir != 1 || p->down[1] != NULL))
+            p = abt_prev (abt, p);
+          abt_insert_after (abt, p, &insert->node); 
+        }
+      else
+        {
+          if (p != NULL && (dir != 0 || p->down[0] != NULL))
+            p = abt_next (abt, p);
+          abt_insert_before (abt, p, &insert->node); 
+        }
+    }
+}
+
+
 /* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
-   ABT in the order specified by INSERTIONS, then deletes them in
-   the order specified by DELETIONS, checking the ABT's contents
-   for correctness after each operation. */
+   ABT in the order specified by INSERTIONS using the given
+   METHOD, then deletes them in the order specified by DELETIONS,
+   checking the ABT's contents for correctness after each
+   operation. */
 static void
-test_insert_delete (const int insertions[],
+do_test_insert_delete (enum insertion_method method,
+                       const int insertions[],
                     const int deletions[],
                     size_t cnt) 
 {
@@ -398,11 +446,12 @@
   for (i = 0; i < cnt; i++)
     elements[i].data = i;
 
-  abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
+  abt_init (&abt, method == INSERT ? compare_elements : NULL,
+            reaugment_elements, &aux_data);
   check_abt (&abt, NULL, 0);
   for (i = 0; i < cnt; i++)
     {
-      check (abt_insert (&abt, &elements[insertions[i]].node) == NULL);
+      insert_node (&abt, &elements[insertions[i]], method);
       check_abt (&abt, insertions, i + 1);
     }
   for (i = 0; i < cnt; i++)
@@ -414,6 +463,20 @@
   free (elements);
 }
 
+/* Inserts the CNT values from 0 to CNT - 1 (inclusive) into an
+   ABT in the order specified by INSERTIONS, then deletes them in
+   the order specified by DELETIONS, checking the ABT's contents
+   for correctness after each operation. */
+static void
+test_insert_delete (const int insertions[],
+                    const int deletions[],
+                    size_t cnt) 
+{
+  do_test_insert_delete (INSERT, insertions, deletions, cnt);
+  do_test_insert_delete (INSERT_AFTER, insertions, deletions, cnt);
+  do_test_insert_delete (INSERT_BEFORE, insertions, deletions, cnt);
+}
+
 /* Inserts values into an ABT in each possible order, then
    removes them in each possible order, up to a specified maximum
    size. */

Index: src/libpspp/abt.h
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/abt.h,v
retrieving revision 1.1
retrieving revision 1.1.2.1
diff -u -b -r1.1 -r1.1.2.1
--- src/libpspp/abt.h   26 Jan 2007 03:34:00 -0000      1.1
+++ src/libpspp/abt.h   28 Mar 2007 05:16:13 -0000      1.1.2.1
@@ -61,7 +61,7 @@
    larger tree is rearranged, e.g. via a series of rotations,
    then the implementation will not call the reaugmentation
    function outside of the subtree, because the overall
-   augmentation data for the subtree is assumed not to changed.
+   augmentation data for the subtree is assumed not to change.
    This optimization is valid for the forms of augmentation
    described in CLR and Knuth (see below), and it is possible
    that it is valid for every efficient binary search tree
@@ -193,6 +193,10 @@
                const void *aux);
 
 struct abt_node *abt_insert (struct abt *, struct abt_node *);
+void abt_insert_after (struct abt *,
+                       const struct abt_node *, struct abt_node *);
+void abt_insert_before (struct abt *,
+                        const struct abt_node *, struct abt_node *);
 void abt_delete (struct abt *, struct abt_node *);
 
 struct abt_node *abt_first (const struct abt *);

Index: src/libpspp/abt.c
===================================================================
RCS file: /cvsroot/pspp/pspp/src/libpspp/abt.c,v
retrieving revision 1.1
retrieving revision 1.1.2.1
diff -u -b -r1.1 -r1.1.2.1
--- src/libpspp/abt.c   26 Jan 2007 03:34:00 -0000      1.1
+++ src/libpspp/abt.c   28 Mar 2007 05:16:13 -0000      1.1.2.1
@@ -32,18 +32,31 @@
 
 #include <libpspp/abt.h>
 
+#include <stdbool.h>
+
+#include <libpspp/assertion.h>
+
 static struct abt_node **down_link (struct abt *, struct abt_node *);
 static struct abt_node *skew (struct abt *, struct abt_node *);
 static struct abt_node *split (struct abt *, struct abt_node *);
 
 /* Initializes ABT as an empty ABT that uses COMPARE and
-   REAUGMENT functions, passing in AUX as auxiliary data. */
+   REAUGMENT functions, passing in AUX as auxiliary data.
+
+   The comparison function is optional.  If it is null, this
+   indicates that the tree is being used for its augmentations
+   only.  ABT functions that compare nodes may not be used with
+   trees that lack comparison functions; contrariwise, other
+   functions that could disrupt the ordering of a tree may not be
+   used if a comparison function is specified.  Refer to
+   individual function descriptions for details. */
 void
 abt_init (struct abt *abt,
           abt_compare_func *compare,
           abt_reaugment_func *reaugment,
           const void *aux) 
 {
+  assert (reaugment != NULL);
   abt->root = NULL;
   abt->compare = compare;
   abt->reaugment = reaugment;
@@ -53,7 +66,9 @@
 /* Inserts the given NODE into ABT.
    Returns a null pointer if successful.
    Returns the existing node already in ABT equal to NODE, on
-   failure. */
+   failure.
+   This function may be used only if ABT has a comparison
+   function. */
 struct abt_node *
 abt_insert (struct abt *abt, struct abt_node *node) 
 {
@@ -99,6 +114,77 @@
   return NULL;
 }
 
+/* Inserts NODE before or after node P in ABT, depending on the
+   value of AFTER.
+   If P is null, then the node is inserted as the first node in
+   the tree, if AFTER is true, or the last node, if AFTER is
+   false. */
+static inline void
+insert_relative (struct abt *abt, struct abt_node *p, bool after,
+                 struct abt_node *node)
+{
+  node->down[0] = NULL;
+  node->down[1] = NULL;
+  node->level = 1;
+
+  if (abt->root == NULL) 
+    {
+      assert (p == NULL);
+      abt->root = node;
+      node->up = NULL;
+      abt_reaugmented (abt, node);
+    }
+  else 
+    {
+      int dir = after;
+      if (p == NULL) 
+        {
+          p = abt->root;
+          dir = !after;
+        }
+      while (p->down[dir] != NULL) 
+        {
+          p = p->down[dir];
+          dir = !after; 
+        }
+      p->down[dir] = node;
+      node->up = p;
+      abt_reaugmented (abt, node);
+    }
+
+  while ((node = node->up) != NULL) 
+    {
+      node = skew (abt, node);
+      node = split (abt, node);
+    }
+}
+
+/* Inserts NODE after node P in ABT.
+   If P is null, then the node is inserted as the first node in
+   the tree.
+   This function may be used only if ABT lacks a comparison
+   function. */
+void
+abt_insert_after (struct abt *abt,
+                  const struct abt_node *p, struct abt_node *node) 
+{
+  assert (abt->compare == NULL);
+  insert_relative (abt, (struct abt_node *) p, true, node);
+}
+
+/* Inserts NODE before node P in ABT.
+   If P is null, then the node is inserted as the last node in
+   the tree.
+   This function may be used only if ABT lacks a comparison
+   function. */
+void
+abt_insert_before (struct abt *abt,
+                   const struct abt_node *p, struct abt_node *node) 
+{
+  assert (abt->compare == NULL);
+  insert_relative (abt, (struct abt_node *) p, false, node);
+}
+
 /* Deletes P from ABT. */
 void
 abt_delete (struct abt *abt, struct abt_node *p)
@@ -183,7 +269,9 @@
 }
 
 /* Searches ABT for a node equal to TARGET.
-   Returns the node if found, or a null pointer otherwise. */
+   Returns the node if found, or a null pointer otherwise.
+   This function may be used only if ABT has a comparison
+   function. */
 struct abt_node *
 abt_find (const struct abt *abt, const struct abt_node *target)
 {
@@ -282,7 +370,11 @@
    call this function for each node.  Instead, update a single
    node's key, call this function, update another node's key, and
    so on.  Alternatively, remove all affected nodes from the
-   tree, update their keys, then re-insert all of them. */
+   tree, update their keys, then re-insert all of them.
+
+   This function may be used only if ABT has a comparison
+   function.  If it doesn't, then you probably just want
+   abt_reaugmented. */
 struct abt_node *
 abt_changed (struct abt *abt, struct abt_node *p) 
 {
@@ -312,7 +404,10 @@
    function for each node.  Instead, move a single node, call
    this function, move another node, and so on.  Alternatively,
    remove all affected nodes from the tree, move them, then
-   re-insert all of them. */
+   re-insert all of them.
+
+   This function may be used only if ABT has a comparison
+   function. */
 void
 abt_moved (struct abt *abt, struct abt_node *p) 
 {