From: Victor Drobny <v.drobny@postgrespro.ru>
To: Pgsql Hackers <pgsql-hackers@postgresql.org>
Subject: Red-Black tree traversal tests
Date: Fri, 28 Jul 2017 20:39:37 +0300
Message-ID: <c9d61310e16e75f8acaf6cb1c48b7b77@postgrespro.ru> (raw)
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-hackers>
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
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackersAttachments:rbtree_test.patch (text/x-diff, 15.7K) downloaddiff --git a/src/test/modules/Makefile b/src/test/modules/Makefileindex 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/.gitignorenew file mode 100644index 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/Makefilenew file mode 100644index 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+endifdiff --git a/src/test/modules/test_rbtree/README b/src/test/modules/test_rbtree/READMEnew file mode 100644index 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.outnew file mode 100644index 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.hnew file mode 100644index 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_Hdiff --git a/src/test/modules/test_rbtree/sql/test_rbtree.sql b/src/test/modules/test_rbtree/sql/test_rbtree.sqlnew file mode 100644index 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.cnew file mode 100644index 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.sqlnew file mode 100644index 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.controlnew file mode 100644index 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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: v.drobny@postgrespro.ru
Subject: Re: Red-Black tree traversal tests
In-Reply-To: <c9d61310e16e75f8acaf6cb1c48b7b77@postgrespro.ru>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox