Check in patch #5709: Augmented Balanced Tree data structure.
authorBen Pfaff <blp@gnu.org>
Fri, 26 Jan 2007 03:34:00 +0000 (03:34 +0000)
committerBen Pfaff <blp@gnu.org>
Fri, 26 Jan 2007 03:34:00 +0000 (03:34 +0000)
Thanks to John Darrington for review.

src/libpspp/ChangeLog
src/libpspp/abt.c [new file with mode: 0644]
src/libpspp/abt.h [new file with mode: 0644]
src/libpspp/automake.mk
tests/ChangeLog
tests/automake.mk
tests/libpspp/ChangeLog [deleted file]
tests/libpspp/abt-test.c [new file with mode: 0644]
tests/libpspp/heap-test.c
tests/libpspp/ll-test.c
tests/libpspp/llx-test.c

index ddecc4dff587f0b0f8d748ccde0f98380ca73d6d..3deaa432159c8689ebdda089f73ecfbead93f339 100644 (file)
@@ -1,3 +1,11 @@
+Wed Jan 24 21:13:32 2007  Ben Pfaff  <blp@gnu.org>
+
+       * abt.c: New file.
+
+       * abt.h: New file.
+
+       * automake.mk: Add abt.c, abt.h to sources.
+
 Sun Jan 14 21:44:18 2007  Ben Pfaff  <blp@gnu.org>
 
        * automake.mk: Add deque.h to sources.
