test/rbt.h

   1 #define MAIN(x) rbt##x
   2 #include "test.h"
   3 #include "a/rbt.h"
   4 #include "a/str.h"
   5
   6 typedef struct
   7 {
   8     a_rbt_node node;
   9     int data;
  10     int reached;
  11 } int_node;
  12
  13 static A_INLINE int_node *int_entry(void const *node)
  14 {
  15     return a_cast_r(int_node *, a_cast_r(a_uptr, node) - a_offsetof(int_node, node)); // NOLINT
  16 }
  17
  18 static int int_cmp(void const *lhs, void const *rhs)
  19 {
  20     return int_entry(lhs)->data - int_entry(rhs)->data;
  21 }
  22
  23 static int intcmp(void const *lhs, void const *rhs)
  24 {
  25     return *a_int_(const *, lhs) - *a_int_(const *, rhs);
  26 }
  27
  28 static int test(int argc, char *argv[])
  29 {
  30     (void)(argc);
  31     (void)(argv);
  32
  33     unsigned int const n = 0x1000;
  34
  35     a_str str = A_STR_NUL;
  36     a_rbt root = A_RBT_ROOT;
  37     int_node *vec = a_new(int_node, A_NULL, n);
  38     int *sorted = a_new(int, A_NULL, n);
  39     for (unsigned int i = 0; i < n; ++i)
  40     {
  41         a_str_putf(&str, "%u", i);
  42         vec[i].data = a_cast_s(int, a_hash_bkdr(a_str_ptr(&str), 0));
  43         a_str_drop(&str);
  44         sorted[i] = vec[i].data;
  45         a_rbt_insert(&root, &vec[i].node, int_cmp);
  46         if (i % 0x100 == 0)
  47         {
  48             debug("insert 0x%04X/0x%04X\n", i, n);
  49         }
  50     }
  51     a_str_dtor(&str);
  52
  53     for (unsigned int i = 0; i < n; ++i)
  54     {
  55         TEST_BUG(a_rbt_search(&root, &vec[i].node, int_cmp));
  56     }
  57
  58     unsigned int x;
  59     qsort(sorted, n, sizeof(int), intcmp);
  60
  61     x = 0;
  62     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
  74     {
  75         TEST_BUG(vec[i].reached);
  76     }
  77     TEST_BUG(x == n);
  78
  79     x = n;
  80     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
  91     {
  92         TEST_BUG(vec[i].reached);
  93     }
  94     TEST_BUG(x == 0);
  95
  96     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
 106     {
 107         TEST_BUG(vec[i].reached);
 108     }
 109
 110     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
 120     {
 121         TEST_BUG(vec[i].reached);
 122     }
 123
 124     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
 134     {
 135         TEST_BUG(vec[i].reached);
 136     }
 137
 138     for (unsigned int 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 (unsigned int i = 0; i < n; ++i)
 148     {
 149         TEST_BUG(vec[i].reached);
 150     }
 151
 152     for (unsigned int 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%04X\n", i, n);
 158         }
 159     }
 160
 161     TEST_BUG(!a_rbt_search(&root, &vec->node, int_cmp));
 162
 163     for (unsigned int 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 (unsigned int 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     printf("%s\n", A_FUNC);
 185     test(argc, argv);
 186     return 0;
 187 }