LCOV - code coverage report
Current view: top level - src/test/modules/test_rbtree - test_rbtree.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 131 153 85.6 %
Date: 2019-06-19 16:07:09 Functions: 15 15 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*--------------------------------------------------------------------------
       2             :  *
       3             :  * test_rbtree.c
       4             :  *      Test correctness of red-black tree operations.
       5             :  *
       6             :  * Copyright (c) 2009-2019, PostgreSQL Global Development Group
       7             :  *
       8             :  * IDENTIFICATION
       9             :  *      src/test/modules/test_rbtree/test_rbtree.c
      10             :  *
      11             :  * -------------------------------------------------------------------------
      12             :  */
      13             : 
      14             : #include "postgres.h"
      15             : 
      16             : #include "fmgr.h"
      17             : #include "lib/rbtree.h"
      18             : #include "utils/memutils.h"
      19             : 
      20           2 : PG_MODULE_MAGIC;
      21             : 
      22             : 
      23             : /*
      24             :  * Our test trees store an integer key, and nothing else.
      25             :  */
      26             : typedef struct IntRBTreeNode
      27             : {
      28             :     RBTNode     rbtnode;
      29             :     int         key;
      30             : } IntRBTreeNode;
      31             : 
      32             : 
      33             : /*
      34             :  * Node comparator.  We don't worry about overflow in the subtraction,
      35             :  * since none of our test keys are negative.
      36             :  */
      37             : static int
      38     2174060 : irbt_cmp(const RBTNode *a, const RBTNode *b, void *arg)
      39             : {
      40     2174060 :     const IntRBTreeNode *ea = (const IntRBTreeNode *) a;
      41     2174060 :     const IntRBTreeNode *eb = (const IntRBTreeNode *) b;
      42             : 
      43     2174060 :     return ea->key - eb->key;
      44             : }
      45             : 
      46             : /*
      47             :  * Node combiner.  For testing purposes, just check that library doesn't
      48             :  * try to combine unequal keys.
      49             :  */
      50             : static void
      51          10 : irbt_combine(RBTNode *existing, const RBTNode *newdata, void *arg)
      52             : {
      53          10 :     const IntRBTreeNode *eexist = (const IntRBTreeNode *) existing;
      54          10 :     const IntRBTreeNode *enew = (const IntRBTreeNode *) newdata;
      55             : 
      56          10 :     if (eexist->key != enew->key)
      57           0 :         elog(ERROR, "red-black tree combines %d into %d",
      58             :              enew->key, eexist->key);
      59          10 : }
      60             : 
      61             : /* Node allocator */
      62             : static RBTNode *
      63      100000 : irbt_alloc(void *arg)
      64             : {
      65      100000 :     return (RBTNode *) palloc(sizeof(IntRBTreeNode));
      66             : }
      67             : 
      68             : /* Node freer */
      69             : static void
      70       20000 : irbt_free(RBTNode *node, void *arg)
      71             : {
      72       20000 :     pfree(node);
      73       20000 : }
      74             : 
      75             : /*
      76             :  * Create a red-black tree using our support functions
      77             :  */
      78             : static RBTree *
      79          10 : create_int_rbtree(void)
      80             : {
      81          10 :     return rbt_create(sizeof(IntRBTreeNode),
      82             :                       irbt_cmp,
      83             :                       irbt_combine,
      84             :                       irbt_alloc,
      85             :                       irbt_free,
      86             :                       NULL);
      87             : }
      88             : 
      89             : /*
      90             :  * Generate a random permutation of the integers 0..size-1
      91             :  */
      92             : static int *
      93          10 : GetPermutation(int size)
      94             : {
      95             :     int        *permutation;
      96             :     int         i;
      97             : 
      98          10 :     permutation = (int *) palloc(size * sizeof(int));
      99             : 
     100          10 :     permutation[0] = 0;
     101             : 
     102             :     /*
     103             :      * This is the "inside-out" variant of the Fisher-Yates shuffle algorithm.
     104             :      * Notionally, we append each new value to the array and then swap it with
     105             :      * a randomly-chosen array element (possibly including itself, else we
     106             :      * fail to generate permutations with the last integer last).  The swap
     107             :      * step can be optimized by combining it with the insertion.
     108             :      */
     109      100000 :     for (i = 1; i < size; i++)
     110             :     {
     111       99990 :         int         j = random() % (i + 1);
     112             : 
     113       99990 :         if (j < i)               /* avoid fetching undefined data if j=i */
     114       99914 :             permutation[i] = permutation[j];
     115       99990 :         permutation[j] = i;
     116             :     }
     117             : 
     118          10 :     return permutation;
     119             : }
     120             : 
     121             : /*
     122             :  * Populate an empty RBTree with "size" integers having the values
     123             :  * 0, step, 2*step, 3*step, ..., inserting them in random order
     124             :  */
     125             : static void
     126          10 : rbt_populate(RBTree *tree, int size, int step)
     127             : {
     128          10 :     int        *permutation = GetPermutation(size);
     129             :     IntRBTreeNode node;
     130             :     bool        isNew;
     131             :     int         i;
     132             : 
     133             :     /* Insert values.  We don't expect any collisions. */
     134      100010 :     for (i = 0; i < size; i++)
     135             :     {
     136      100000 :         node.key = step * permutation[i];
     137      100000 :         rbt_insert(tree, (RBTNode *) &node, &isNew);
     138      100000 :         if (!isNew)
     139           0 :             elog(ERROR, "unexpected !isNew result from rbt_insert");
     140             :     }
     141             : 
     142             :     /*
     143             :      * Re-insert the first value to make sure collisions work right.  It's
     144             :      * probably not useful to test that case over again for all the values.
     145             :      */
     146          10 :     if (size > 0)
     147             :     {
     148          10 :         node.key = step * permutation[0];
     149          10 :         rbt_insert(tree, (RBTNode *) &node, &isNew);
     150          10 :         if (isNew)
     151           0 :             elog(ERROR, "unexpected isNew result from rbt_insert");
     152             :     }
     153             : 
     154          10 :     pfree(permutation);
     155          10 : }
     156             : 
     157             : /*
     158             :  * Check the correctness of left-right traversal.
     159             :  * Left-right traversal is correct if all elements are
     160             :  * visited in increasing order.
     161             :  */
     162             : static void
     163           2 : testleftright(int size)
     164             : {
     165           2 :     RBTree     *tree = create_int_rbtree();
     166             :     IntRBTreeNode *node;
     167             :     RBTreeIterator iter;
     168           2 :     int         lastKey = -1;
     169           2 :     int         count = 0;
     170             : 
     171             :     /* check iteration over empty tree */
     172           2 :     rbt_begin_iterate(tree, LeftRightWalk, &iter);
     173           2 :     if (rbt_iterate(&iter) != NULL)
     174           0 :         elog(ERROR, "left-right walk over empty tree produced an element");
     175             : 
     176             :     /* fill tree with consecutive natural numbers */
     177           2 :     rbt_populate(tree, size, 1);
     178             : 
     179             :     /* iterate over the tree */
     180           2 :     rbt_begin_iterate(tree, LeftRightWalk, &iter);
     181             : 
     182       20004 :     while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
     183             :     {
     184             :         /* check that order is increasing */
     185       20000 :         if (node->key <= lastKey)
     186           0 :             elog(ERROR, "left-right walk gives elements not in sorted order");
     187       20000 :         lastKey = node->key;
     188       20000 :         count++;
     189             :     }
     190             : 
     191           2 :     if (lastKey != size - 1)
     192           0 :         elog(ERROR, "left-right walk did not reach end");
     193           2 :     if (count != size)
     194           0 :         elog(ERROR, "left-right walk missed some elements");
     195           2 : }
     196             : 
     197             : /*
     198             :  * Check the correctness of right-left traversal.
     199             :  * Right-left traversal is correct if all elements are
     200             :  * visited in decreasing order.
     201             :  */
     202             : static void
     203           2 : testrightleft(int size)
     204             : {
     205           2 :     RBTree     *tree = create_int_rbtree();
     206             :     IntRBTreeNode *node;
     207             :     RBTreeIterator iter;
     208           2 :     int         lastKey = size;
     209           2 :     int         count = 0;
     210             : 
     211             :     /* check iteration over empty tree */
     212           2 :     rbt_begin_iterate(tree, RightLeftWalk, &iter);
     213           2 :     if (rbt_iterate(&iter) != NULL)
     214           0 :         elog(ERROR, "right-left walk over empty tree produced an element");
     215             : 
     216             :     /* fill tree with consecutive natural numbers */
     217           2 :     rbt_populate(tree, size, 1);
     218             : 
     219             :     /* iterate over the tree */
     220           2 :     rbt_begin_iterate(tree, RightLeftWalk, &iter);
     221             : 
     222       20004 :     while ((node = (IntRBTreeNode *) rbt_iterate(&iter)) != NULL)
     223             :     {
     224             :         /* check that order is decreasing */
     225       20000 :         if (node->key >= lastKey)
     226           0 :             elog(ERROR, "right-left walk gives elements not in sorted order");
     227       20000 :         lastKey = node->key;
     228       20000 :         count++;
     229             :     }
     230             : 
     231           2 :     if (lastKey != 0)
     232           0 :         elog(ERROR, "right-left walk did not reach end");
     233           2 :     if (count != size)
     234           0 :         elog(ERROR, "right-left walk missed some elements");
     235           2 : }
     236             : 
     237             : /*
     238             :  * Check the correctness of the rbt_find operation by searching for
     239             :  * both elements we inserted and elements we didn't.
     240             :  */
     241             : static void
     242           2 : testfind(int size)
     243             : {
     244           2 :     RBTree     *tree = create_int_rbtree();
     245             :     int         i;
     246             : 
     247             :     /* Insert even integers from 0 to 2 * (size-1) */
     248           2 :     rbt_populate(tree, size, 2);
     249             : 
     250             :     /* Check that all inserted elements can be found */
     251       20002 :     for (i = 0; i < size; i++)
     252             :     {
     253             :         IntRBTreeNode node;
     254             :         IntRBTreeNode *resultNode;
     255             : 
     256       20000 :         node.key = 2 * i;
     257       20000 :         resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
     258       20000 :         if (resultNode == NULL)
     259           0 :             elog(ERROR, "inserted element was not found");
     260       20000 :         if (node.key != resultNode->key)
     261           0 :             elog(ERROR, "find operation in rbtree gave wrong result");
     262             :     }
     263             : 
     264             :     /*
     265             :      * Check that not-inserted elements can not be found, being sure to try
     266             :      * values before the first and after the last element.
     267             :      */
     268       20004 :     for (i = -1; i <= 2 * size; i += 2)
     269             :     {
     270             :         IntRBTreeNode node;
     271             :         IntRBTreeNode *resultNode;
     272             : 
     273       20002 :         node.key = i;
     274       20002 :         resultNode = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
     275       20002 :         if (resultNode != NULL)
     276           0 :             elog(ERROR, "not-inserted element was found");
     277             :     }
     278           2 : }
     279             : 
     280             : /*
     281             :  * Check the correctness of the rbt_leftmost operation.
     282             :  * This operation should always return the smallest element of the tree.
     283             :  */
     284             : static void
     285           2 : testleftmost(int size)
     286             : {
     287           2 :     RBTree     *tree = create_int_rbtree();
     288             :     IntRBTreeNode *result;
     289             : 
     290             :     /* Check that empty tree has no leftmost element */
     291           2 :     if (rbt_leftmost(tree) != NULL)
     292           0 :         elog(ERROR, "leftmost node of empty tree is not NULL");
     293             : 
     294             :     /* fill tree with consecutive natural numbers */
     295           2 :     rbt_populate(tree, size, 1);
     296             : 
     297             :     /* Check that leftmost element is the smallest one */
     298           2 :     result = (IntRBTreeNode *) rbt_leftmost(tree);
     299           2 :     if (result == NULL || result->key != 0)
     300           0 :         elog(ERROR, "rbt_leftmost gave wrong result");
     301           2 : }
     302             : 
     303             : /*
     304             :  * Check the correctness of the rbt_delete operation.
     305             :  */
     306             : static void
     307           2 : testdelete(int size, int delsize)
     308             : {
     309           2 :     RBTree     *tree = create_int_rbtree();
     310             :     int        *deleteIds;
     311             :     bool       *chosen;
     312             :     int         i;
     313             : 
     314             :     /* fill tree with consecutive natural numbers */
     315           2 :     rbt_populate(tree, size, 1);
     316             : 
     317             :     /* Choose unique ids to delete */
     318           2 :     deleteIds = (int *) palloc(delsize * sizeof(int));
     319           2 :     chosen = (bool *) palloc0(size * sizeof(bool));
     320             : 
     321        2002 :     for (i = 0; i < delsize; i++)
     322             :     {
     323        2000 :         int         k = random() % size;
     324             : 
     325        4116 :         while (chosen[k])
     326         116 :             k = (k + 1) % size;
     327        2000 :         deleteIds[i] = k;
     328        2000 :         chosen[k] = true;
     329             :     }
     330             : 
     331             :     /* Delete elements */
     332        2002 :     for (i = 0; i < delsize; i++)
     333             :     {
     334             :         IntRBTreeNode find;
     335             :         IntRBTreeNode *node;
     336             : 
     337        2000 :         find.key = deleteIds[i];
     338             :         /* Locate the node to be deleted */
     339        2000 :         node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
     340        2000 :         if (node == NULL || node->key != deleteIds[i])
     341           0 :             elog(ERROR, "expected element was not found during deleting");
     342             :         /* Delete it */
     343        2000 :         rbt_delete(tree, (RBTNode *) node);
     344             :     }
     345             : 
     346             :     /* Check that deleted elements are deleted */
     347       20002 :     for (i = 0; i < size; i++)
     348             :     {
     349             :         IntRBTreeNode node;
     350             :         IntRBTreeNode *result;
     351             : 
     352       20000 :         node.key = i;
     353       20000 :         result = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &node);
     354       20000 :         if (chosen[i])
     355             :         {
     356             :             /* Deleted element should be absent */
     357        2000 :             if (result != NULL)
     358           0 :                 elog(ERROR, "deleted element still present in the rbtree");
     359             :         }
     360             :         else
     361             :         {
     362             :             /* Else it should be present */
     363       18000 :             if (result == NULL || result->key != i)
     364           0 :                 elog(ERROR, "delete operation removed wrong rbtree value");
     365             :         }
     366             :     }
     367             : 
     368             :     /* Delete remaining elements, so as to exercise reducing tree to empty */
     369       20002 :     for (i = 0; i < size; i++)
     370             :     {
     371             :         IntRBTreeNode find;
     372             :         IntRBTreeNode *node;
     373             : 
     374       20000 :         if (chosen[i])
     375        2000 :             continue;
     376       18000 :         find.key = i;
     377             :         /* Locate the node to be deleted */
     378       18000 :         node = (IntRBTreeNode *) rbt_find(tree, (RBTNode *) &find);
     379       18000 :         if (node == NULL || node->key != i)
     380           0 :             elog(ERROR, "expected element was not found during deleting");
     381             :         /* Delete it */
     382       18000 :         rbt_delete(tree, (RBTNode *) node);
     383             :     }
     384             : 
     385             :     /* Tree should now be empty */
     386           2 :     if (rbt_leftmost(tree) != NULL)
     387           0 :         elog(ERROR, "deleting all elements failed");
     388             : 
     389           2 :     pfree(deleteIds);
     390           2 :     pfree(chosen);
     391           2 : }
     392             : 
     393             : /*
     394             :  * SQL-callable entry point to perform all tests
     395             :  *
     396             :  * Argument is the number of entries to put in the trees
     397             :  */
     398           4 : PG_FUNCTION_INFO_V1(test_rb_tree);
     399             : 
     400             : Datum
     401           2 : test_rb_tree(PG_FUNCTION_ARGS)
     402             : {
     403           2 :     int         size = PG_GETARG_INT32(0);
     404             : 
     405           2 :     if (size <= 0 || size > MaxAllocSize / sizeof(int))
     406           0 :         elog(ERROR, "invalid size for test_rb_tree: %d", size);
     407           2 :     testleftright(size);
     408           2 :     testrightleft(size);
     409           2 :     testfind(size);
     410           2 :     testleftmost(size);
     411           2 :     testdelete(size, Max(size / 10, 1));
     412           2 :     PG_RETURN_VOID();
     413             : }

Generated by: LCOV version 1.13