X-Git-Url: https://pintos-os.org/cgi-bin/gitweb.cgi?a=blobdiff_plain;f=src%2Flibpspp%2Fabt.c;h=c06047b4abdbb8e128910a17049f972893abd295;hb=81579d9e9f994fb2908f50af41c3eb033d216e58;hp=c181b90473f84b19590c572de6d9961aa40115c4;hpb=9683d7528884fcb3c60705812de9f96889536388;p=pspp-builds.git

diff --git a/src/libpspp/abt.c b/src/libpspp/abt.c
index c181b904..c06047b4 100644
--- a/src/libpspp/abt.c
+++ b/src/libpspp/abt.c
@@ -1,20 +1,18 @@
-/* PSPP - computes sample statistics.
-   Copyright (C) 2007 Free Software Foundation, Inc.
+/* PSPP - a program for statistical analysis.
+   Copyright (C) 2007, 2009, 2011 Free Software Foundation, Inc.
 
-   This program is free software; you can redistribute it and/or
-   modify it under the terms of the GNU General Public License as
-   published by the Free Software Foundation; either version 2 of the
-   License, or (at your option) any later version.
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
 
-   This program is distributed in the hope that it will be useful, but
-   WITHOUT ANY WARRANTY; without even the implied warranty of
-   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
-   General Public License for more details.
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
 
    You should have received a copy of the GNU General Public License
-   along with this program; if not, write to the Free Software
-   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-   02110-1301, USA. */
+   along with this program.  If not, see <http://www.gnu.org/licenses/>. */
 
 /* Augmented binary tree (ABT) data structure. */
 
@@ -30,20 +28,34 @@
 #include <config.h>
 #endif
 