diff --git a/src/libpspp/abt.c b/src/libpspp/abt.c
new file mode 100644 (file)
index 0000000..c181b90
--- /dev/null
@@ -0,0 +1,399 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 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 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. */
+
+/* Augmented binary tree (ABT) data structure. */
+
+/* These library routines have no external dependencies other
+   than the standard C library.
+
+   If you add routines in this file, please add a corresponding
+   test to abt-test.c.  This test program should achieve 100%
+   coverage of lines and branches in this code, as reported by
+   "gcov -b". */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <libpspp/abt.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. */
+void
+abt_init (struct abt *abt,
+          abt_compare_func *compare,
+          abt_reaugment_func *reaugment,
+          const void *aux) 
+{
+  abt->root = NULL;
+  abt->compare = compare;
+  abt->reaugment = reaugment;
+  abt->aux = aux;
+}
+
+/* Inserts the given NODE into ABT.
+   Returns a null pointer if successful.
+   Returns the existing node already in ABT equal to NODE, on
+   failure. */
+struct abt_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) 
+    {
+      abt->root = node;
+      node->up = NULL;
+      abt_reaugmented (abt, node);
+    }
+  else 
+    {
+      struct abt_node *p = abt->root;
+      for (;;) 
+        {
+          int cmp, dir;
+
+          cmp = abt->compare (node, p, abt->aux);
+          if (cmp == 0)
+            return p;
+
+          dir = cmp > 0;
+          if (p->down[dir] == NULL)
+            {
+              p->down[dir] = node;
+              node->up = p;
+              abt_reaugmented (abt, node);
+              break;
+            }
+          p = p->down[dir];
+        } 
+    }
+
+  while ((node = node->up) != NULL) 
+    {
+      node = skew (abt, node);
+      node = split (abt, node);
+    }
+
+  return NULL;
+}
+
+/* Deletes P from ABT. */
+void
+abt_delete (struct abt *abt, struct abt_node *p)
+{
+  struct abt_node **q = down_link (abt, p);
+  struct abt_node *r = p->down[1];
+  if (r == NULL)
+    {
+      *q = NULL;
+      p = p->up;
+    }
+  else if (r->down[0] == NULL)
+    {
+      r->down[0] = p->down[0];
+      *q = r;
+      r->up = p->up;
+      if (r->down[0] != NULL)
+        r->down[0]->up = r;
+      r->level = p->level;
+      p = r;
+    }
+  else
+    {
+      struct abt_node *s = r->down[0];
+      while (s->down[0] != NULL)
+        s = s->down[0];
+      r = s->up;
+      r->down[0] = s->down[1];
+      s->down[0] = p->down[0];
+      s->down[1] = p->down[1];
+      *q = s;
+      s->down[0]->up = s;
+      s->down[1]->up = s;
+      s->up = p->up;
+      s->level = p->level;
+      if (r->down[0] != NULL)
+        r->down[0]->up = r;
+      p = r;
+    }
+  abt_reaugmented (abt, p);
+
+  for (; p != NULL; p = p->up)
+    if ((p->down[0] != NULL ? p->down[0]->level : 0) < p->level - 1
+        || (p->down[1] != NULL ? p->down[1]->level : 0) < p->level - 1)
+      {
+        p->level--;
+        if (p->down[1] != NULL && p->down[1]->level > p->level)
+          p->down[1]->level = p->level;
+
+        p = skew (abt, p);
+        skew (abt, p->down[1]);
+        if (p->down[1]->down[1] != NULL)
+          skew (abt, p->down[1]->down[1]);
+
+        p = split (abt, p);
+        split (abt, p->down[1]);
+      }
+}
+
+/* Returns the node with minimum value in ABT, or a null pointer
+   if ABT is empty. */ 
+struct abt_node *
+abt_first (const struct abt *abt) 
+{
+  struct abt_node *p = abt->root;
+  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. */ 
+struct abt_node *
+abt_last (const struct abt *abt) 
+{
+  struct abt_node *p = abt->root;
+  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. */
+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 NULL;
+}
+
+/* Returns the node in ABT following P in in-order.
+   If P is null, returns the minimum node in ABT.
+   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) 
+{
+  if (p == NULL) 
+    return abt_first (abt);
+  else if (p->down[1] == NULL)
+    {
+      struct abt_node *q;
+      for (q = p->up; ; p = q, q = q->up)
+        if (q == NULL || p == q->down[0])
+          return q;
+    }
+  else
+    {
+      p = p->down[1];
+      while (p->down[0] != NULL)
+        p = p->down[0];
+      return (struct abt_node *) p;
+    }
+}
+
+/* Returns the node in ABT preceding P in in-order.
+   If P is null, returns the maximum node in ABT.
+   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) 
+{
+  if (p == NULL) 
+    return abt_last (abt);
+  else if (p->down[0] == NULL)
+    {
+      struct abt_node *q;
+      for (q = p->up; ; p = q, q = q->up)
+        if (q == NULL || p == q->down[1])
+          return q;
+    }
+  else
+    {
+      p = p->down[0];
+      while (p->down[1] != NULL)
+        p = p->down[1];
+      return (struct abt_node *) p;
+    }
+}
+
+/* Calls ABT's reaugmentation function to compensate for
+   augmentation data in P having been modified.  Use abt_changed,
+   instead, if the key data in P has changed.
+
+   It is not safe to update more than one node's augmentation
+   data, then to call this function for each node.  Instead,
+   update a single node's data, call this function, update
+   another node's data, and so on.  Alternatively, remove all
+   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) 
+{
+  for (; p != NULL; p = p->up)
+    abt->reaugment (p, p->down[0], p->down[1], abt->aux);
+}
+
+/* Moves P around in ABT to compensate for its key having
+   changed.  Returns a null pointer if successful.  If P's new
+   value is equal to that of some other node in ABT, returns the
+   other node after removing P from ABT.
+
+   This function is an optimization only if it is likely that 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.  
+
+   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. */
+struct abt_node *
+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)) 
+    {
+      abt_delete (abt, p);
+      return abt_insert (abt, p);
+    }
+  else 
+    {
+      abt_reaugmented (abt, p);
+      return NULL; 
+    }
+}
+
+/* ABT nodes may be moved around in memory as necessary, e.g. as
+   the result of an realloc operation on a block that contains a
+   node.  Once this is done, call this function passing node P
+   that was moved and its ABT before attempting any other
+   operation on ABT.
+
+   It is not safe to move more than one node, then to call this
+   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. */
+void
+abt_moved (struct abt *abt, struct abt_node *p) 
+{
+  if (p->up != NULL) 
+    {
+      int d = p->up->down[0] == NULL || abt->compare (p, p->up, abt->aux) > 0;
+      p->up->down[d] = p; 
+    }
+  else
+    abt->root = p;
+  if (p->down[0] != NULL)
+    p->down[0]->up = p;
+  if (p->down[1] != NULL)
+    p->down[1]->up = p;
+}
+\f
+/* 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) 
+{
+  return (p->up != NULL
+          ? &p->up->down[p->up->down[0] != p]
+          : &abt->root);
+}
+
+/* Remove a left "horizontal link" at A, if present.
+   Returns the node that occupies the position previously
+   occupied by A. */
+static struct abt_node *
+skew (struct abt *abt, struct abt_node *a)
+{
+  struct abt_node *b = a->down[0];
+  if (b != NULL && b->level == a->level)
+    {
+      /* Rotate right. */
+      a->down[0] = b->down[1];
+      b->down[1] = a;
+      *down_link (abt, a) = b;
+
+      if (a->down[0] != NULL)
+        a->down[0]->up = a;
+      b->up = a->up;
+      a->up = b;
+
+      abt->reaugment (a, a->down[0], a->down[1], abt->aux);
+      abt->reaugment (b, b->down[0], b->down[1], abt->aux);
+
+      return b;
+    }
+  else
+    return a;
+}
+
+/* Removes a pair of consecutive right "horizontal links" at A,
+   if present.
+   Returns the node that occupies the position previously
+   occupied by A. */
+static struct abt_node *
+split (struct abt *abt, struct abt_node *a)
+{
+  struct abt_node *b = a->down[1];
+  if (b != NULL && b->down[1] != NULL && b->down[1]->level == a->level)
+    {
+      /* Rotate left. */
+      a->down[1] = b->down[0];
+      b->down[0] = a;
+      *down_link (abt, a) = b;
+
+      if (a->down[1] != NULL)
+        a->down[1]->up = a;
+      b->up = a->up;
+      a->up = b;
+
+      b->level++;
+
+      abt->reaugment (a, a->down[0], a->down[1], abt->aux);
+      abt->reaugment (b, b->down[0], b->down[1], abt->aux);
+
+      return b;
+    }
+  else
+    return a;
+}
diff --git a/src/libpspp/abt.h b/src/libpspp/abt.h
new file mode 100644 (file)
index 0000000..f48e7a2
--- /dev/null
@@ -0,0 +1,208 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 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 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. */
+
+#ifndef LIBPSPP_ABT_H
+#define LIBPSPP_ABT_H 1
+
+/* Augmented binary tree (ABT) data structure.
+
+   A data structure can be "augmented" by defining new
+   information for it to maintain.  One commonly useful way to
+   augment a binary search tree-based data structure is to define
+   part of its data as a function of its immediate children's
+   data.  Furthermore, augmented data defined in this way can be
+   efficiently maintained as the tree changes over time.
+   
+   For example, suppose we define the "size" of a node as the sum
+   of the "size" of its immediate children, plus 1.  In such an
+   annotated BST with height H, we can find the node that would
+   be Kth in in-order traversal in O(H) time, instead of O(K)
+   time, which is a significant saving for balanced trees.
+
+   The ABT data structure partially abstracts augmentation.  The
+   client passes in a "reaugmentation" function that accepts a
+   node and its left and right children.  This function must
+   recalculate the node's augmentation data based on its own
+   contents and the contents of its children, and store the new
+   augmentation data in the node.
+
+   The ABT automatically calls the reaugmentation function
+   whenever it can tell that a node's augmentation data might
+   need to be updated: when the node is inserted or when a node's
+   descendants change due to insertion or deletion.  The ABT does
+   not know to call the reaugmentation function if a node's data
+   is updated while it is in the ABT.  In such a case, call the
+   abt_reaugmented or abt_changed function to update the
+   augmentation.
+
+   Augmentation is only partially abstracted: we do not provide
+   any way to search an ABT based on its augmentations.  The
+   tree structure is thus exposed to the client to allow it to
+   implement search.
+
+   To allow for optimization, the ABT implementation assumes that
+   the augmentation function in use is unaffected by the shape of
+   a binary search tree.  That is, if a given subtree within a
+   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.
+   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
+   augmentation.
+
+   The client should not need to be aware of the form of
+   balancing applied to the ABT, as its operation should be fully
+   encapsulated by the reaugmentation function.  The current
+   implementation uses an AA (Arne Andersson) tree, but this is
+   subject to change.
+
+   The following example illustrates how to use an ABT to build a
+   tree that can be searched either by a data value or in-order
+   position:
+
+     // Test data element.
+     struct element
+       {
+         struct abt_node node;       // Embedded binary tree element.
+         int data;                   // Primary value.
+         int count;                  // Number of nodes in subtree,
+                                     // including this node. 
+       };
+
+     // Returns the `struct element' that NODE is embedded within.
+     static struct element *
+     node_to_element (const struct abt_node *node)
+     {
+       return abt_data (node, struct element, node);
+     }
+
+     // Compares the DATA values in A and B and returns a
+     // strcmp-type return value.
+     static int
+     compare_elements (const struct abt_node *a_, const struct abt_node *b_,
+                       const void *aux) 
+     {
+       const struct element *a = node_to_element (a_);
+       const struct element *b = node_to_element (b_);
+
+       return a->data < b->data ? -1 : a->data > b->data;
+     }
+
+     // Recalculates the count for NODE's subtree by adding up the
+     // counts for its LEFT and RIGHT child subtrees.
+     static void
+     reaugment_elements (struct abt_node *node_,
+                         const struct abt_node *left,
+                         const struct abt_node *right,
+                         const void *aux) 
+     {
+       struct element *node = node_to_element (node_);
+       node->count = 1;
+       if (left != NULL)
+         node->count += node_to_element (left)->count;
+       if (right != NULL)
+         node->count += node_to_element (right)->count;
+     }
+
+     // Finds and returns the element in ABT that is in the given
+     // 0-based POSITION in in-order.
+     static struct element *
+     find_by_position (struct abt *abt, int position) 
+     {
+       struct abt_node *p;
+       for (p = abt->root; p != NULL; ) 
+         {
+           int p_pos = p->down[0] ? node_to_element (p->down[0])->count : 0;
+           if (position == p_pos)
+             return node_to_element (p);
+           else if (position < p_pos)
+             p = p->down[0]; 
+           else
+             {
+               p = p->down[1];
+               position -= p_pos + 1;
+             }
+         }
+       return NULL;
+     }
+
+   For more information on augmenting binary search tree-based
+   data structures, see Cormen-Leiserson-Rivest, chapter 15, or
+   Knuth vol. 3, section 6.2.3, under "Linear list
+   representation."  For more information on AA trees, see
+   <http://en.wikipedia.org/wiki/AA_tree>, which includes source
+   code and links to other resources, such as the original AA
+   tree paper.  */
+
+#include <stddef.h>
+
+/* Returns the data structure corresponding to the given NODE,
+   assuming that NODE is embedded as the given MEMBER name in
+   data type STRUCT. */
+#define abt_data(NODE, STRUCT, MEMBER)                                  \
+        ((STRUCT *) ((char *) (NODE) - offsetof (STRUCT, MEMBER)))
+
+/* Node in an augmented binary tree. */
+struct abt_node 
+  {
+    struct abt_node *up;        /* Parent (NULL for root). */
+    struct abt_node *down[2];   /* Left child, right child. */
+    int level;                  /* AA tree level (not ordinary BST level). */
+  };
+
+/* Compares nodes A and B, with the tree's AUX.
+   Returns a strcmp-like result. */
+typedef int abt_compare_func (const struct abt_node *a,
+                              const struct abt_node *b,
+                              const void *aux);
+
+/* Recalculates NODE's augmentation based on NODE's data and that
+   of its LEFT and RIGHT children, with the tree's AUX. */
+typedef void abt_reaugment_func (struct abt_node *node,
+                                 const struct abt_node *left,
+                                 const struct abt_node *right,
+                                 const void *aux);
+
+/* An augmented binary tree. */
+struct abt 
+  {
+    struct abt_node *root;         /* Tree's root, NULL if empty. */
+    abt_compare_func *compare;     /* To compare nodes. */
+    abt_reaugment_func *reaugment; /* To augment a node using its children. */
+    const void *aux;               /* Auxiliary data. */
+  };
+
+void abt_init (struct abt *, abt_compare_func *, abt_reaugment_func *,
+               const void *aux);
+
+struct abt_node *abt_insert (struct abt *, struct abt_node *);
+void abt_delete (struct abt *, struct abt_node *);
+
+struct abt_node *abt_first (const struct abt *);
+struct abt_node *abt_last (const struct abt *);
+struct abt_node *abt_find (const struct abt *, const struct abt_node *);
+struct abt_node *abt_next (const struct abt *, const struct abt_node *);
+struct abt_node *abt_prev (const struct abt *, const struct abt_node *);
+
+void abt_reaugmented (const struct abt *, struct abt_node *);
+struct abt_node *abt_changed (struct abt *, struct abt_node *);
+void abt_moved (struct abt *, struct abt_node *);
+
+#endif /* libpspp/abt.h */
index 0dcdc1b1b4d8b74c08feb7253d0a12bd43bd68e1..afbc34b0fe827213d8e24cf512e1d408a00c85d7 100644 (file)
@@ -4,6 +4,8 @@
 noinst_LIBRARIES += src/libpspp/libpspp.a
 
 src_libpspp_libpspp_a_SOURCES = \
