Re: [HACKERS] Red-Black tree traversal tests

Victor Drobny <v.drobny@postgrespro.ru> writes:
> On 2017-09-08 15:23, Thomas Munro wrote:
>> It's trying to call rb->combiner which is null.

> Thank you for pointing on it. Here is a fixed version.

Actually, I think we *do* want the tests to call the combiner
occasionally ...

I whacked this around quite a bit and had gotten it to a state
that I thought was committable, when it occurred to me to wonder
why exactly we're going to this much effort to test the preorder
and postorder traversal logic.  I'm inclined to think we should
rip that out, instead, because I can think of no reason that
anyone would ever want to use it in Postgres.

I'll make that argument in a separate thread, so it gets a little
more visibility in the pgsql-hackers firehose.

In the meantime, here's my version.  Notable changes:

* Got rid of separate .h file; seemed pointless, especially
  since the combiner function needs to know what the test
  expectations are.
* Corrected the random-permutation algorithm.
* Made the preorder/postorder check logic more paranoid
  (though I now feel that was a waste of effort).
* Improved English grammar in a lot of comments.
* Added some more test cases; code coverage report shows
  that this exercises every non-error-case line in rbtree.c.
* Added an rbtree "rb_root()" function to avoid the unsafe
  casting the previous version did to get the root pointer.
* Removed the assumption that the nil element is unique;
  now it just knows that a leaf element points to itself.

We could dispense with rb_root(), as well as the test code's knowledge
about RBNIL representation, if we dropped the preorder/postorder cases
... which is another good reason to do so.

            regards, tom lane

diff --git a/src/backend/lib/rbtree.c b/src/backend/lib/rbtree.c
index 3d80090..0ae5bc8 100644
*** a/src/backend/lib/rbtree.c
--- b/src/backend/lib/rbtree.c
*************** rb_leftmost(RBTree *rb)
*** 195,200 ****
--- 195,215 ----
      return NULL;
  }

+ /*
+  * rb_root: fetch the root node.
+  * Returns RBNIL if tree is empty.
+  *
+  * This function has no great use in normal operation, since there's no
+  * particular semantic meaning to the current root node.  It's useful
+  * for testing purposes, though.
+  */
+ RBNode *
+ rb_root(RBTree *rb)
+ {
+     return rb->root;
+ }
+
+
  /**********************************************************************
   *                              Insertion                                  *
   **********************************************************************/
