test/avl.h

   1 #define MAIN(x) avl##x
   2 #include "test.h"
   3 #include "a/avl.h"
   4 #include "a/str.h"
   5
   6 typedef struct
   7 {
   8     a_avl_node node;
   9     int data;
  10     int height;
  11     int reached;
  12 } int_node;
  13
  14 static A_INLINE int int_factor(a_avl_node *node)
  15 {
  16 #if defined(A_SIZE_POINTER) && (A_SIZE_POINTER + 0 > 3)
  17     return a_cast_s(int, node->parent_ & 3) - 1;
  18 #else /* !A_SIZE_POINTER */
  19     return node->factor;
  20 #endif /* A_SIZE_POINTER */
  21 }
  22
  23 static A_INLINE int_node *int_entry(void const *node)
  24 {
  25     return a_cast_r(int_node *, a_cast_r(a_uptr, node) - a_offsetof(int_node, node)); // NOLINT
  26 }
  27
  28 static int int_cmp(void const *lhs, void const *rhs)
  29 {
  30     int a = int_entry(lhs)->data;
  31     int b = int_entry(rhs)->data;
  32     return (a > b) - (a < b);
  33 }
  34
  35 static int intcmp(void const *lhs, void const *rhs)
  36 {
  37     int a = *a_int_(const *, lhs);
  38     int b = *a_int_(const *, rhs);
  39     return (a > b) - (a < b);
  40 }
  41
  42 #define int_max(a, b) ((a) > (b) ? (a) : (b))
  43 #define int_height(node) ((node) ? int_entry(node)->height : 0)
  44 static void set_height(a_avl_node *node) // NOLINT
  45 {
  46     if (node)
  47     {
  48         TEST_BUG(node->left != node);
  49         TEST_BUG(node->right != node);
  50         set_height(node->left);
  51         set_height(node->right);
  52         int const hl = int_height(node->left);
  53         int const hr = int_height(node->right);
  54         int_entry(node)->height = int_max(hl, hr) + 1;
  55     }
  56 }
  57
  58 static void check_tree(a_avl_node *node) // NOLINT
  59 {
  60     if (node)
  61     {
  62         int const e = int_factor(node);
  63         TEST_BUG(-1 <= e && e <= 1);
  64         TEST_BUG(int_height(node->right) - int_height(node->left) == e);
  65         if (node->left)
  66         {
  67             TEST_BUG(int_entry(node->left)->data < int_entry(node)->data);
  68             check_tree(node->left);
  69         }
  70         if (node->right)
  71         {
  72             TEST_BUG(int_entry(node->right)->data > int_entry(node)->data);
  73             check_tree(node->right);
  74         }
  75     }
  76 }
  77
  78 static int test(unsigned long n)
  79 {
  80     a_str str = A_STR_INIT;
  81     a_avl root = A_AVL_ROOT;
  82     int *sorted = a_new(int, A_NULL, n);
  83     int_node *vec = a_new(int_node, A_NULL, n);
  84     for (unsigned int i = 0; i < n; ++i)
  85     {
  86         a_str_setf(&str, "%u", i);
  87         vec[i].data = sorted[i] = a_cast_s(int, a_hash_bkdr(a_str_ptr(&str), 0));
  88         a_avl_insert(&root, &vec[i].node, int_cmp);
  89         set_height(root.node);
  90         check_tree(root.node);
  91         if (i % 0x100 == 0)
  92         {
  93             debug("insert 0x%04X/0x%04lX\n", i, n);
  94         }
  95     }
  96     a_str_dtor(&str);
  97
  98     for (unsigned int i = 0; i < n; ++i)
  99     {
 100         TEST_BUG(a_avl_search(&root, &vec[i].node, int_cmp));
 101     }
 102
 103     unsigned long x;
 104     qsort(sorted, n, sizeof(int), intcmp);
 105
 106     x = 0;
 107     for (unsigned int i = 0; i < n; ++i)
 108     {
 109         vec[i].reached = 0;
 110     }
 111     a_avl_foreach(cur, &root)
 112     {
 113         int_node *it = int_entry(cur);
 114         TEST_BUG(it->data == sorted[x]);
 115         it->reached = 1;
 116         ++x;
 117     }
 118     for (unsigned int i = 0; i < n; ++i)
 119     {
 120         TEST_BUG(vec[i].reached);
 121     }
 122     TEST_BUG(x == n);
 123
 124     x = n;
 125     for (unsigned int i = 0; i < n; ++i)
 126     {
 127         vec[i].reached = 0;
 128     }
 129     a_avl_foreach_reverse(cur, &root)
 130     {
 131         int_node *it = int_entry(cur);
 132         TEST_BUG(it->data == sorted[--x]);
 133         it->reached = 1;
 134     }
 135     for (unsigned int i = 0; i < n; ++i)
 136     {
 137         TEST_BUG(vec[i].reached);
 138     }
 139     TEST_BUG(x == 0);
 140
 141     for (unsigned int i = 0; i < n; ++i)
 142     {
 143         vec[i].reached = 0;
 144     }
 145     a_avl_pre_foreach(cur, &root)
 146     {
 147         int_node *it = int_entry(cur);
 148         it->reached = 1;
 149     }
 150     for (unsigned int i = 0; i < n; ++i)
 151     {
 152         TEST_BUG(vec[i].reached);
 153     }
 154
 155     for (unsigned int i = 0; i < n; ++i)
 156     {
 157         vec[i].reached = 0;
 158     }
 159     a_avl_pre_foreach_reverse(cur, &root)
 160     {
 161         int_node *it = int_entry(cur);
 162         it->reached = 1;
 163     }
 164     for (unsigned int i = 0; i < n; ++i)
 165     {
 166         TEST_BUG(vec[i].reached);
 167     }
 168
 169     for (unsigned int i = 0; i < n; ++i)
 170     {
 171         vec[i].reached = 0;
 172     }
 173     a_avl_post_foreach(cur, &root)
 174     {
 175         int_node *it = int_entry(cur);
 176         it->reached = 1;
 177     }
 178     for (unsigned int i = 0; i < n; ++i)
 179     {
 180         TEST_BUG(vec[i].reached);
 181     }
 182
 183     for (unsigned int i = 0; i < n; ++i)
 184     {
 185         vec[i].reached = 0;
 186     }
 187     a_avl_post_foreach_reverse(cur, &root)
 188     {
 189         int_node *it = int_entry(cur);
 190         it->reached = 1;
 191     }
 192     for (unsigned int i = 0; i < n; ++i)
 193     {
 194         TEST_BUG(vec[i].reached);
 195     }
 196
 197     for (unsigned int i = 0; i < n; ++i)
 198     {
 199         a_avl_remove(&root, &vec[i].node);
 200         set_height(root.node);
 201         check_tree(root.node);
 202         if (i % 0x100 == 0)
 203         {
 204             debug("remove 0x%04X/0x%04lX\n", i, n);
 205         }
 206     }
 207
 208     TEST_BUG(!a_avl_search(&root, &vec->node, int_cmp));
 209
 210     for (unsigned int i = 0; i < n; ++i)
 211     {
 212         a_avl_insert(&root, &vec[i].node, int_cmp);
 213         vec[i].reached = 0;
 214     }
 215     a_avl_fortear(cur, next, &root)
 216     {
 217         int_entry(cur)->reached = 1;
 218     }
 219     for (unsigned int i = 0; i < n; ++i)
 220     {
 221         TEST_BUG(vec[i].reached);
 222     }
 223
 224     a_die(sorted);
 225     a_die(vec);
 226     return 0;
 227 }
 228
 229 int main(int argc, char *argv[]) // NOLINT(misc-definitions-in-headers)
 230 {
 231     printf("%s\n", A_FUNC);
 232     unsigned long n = 0x1000;
 233     if (argc > 1) { n = strtoul(argv[1], A_NULL, 0); }
 234     test(n);
 235     return 0;
 236 }