src/util/rb_tree_test.c

   1 /*
   2  * Copyright © 2017 Jason Ekstrand
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining a
   5  * copy of this software and associated documentation files (the "Software"),
   6  * to deal in the Software without restriction, including without limitation
   7  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   8  * and/or sell copies of the Software, and to permit persons to whom the
   9  * Software is furnished to do so, subject to the following conditions:
  10  *
  11  * The above copyright notice and this permission notice shall be included in
  12  * all copies or substantial portions of the Software.
  13  *
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  20  * DEALINGS IN THE SOFTWARE.
  21  */
  22
  23 #undef NDEBUG
  24
  25 #include "rb_tree.h"
  26
  27 #include <assert.h>
  28 #include <limits.h>
  29
  30 /* A list of 100 random numbers from 1 to 100.  The number 30 is explicitly
  31  * missing from this list.
  32  */
  33 int test_numbers[] = {
  34     26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
  35     39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
  36     10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
  37     9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
  38     32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
  39     38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
  40     31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
  41     42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
  42     32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
  43     32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
  44 };
  45
  46 #define NON_EXISTANT_NUMBER 30
  47
  48 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
  49
  50 struct rb_test_node {
  51     int key;
  52     struct rb_node node;
  53 };
  54
  55 static int
  56 rb_test_node_cmp_void(const struct rb_node *n, const void *v)
  57 {
  58     struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
  59     return *(int *)v - tn->key;
  60 }
  61
  62 static int
  63 rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
  64 {
  65     struct rb_test_node *ta = rb_node_data(struct rb_test_node, a, node);
  66     struct rb_test_node *tb = rb_node_data(struct rb_test_node, b, node);
  67
  68     return tb->key - ta->key;
  69 }
  70
  71 static void
  72 validate_tree_order(struct rb_tree *tree, unsigned expected_count)
  73 {
  74     struct rb_test_node *prev = NULL;
  75     int max_val = -1;
  76     unsigned count = 0;
  77     rb_tree_foreach(struct rb_test_node, n, tree, node) {
  78         /* Everything should be in increasing order */
  79         assert(n->key >= max_val);
  80         if (n->key > max_val) {
  81             max_val = n->key;
  82         } else {
  83             /* Things should be stable, i.e., given equal keys, they should
  84              * show up in the list in order of insertion.  We insert them
  85              * in the order they are in in the array.
  86              */
  87             assert(prev == NULL || prev < n);
  88         }
  89
  90         prev = n;
  91         count++;
  92     }
  93     assert(count == expected_count);
  94
  95     prev = NULL;
  96     max_val = -1;
  97     count = 0;
  98     rb_tree_foreach_safe(struct rb_test_node, n, tree, node) {
  99         /* Everything should be in increasing order */
 100         assert(n->key >= max_val);
 101         if (n->key > max_val) {
 102             max_val = n->key;
 103         } else {
 104             /* Things should be stable, i.e., given equal keys, they should
 105              * show up in the list in order of insertion.  We insert them
 106              * in the order they are in in the array.
 107              */
 108             assert(prev == NULL || prev < n);
 109         }
 110
 111         prev = n;
 112         count++;
 113     }
 114     assert(count == expected_count);
 115
 116     prev = NULL;
 117     int min_val = INT_MAX;
 118     count = 0;
 119     rb_tree_foreach_rev(struct rb_test_node, n, tree, node) {
 120         /* Everything should be in increasing order */
 121         assert(n->key <= min_val);
 122         if (n->key < min_val) {
 123             min_val = n->key;
 124         } else {
 125             /* Things should be stable, i.e., given equal keys, they should
 126              * show up in the list in order of insertion.  We insert them
 127              * in the order they are in in the array.
 128              */
 129             assert(prev == NULL || prev > n);
 130         }
 131
 132         prev = n;
 133         count++;
 134     }
 135     assert(count == expected_count);
 136
 137     prev = NULL;
 138     min_val = INT_MAX;
 139     count = 0;
 140     rb_tree_foreach_rev_safe(struct rb_test_node, n, tree, node) {
 141         /* Everything should be in increasing order */
 142         assert(n->key <= min_val);
 143         if (n->key < min_val) {
 144             min_val = n->key;
 145         } else {
 146             /* Things should be stable, i.e., given equal keys, they should
 147              * show up in the list in order of insertion.  We insert them
 148              * in the order they are in in the array.
 149              */
 150             assert(prev == NULL || prev > n);
 151         }
 152
 153         prev = n;
 154         count++;
 155     }
 156     assert(count == expected_count);
 157 }
 158
 159 static void
 160 validate_search(struct rb_tree *tree, int first_number,
 161                 int last_number)
 162 {
 163     struct rb_node *n;
 164     struct rb_test_node *tn;
 165
 166     /* Search for all of the values */
 167     for (int i = first_number; i <= last_number; i++) {
 168         n = rb_tree_search(tree, &test_numbers[i], rb_test_node_cmp_void);
 169         tn = rb_node_data(struct rb_test_node, n, node);
 170         assert(tn->key == test_numbers[i]);
 171
 172         n = rb_tree_search_sloppy(tree, &test_numbers[i],
 173                                   rb_test_node_cmp_void);
 174         tn = rb_node_data(struct rb_test_node, n, node);
 175         assert(tn->key == test_numbers[i]);
 176     }
 177
 178     int missing_key = NON_EXISTANT_NUMBER;
 179     n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
 180     assert(n == NULL);
 181
 182     n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
 183     if (rb_tree_is_empty(tree)) {
 184         assert(n == NULL);
 185     } else {
 186         assert(n != NULL);
 187         tn = rb_node_data(struct rb_test_node, n, node);
 188         assert(tn->key != missing_key);
 189         if (tn->key < missing_key) {
 190             struct rb_node *next = rb_node_next(n);
 191             if (next != NULL) {
 192                 struct rb_test_node *tnext =
 193                     rb_node_data(struct rb_test_node, next, node);
 194                 assert(missing_key < tnext->key);
 195             }
 196         } else {
 197             struct rb_node *prev = rb_node_prev(n);
 198             if (prev != NULL) {
 199                 struct rb_test_node *tprev =
 200                     rb_node_data(struct rb_test_node, prev, node);
 201                 assert(missing_key > tprev->key);
 202             }
 203         }
 204     }
 205 }
 206
 207 int
 208 main()
 209 {
 210     struct rb_test_node nodes[ARRAY_SIZE(test_numbers)];
 211     struct rb_tree tree;
 212
 213     rb_tree_init(&tree);
 214
 215     for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
 216         nodes[i].key = test_numbers[i];
 217         rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
 218         rb_tree_validate(&tree);
 219         validate_tree_order(&tree, i + 1);
 220         validate_search(&tree, 0, i);
 221     }
 222
 223     for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
 224         rb_tree_remove(&tree, &nodes[i].node);
 225         rb_tree_validate(&tree);
 226         validate_tree_order(&tree, ARRAY_SIZE(test_numbers) - i - 1);
 227         validate_search(&tree, i + 1, ARRAY_SIZE(test_numbers) - 1);
 228     }
 229 }