230 lines
7.3 KiB
C++
230 lines
7.3 KiB
C++
/*
|
|
* Copyright © 2017 Jason Ekstrand
|
|
*
|
|
* Permission is hereby granted, free of charge, to any person obtaining a
|
|
* copy of this software and associated documentation files (the "Software"),
|
|
* to deal in the Software without restriction, including without limitation
|
|
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
|
|
* and/or sell copies of the Software, and to permit persons to whom the
|
|
* Software is furnished to do so, subject to the following conditions:
|
|
*
|
|
* The above copyright notice and this permission notice shall be included in
|
|
* all copies or substantial portions of the Software.
|
|
*
|
|
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
|
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
|
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
|
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
|
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
|
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
|
|
* DEALINGS IN THE SOFTWARE.
|
|
*/
|
|
|
|
#undef NDEBUG
|
|
|
|
#include "rb_tree.h"
|
|
|
|
#include <assert.h>
|
|
#include <gtest/gtest.h>
|
|
#include <limits.h>
|
|
|
|
/* A list of 100 random numbers from 1 to 100. The number 30 is explicitly
|
|
* missing from this list.
|
|
*/
|
|
int test_numbers[] = {
|
|
26, 12, 35, 15, 48, 11, 39, 23, 40, 18,
|
|
39, 15, 40, 11, 42, 2, 5, 2, 28, 8,
|
|
10, 22, 23, 38, 47, 12, 31, 22, 26, 39,
|
|
9, 42, 32, 18, 36, 8, 32, 29, 9, 3,
|
|
32, 49, 23, 11, 43, 41, 22, 42, 6, 35,
|
|
38, 48, 5, 35, 39, 44, 22, 16, 16, 32,
|
|
31, 50, 48, 5, 50, 8, 2, 32, 27, 34,
|
|
42, 48, 22, 47, 10, 48, 39, 36, 28, 40,
|
|
32, 33, 21, 17, 14, 38, 27, 6, 25, 18,
|
|
32, 38, 19, 22, 20, 47, 50, 41, 29, 50,
|
|
};
|
|
|
|
#define NON_EXISTANT_NUMBER 30
|
|
|
|
#define ARRAY_SIZE(a) (sizeof(a) / sizeof(*a))
|
|
|
|
struct rb_test_node {
|
|
int key;
|
|
struct rb_node node;
|
|
};
|
|
|
|
static int
|
|
rb_test_node_cmp_void(const struct rb_node *n, const void *v)
|
|
{
|
|
struct rb_test_node *tn = rb_node_data(struct rb_test_node, n, node);
|
|
return *(int *)v - tn->key;
|
|
}
|
|
|
|
static int
|
|
rb_test_node_cmp(const struct rb_node *a, const struct rb_node *b)
|
|
{
|
|
struct rb_test_node *ta = rb_node_data(struct rb_test_node, a, node);
|
|
struct rb_test_node *tb = rb_node_data(struct rb_test_node, b, node);
|
|
|
|
return tb->key - ta->key;
|
|
}
|
|
|
|
static void
|
|
validate_tree_order(struct rb_tree *tree, unsigned expected_count)
|
|
{
|
|
struct rb_test_node *prev = NULL;
|
|
int max_val = -1;
|
|
unsigned count = 0;
|
|
rb_tree_foreach(struct rb_test_node, n, tree, node) {
|
|
/* Everything should be in increasing order */
|
|
assert(n->key >= max_val);
|
|
if (n->key > max_val) {
|
|
max_val = n->key;
|
|
} else {
|
|
/* Things should be stable, i.e., given equal keys, they should
|
|
* show up in the list in order of insertion. We insert them
|
|
* in the order they are in in the array.
|
|
*/
|
|
assert(prev == NULL || prev < n);
|
|
}
|
|
|
|
prev = n;
|
|
count++;
|
|
}
|
|
assert(count == expected_count);
|
|
|
|
prev = NULL;
|
|
max_val = -1;
|
|
count = 0;
|
|
rb_tree_foreach_safe(struct rb_test_node, n, tree, node) {
|
|
/* Everything should be in increasing order */
|
|
assert(n->key >= max_val);
|
|
if (n->key > max_val) {
|
|
max_val = n->key;
|
|
} else {
|
|
/* Things should be stable, i.e., given equal keys, they should
|
|
* show up in the list in order of insertion. We insert them
|
|
* in the order they are in in the array.
|
|
*/
|
|
assert(prev == NULL || prev < n);
|
|
}
|
|
|
|
prev = n;
|
|
count++;
|
|
}
|
|
assert(count == expected_count);
|
|
|
|
prev = NULL;
|
|
int min_val = INT_MAX;
|
|
count = 0;
|
|
rb_tree_foreach_rev(struct rb_test_node, n, tree, node) {
|
|
/* Everything should be in increasing order */
|
|
assert(n->key <= min_val);
|
|
if (n->key < min_val) {
|
|
min_val = n->key;
|
|
} else {
|
|
/* Things should be stable, i.e., given equal keys, they should
|
|
* show up in the list in order of insertion. We insert them
|
|
* in the order they are in in the array.
|
|
*/
|
|
assert(prev == NULL || prev > n);
|
|
}
|
|
|
|
prev = n;
|
|
count++;
|
|
}
|
|
assert(count == expected_count);
|
|
|
|
prev = NULL;
|
|
min_val = INT_MAX;
|
|
count = 0;
|
|
rb_tree_foreach_rev_safe(struct rb_test_node, n, tree, node) {
|
|
/* Everything should be in increasing order */
|
|
assert(n->key <= min_val);
|
|
if (n->key < min_val) {
|
|
min_val = n->key;
|
|
} else {
|
|
/* Things should be stable, i.e., given equal keys, they should
|
|
* show up in the list in order of insertion. We insert them
|
|
* in the order they are in in the array.
|
|
*/
|
|
assert(prev == NULL || prev > n);
|
|
}
|
|
|
|
prev = n;
|
|
count++;
|
|
}
|
|
assert(count == expected_count);
|
|
}
|
|
|
|
static void
|
|
validate_search(struct rb_tree *tree, int first_number,
|
|
int last_number)
|
|
{
|
|
struct rb_node *n;
|
|
struct rb_test_node *tn;
|
|
|
|
/* Search for all of the values */
|
|
for (int i = first_number; i <= last_number; i++) {
|
|
n = rb_tree_search(tree, &test_numbers[i], rb_test_node_cmp_void);
|
|
tn = rb_node_data(struct rb_test_node, n, node);
|
|
assert(tn->key == test_numbers[i]);
|
|
|
|
n = rb_tree_search_sloppy(tree, &test_numbers[i],
|
|
rb_test_node_cmp_void);
|
|
tn = rb_node_data(struct rb_test_node, n, node);
|
|
assert(tn->key == test_numbers[i]);
|
|
}
|
|
|
|
int missing_key = NON_EXISTANT_NUMBER;
|
|
n = rb_tree_search(tree, &missing_key, rb_test_node_cmp_void);
|
|
assert(n == NULL);
|
|
|
|
n = rb_tree_search_sloppy(tree, &missing_key, rb_test_node_cmp_void);
|
|
if (rb_tree_is_empty(tree)) {
|
|
assert(n == NULL);
|
|
} else {
|
|
assert(n != NULL);
|
|
tn = rb_node_data(struct rb_test_node, n, node);
|
|
assert(tn->key != missing_key);
|
|
if (tn->key < missing_key) {
|
|
struct rb_node *next = rb_node_next(n);
|
|
if (next != NULL) {
|
|
struct rb_test_node *tnext =
|
|
rb_node_data(struct rb_test_node, next, node);
|
|
assert(missing_key < tnext->key);
|
|
}
|
|
} else {
|
|
struct rb_node *prev = rb_node_prev(n);
|
|
if (prev != NULL) {
|
|
struct rb_test_node *tprev =
|
|
rb_node_data(struct rb_test_node, prev, node);
|
|
assert(missing_key > tprev->key);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
TEST(RBTreeTest, InsertAndSearch)
|
|
{
|
|
struct rb_test_node nodes[ARRAY_SIZE(test_numbers)];
|
|
struct rb_tree tree;
|
|
|
|
rb_tree_init(&tree);
|
|
|
|
for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
|
|
nodes[i].key = test_numbers[i];
|
|
rb_tree_insert(&tree, &nodes[i].node, rb_test_node_cmp);
|
|
rb_tree_validate(&tree);
|
|
validate_tree_order(&tree, i + 1);
|
|
validate_search(&tree, 0, i);
|
|
}
|
|
|
|
for (unsigned i = 0; i < ARRAY_SIZE(test_numbers); i++) {
|
|
rb_tree_remove(&tree, &nodes[i].node);
|
|
rb_tree_validate(&tree);
|
|
validate_tree_order(&tree, ARRAY_SIZE(test_numbers) - i - 1);
|
|
validate_search(&tree, i + 1, ARRAY_SIZE(test_numbers) - 1);
|
|
}
|
|
}
|