diff --git a/src/include/lib/rbtree.h b/src/include/lib/rbtree.h
index a7183bb..1d352a3 100644
*** a/src/include/lib/rbtree.h
--- b/src/include/lib/rbtree.h
*************** extern RBTree *rb_create(Size node_size,
*** 71,76 ****
--- 71,77 ----

  extern RBNode *rb_find(RBTree *rb, const RBNode *data);
  extern RBNode *rb_leftmost(RBTree *rb);
+ extern RBNode *rb_root(RBTree *rb);

  extern RBNode *rb_insert(RBTree *rb, const RBNode *data, bool *isNew);
  extern void rb_delete(RBTree *rb, RBNode *node);
diff --git a/src/test/modules/Makefile b/src/test/modules/Makefile
index 3ce9904..b7ed0af 100644
*** a/src/test/modules/Makefile
--- b/src/test/modules/Makefile
*************** SUBDIRS = \
*** 13,18 ****
--- 13,19 ----
            test_extensions \
            test_parser \
            test_pg_dump \
+           test_rbtree \
            test_rls_hooks \
            test_shm_mq \
            worker_spi
diff --git a/src/test/modules/test_rbtree/.gitignore b/src/test/modules/test_rbtree/.gitignore
index ...5dcb3ff .
*** a/src/test/modules/test_rbtree/.gitignore
--- b/src/test/modules/test_rbtree/.gitignore
***************
*** 0 ****
--- 1,4 ----
+ # Generated subdirectories
+ /log/
+ /results/
+ /tmp_check/
diff --git a/src/test/modules/test_rbtree/Makefile b/src/test/modules/test_rbtree/Makefile
index ...a4184b4 .
*** a/src/test/modules/test_rbtree/Makefile
--- b/src/test/modules/test_rbtree/Makefile
***************
*** 0 ****
--- 1,21 ----
+ # src/test/modules/test_rbtree/Makefile
+
+ MODULE_big = test_rbtree
+ OBJS = test_rbtree.o $(WIN32RES)
+ PGFILEDESC = "test_rbtree - test code for red-black tree library"
+
+ EXTENSION = test_rbtree
+ DATA = test_rbtree--1.0.sql
+
+ REGRESS = test_rbtree
+
+ ifdef USE_PGXS
+ PG_CONFIG = pg_config
+ PGXS := $(shell $(PG_CONFIG) --pgxs)
+ include $(PGXS)
+ else
+ subdir = src/test/modules/test_rbtree
+ top_builddir = ../../../..
+ include $(top_builddir)/src/Makefile.global
+ include $(top_srcdir)/contrib/contrib-global.mk
+ endif
diff --git a/src/test/modules/test_rbtree/README b/src/test/modules/test_rbtree/README
index ...fe63ce8 .
*** a/src/test/modules/test_rbtree/README
--- b/src/test/modules/test_rbtree/README
***************
*** 0 ****
--- 1,28 ----
+ test_rbtree is a test module for checking the correctness of red-black
+ tree operations.
+
+ These tests are performed on red-black trees that store integers.
+ Since the rbtree logic treats the comparison function as a black
+ box, it shouldn't be important exactly what the key type is.
+
+ rbtree in postgres has 4 kinds of traversals: Left-Current-Right,
+ Right-Current-Left, Current-Left-Right and Left-Right-Current.
+
+ Checking the correctness of the first two types is based on the fact that
+ red-black tree is a binary search tree, so the elements should be visited in
+ increasing (for Left-Current-Right) or decreasing (for Right-Current-Left)
+ order.
+
+ In order to verify the last two strategies, we perform the traversal and
+ then retrospectively see if the resulting sequence meets the constraints
+ for a preorder or postorder binary tree, that is that we can recursively
+ divide it into a root, a left subtree containing only values less than
+ the root, and a right subtree containing only values greater than the root.
+ We also do a manual tree descent and verify that it matches the results
+ of the iterator.  (This manual descent requires knowing a bit more than
+ we should about RBNodes: we have to touch the left and right sublinks,
+ which rbtree.h says we should not, and we have to know how to identify
+ empty leaf nodes.)
+
+ Also, this module does some checks of the correctness of the find, delete
+ and leftmost operations.
diff --git a/src/test/modules/test_rbtree/expected/test_rbtree.out
b/src/test/modules/test_rbtree/expected/test_rbtree.out
index ...3e32956 .
*** a/src/test/modules/test_rbtree/expected/test_rbtree.out
--- b/src/test/modules/test_rbtree/expected/test_rbtree.out
***************
*** 0 ****
--- 1,12 ----
+ CREATE EXTENSION test_rbtree;
+ --
+ -- These tests don't produce any interesting output.  We're checking that
+ -- the operations complete without crashing or hanging and that none of their
+ -- internal sanity tests fail.
+ --
+ SELECT test_rb_tree(10000);
+  test_rb_tree
+ --------------
+
+ (1 row)
+
diff --git a/src/test/modules/test_rbtree/sql/test_rbtree.sql b/src/test/modules/test_rbtree/sql/test_rbtree.sql
index ...d8dc88e .
*** a/src/test/modules/test_rbtree/sql/test_rbtree.sql
--- b/src/test/modules/test_rbtree/sql/test_rbtree.sql
***************
*** 0 ****
--- 1,8 ----
+ CREATE EXTENSION test_rbtree;
+
+ --
+ -- These tests don't produce any interesting output.  We're checking that
+ -- the operations complete without crashing or hanging and that none of their
+ -- internal sanity tests fail.
+ --
+ SELECT test_rb_tree(10000);
diff --git a/src/test/modules/test_rbtree/test_rbtree--1.0.sql b/src/test/modules/test_rbtree/test_rbtree--1.0.sql
index ...04f2a3a .
*** a/src/test/modules/test_rbtree/test_rbtree--1.0.sql
--- b/src/test/modules/test_rbtree/test_rbtree--1.0.sql
***************
*** 0 ****
--- 1,8 ----
+ /* src/test/modules/test_rbtree/test_rbtree--1.0.sql */
+
+ -- complain if script is sourced in psql, rather than via CREATE EXTENSION
+ \echo Use "CREATE EXTENSION test_rbtree" to load this file. \quit
+
+ CREATE FUNCTION test_rb_tree(size INTEGER)
+     RETURNS pg_catalog.void STRICT
+     AS 'MODULE_PATHNAME' LANGUAGE C;
diff --git a/src/test/modules/test_rbtree/test_rbtree.c b/src/test/modules/test_rbtree/test_rbtree.c
index ...254c4f4 .
*** a/src/test/modules/test_rbtree/test_rbtree.c
--- b/src/test/modules/test_rbtree/test_rbtree.c
***************
*** 0 ****
--- 1,722 ----
+ /*--------------------------------------------------------------------------
+  *
+  * test_rbtree.c
+  *        Test correctness of red-black tree operations.
+  *
+  * Copyright (c) 2009-2017, PostgreSQL Global Development Group
+  *
+  * IDENTIFICATION
+  *        src/test/modules/test_rbtree/test_rbtree.c
+  *
+  * -------------------------------------------------------------------------
+  */
+
+ #include "postgres.h"
+
+ #include "fmgr.h"
+ #include "lib/rbtree.h"
+ #include "utils/memutils.h"
+
+ PG_MODULE_MAGIC;
+
+
+ /*
+  * Our test trees store an integer key, and nothing else.
+  */
+ typedef struct IntRBTreeNode
+ {
+     RBNode        rbnode;
+     int            key;
+ } IntRBTreeNode;
+
+
+ /*
+  * Node comparator.  We don't worry about overflow in the subtraction,
+  * since none of our test keys are negative.
+  */
+ static int
+ irb_cmp(const RBNode *a, const RBNode *b, void *arg)
+ {
+     const IntRBTreeNode *ea = (const IntRBTreeNode *) a;
+     const IntRBTreeNode *eb = (const IntRBTreeNode *) b;
+
+     return ea->key - eb->key;
+ }
+
+ /*
+  * Node combiner.  For testing purposes, just check that library doesn't
+  * try to combine unequal keys.
+  */
+ static void
+ irb_combine(RBNode *existing, const RBNode *newdata, void *arg)
+ {
+     const IntRBTreeNode *eexist = (const IntRBTreeNode *) existing;
+     const IntRBTreeNode *enew = (const IntRBTreeNode *) newdata;
+
+     if (eexist->key != enew->key)
+         elog(ERROR, "red-black tree combines %d into %d",
+              enew->key, eexist->key);
+ }
+
+ /* Node allocator */
+ static RBNode *
+ irb_alloc(void *arg)
+ {
+     return (RBNode *) palloc(sizeof(IntRBTreeNode));
+ }
+
+ /* Node freer */
+ static void
+ irb_free(RBNode *node, void *arg)
+ {
+     pfree(node);
+ }
+
+ /*
+  * Create a red-black tree using our support functions
+  */
+ static RBTree *
+ create_int_rbtree(void)
+ {
+     return rb_create(sizeof(IntRBTreeNode),
+                      irb_cmp,
+                      irb_combine,
+                      irb_alloc,
+                      irb_free,
+                      NULL);
+ }
+
+ /*
+  * Generate a random permutation of the integers 0..size-1
+  */
+ static int *
+ GetPermutation(int size)
+ {
+     int           *permutation;
+     int            i;
+
+     permutation = (int *) palloc(size * sizeof(int));
+
+     permutation[0] = 0;
+
+     /*
+      * This is the "inside-out" variant of the Fisher-Yates shuffle algorithm.
+      * Notionally, we append each new value to the array and then swap it with
+      * a randomly-chosen array element (possibly including itself, else we
+      * fail to generate permutations with the last integer last).  The swap
+      * step can be optimized by combining it with the insertion.
+      */
+     for (i = 1; i < size; i++)
+     {
+         int            j = random() % (i + 1);
+
+         if (j < i)                /* avoid fetching undefined data if j=i */
+             permutation[i] = permutation[j];
+         permutation[j] = i;
+     }
+
+     return permutation;
+ }
+
+ /*
+  * Populate an empty RBTree with "size" integers having the values
+  * 0, step, 2*step, 3*step, ..., inserting them in random order
+  */
+ static void
+ rb_populate(RBTree *tree, int size, int step)
+ {
+     int           *permutation = GetPermutation(size);
+     IntRBTreeNode node;
+     bool        isNew;
+     int            i;
+
+     /* Insert values.  We don't expect any collisions. */
+     for (i = 0; i < size; i++)
+     {
+         node.key = step * permutation[i];
+         rb_insert(tree, (RBNode *) &node, &isNew);
+         if (!isNew)
+             elog(ERROR, "unexpected !isNew result from rb_insert");
+     }
+
+     /*
+      * Re-insert the first value to make sure collisions work right.  It's
+      * probably not useful to test that case over again for all the values.
+      */
+     if (size > 0)
+     {
+         node.key = step * permutation[0];
+         rb_insert(tree, (RBNode *) &node, &isNew);
+         if (isNew)
+             elog(ERROR, "unexpected isNew result from rb_insert");
+     }
+
+     pfree(permutation);
+ }
+
+ /*
+  * Check the correctness of left-right traversal.
+  * Left-right traversal is correct if all elements are
+  * visited in increasing order.
+  */
+ static void
+ testleftright(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     IntRBTreeNode *node;
+     RBTreeIterator iter;
+     int            lastKey = -1;
+     int            count = 0;
+
+     /* check iteration over empty tree */
+     rb_begin_iterate(tree, LeftRightWalk, &iter);
+     if (rb_iterate(&iter) != NULL)
+         elog(ERROR, "left-right walk over empty tree produced an element");
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* iterate over the tree */
+     rb_begin_iterate(tree, LeftRightWalk, &iter);
+
+     while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL)
+     {
+         /* check that order is increasing */
+         if (node->key <= lastKey)
+             elog(ERROR, "left-right walk gives elements not in sorted order");
+         lastKey = node->key;
+         count++;
+     }
+
+     if (lastKey != size - 1)
+         elog(ERROR, "left-right walk did not reach end");
+     if (count != size)
+         elog(ERROR, "left-right walk missed some elements");
+ }
+
+ /*
+  * Check the correctness of right-left traversal.
+  * Right-left traversal is correct if all elements are
+  * visited in decreasing order.
+  */
+ static void
+ testrightleft(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     IntRBTreeNode *node;
+     RBTreeIterator iter;
+     int            lastKey = size;
+     int            count = 0;
+
+     /* check iteration over empty tree */
+     rb_begin_iterate(tree, RightLeftWalk, &iter);
+     if (rb_iterate(&iter) != NULL)
+         elog(ERROR, "right-left walk over empty tree produced an element");
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* iterate over the tree */
+     rb_begin_iterate(tree, RightLeftWalk, &iter);
+
+     while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL)
+     {
+         /* check that order is decreasing */
+         if (node->key >= lastKey)
+             elog(ERROR, "right-left walk gives elements not in sorted order");
+         lastKey = node->key;
+         count++;
+     }
+
+     if (lastKey != 0)
+         elog(ERROR, "right-left walk did not reach end");
+     if (count != size)
+         elog(ERROR, "right-left walk missed some elements");
+ }
+
+ /*
+  * Detect whether an RBNode is a leaf node.
+  * (This is white-box testing ... we know that rbtree.c uses a sentinel node
+  * that points to itself.)
+  */
+ #define IsRBLeaf(node)  (((RBNode *) (node))->left == (RBNode *) (node))
+
+ /*
+  * Check the correctness of given preorder traversal.
+  *
+  * For the preorder traversal the root key is always in the first position.
+  * It's correct if the array consists of the root value, then a left subtree
+  * containing only values less than the root, then a right subtree
+  * containing only values greater than the root, and this condition holds
+  * recursively for each of the two subtrees.
+  */
+ static bool
+ ValidatePreorderInt(int *array, int len)
+ {
+     int            rootval;
+     int           *left,
+                *right,
+                *tmp;
+
+     /* vacuously true for empty or root-only tree */
+     if (len <= 1)
+         return true;
+
+     rootval = *array;
+     left = array + 1;
+
+     /* search for the right subtree */
+     right = left;
+     while (right < array + len && *right < rootval)
+         right++;
+
+     /* check that right subtree has only elements that are bigger than root */
+     tmp = right;
+     while (tmp < array + len)
+     {
+         if (*tmp <= rootval)
+             return false;
+         tmp++;
+     }
+
+     /* check left subtree and right subtree recursively */
+     return ValidatePreorderInt(left, right - left) &&
+         ValidatePreorderInt(right, array + len - right);
+ }
+
+ /* Check preorder traversal by manually traversing the tree */
+ static bool
+ ValidatePreorderIntTree(IntRBTreeNode *node, int *array, int len)
+ {
+     int            rightValue;
+     int            leftValue;
+     int           *right = NULL;
+     int            i;
+
+     /* At leaf, we're good if subarray is empty */
+     if (IsRBLeaf(node))
+         return (len == 0);
+     /* Else, node should match array's root position */
+     if (len < 1 || node->key != *array)
+         return false;
+
+     /* If node has left child -> check it */
+     if (!IsRBLeaf(node->rbnode.left))
+     {
+         leftValue = ((IntRBTreeNode *) node->rbnode.left)->key;
+         if (len < 2)
+             return false;
+         if (leftValue != array[1])
+             return false;
+         if (!IsRBLeaf(node->rbnode.right))
+         {
+             /* search for right part */
+             rightValue = ((IntRBTreeNode *) node->rbnode.right)->key;
+             if (len < 3)
+                 return false;
+             i = 2;
+             while (array[i] != rightValue)
+             {
+                 i++;
+                 if (i >= len)
+                     return false;
+             }
+             right = array + i;
+         }
+         else
+         {
+             right = array + len;
+         }
+         if (!ValidatePreorderIntTree((IntRBTreeNode *) node->rbnode.left,
+                                      array + 1, right - array - 1))
+             return false;
+     }
+
+     /* If node has right child -> check it */
+     if (!IsRBLeaf(node->rbnode.right))
+     {
+         rightValue = ((IntRBTreeNode *) node->rbnode.right)->key;
+
+         /*
+          * if left child is not null then we already found right subarray,
+          * else right subarray must be all but the root
+          */
+         if (right == NULL)
+         {
+             if (len < 2)
+                 return false;
+             right = array + 1;
+         }
+         if (rightValue != *right)
+             return false;
+         return ValidatePreorderIntTree((IntRBTreeNode *) node->rbnode.right,
+                                        right, array + len - right);
+     }
+
+     return true;
+ }
+
+ /*
+  * Check the correctness of preorder (direct) traversal.
+  * Firstly, the correctness of the sequence by itself is checked.
+  * Secondly, correspondence to the tree is checked.
+  */
+ static void
+ testdirect(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     IntRBTreeNode *node;
+     RBTreeIterator iter;
+     int           *elements;
+     int            i;
+
+     /* check iteration over empty tree */
+     rb_begin_iterate(tree, DirectWalk, &iter);
+     if (rb_iterate(&iter) != NULL)
+         elog(ERROR, "preorder walk over empty tree produced an element");
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* iterate and collect elements in direct order */
+     elements = (int *) palloc(sizeof(int) * size);
+     rb_begin_iterate(tree, DirectWalk, &iter);
+     i = 0;
+     while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL)
+     {
+         elements[i++] = node->key;
+     }
+     if (i != size)
+         elog(ERROR, "preorder walk found wrong number of elements");
+
+     if (!ValidatePreorderInt(elements, size))
+         elog(ERROR, "preorder walk gives elements not in the correct order");
+
+     if (!ValidatePreorderIntTree((IntRBTreeNode *) rb_root(tree),
+                                  elements, size))
+         elog(ERROR, "preorder walk tree check failed");
+
+     pfree(elements);
+ }
+
+ /*
+  * Check the correctness of given postorder traversal.
+  *
+  * For the postorder traversal the root key is always the last.
+  * It's correct if the array consists of a left subtree containing only values
+  * less than the root, then a right subtree containing only values greater
+  * than the root, then the root value, and this condition holds recursively
+  * for each of the two subtrees.
+  */
+ static bool
+ ValidatePostorderInt(int *array, int len)
+ {
+     int            rootval;
+     int           *left,
+                *right,
+                *tmp;
+
+     /* vacuously true for empty or root-only tree */
+     if (len <= 1)
+         return true;
+
+     rootval = array[len - 1];
+     left = array;
+
+     /* search for the right subtree */
+     right = left;
+     while (right < array + len - 1 && *right < rootval)
+         right++;
+
+     /* check that right subtree has only elements that are bigger than root */
+     tmp = right;
+     while (tmp < array + len - 1)
+     {
+         if (*tmp <= rootval)
+             return false;
+         tmp++;
+     }
+
+     /* check left subtree and right subtree recursively */
+     return ValidatePostorderInt(left, right - left) &&
+         ValidatePostorderInt(right, array + len - right - 1);
+ }
+
+ /* Check postorder traversal by manually traversing the tree */
+ static bool
+ ValidatePostorderIntTree(IntRBTreeNode *node, int *array, int len)
+ {
+     int           *right = array;
+     int            leftValue;
+     int            i;
+
+     /* At leaf, we're good if subarray is empty */
+     if (IsRBLeaf(node))
+         return (len == 0);
+     /* Else, node should match array's root position */
+     if (len < 1 || node->key != array[len - 1])
+         return false;
+
+     /* If node has left child -> check it */
+     if (!IsRBLeaf(node->rbnode.left))
+     {
+         leftValue = ((IntRBTreeNode *) node->rbnode.left)->key;
+         if (len < 2)
+             return false;
+         if (!IsRBLeaf(node->rbnode.right))
+         {
+             /* search for right part, which begins just after left subroot */
+             i = 0;
+             while (array[i] != leftValue)
+             {
+                 i++;
+                 if (i >= len - 1)
+                     return false;
+             }
+             right = array + i + 1;
+         }
+         else
+         {
+             right = array + len - 1;
+         }
+         if (!ValidatePostorderIntTree((IntRBTreeNode *) node->rbnode.left,
+                                       array, right - array))
+             return false;
+     }
+
+     /* If node has right child -> check it */
+     if (!IsRBLeaf(node->rbnode.right))
+     {
+         /*
+          * if left child is not null then we already found right subarray,
+          * else right subarray must be all but the root
+          */
+         return ValidatePostorderIntTree((IntRBTreeNode *) node->rbnode.right,
+                                         right, array + len - right - 1);
+     }
+
+     return true;
+ }
+
+ /*
+  * Check the correctness of postorder (inverted) traversal.
+  * Firstly, the correctness of the sequence by itself is checked.
+  * Secondly, correspondence to the tree is checked.
+  */
+ static void
+ testinverted(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     IntRBTreeNode *node;
+     RBTreeIterator iter;
+     int           *elements;
+     int            i;
+
+     /* check iteration over empty tree */
+     rb_begin_iterate(tree, InvertedWalk, &iter);
+     if (rb_iterate(&iter) != NULL)
+         elog(ERROR, "postorder walk over empty tree produced an element");
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* iterate and collect elements in inverted order */
+     elements = (int *) palloc(sizeof(int) * size);
+     rb_begin_iterate(tree, InvertedWalk, &iter);
+     i = 0;
+     while ((node = (IntRBTreeNode *) rb_iterate(&iter)) != NULL)
+     {
+         elements[i++] = node->key;
+     }
+     if (i != size)
+         elog(ERROR, "postorder walk found wrong number of elements");
+
+     if (!ValidatePostorderInt(elements, size))
+         elog(ERROR, "postorder walk gives elements not in the correct order");
+
+     if (!ValidatePostorderIntTree((IntRBTreeNode *) rb_root(tree),
+                                   elements, size))
+         elog(ERROR, "postorder walk tree check failed");
+
+     pfree(elements);
+ }
+
+ /*
+  * Check the correctness of the rb_find operation by searching for
+  * both elements we inserted and elements we didn't.
+  */
+ static void
+ testfind(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     int            i;
+
+     /* Insert even integers from 0 to 2 * (size-1) */
+     rb_populate(tree, size, 2);
+
+     /* Check that all inserted elements can be found */
+     for (i = 0; i < size; i++)
+     {
+         IntRBTreeNode node;
+         IntRBTreeNode *resultNode;
+
+         node.key = 2 * i;
+         resultNode = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node);
+         if (resultNode == NULL)
+             elog(ERROR, "inserted element was not found");
+         if (node.key != resultNode->key)
+             elog(ERROR, "find operation in rbtree gave wrong result");
+     }
+
+     /*
+      * Check that not-inserted elements can not be found, being sure to try
+      * values before the first and after the last element.
+      */
+     for (i = -1; i <= 2 * size; i += 2)
+     {
+         IntRBTreeNode node;
+         IntRBTreeNode *resultNode;
+
+         node.key = i;
+         resultNode = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node);
+         if (resultNode != NULL)
+             elog(ERROR, "not-inserted element was found");
+     }
+ }
+
+ /*
+  * Check the correctness of the rb_leftmost operation.
+  * This operation should always return the smallest element of the tree.
+  */
+ static void
+ testleftmost(int size)
+ {
+     RBTree       *tree = create_int_rbtree();
+     IntRBTreeNode *result;
+
+     /* Check that empty tree has no leftmost element */
+     if (rb_leftmost(tree) != NULL)
+         elog(ERROR, "leftmost node of empty tree is not NULL");
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* Check that leftmost element is the smallest one */
+     result = (IntRBTreeNode *) rb_leftmost(tree);
+     if (result == NULL || result->key != 0)
+         elog(ERROR, "rb_leftmost gave wrong result");
+ }
+
+ /*
+  * Check the correctness of the rb_delete operation.
+  */
+ static void
+ testdelete(int size, int delsize)
+ {
+     RBTree       *tree = create_int_rbtree();
+     int           *deleteIds;
+     bool       *chosen;
+     int            i;
+
+     /* fill tree with consecutive natural numbers */
+     rb_populate(tree, size, 1);
+
+     /* Choose unique ids to delete */
+     deleteIds = (int *) palloc(delsize * sizeof(int));
+     chosen = (bool *) palloc0(size * sizeof(bool));
+
+     for (i = 0; i < delsize; i++)
+     {
+         int            k = random() % size;
+
+         while (chosen[k])
+             k = (k + 1) % size;
+         deleteIds[i] = k;
+         chosen[k] = true;
+     }
+
+     /* Delete elements */
+     for (i = 0; i < delsize; i++)
+     {
+         IntRBTreeNode find;
+         IntRBTreeNode *node;
+
+         find.key = deleteIds[i];
+         /* Locate the node to be deleted */
+         node = (IntRBTreeNode *) rb_find(tree, (RBNode *) &find);
+         if (node == NULL || node->key != deleteIds[i])
+             elog(ERROR, "expected element was not found during deleting");
+         /* Delete it */
+         rb_delete(tree, (RBNode *) node);
+     }
+
+     /* Check that deleted elements are deleted */
+     for (i = 0; i < size; i++)
+     {
+         IntRBTreeNode node;
+         IntRBTreeNode *result;
+
+         node.key = i;
+         result = (IntRBTreeNode *) rb_find(tree, (RBNode *) &node);
+         if (chosen[i])
+         {
+             /* Deleted element should be absent */
+             if (result != NULL)
+                 elog(ERROR, "deleted element still present in the rbtree");
+         }
+         else
+         {
+             /* Else it should be present */
+             if (result == NULL || result->key != i)
+                 elog(ERROR, "delete operation removed wrong rbtree value");
+         }
+     }
+
+     /* Delete remaining elements, so as to exercise reducing tree to empty */
+     for (i = 0; i < size; i++)
+     {
+         IntRBTreeNode find;
+         IntRBTreeNode *node;
+
+         if (chosen[i])
+             continue;
+         find.key = i;
+         /* Locate the node to be deleted */
+         node = (IntRBTreeNode *) rb_find(tree, (RBNode *) &find);
+         if (node == NULL || node->key != i)
+             elog(ERROR, "expected element was not found during deleting");
+         /* Delete it */
+         rb_delete(tree, (RBNode *) node);
+     }
+
+     /* Tree should now be empty */
+     if (rb_leftmost(tree) != NULL)
+         elog(ERROR, "deleting all elements failed");
+
+     pfree(deleteIds);
+     pfree(chosen);
+ }
+
+ /*
+  * SQL-callable entry point to perform all tests
+  *
+  * Argument is the number of entries to put in the trees
+  */
+ PG_FUNCTION_INFO_V1(test_rb_tree);
+
+ Datum
+ test_rb_tree(PG_FUNCTION_ARGS)
+ {
+     int            size = PG_GETARG_INT32(0);
+
+     if (size <= 0 || size > MaxAllocSize / sizeof(int))
+         elog(ERROR, "invalid size for test_rb_tree: %d", size);
+     testleftright(size);
+     testrightleft(size);
+     testdirect(size);
+     testinverted(size);
+     testfind(size);
+     testleftmost(size);
+     testdelete(size, size / 10);
+     PG_RETURN_VOID();
+ }
diff --git a/src/test/modules/test_rbtree/test_rbtree.control b/src/test/modules/test_rbtree/test_rbtree.control
index ...17966a5 .
*** a/src/test/modules/test_rbtree/test_rbtree.control
--- b/src/test/modules/test_rbtree/test_rbtree.control
***************
*** 0 ****
--- 1,4 ----
+ comment = 'Test code for red-black tree library'
+ default_version = '1.0'
+ module_pathname = '$libdir/test_rbtree'
+ relocatable = true

-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers