Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 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); |
Jason Ekstrand | dae3305 | 2019-09-19 15:17:24 -0500 | [diff] [blame] | 59 | return *(int *)v - tn->key; |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 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 | |
Jason Ekstrand | dae3305 | 2019-09-19 15:17:24 -0500 | [diff] [blame] | 68 | return tb->key - ta->key; |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 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 | */ |
Jason Ekstrand | 0391119 | 2019-09-23 12:24:12 -0500 | [diff] [blame] | 87 | assert(prev == NULL || prev < n); |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 88 | } |
| 89 | |
| 90 | prev = n; |
| 91 | count++; |
| 92 | } |
| 93 | assert(count == expected_count); |
| 94 | |
| 95 | prev = NULL; |
Jason Ekstrand | f18aad6 | 2019-09-25 10:01:27 -0500 | [diff] [blame] | 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; |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 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 | */ |
Jason Ekstrand | 0391119 | 2019-09-23 12:24:12 -0500 | [diff] [blame] | 129 | assert(prev == NULL || prev > n); |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 130 | } |
| 131 | |
| 132 | prev = n; |
| 133 | count++; |
| 134 | } |
| 135 | assert(count == expected_count); |
Jason Ekstrand | f18aad6 | 2019-09-25 10:01:27 -0500 | [diff] [blame] | 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); |
Jason Ekstrand | d35d734 | 2019-09-19 15:05:51 -0500 | [diff] [blame] | 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 | } |