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