test/avl.h

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