+       src/libpspp/abt.c \
+       src/libpspp/abt.h \
        src/libpspp/array.c \
        src/libpspp/array.h \
        src/libpspp/assertion.h \
index c6a34d637fa559dc02a583b8696b4c1418b819a4..5b5c8912f1cfa59636a5ee07b3996053cbc1487f 100644 (file)
@@ -1,8 +1,17 @@
+Wed Jan 24 21:13:53 2007  Ben Pfaff  <blp@gnu.org>
+
+       * automake.mk: Add tests/libpspp/abt-test.
+
+       * libpspp/abt-test.c: New test.
+
+       * libpspp/heap-test.c, libpspp/ll-test.c, libpspp/llx-test.c:
+       Style fixes.
+
 Wed Jan 10 06:50:01 2007  Ben Pfaff  <blp@gnu.org>
 
        * automake.mk: Add tests/libpspp/heap-test.
 
-       * test/libpspp/heap-test.c: New test.
+       * libpspp/heap-test.c: New test.
 
 Wed Dec 13 21:00:46 2006  Ben Pfaff  <blp@gnu.org>
 
@@ -112,6 +121,10 @@ Sat Nov  4 16:08:58 2006  Ben Pfaff  <blp@gnu.org>
 
        * formats/wkday-out.sh: New test.
 
