Hello,
Postgres now has its own red-black tree implementation. This tree has 4
types of traversals. In the attachment, you can find module test that
checks the correctness of tree traversal strategies.
I hope that someone can find it useful.
Thank you for attention!
--
------
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/.gitignore b/src/test/modules/test_rbtree/.gitignore
new file mode 100644
index 0000000..5dcb3ff
--- /dev/null
+++ b/src/test/modules/test_rbtree/.gitignore
@@ -0,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
new file mode 100644
index 0000000..11a10cf
--- /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 triversal 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..9e6c977
--- /dev/null
+++ b/src/test/modules/test_rbtree/README
@@ -0,0 +1,17 @@
+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 extention 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.
+
+This tests are performed on red-black trees that store integers.
\ No newline at end of file
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..be8cd75
--- /dev/null
+++ b/src/test/modules/test_rbtree/expected/test_rbtree.out
@@ -0,0 +1,25 @@
+CREATE EXTENSION test_rbtree;
+SELECT testleftright();
+ testleftright
+---------------
+
+(1 row)
+
+SELECT testrightleft();
+ testrightleft
+---------------
+
+(1 row)
+
+SELECT testdirect();
+ testdirect
+------------
+
+(1 row)
+
+SELECT testinverted();
+ testinverted
+--------------
+
+(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..d153616
--- /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..edd90c1
--- /dev/null
+++ b/src/test/modules/test_rbtree/sql/test_rbtree.sql
@@ -0,0 +1,6 @@
+CREATE EXTENSION test_rbtree;
+
+SELECT testleftright();
+SELECT testrightleft();
+SELECT testdirect();
+SELECT testinverted();
\ No newline at end of file
diff --git a/src/test/modules/test_rbtree/test.c b/src/test/modules/test_rbtree/test.c
new file mode 100644
index 0000000..b28591e
--- /dev/null
+++ b/src/test/modules/test_rbtree/test.c
@@ -0,0 +1,407 @@
+/*--------------------------------------------------------------------------
+ *
+ * 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(testleftright);
+PG_FUNCTION_INFO_V1(testrightleft);
+PG_FUNCTION_INFO_V1(testdirect);
+PG_FUNCTION_INFO_V1(testinverted);
+
+void _PG_init(void);
+
+#define TEST_SIZE 100000
+
+/*
+ * Checking the correctness of left-right traversal.
+ * Left-right traversal is correct if elements are
+ * given in the increasing order.
+ */
+Datum
+testleftright(PG_FUNCTION_ARGS)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ int i;
+ int lastKey = -1;
+ int size = TEST_SIZE;
+
+ /* filling tree by consecutive natural numbers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = 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;
+ }
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * Checking the correctness of right-left traversal.
+ * Right-left traversal is correct if elements are
+ * given in the decreasing order.
+ */
+Datum
+testrightleft(PG_FUNCTION_ARGS)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ int i;
+ int size = TEST_SIZE;
+ int lastKey = size + 1;
+
+ /* filling tree by consecutive natural numbers */
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = 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;
+ }
+
+ PG_RETURN_VOID();
+}
+
+/*
+ * 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 correspondance to the tree is checked.
+ */
+Datum
+testdirect(PG_FUNCTION_ARGS)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ void *null;
+ int size = TEST_SIZE;
+ int *elements;
+ int i;
+
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = i;
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ elements = (int *) malloc(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))
+ {
+ free(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))
+ {
+ free(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("preorder walk give elements not in the correct order in tree check")));
+
+ }
+
+ free(elements);
+ PG_RETURN_VOID();
+}
+
+/*
+ * 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 && *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 correspondance to the tree is checked.
+ */
+Datum
+testinverted(PG_FUNCTION_ARGS)
+{
+ IntRBTreeNode *node;
+ RBTree *tree = rb_create(sizeof(IntRBTreeNode), cmp, NULL, alloc, fr, NULL);
+ RBTreeIterator iter;
+ void *null;
+ int size = TEST_SIZE;
+ int *elements;
+ int i;
+
+ for (i = 0; i < size; i++)
+ {
+ IntRBTreeNode node;
+ bool isNew;
+ node.key = i;
+ rb_insert(tree, (RBNode *) &node, &isNew);
+ }
+
+ elements = (int *) malloc(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))
+ {
+ free(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))
+ {
+ free(elements);
+ ereport(ERROR,
+ (errcode(ERRCODE_WARNING),
+ errmsg("postorder walk give elements not in the correct order in tree check")));
+
+ }
+
+ free(elements);
+ 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..d17746b
--- /dev/null
+++ b/src/test/modules/test_rbtree/test_rbtree--1.0.sql
@@ -0,0 +1,20 @@
+/* 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 testleftright()
+ RETURNS pg_catalog.void STRICT
+ AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION testrightleft()
+ RETURNS pg_catalog.void STRICT
+ AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION testdirect()
+ RETURNS pg_catalog.void STRICT
+ AS 'MODULE_PATHNAME' LANGUAGE C;
+
+CREATE FUNCTION testinverted()
+ RETURNS pg_catalog.void STRICT
+ AS 'MODULE_PATHNAME' LANGUAGE C;
\ No newline at end of file
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..2fade6a
--- /dev/null
+++ b/src/test/modules/test_rbtree/test_rbtree.control
@@ -0,0 +1,4 @@
+comment = 'Test rbtree triversal'
+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
