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