test/rbt.h

   1 #define MAIN(x) rbt##x
   2 #include "test.h"
   3 #include "a/rbt.h"
   4 #include "a/str.h"
   5 #include "a/hash.h"
   6
   7 typedef struct
   8 {
   9     a_rbt_node node;
  10     int data;
  11     int reached;
  12 } int_node;
  13
  14 static A_INLINE int_node *int_entry(void const *node)
  15 {
  16     return a_cast_r(int_node *, a_cast_r(a_uptr, node) - a_offsetof(int_node, node)); /* NOLINT */
  17 }
  18
  19 static int int_cmp(void const *lhs, void const *rhs)
  20 {
  21     int a = int_entry(lhs)->data;
  22     int b = int_entry(rhs)->data;
  23     return (a > b) - (a < b);
  24 }
  25
  26 static int intcmp(void const *lhs, void const *rhs)
  27 {
  28     int a = *a_int_(const *, lhs);
  29     int b = *a_int_(const *, rhs);
  30     return (a > b) - (a < b);
  31 }
  32
  33 static int test(unsigned long n)
  34 {
  35     unsigned int i;
  36     unsigned long x;
  37     a_rbt_node *cur, *next;
  38     a_str str = A_STR_INIT;
  39     a_rbt root = A_RBT_ROOT;
  40     int *sorted = a_new(int, A_NULL, n);
  41     int_node *vec = a_new(int_node, A_NULL, n);
  42     for (i = 0; i < n; ++i)
  43     {
  44         a_str_setf(&str, "%u", i);
  45         vec[i].data = sorted[i] = a_cast_s(int, a_hash_bkdr(a_str_ptr(&str), 0));
  46         a_rbt_insert(&root, &vec[i].node, int_cmp);
  47         if (i % 0x100 == 0)
  48         {
  49             debug("insert 0x%04X/0x%04lX\n", i, n);
  50         }
  51     }
  52     a_str_dtor(&str);
  53
  54     for (i = 0; i < n; ++i)
  55     {
  56         TEST_BUG(a_rbt_search(&root, &vec[i].node, int_cmp));
  57     }
  58
  59     qsort(sorted, n, sizeof(int), intcmp);
  60
  61     x = 0;
  62     for (i = 0; i < n; ++i)
  63     {
  64         vec[i].reached = 0;
  65     }
  66     A_RBT_FOREACH(cur, &root)
  67     {
  68         int_node *it = int_entry(cur);
  69         TEST_BUG(it->data == sorted[x]);
  70         it->reached = 1;
  71         ++x;
  72     }
  73     for (i = 0; i < n; ++i)
  74     {
  75         TEST_BUG(vec[i].reached);
  76     }
  77     TEST_BUG(x == n);
  78
  79     x = n;
  80     for (i = 0; i < n; ++i)
  81     {
  82         vec[i].reached = 0;
  83     }
  84     A_RBT_FOREACH_REVERSE(cur, &root)
  85     {
  86         int_node *it = int_entry(cur);
  87         TEST_BUG(it->data == sorted[--x]);
  88         it->reached = 1;
  89     }
  90     for (i = 0; i < n; ++i)
  91     {
  92         TEST_BUG(vec[i].reached);
  93     }
  94     TEST_BUG(x == 0);
  95
  96     for (i = 0; i < n; ++i)
  97     {
  98         vec[i].reached = 0;
  99     }
 100     A_RBT_PRE_FOREACH(cur, &root)
 101     {
 102         int_node *it = int_entry(cur);
 103         it->reached = 1;
 104     }
 105     for (i = 0; i < n; ++i)
 106     {
 107         TEST_BUG(vec[i].reached);
 108     }
 109
 110     for (i = 0; i < n; ++i)
 111     {
 112         vec[i].reached = 0;
 113     }
 114     A_RBT_PRE_FOREACH_REVERSE(cur, &root)
 115     {
 116         int_node *it = int_entry(cur);
 117         it->reached = 1;
 118     }
 119     for (i = 0; i < n; ++i)
 120     {
 121         TEST_BUG(vec[i].reached);
 122     }
 123
 124     for (i = 0; i < n; ++i)
 125     {
 126         vec[i].reached = 0;
 127     }
 128     A_RBT_POST_FOREACH(cur, &root)
 129     {
 130         int_node *it = int_entry(cur);
 131         it->reached = 1;
 132     }
 133     for (i = 0; i < n; ++i)
 134     {
 135         TEST_BUG(vec[i].reached);
 136     }
 137
 138     for (i = 0; i < n; ++i)
 139     {
 140         vec[i].reached = 0;
 141     }
 142     A_RBT_POST_FOREACH_REVERSE(cur, &root)
 143     {
 144         int_node *it = int_entry(cur);
 145         it->reached = 1;
 146     }
 147     for (i = 0; i < n; ++i)
 148     {
 149         TEST_BUG(vec[i].reached);
 150     }
 151
 152     for (i = 0; i < n; ++i)
 153     {
 154         a_rbt_remove(&root, &vec[i].node);
 155         if (i % 0x100 == 0)
 156         {
 157             debug("remove 0x%04X/0x%04lX\n", i, n);
 158         }
 159     }
 160
 161     TEST_BUG(!a_rbt_search(&root, &vec->node, int_cmp));
 162
 163     for (i = 0; i < n; ++i)
 164     {
 165         a_rbt_insert(&root, &vec[i].node, int_cmp);
 166         vec[i].reached = 0;
 167     }
 168     A_RBT_FORTEAR(cur, next, &root)
 169     {
 170         int_entry(cur)->reached = 1;
 171     }
 172     for (i = 0; i < n; ++i)
 173     {
 174         TEST_BUG(vec[i].reached);
 175     }
 176
 177     a_die(sorted);
 178     a_die(vec);
 179     return 0;
 180 }
 181
 182 int main(int argc, char *argv[]) /* NOLINT(misc-definitions-in-headers) */
 183 {
 184     unsigned long n = 0x1000;
 185     if (argc > 1) { n = strtoul(argv[1], A_NULL, 0); }
 186     puts(A_FUNC);
 187     test(n);
 188     return 0;
 189 }