+Sun Oct 29 14:03:37 2006  Ben Pfaff  <blp@gnu.org>
+
+       * ll-test.c, llx-test.c: Reduce verbosity of output.
+
 Thu Oct 26 20:20:39 2006  Ben Pfaff  <blp@gnu.org>
 
        * automake.mk: Add tests/formats/float-format.sh.
index c83dd6e32f694a22ee039ad672dc1d0f1f44be9c..c976b89844239c13787dd464e92961a3a338e8aa 100644 (file)
@@ -132,13 +132,15 @@ TESTS = \
        tests/expressions/vectors.sh \
        tests/libpspp/ll-test \
        tests/libpspp/llx-test \
-       tests/libpspp/heap-test
+       tests/libpspp/heap-test \
+       tests/libpspp/abt-test
 
 check_PROGRAMS += \
        tests/libpspp/ll-test \
        tests/libpspp/llx-test \
        tests/formats/inexactify \
-       tests/libpspp/heap-test
+       tests/libpspp/heap-test \
+       tests/libpspp/abt-test
 
 tests_libpspp_ll_test_SOURCES = \
        src/libpspp/ll.c \
@@ -161,6 +163,13 @@ tests_libpspp_heap_test_SOURCES = \
 tests_libpspp_heap_test_LDADD = gl/libgl.la @LIBINTL@
 tests_libpspp_heap_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
 
+tests_libpspp_abt_test_SOURCES = \
+       src/libpspp/abt.c \
+       src/libpspp/abt.h \
+       tests/libpspp/abt-test.c
+tests_libpspp_abt_test_LDADD = gl/libgl.la
+tests_libpspp_abt_test_CPPFLAGS = $(AM_CPPFLAGS) -DASSERT_LEVEL=10
+
 tests_formats_inexactify_SOURCES = tests/formats/inexactify.c
 
 EXTRA_DIST += $(TESTS) tests/weighting.data tests/data-list.data tests/list.data \
