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 <gtest/gtest.h>
29#include <limits.h>
30
31/* A list of 100 random numbers from 1 to 100.  The number 30 is explicitly
32 * missing from this list.
33 */
34int test_numbers[] = {
35    26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
36    39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
37    10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
38    9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
39    32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
40    38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
41    31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
42    42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
43    32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
44    32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
45};
46
47#define NON_EXISTANT_NUMBER 30
48
49#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
50
51struct rb_test_node {
52    int key;
53    struct rb_node node;
54};
55
56static int
57rb_test_node_cmp_void(const struct rb_node *n, const void *v)
58{
59    struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
60    return *(int *)v - tn->key;
61}
62
63static int
64rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
65{
66    struct rb_test_node *ta = rb_node_data(struct rb_test_node, a, node);
67    struct rb_test_node *tb = rb_node_data(struct rb_test_node, b, node);
68
69    return tb->key - ta->key;
70}
71
72static void
73validate_tree_order(struct rb_tree *tree, unsigned expected_count)
74{
75    struct rb_test_node *prev = NULL;
76    int max_val = -1;
77    unsigned count = 0;
78    rb_tree_foreach(struct rb_test_node, n, tree, node) {
79        /* Everything should be in increasing order */
80        assert(n->key >= max_val);
81        if (n->key > max_val) {
82            max_val = n->key;
83        } else {
84            /* Things should be stable, i.e., given equal keys, they should
85             * show up in the list in order of insertion.  We insert them
86             * in the order they are in in the array.
87             */
88            assert(prev == NULL || prev < n);
89        }
90
91        prev = n;
92        count++;
93    }
94    assert(count == expected_count);
95
96    prev = NULL;
97    max_val = -1;
98    count = 0;
99    rb_tree_foreach_safe(struct rb_test_node, n, tree, node) {
100        /* Everything should be in increasing order */
101        assert(n->key >= max_val);
102        if (n->key > max_val) {
103            max_val = n->key;
104        } else {
105            /* Things should be stable, i.e., given equal keys, they should
106             * show up in the list in order of insertion.  We insert them
107             * in the order they are in in the array.
108             */
109            assert(prev == NULL || prev < n);
110        }
111
112        prev = n;
113        count++;
114    }
115    assert(count == expected_count);
116
117    prev = NULL;
118    int min_val = INT_MAX;
119    count = 0;
120    rb_tree_foreach_rev(struct rb_test_node, n, tree, node) {
121        /* Everything should be in increasing order */
122        assert(n->key <= min_val);
123        if (n->key < min_val) {
124            min_val = n->key;
125        } else {
126            /* Things should be stable, i.e., given equal keys, they should
127             * show up in the list in order of insertion.  We insert them
128             * in the order they are in in the array.
129             */
130            assert(prev == NULL || prev > n);
131        }
132
133        prev = n;
134        count++;
135    }
136    assert(count == expected_count);
137
138    prev = NULL;
139    min_val = INT_MAX;
140    count = 0;
141    rb_tree_foreach_rev_safe(struct rb_test_node, n, tree, node) {
142        /* Everything should be in increasing order */
143        assert(n->key <= min_val);
144        if (n->key < min_val) {
145            min_val = n->key;
146        } else {
147            /* Things should be stable, i.e., given equal keys, they should
148             * show up in the list in order of insertion.  We insert them
149             * in the order they are in in the array.
150             */
151            assert(prev == NULL || prev > n);
152        }
153
154        prev = n;
155        count++;
156    }
157    assert(count == expected_count);
158}
159
160static void
161validate_search(struct rb_tree *tree, int first_number,
162                int last_number)
163{
164    struct rb_node *n;
165    struct rb_test_node *tn;
166
167    /* Search for all of the values */
168    for (int i = first_number; i <= last_number; i++) {
169        n = rb_tree_search(tree, &test_numbers[i], rb_test_node_cmp_void);
170        tn = rb_node_data(struct rb_test_node, n, node);
171        assert(tn->key == test_numbers[i]);
172
173        n = rb_tree_search_sloppy(tree, &test_numbers[i],
174                                  rb_test_node_cmp_void);
175        tn = rb_node_data(struct rb_test_node, n, node);
176        assert(tn->key == test_numbers[i]);
177    }
178
179    int missing_key = NON_EXISTANT_NUMBER;
180    n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
181    assert(n == NULL);
182
183    n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
184    if (rb_tree_is_empty(tree)) {
185        assert(n == NULL);
186    } else {
187        assert(n != NULL);
188        tn = rb_node_data(struct rb_test_node, n, node);
189        assert(tn->key != missing_key);
190        if (tn->key < missing_key) {
191            struct rb_node *next = rb_node_next(n);
192            if (next != NULL) {
193                struct rb_test_node *tnext =
194                    rb_node_data(struct rb_test_node, next, node);
195                assert(missing_key < tnext->key);
196            }
197        } else {
198            struct rb_node *prev = rb_node_prev(n);
199            if (prev != NULL) {
200                struct rb_test_node *tprev =
201                    rb_node_data(struct rb_test_node, prev, node);
202                assert(missing_key > tprev->key);
203            }
204        }
205    }
206}
207
208TEST(RBTreeTest, InsertAndSearch)
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}
230