-#include <libpspp/abt.h>
+#include "libpspp/abt.h"
+
+#include <stdbool.h>
+
+#include "libpspp/cast.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) 
+          const void *aux)
 {
+  assert (reaugment != NULL);
   abt->root = NULL;
   abt->compare = compare;
   abt->reaugment = reaugment;
@@ -53,24 +65,26 @@ abt_init (struct abt *abt,
 /* 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) 
+abt_insert (struct abt *abt, struct abt_node *node)
 {
   node->down[0] = NULL;
   node->down[1] = NULL;
   node->level = 1;
 
-  if (abt->root == NULL) 
+  if (abt->root == NULL)
     {
       abt->root = node;
       node->up = NULL;
       abt_reaugmented (abt, node);
     }
-  else 
+  else
     {
       struct abt_node *p = abt->root;
-      for (;;) 
+      for (;;)
         {
           int cmp, dir;
 
@@ -87,10 +101,10 @@ abt_insert (struct abt *abt, struct abt_node *node)
               break;
             }
           p = p->down[dir];
-        } 
+        }
     }
 
-  while ((node = node->up) != NULL) 
+  while ((node = node->up) != NULL)
     {
       node = skew (abt, node);
       node = split (abt, node);
@@ -99,6 +113,77 @@ abt_insert (struct abt *abt, struct abt_node *node)
   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, const 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;
+        }
+      CONST_CAST (struct abt_node *, p)->down[dir] = node;
+      node->up = CONST_CAST (struct abt_node *, 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, 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, p, false, node);
+}
+
 /* Deletes P from ABT. */
 void
 abt_delete (struct abt *abt, struct abt_node *p)
@@ -159,44 +244,46 @@ abt_delete (struct abt *abt, struct abt_node *p)
 }
 
 /* Returns the node with minimum value in ABT, or a null pointer
-   if ABT is empty. */ 
+   if ABT is empty. */
 struct abt_node *
-abt_first (const struct abt *abt) 
+abt_first (const struct abt *abt)
 {
   struct abt_node *p = abt->root;
-  if (p != NULL) 
+  if (p != NULL)
     while (p->down[0] != NULL)
       p = p->down[0];
   return p;
 }
 
 /* Returns the node with maximum value in ABT, or a null pointer
-   if ABT is empty. */ 
+   if ABT is empty. */
 struct abt_node *
-abt_last (const struct abt *abt) 
+abt_last (const struct abt *abt)
 {
   struct abt_node *p = abt->root;
-  if (p != NULL) 
+  if (p != NULL)
     while (p->down[1] != NULL)
       p = p->down[1];
   return p;
 }
 
 /* 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)
 {
   const struct abt_node *p;
   int cmp;
-  
+
   for (p = abt->root; p != NULL; p = p->down[cmp > 0])
     {
       cmp = abt->compare (target, p, abt->aux);
       if (cmp == 0)
-        return (struct abt_node *) p;
+        return CONST_CAST (struct abt_node *, p);
     }
-  
+
   return NULL;
 }
 
@@ -205,9 +292,9 @@ abt_find (const struct abt *abt, const struct abt_node *target)
    Returns a null pointer if P is the maximum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *
-abt_next (const struct abt *abt, const struct abt_node *p) 
+abt_next (const struct abt *abt, const struct abt_node *p)
 {
-  if (p == NULL) 
+  if (p == NULL)
     return abt_first (abt);
   else if (p->down[1] == NULL)
     {
@@ -221,7 +308,7 @@ abt_next (const struct abt *abt, const struct abt_node *p)
       p = p->down[1];
       while (p->down[0] != NULL)
         p = p->down[0];
-      return (struct abt_node *) p;
+      return CONST_CAST (struct abt_node *, p);
     }
 }
 
@@ -230,9 +317,9 @@ abt_next (const struct abt *abt, const struct abt_node *p)
    Returns a null pointer if P is the minimum node in ABT or if P
    is null and ABT is empty. */
 struct abt_node *
-abt_prev (const struct abt *abt, const struct abt_node *p) 
+abt_prev (const struct abt *abt, const struct abt_node *p)
 {
-  if (p == NULL) 
+  if (p == NULL)
     return abt_last (abt);
   else if (p->down[0] == NULL)
     {
@@ -246,7 +333,7 @@ abt_prev (const struct abt *abt, const struct abt_node *p)
       p = p->down[0];
       while (p->down[1] != NULL)
         p = p->down[1];
-      return (struct abt_node *) p;
+      return CONST_CAST (struct abt_node *, p);
     }
 }
 
@@ -261,7 +348,7 @@ abt_prev (const struct abt *abt, const struct abt_node *p)
    affected nodes from the tree, update their values, then
    re-insert all of them. */
 void
-abt_reaugmented (const struct abt *abt, struct abt_node *p) 
+abt_reaugmented (const struct abt *abt, struct abt_node *p)
 {
   for (; p != NULL; p = p->up)
     abt->reaugment (p, p->down[0], p->down[1], abt->aux);
@@ -276,29 +363,33 @@ abt_reaugmented (const struct abt *abt, struct abt_node *p)
    can actually retain its relative position in ABT, e.g. its key
    has only been adjusted slightly.  Otherwise, it is more
    efficient to simply remove P from ABT, change its key, and
-   re-insert P.  
+   re-insert P.
 
    It is not safe to update more than one node's key, then to
    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) 
+abt_changed (struct abt *abt, struct abt_node *p)
 {
   struct abt_node *prev = abt_prev (abt, p);
   struct abt_node *next = abt_next (abt, p);
 
   if ((prev != NULL && abt->compare (prev, p, abt->aux) >= 0)
-      || (next != NULL && abt->compare (p, next, abt->aux) >= 0)) 
+      || (next != NULL && abt->compare (p, next, abt->aux) >= 0))
     {
       abt_delete (abt, p);
       return abt_insert (abt, p);
     }
-  else 
+  else
     {
       abt_reaugmented (abt, p);
-      return NULL; 
+      return NULL;
     }
 }
 
@@ -312,14 +403,17 @@ abt_changed (struct abt *abt, struct abt_node *p)
    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) 
+abt_moved (struct abt *abt, struct abt_node *p)
 {
-  if (p->up != NULL) 
+  if (p->up != NULL)
     {
       int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
-      p->up->down[d] = p; 
+      p->up->down[d] = p;
     }
   else
     abt->root = p;
@@ -332,7 +426,7 @@ abt_moved (struct abt *abt, struct abt_node *p)
 /* Returns the address of the pointer that points down to P
    within ABT. */
 static struct abt_node **
-down_link (struct abt *abt, struct abt_node *p) 
+down_link (struct abt *abt, struct abt_node *p)
 {
   return (p->up != NULL
           ? &p->up->down[p->up->down[0] != p]