diff --git a/tests/libpspp/ChangeLog b/tests/libpspp/ChangeLog
deleted file mode 100644 (file)
index 2c22cc1..0000000
+++ /dev/null
@@ -1,9 +0,0 @@
-Sun Oct 29 14:03:37 2006  Ben Pfaff  <blp@gnu.org>
-
-       * ll-test.c, llx-test.c: Reduce verbosity of output.
-
-----------------------------------------------------------------------
-Local Variables:
-mode: change-log
-version-control: never
-End:
diff --git a/tests/libpspp/abt-test.c b/tests/libpspp/abt-test.c
new file mode 100644 (file)
index 0000000..6a16592
--- /dev/null
@@ -0,0 +1,723 @@
+/* PSPP - computes sample statistics.
+   Copyright (C) 2007 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 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. */
+
+/* This is a test program for the abt_* routines defined in
+   abt.c.  This test program aims to be as comprehensive as
+   possible.  "gcov -b" should report 100% coverage of lines and
+   branches in the abt_* routines.  "valgrind --leak-check=yes
+   --show-reachable=yes" should give a clean report. */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <libpspp/abt.h>
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <libpspp/compiler.h>
+\f
+/* Currently running test. */
+static const char *test_name;
+
+/* Exit with a failure code.
+   (Place a breakpoint on this function while debugging.) */
+static void
+check_die (void) 
+{
+  exit (EXIT_FAILURE);   
+}
+
+/* If OK is not true, prints a message about failure on the
+   current source file and the given LINE and terminates. */
+static void
+check_func (bool ok, int line) 
+{
+  if (!ok) 
+    {
+      printf ("Check failed in %s test at %s, line %d\n",
+              test_name, __FILE__, line);
+      check_die ();
+    }
+}
+
+/* Verifies that EXPR evaluates to true.
+   If not, prints a message citing the calling line number and
+   terminates. */
+#define check(EXPR) check_func ((EXPR), __LINE__)
+
+/* Prints a message about memory exhaustion and exits with a
+   failure code. */
+static void
+xalloc_die (void)
+{
+  printf ("virtual memory exhausted\n");
+  exit (EXIT_FAILURE);
+}
+
+/* Allocates and returns N bytes of memory. */
+static void *
+xmalloc (size_t n) 
+{
+  if (n != 0) 
+    {
+      void *p = malloc (n);
+      if (p == NULL)
+        xalloc_die ();
+
+      return p;
+    }
+  else
+    return NULL;
+}
+
+static void *
+xmemdup (const void *p, size_t n) 
+{
+  void *q = xmalloc (n);
+  memcpy (q, p, n);
+  return q;
+}
+
+/* Allocates and returns N * M bytes of memory. */
+static void *
+xnmalloc (size_t n, size_t m) 
+{
+  if ((size_t) -1 / m <= n)
+    xalloc_die ();
+  return xmalloc (n * m);
+}
+\f
+/* Node type and support routines. */
+
+/* Test data element. */
+struct element
+  {
+    struct abt_node node;       /* Embedded binary tree element. */
+    int data;                   /* Primary value. */
+    int count;                  /* Number of nodes in subtree,
+                                   including this node. */
+  };
+
+static int aux_data;
+
+/* Returns the `struct element' that NODE is embedded within. */
+static struct element *
+abt_node_to_element (const struct abt_node *node)
+{
+  return abt_data (node, struct element, node);
+}
+
+/* Compares the `x' values in A and B and returns a strcmp-type
+   return value.  Verifies that AUX points to aux_data. */
+static int
+compare_elements (const struct abt_node *a_, const struct abt_node *b_,
+                  const void *aux) 
+{
+  const struct element *a = abt_node_to_element (a_);
+  const struct element *b = abt_node_to_element (b_);
+
+  check (aux == &aux_data);
+  return a->data < b->data ? -1 : a->data > b->data;
+}
+
+/* Recalculates the count for NODE's subtree by adding up the
+   counts for its LEFT and RIGHT child subtrees. */
+static void
+reaugment_elements (struct abt_node *node_,
+                    const struct abt_node *left,
+                    const struct abt_node *right,
+                    const void *aux) 
+{
+  struct element *node = abt_node_to_element (node_);
+
+  check (aux == &aux_data);
+
+  node->count = 1;
+  if (left != NULL)
+    node->count += abt_node_to_element (left)->count;
+  if (right != NULL)
+    node->count += abt_node_to_element (right)->count;
+}
+
+/* Compares A and B and returns a strcmp-type return value. */
+static int
+compare_ints_noaux (const void *a_, const void *b_) 
+{
+  const int *a = a_;
+  const int *b = b_;
+
+  return *a < *b ? -1 : *a > *b;
+}
+
+/* Swaps *A and *B. */
+static void
+swap (int *a, int *b) 
+{
+  int t = *a;
+  *a = *b;
+  *b = t;
+}
+
+/* Reverses the order of the CNT integers starting at VALUES. */
+static void
+reverse (int *values, size_t cnt)
+{
+  size_t i = 0;
+  size_t j = cnt;
+
+  while (j > i)
+    swap (&values[i++], &values[--j]);
+}
+
+/* Arranges the CNT elements in VALUES into the lexicographically
+   next greater permutation.  Returns true if successful.
+   If VALUES is already the lexicographically greatest
+   permutation of its elements (i.e. ordered from greatest to
+   smallest), arranges them into the lexicographically least
+   permutation (i.e. ordered from smallest to largest) and
+   returns false. */
+static bool
+next_permutation (int *values, size_t cnt)
+{
+  if (cnt > 0)
+    {
+      size_t i = cnt - 1;
+      while (i != 0) 
+        {
+          i--;
+          if (values[i] < values[i + 1])
+            {
+              size_t j;
+              for (j = cnt - 1; values[i] >= values[j]; j--)
+                continue;
+              swap (values + i, values + j);
+              reverse (values + (i + 1), cnt - (i + 1));
+              return true;
+            } 
+        }
+      
+      reverse (values, cnt);
+    }
+  
+  return false;
+}
+
+/* Returns N!. */
+static unsigned int
+factorial (unsigned int n) 
+{
+  unsigned int value = 1;
+  while (n > 1)
+    value *= n--;
+  return value;
+}
+
+/* Randomly shuffles the CNT elements in ARRAY, each of which is
+   SIZE bytes in size. */
+static void
+random_shuffle (void *array_, size_t cnt, size_t size)
+{
+  char *array = array_;
+  char *tmp = xmalloc (size);
+  size_t i;
+
+  for (i = 0; i < cnt; i++) 
+    {
+      size_t j = rand () % (cnt - i) + i;
+      if (i != j) 
+        {
+          memcpy (tmp, array + j * size, size);
+          memcpy (array + j * size, array + i * size, size);
+          memcpy (array + i * size, tmp, size);
+        }
+    }
+
+  free (tmp);
+}
+
+/* Finds and returns the element in ABT that is in the given
+   0-based POSITION in in-order. */
+static struct element *
+find_by_position (struct abt *abt, int position) 
+{
+  struct abt_node *p;
+  for (p = abt->root; p != NULL; ) 
+    {
+      int p_pos = p->down[0] ? abt_node_to_element (p->down[0])->count : 0;
+      if (position == p_pos)
+        return abt_node_to_element (p);
+      else if (position < p_pos)
+        p = p->down[0]; 
+      else
+        {
+          p = p->down[1];
+          position -= p_pos + 1;
+        }
+    }
+  return NULL;
+}
+
+/* Checks that all the augmentations are correct in the subtree
+   rooted at P.  Returns the number of nodes in the subtree. */
+static int
+check_augmentations (struct abt_node *p_) 
+{
+  if (p_ == NULL)
+    return 0;
+  else 
+    {
+      struct element *p = abt_node_to_element (p_);
+      int left_count = check_augmentations (p->node.down[0]);
+      int right_count = check_augmentations (p->node.down[1]);
+      int total = left_count + right_count + 1;
+      check (p->count == total);
+      return total;
+    }
+}
+
+/* Check that the levels are correct in the subtree rooted at P. */
+static void
+check_levels (struct abt_node *p) 
+{
+  if (p != NULL) 
+    {
+      int i, j;
+
+      check_levels (p->down[0]);
+      check_levels (p->down[1]);
+
+      check (p->level >= 1);
+      if (p->level > 1) 
+        {
+          struct abt_node *q = p->down[1];
+          check (q != NULL);
+          check (q->level == p->level || q->level == p->level - 1); 
+        }
+
+      for (i = 0; i < 2; i++)
+        if (p->down[i] != NULL)
+          for (j = 0; j < 2; j++)
+            if (p->down[i]->down[j] != NULL)
+              check (p->down[i]->down[j]->level < p->level);
+    }
+}
+
+/* Checks that ABT contains the CNT ints in DATA, that its
+   structure is correct, and that certain operations on ABT
+   produce the expected results. */
+static void
+check_abt (struct abt *abt, const int data[], size_t cnt) 
+{
+  struct element e;
+  size_t i;
+  int *order;
+
+  order = xmemdup (data, cnt * sizeof *data);
+  qsort (order, cnt, sizeof *order, compare_ints_noaux);
+
+  for (i = 0; i < cnt; i++)
+    {
+      struct abt_node *p;
+      
+      e.data = data[i];
+      if (rand () % 2)
+        p = abt_find (abt, &e.node);
+      else
+        p = abt_insert (abt, &e.node);
+      check (p != NULL);
+      check (p != &e.node);
+      check (abt_node_to_element (p)->data == data[i]);
+    }
+
+  e.data = -1;
+  check (abt_find (abt, &e.node) == NULL);
+
+  check_levels (abt->root);
+  check_augmentations (abt->root);
+  for (i = 0; i < cnt; i++)
+    check (find_by_position (abt, i)->data == order[i]);
+
+  if (cnt == 0) 
+    {
+      check (abt_first (abt) == NULL);
+      check (abt_last (abt) == NULL);
+      check (abt_next (abt, NULL) == NULL);
+      check (abt_prev (abt, NULL) == NULL);
+    }
+  else 
+    {
+      struct abt_node *p;
+  
+      for (p = abt_first (abt), i = 0; i < cnt; p = abt_next (abt, p), i++)
+        check (abt_node_to_element (p)->data == order[i]);
+      check (p == NULL);
+
+      for (p = abt_last (abt), i = 0; i < cnt; p = abt_prev (abt, p), i++)
+        check (abt_node_to_element (p)->data == order[cnt - i - 1]);
+      check (p == NULL);
+    }
+
+  free (order);
+}
+
+/* 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) 
+{
+  struct element *elements;
+  struct abt abt;
+  size_t i;
+  
+  elements = xnmalloc (cnt, sizeof *elements);
+  for (i = 0; i < cnt; i++)
+    elements[i].data = i;
+
+  abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
+  check_abt (&abt, NULL, 0);
+  for (i = 0; i < cnt; i++)
+    {
+      check (abt_insert (&abt, &elements[insertions[i]].node) == NULL);
+      check_abt (&abt, insertions, i + 1);
+    }
+  for (i = 0; i < cnt; i++)
+    {
+      abt_delete (&abt, &elements[deletions[i]].node);
+      check_abt (&abt, deletions + i + 1, cnt - i - 1);
+    }
+
+  free (elements);
+}
+\f
+/* Inserts values into an ABT in each possible order, then
+   removes them in each possible order, up to a specified maximum
+   size. */
+static void
+test_insert_any_remove_any (void) 
+{
+  const int max_elems = 5;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      int *insertions, *deletions;
+      unsigned int ins_perm_cnt;
+      int i;
+
+      insertions = xnmalloc (cnt, sizeof *insertions);
+      deletions = xnmalloc (cnt, sizeof *deletions);
+      for (i = 0; i < cnt; i++) 
+        insertions[i] = i;
+
+      for (ins_perm_cnt = 0;
+           ins_perm_cnt == 0 || next_permutation (insertions, cnt);
+           ins_perm_cnt++) 
+        {
+          unsigned int del_perm_cnt;
+          int i;
+
+          for (i = 0; i < cnt; i++) 
+            deletions[i] = i;
+
+          for (del_perm_cnt = 0;
+               del_perm_cnt == 0 || next_permutation (deletions, cnt);
+               del_perm_cnt++) 
+            test_insert_delete (insertions, deletions, cnt);
+
+          check (del_perm_cnt == factorial (cnt));
+        }
+      check (ins_perm_cnt == factorial (cnt));
+
+      free (insertions);
+      free (deletions);
+    }
+}
+
+/* Inserts values into an ABT in each possible order, then
+   removes them in the same order, up to a specified maximum
+   size. */
+static void
+test_insert_any_remove_same (void) 
+{
+  const int max_elems = 7;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      int *values;
+      unsigned int permutation_cnt;
+      int i;
+
+      values = xnmalloc (cnt, sizeof *values);
+      for (i = 0; i < cnt; i++) 
+        values[i] = i;
+
+      for (permutation_cnt = 0;
+           permutation_cnt == 0 || next_permutation (values, cnt);
+           permutation_cnt++)
+        test_insert_delete (values, values, cnt);
+      check (permutation_cnt == factorial (cnt));
+
+      free (values);
+    }
+}
+
+/* Inserts values into an ABT in each possible order, then
+   removes them in reverse order, up to a specified maximum
+   size. */
+static void
+test_insert_any_remove_reverse (void) 
+{
+  const int max_elems = 7;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      int *insertions, *deletions;
+      unsigned int permutation_cnt;
+      int i;
+
+      insertions = xnmalloc (cnt, sizeof *insertions);
+      deletions = xnmalloc (cnt, sizeof *deletions);
+      for (i = 0; i < cnt; i++) 
+        insertions[i] = i;
+
+      for (permutation_cnt = 0;
+           permutation_cnt == 0 || next_permutation (insertions, cnt);
+           permutation_cnt++) 
+        {
+          memcpy (deletions, insertions, sizeof *insertions * cnt);
+          reverse (deletions, cnt);
+          
+          test_insert_delete (insertions, deletions, cnt); 
+        }
+      check (permutation_cnt == factorial (cnt));
+
+      free (insertions);
+      free (deletions);
+    }
+}
+
+/* Inserts and removes values in an ABT in random orders. */
+static void
+test_random_sequence (void) 
+{
+  const int max_elems = 128;
+  const int max_trials = 8;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt += 2) 
+    {
+      int *insertions, *deletions;
+      int trial;
+      int i;
+
+      insertions = xnmalloc (cnt, sizeof *insertions);
+      deletions = xnmalloc (cnt, sizeof *deletions);
+      for (i = 0; i < cnt; i++) 
+        insertions[i] = i;
+      for (i = 0; i < cnt; i++) 
+        deletions[i] = i;
+
+      for (trial = 0; trial < max_trials; trial++) 
+        {
+          random_shuffle (insertions, cnt, sizeof *insertions);
+          random_shuffle (deletions, cnt, sizeof *deletions);
+      
+          test_insert_delete (insertions, deletions, cnt); 
+        }
+
+      free (insertions);
+      free (deletions);
+    }
+}
+
+/* Inserts elements into an ABT in ascending order. */
+static void
+test_insert_ordered (void) 
+{
+  const int max_elems = 1024;
+  struct element *elements;
+  int *values;
+  struct abt abt;
+  int i;
+
+  abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
+  elements = xnmalloc (max_elems, sizeof *elements);
+  values = xnmalloc (max_elems, sizeof *values);
+  for (i = 0; i < max_elems; i++) 
+    {
+      values[i] = elements[i].data = i;
+      check (abt_insert (&abt, &elements[i].node) == NULL);
+      check_abt (&abt, values, i + 1);
+    }
+  free (elements);
+  free (values);
+}
+
+/* Inserts elements into an ABT, then moves the nodes around in
+   memory. */
+static void
+test_moved (void) 
+{
+  const int max_elems = 128;
+  struct element *e[2];
+  int cur;
+  int *values;
+  struct abt abt;
+  int i, j;
+
+  abt_init (&abt, compare_elements, reaugment_elements, &aux_data);
+  e[0] = xnmalloc (max_elems, sizeof *e[0]);
+  e[1] = xnmalloc (max_elems, sizeof *e[1]);
+  values = xnmalloc (max_elems, sizeof *values);
+  cur = 0;
+  for (i = 0; i < max_elems; i++) 
+    {
+      values[i] = e[cur][i].data = i;
+      check (abt_insert (&abt, &e[cur][i].node) == NULL);
+      check_abt (&abt, values, i + 1);
+
+      for (j = 0; j <= i; j++) 
+        {
+          e[!cur][j] = e[cur][j];
+          abt_moved (&abt, &e[!cur][j].node);
+          check_abt (&abt, values, i + 1);
+        }
+      cur = !cur;
+    }
+  free (e[0]);
+  free (e[1]);
+  free (values);
+}
+
+/* Inserts values into an ABT, then changes their values. */
+static void
+test_changed (void)
+{
+  const int max_elems = 6;
+  int cnt;
+
+  for (cnt = 0; cnt <= max_elems; cnt++) 
+    {
+      int *values, *changed_values;
+      struct element *elements;
+      unsigned int permutation_cnt;
+      int i;
+
+      values = xnmalloc (cnt, sizeof *values);
+      changed_values = xnmalloc (cnt, sizeof *changed_values);
+      elements = xnmalloc (cnt, sizeof *elements);
+      for (i = 0; i < cnt; i++) 
+        values[i] = i;
+
+      for (permutation_cnt = 0;
+           permutation_cnt == 0 || next_permutation (values, cnt);
+           permutation_cnt++) 
+        {
+          for (i = 0; i < cnt; i++) 
+            {
+              int j, k;
+              for (j = 0; j <= cnt; j++) 
+                {
+                  struct abt abt;
+                  struct abt_node *changed_retval;
+
+                  abt_init (&abt, compare_elements, reaugment_elements,
+                            &aux_data);
+
+                  /* Add to ABT in order. */
+                  for (k = 0; k < cnt; k++) 
+                    {
+                      int n = values[k];
+                      elements[n].data = n;
+                      check (abt_insert (&abt, &elements[n].node) == NULL); 
+                    }
+                  check_abt (&abt, values, cnt);
+
+                  /* Change value i to j. */
+                  elements[i].data = j;
+                  for (k = 0; k < cnt; k++)
+                    changed_values[k] = k;
+                  changed_retval = abt_changed (&abt, &elements[i].node);
+                  if (i != j && j < cnt)
+                    {
+                      /* Will cause duplicate. */
+                      check (changed_retval == &elements[j].node);
+                      changed_values[i] = changed_values[cnt - 1];
+                      check_abt (&abt, changed_values, cnt - 1);
+                    }
+                  else
+                    {
+                      /* Succeeds. */
+                      check (changed_retval == NULL);
+                      changed_values[i] = j;
+                      check_abt (&abt, changed_values, cnt);
+                    }
+                }
+            } 
+        }
+      check (permutation_cnt == factorial (cnt));
+
+      free (values);
+      free (changed_values);
+      free (elements);
+    }
+}
+\f
+/* Main program. */
+
+/* Runs TEST_FUNCTION and prints a message about NAME. */
+static void
+run_test (void (*test_function) (void), const char *name) 
+{
+  test_name = name;
+  putchar ('.');
+  fflush (stdout);
+  test_function ();
+}
+
+int
+main (void) 
+{
+  run_test (test_insert_any_remove_any,
+            "insert any order, delete any order");
+  run_test (test_insert_any_remove_same,
+            "insert any order, delete same order");
+  run_test (test_insert_any_remove_reverse,
+            "insert any order, delete reverse order");
+  run_test (test_random_sequence,
+            "insert and delete in random sequence");
+  run_test (test_insert_ordered,
+            "insert in ascending order");
+  run_test (test_moved, "move elements around in memory");
+  run_test (test_changed, "change key data in nodes");
+  putchar ('\n');
+
+  return 0;
+}
index 34ece38aebbb91a370d7d940395b9a41c8279d62..642ce7e05a0c3a5c904945ccc161d41e12679142 100644 (file)
@@ -126,10 +126,13 @@ swap (int *a, int *b)
 
 /* Reverses the order of the CNT integers starting at VALUES. */
 static void
