Dear Tom,
Thank you very much for your review. In the attachment you can find v2
of the patch.
On 2017-09-07 01:38, Tom Lane wrote:
[ btw, please don't cc pgsql-hackers-owner, the list moderators don't
need the noise ]
Aleksander Alekseev <a.aleks...@postgrespro.ru> writes:
I would say that this patch is in a pretty good shape now. And I see a
99% code coverage of rbtree.c. Let's see what committers think.
I took a quick look through the patch --- haven't tried to compile it
or anything like that --- and have a few comments:
* There's some typos, eg extention should be extension, triversal
should be traversal. Maybe try a spell checker?
Done. I fixed all spelling mistakes that i found.
* The diff complains about lack of file-ending newlines in several
places
* There's something weird at the start of test.c:
@@ -0,0 +1,577 @@
+/*--------------------------------------------------------------------------
Maybe your compiler thinks that's a BOM? It's hard to see how it
compiles otherwise.
Now it is in UTF-8 without BOM. It seems that there is no such data in
the beginning
of the test.c
* I think it might be simpler to have the module expose just one SQL
function that invokes all these individual tests internally. Less
boilerplate text that way, and less to change if you add more tests
later. Also, you might consider passing in TEST_SIZE as an argument
of the SQL function instead of having it be hard-wired.
You are right. Done.
* We don't do C++-style (//) comments around here. Please use C
style. (You might consider running the code through pgindent,
which will convert those comments automatically.)
Fixed.
* It's also generally not per project style to use malloc/calloc/free
directly in backend code; and it's certainly not cool to use malloc or
calloc and then not check for a null result. Use palloc instead.
Given
the short runtime of this test, you likely needn't be too worried about
pfree'ing stuff.
* _PG_init() declaration seems to be a leftover? <stdio.h> doesn't
belong here either, as postgres.h will bring that in for you.
* I know next to zip about red-black trees, but it disturbs me that
the traversal tests use trees whose values were inserted in strictly
increasing order. Seems like that's not proving as much as it could.
I wonder how hard it would be to insert those integers in random order.
* I'm not too pleased that the rb_find calls mostly just assume that
the find won't return NULL. You should be testing for that and
reporting
the problem, not just dying on a null pointer crash if it happens.
Done.
* Possibly the tests should exercise rb_delete on keys *not* present.
And how about insertion of already-existing keys? Although that's
a bit outside the scope of testing traversal, so if you want to leave
it for some future expansion, that'd be OK.
Deletion requires to get pointer to the tree node. Otherwise it could
break
the tree. It is mentioned in the description of the rb_delete function.
" * "node" must have previously been found via rb_find or rb_leftmost."
Insertion of the same elements is managed by the specific implementation
of the tree. One of the input arguments of the rb_create function is
combiner function that will be called in case of repeated insertion.
However, during looking through this i found that nobody checks that
combiner function(as well as comparator, freefunc and allocfunc) is
not NULL. So if it was not specified, postgres will fall. I think that
it is better to add this checks.
I'll set this back to Waiting on Author. I do encourage you to finish
it up.
regards, tom lane
--
Victor Drobny
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
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
@@ -13,6 +13,7 @@ SUBDIRS = \
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/Makefile b/src/test/modules/test_rbtree/Makefile
new file mode 100644
index 0000000..4e53e86
--- /dev/null
+++ b/src/test/modules/test_rbtree/Makefile
@@ -0,0 +1,21 @@
+# src/test/modules/test_rbtree/Makefile
+
+MODULE_big = test_rbtree
+OBJS = test.o $(WIN32RES)
+PGFILEDESC = "test_rbtree - rbtree traversal testing"
+
+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
new file mode 100644
index 0000000..40f586d
--- /dev/null
+++ b/src/test/modules/test_rbtree/README
@@ -0,0 +1,20 @@
+test_rbtree is a module tests for checking the correctness of all kinds of
+traversal of red-black tree. Right now rbtree in postgres has 4 kinds of
+traversals: Left-Current-Right, Right-Current-Left, Current-Left-Right and
+Left-Right-Current.
+
+This extension has 4 functions. Each function checks one traversal.
+The checking the correctness of first two types are based on the fact that
+red-black tree is a binary search tree, so the elements should be iterated in
+increasing(for Left-Current-Right) or decreasing(for Right-Current-Left)
+order.
+In order to verify last two strategies, we will check the sequence if it is
+correct or not. For given pre- or post- order traversing of binary search tree
+it is always possible to say is it correct or not and to rebuild original tree.
+The idea is based on the fact that in such traversal sequence is always
+possible to determine current node, left subtree and right subtree.
+
+Also, this module is checking the correctness of the find, delete and leftmost
+operation.
+
+These tests are performed on red-black trees that store integers.
diff --git a/src/test/modules/test_rbtree/expected/test_rbtree.out b/src/test/modules/test_rbtree/expected/test_rbtree.out
new file mode 100644
index 0000000..8223e81
--- /dev/null
+++ b/src/test/modules/test_rbtree/expected/test_rbtree.out
@@ -0,0 +1,7 @@
+CREATE EXTENSION test_rbtree;
+SELECT testrbtree(100000);
+ testrbtree
+------------
+
+(1 row)
+
diff --git a/src/test/modules/test_rbtree/int_rbtree.h b/src/test/modules/test_rbtree/int_rbtree.h
new file mode 100644
index 0000000..57754bf
--- /dev/null
+++ b/src/test/modules/test_rbtree/int_rbtree.h
@@ -0,0 +1,49 @@
+/*--------------------------------------------------------------------------
+ *
+ * int_rbtree.h
+ * Definitions for integer red-black tree
+ *
+ * Copyright (c) 2013-2017, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/test/modules/test_rbtree/int_rbtree.h
+ *
+ * -------------------------------------------------------------------------
+ */
+
+#ifndef INT_RBTREE_H
+#define INT_RBTREE_H
+
+#include "lib/rbtree.h"
+
+typedef struct IntRBTreeNode
+{
+ RBNode rbnode;
+ int key;
+
+} IntRBTreeNode;
+
+static int
+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;
+}
+
+static RBNode *
+alloc(void *arg)
+{
+ IntRBTreeNode *ea;
+ ea = malloc(sizeof(IntRBTreeNode));
+ return (RBNode *) ea;
+}
+
+static void
+fr(RBNode * node, void *arg)
+{
+ free(node);
+}
+
+#endif /* INT_RBTREE_H */
diff --git a/src/test/modules/test_rbtree/sql/test_rbtree.sql b/src/test/modules/test_rbtree/sql/test_rbtree.sql
new file mode 100644
index 0000000..8263df3
--- /dev/null
+++ b/src/test/modules/test_rbtree/sql/test_rbtree.sql
@@ -0,0 +1,3 @@
+CREATE EXTENSION test_rbtree;
+
+SELECT testrbtree(100000);
diff --git a/src/test/modules/test_rbtree/test.c b/src/test/modules/test_rbtree/test.c
new file mode 100644
index 0000000..b6f4ce6
--- /dev/null
+++ b/src/test/modules/test_rbtree/test.c
@@ -0,0 +1,633 @@
+/*--------------------------------------------------------------------------
+ *
+ * test.c
+ * Test correctness of red-black tree traversals.
+ *
+ * Copyright (c) 2013-2017, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/test/modules/test_rbtree/test.c
+ *
+ * -------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "fmgr.h"
+#include "miscadmin.h"
+#include "pgstat.h"
+
+#include "int_rbtree.h"
+
+PG_MODULE_MAGIC;
+
+PG_FUNCTION_INFO_V1(testrbtree);
+
+/*
+ * Generate permutation for [0..size-1] interval
+ */
+static int*
+GetPermutation(int size)
+{
+ int *permutation;
+ int i;
+
+ permutation = (int *)palloc(size * sizeof(int));
+
+ permutation[0] = 0;
+
+ /* Generating random permutation */
+ for (i = 1; i < size; i++)
+ {
+ int j = rand() % i;
+
+ permutation[i] = permutation[j];
+ permutation[j] = i;
+ }
+
+ return permutation;
+}
+
+/*
+ * Checking the correctness of left-right traversal.
+ * Left-right traversal is correct if elements are
+ * given in the increasing order.
+ */
+static void
+testleftright(int size)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ int i;
+ int lastKey = -1;
+ int *permutation = GetPermutation(size);
+
+ /* filling tree by consecutive natural numbers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ rb_begin_iterate(tree, LeftRightWalk, &iter);
+
+ /* iterate over the tree */
+ while ((node = (IntRBTreeNode *)rb_iterate(&iter)) != NULL)
+ {
+ /* checking that order is increasing */
+ if (node->key <= lastKey)
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("left-right walk give elements not in sorted order")));
+ lastKey = node->key;
+ }
+}
+
+/*
+ * Checking the correctness of right-left traversal.
+ * Right-left traversal is correct if elements are
+ * given in the decreasing order.
+ */
+static void
+testrightleft(int size)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ int i;
+ int lastKey = size + 1;
+ int *permutation = GetPermutation(size);
+
+ /* filling tree by consecutive natural numbers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ rb_begin_iterate(tree, RightLeftWalk, &iter);
+
+ /* iterate over the tree */
+ while ((node = (IntRBTreeNode *)rb_iterate(&iter)) != NULL)
+ {
+ /* checking that order is decreasing */
+ if (node->key >= lastKey)
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("right-left walk give elements not in sorted order")));
+ lastKey = node->key;
+ }
+}
+
+/*
+ * Getting NIL element of the tree
+ */
+static RBNode *
+GetNil(RBNode *node)
+{
+ if ((void *)node == (void *)node->left)
+ return node;
+ return GetNil(node->left);
+}
+
+/*
+ * Checking the correctness of given preorder traversal.
+ * For the preorder traversal the root key is always on the first position.
+ * NOTE: BST has only one preorder traversal and vice versa.
+ * Any preorder traversal corresponds to only one BST.
+ * e1 e2 e3 ... ek ... elen
+ * ^ ^ ^
+ * head left right
+ * e1 > ei for all i in [2; k - 1]
+ * e1 < ei for all i in [k; len]
+ */
+static bool
+ValidatePreorderInt(int * array, int len)
+{
+ int *left = array + 1;
+ int *right = left;
+ int *tmp;
+
+ if (len <= 1)
+ return true;
+
+ /* searching for the right subtree */
+ while (right < array + len && *right <= *array)
+ right++;
+
+ /* checking that right subtree has only elements
+ * that are bigger than current */
+ tmp = right;
+ while (tmp < array + len)
+ {
+ if (*tmp <= *array)
+ return false;
+ tmp++;
+ }
+
+ /* checking left subtree and right subtree recursively */
+ return ValidatePreorderInt(left, right - left) &&
+ ValidatePreorderInt(right, array + len - right);
+}
+
+/* Checking traversal by traversing the tree */
+static bool
+ValidatePreorderIntTree(IntRBTreeNode *node, int *array, int len, void *null)
+{
+ int *right = array;
+ int rightValue;
+ int leftValue;
+ int i;
+ if (node == null)
+ return len == 0;
+ if (node->key != *array)
+ return false;
+ /* If node has left child -> check it */
+ if ((void *)node->rbnode.left != null)
+ {
+ leftValue = ((IntRBTreeNode *)node->rbnode.left)->key;
+ if (leftValue != array[1])
+ return false;
+ /* searching for right part */
+ if ((void *)node->rbnode.right != null)
+ {
+ rightValue = ((IntRBTreeNode *)node->rbnode.right)->key;
+ i = 0;
+ 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, null))
+ return false;
+ }
+
+ /* If node has right child -> check it */
+ if ((void *)node->rbnode.right != null)
+ {
+ rightValue = ((IntRBTreeNode *)node->rbnode.right)->key;
+ /* if left child is not null -> right is properly set, otherwise set it now */
+ if (right == array)
+ right++;
+ if (rightValue != *right)
+ return false;
+ return ValidatePreorderIntTree((IntRBTreeNode *)node->rbnode.right, right, array + len - right, null);
+ }
+ return true;
+}
+
+/*
+ * Checking the correctness of preorder(direct) traversal.
+ * Firstly, the correctness of the sequence by itself is checked.
+ * Secondly, a correspondence to the tree is checked.
+ */
+static void
+testdirect(int size)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ void *null;
+ int *elements;
+ int i;
+ int *permutation = GetPermutation(size);
+
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ 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 || !ValidatePreorderInt(elements, size))
+ {
+ pfree(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("preorder walk give elements not in the correct order")));
+
+ }
+
+ null = (void *)GetNil(*(RBNode **)tree);
+ if (!ValidatePreorderIntTree(*(IntRBTreeNode **)tree, elements, size, null))
+ {
+ pfree(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("preorder walk give elements not in the correct order in tree check")));
+
+ }
+
+ pfree(elements);
+}
+
+/*
+ * Checking the correctness of given postorder traversal
+ * For the postorder traversal the root key is always the last.
+ * NOTE: BST has only one postorder traversal and vice versa
+ * Any postorder traversal corresponds to only one BST
+ */
+static bool
+ValidatePostorderInt(int * array, int len)
+{
+ int *left = array;
+ int *right = left;
+ int *tmp;
+
+ if (len <= 1)
+ return true;
+
+ /* searching for the right subtree */
+ while (right < array + len - 1 && *right <= array[len - 1])
+ right++;
+
+ /* checking that right subtree has only elements
+ * that are bigger than current */
+ tmp = right;
+ while (tmp < array + len - 1)
+ {
+ if (*tmp <= array[len - 1])
+ return false;
+ tmp++;
+ }
+
+ /* Checking left subtree and right subtree recursively */
+ return ValidatePostorderInt(left, right - left) &&
+ ValidatePostorderInt(right, array + len - right - 1);
+}
+
+/* Checking traversal by traversing the tree */
+static bool
+ValidatePostorderIntTree(IntRBTreeNode *node, int *array, int len, void *null, int depth)
+{
+ int *right = array;
+ int leftValue;
+ int i;
+ if (node == null)
+ return len == 0;
+ if (node->key != array[len - 1])
+ return false;
+
+ /* If node has left child -> check it */
+ if ((void *)node->rbnode.left != null)
+ {
+ leftValue = ((IntRBTreeNode *)node->rbnode.left)->key;
+ /* searching for right part */
+ if ((void *)node->rbnode.right != null)
+ {
+ i = 0;
+ while (array[i] != leftValue)
+ {
+ i++;
+ if (i >= len)
+ return false;
+ }
+ right = array + i + 1;
+ }
+ else
+ {
+ right = array + len - 1;
+ }
+ if (!ValidatePostorderIntTree((IntRBTreeNode *)node->rbnode.left, array, right - array, null, depth + 1))
+ return false;
+ }
+
+ /* If node has right child -> check it */
+ if ((void *)node->rbnode.right != null)
+ {
+ return ValidatePostorderIntTree((IntRBTreeNode *)node->rbnode.right, right, array + len - right - 1, null, depth + 1);
+ }
+ return true;
+}
+
+/*
+ * Checking the correctness of posorder(inverted) traversal.
+ * Firstly, the correctness of the sequence by itself is checked.
+ * Secondly, a correspondence to the tree is checked.
+ */
+static void
+testinverted(int size)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ void *null;
+ int *elements;
+ int i;
+ int *permutation = GetPermutation(size);
+
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ 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 || !ValidatePostorderInt(elements, size))
+ {
+ pfree(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("postorder walk give elements not in the correct order")));
+
+ }
+
+ null = (void *)GetNil(*(RBNode **)tree);
+ if (!ValidatePostorderIntTree(*(IntRBTreeNode **)tree, elements, size, null, 0))
+ {
+ pfree(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("postorder walk give elements not in the correct order in tree check")));
+
+ }
+
+ pfree(elements);
+}
+
+/*
+ * Checking the correctness of the pg_find operation by inserting and deleting
+ * integers.
+ */
+static void
+testfind(int size)
+{
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ int i;
+ int *permutation = GetPermutation(size);
+
+ /* Insert even integers from 0 to 2 * size */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = 2 * permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ /* Checking 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)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("inserted element was not found")));
+ }
+ if (node.key != resultNode->key)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("find operation in rbtree gave wrong result")));
+ }
+ }
+ /* Checking that not inserted elements can not be found */
+ for (i = -1; i < size + 10; i += 2)
+ {
+ IntRBTreeNode node;
+ IntRBTreeNode *resultNode;
+ node.key = i;
+ resultNode = (IntRBTreeNode *)rb_find(tree, (RBNode *)&node);
+ if (resultNode != NULL)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("not inserted element was found")));
+ }
+ }
+}
+
+/*
+ * Checking the correctness of the pg_leftmost operation. This operation should
+ * always return the smallest element of the tree.
+ */
+static void
+testleftmost(int size)
+{
+ IntRBTreeNode *result;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ int i;
+ int *permutation = GetPermutation(size);
+
+ /* Checking that empty tree has no leftmost element */
+ if (rb_leftmost(tree) != NULL)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("leftmost node of empty tree is not NULL")));
+ }
+
+ /* Populating the tree by integers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ /* Checking that leftmost element is the smallest one */
+ result = (IntRBTreeNode *)rb_leftmost(tree);
+ if (0 != result->key)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("leftmost operation in rbtree gave wrong result")));
+ }
+}
+
+/*
+ * Checking the correctness of the pg_delete operation.
+ */
+static void
+testdelete(int size, int delsize)
+{
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ int i, j;
+ int *deleteIds;
+ bool *chosen;
+ int *permutation = GetPermutation(size);
+
+ deleteIds = (int *)palloc(delsize * sizeof(int));
+ chosen = (bool *)palloc(size * sizeof(bool));
+
+ for (i = 0; i < size; i++)
+ chosen[i] = false;
+
+ /* Choosing unique ids to delete */
+ for (i = 0; i < delsize; i++)
+ {
+ int k = rand() % size;
+ while (chosen[k])
+ k = (k + 1) % size;
+ deleteIds[i] = k;
+ chosen[k] = true;
+ }
+
+ /* Populating the tree by integers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+ /* Populating the tree by integers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = permutation[i];
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ /* Deleting elements */
+ for (i = 0; i < delsize; i++)
+ {
+ IntRBTreeNode find;
+ IntRBTreeNode *node;
+
+ find.key = deleteIds[i];
+ /* In order node to be deleted is should be taken by pg_find */
+ node = (IntRBTreeNode *)rb_find(tree, (RBNode *)&find);
+ if (node == NULL)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("inserted element was not found during deleting")));
+ }
+ rb_delete(tree, (RBNode *)node);
+ }
+
+ /* Checking that deleted elements are deleted */
+ for (i = 0; i < size; i++)
+ {
+ bool isDeleted = false;
+ IntRBTreeNode *result;
+ IntRBTreeNode node;
+
+ for (j = 0; j < delsize && !isDeleted; j++)
+ if (i == deleteIds[j])
+ isDeleted = true;
+
+ node.key = i;
+ result = (IntRBTreeNode *)rb_find(tree, (RBNode *)&node);
+ /* Delete element should be absent */
+ if (isDeleted && result != NULL)
+ {
+ pfree(deleteIds);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("deleted element presents in the rbtree")));
+ }
+ if (!isDeleted && result == 0)
+ {
+ pfree(deleteIds);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("element should presents in the rbtree")));
+ }
+ /* Alive element should be presented */
+ if (!isDeleted && result->key != i)
+ {
+ pfree(deleteIds);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("delete operation corrupted rbtree")));
+ }
+ }
+
+ pfree(deleteIds);
+}
+
+Datum
+testrbtree(PG_FUNCTION_ARGS)
+{
+ int size = PG_GETARG_INT32(0);
+ 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--1.0.sql b/src/test/modules/test_rbtree/test_rbtree--1.0.sql
new file mode 100644
index 0000000..e549867
--- /dev/null
+++ b/src/test/modules/test_rbtree/test_rbtree--1.0.sql
@@ -0,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 testrbtree(size INTEGER)
+ RETURNS pg_catalog.void STRICT
+ AS 'MODULE_PATHNAME' LANGUAGE C;
diff --git a/src/test/modules/test_rbtree/test_rbtree.control b/src/test/modules/test_rbtree/test_rbtree.control
new file mode 100644
index 0000000..890f8a9
--- /dev/null
+++ b/src/test/modules/test_rbtree/test_rbtree.control
@@ -0,0 +1,4 @@
+comment = 'Test rbtree traversal'
+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