-reverse (int *values, size_t cnt) 
+reverse (int *values, size_t cnt)
 {
-  for (; cnt > 1; cnt -= 2, values++)
-    swap (values, &values[cnt - 1]);
+  size_t i = 0;
+  size_t j = cnt;
+
+  while (j > i)
+    swap (&values[i++], &values[--j]);
 }
 
 /* Arranges the CNT elements in VALUES into the lexicographically
@@ -166,10 +169,10 @@ next_permutation (int *values, size_t cnt)
 }
 
 /* Returns N!. */
-static unsigned
-factorial (unsigned n) 
+static unsigned int
+factorial (unsigned int n) 
 {
-  unsigned value = 1;
+  unsigned int value = 1;
   while (n > 1)
     value *= n--;
   return value;
@@ -178,11 +181,11 @@ factorial (unsigned n)
 /* Returns the number of permutations of the CNT values in
    VALUES.  If VALUES contains duplicates, they must be
    adjacent. */
-static unsigned
+static unsigned int
 expected_perms (int *values, size_t cnt) 
 {
   size_t i, j;
-  unsigned perm_cnt;
+  unsigned int perm_cnt;
   
   perm_cnt = factorial (cnt);
   for (i = 0; i < cnt; i = j) 
index 03fc0fd7d8be953061a7b7ed3ad4a6dd860426b8..30e669b3c76b518cb20d131995b7a464c0cc750f 100644 (file)
@@ -212,7 +212,7 @@ static bool
 pattern_pred (const struct ll *element_, void *pattern_) 
 {
   const struct element *element = ll_to_element (element_);
-  unsigned *pattern = pattern_;
+  unsigned int *pattern = pattern_;
 
   return (*pattern & (1u << element->x)) != 0;
 }
@@ -1018,10 +1018,10 @@ test_count_if (void)
 }
 
 /* Returns N!. */
-static unsigned
-factorial (unsigned n) 
+static unsigned int
+factorial (unsigned int n) 
 {
-  unsigned value = 1;
+  unsigned int value = 1;
   while (n > 1)
     value *= n--;
   return value;
@@ -1030,11 +1030,11 @@ factorial (unsigned n)
 /* Returns the number of permutations of the CNT values in
    VALUES.  If VALUES contains duplicates, they must be
    adjacent. */
-static unsigned
+static unsigned int
 expected_perms (int *values, size_t cnt) 
 {
   size_t i, j;
-  unsigned perm_cnt;
+  unsigned int perm_cnt;
   
   perm_cnt = factorial (cnt);
   for (i = 0; i < cnt; i = j) 
@@ -1338,7 +1338,7 @@ test_permutations_with_dups (void)
         int *old_values = xnmalloc (max_elems, sizeof *values);
         int *new_values = xnmalloc (max_elems, sizeof *values);
 
-        unsigned permutation_cnt;
+        unsigned int permutation_cnt;
         int left = cnt;
         int value = 0;
       
@@ -1895,7 +1895,7 @@ test_partition (void)
   const int max_elems = 10;
   
   int cnt;
-  unsigned pbase;
+  unsigned int pbase;
   int r0, r1;
 
   for (cnt = 0; cnt < max_elems; cnt++)
@@ -1908,7 +1908,7 @@ test_partition (void)
             struct ll **elemp;
             int *values;
 
-            unsigned pattern = pbase << r0;
+            unsigned int pattern = pbase << r0;
             int i, j;
             int first_false;
             struct ll *part_ll;
index 1b069a212efef60f8f3177fd279e6d2ae5aa0021..12dc0f52214d8a9a287a76210ff726552f333c5c 100644 (file)
@@ -225,7 +225,7 @@ static bool
 pattern_pred (const void *element_, void *pattern_) 
 {
   const struct element *element = element_;
-  unsigned *pattern = pattern_;
+  unsigned int *pattern = pattern_;
 
   return (*pattern & (1u << element->x)) != 0;
 }
@@ -1007,10 +1007,10 @@ test_count_if (void)
 }
 
 /* Returns N!. */
-static unsigned
-factorial (unsigned n) 
+static unsigned int
+factorial (unsigned int n) 
 {
-  unsigned value = 1;
+  unsigned int value = 1;
   while (n > 1)
     value *= n--;
   return value;
@@ -1019,11 +1019,11 @@ factorial (unsigned n)
 /* Returns the number of permutations of the CNT values in
    VALUES.  If VALUES contains duplicates, they must be
    adjacent. */
-static unsigned
+static unsigned int
 expected_perms (int *values, size_t cnt) 
 {
   size_t i, j;
-  unsigned perm_cnt;
+  unsigned int perm_cnt;
   
   perm_cnt = factorial (cnt);
   for (i = 0; i < cnt; i = j) 
@@ -1362,7 +1362,7 @@ test_permutations_with_dups (void)
         int *old_values = xnmalloc (max_elems, sizeof *values);
         int *new_values = xnmalloc (max_elems, sizeof *values);
 
-        unsigned permutation_cnt;
+        unsigned int permutation_cnt;
         int left = cnt;
         int value = 0;
       
@@ -1929,7 +1929,7 @@ test_partition (void)
   const int max_elems = 10;
   
   int cnt;
-  unsigned pbase;
+  unsigned int pbase;
   int r0, r1;
 
   for (cnt = 0; cnt < max_elems; cnt++)
@@ -1942,7 +1942,7 @@ test_partition (void)
             struct llx **elemp;
             int *values;
 
-            unsigned pattern = pbase << r0;
+            unsigned int pattern = pbase << r0;
             int i, j;
             int first_false;
             struct llx *part_llx;