1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
|
#include <uhub.h>
#include <util/rbtree.h>
#define MAX_NODES 10000
static struct rb_tree* tree = NULL;
int test_tree_compare(const void* a, const void* b)
{
return strcmp((const char*) a, (const char*) b);
}
EXO_TEST(rbtree_create_destroy, {
int ok = 0;
struct rb_tree* atree;
atree = rb_tree_create(test_tree_compare, &hub_malloc, &hub_free);
if (atree) ok = 1;
rb_tree_destroy(atree);
return ok;
});
EXO_TEST(rbtree_create_1, {
tree = rb_tree_create(test_tree_compare, &hub_malloc, &hub_free);
return tree != NULL;
});
EXO_TEST(rbtree_size_0, { return rb_tree_size(tree) == 0; });
EXO_TEST(rbtree_insert_1, {
return rb_tree_insert(tree, "one", "1");
});
EXO_TEST(rbtree_insert_2, {
return rb_tree_insert(tree, "two", "2");
});
EXO_TEST(rbtree_insert_3, {
return rb_tree_insert(tree, "three", "3");
});
EXO_TEST(rbtree_insert_3_again, {
return !rb_tree_insert(tree, "three", "3-again");
});
EXO_TEST(rbtree_size_1, { return rb_tree_size(tree) == 3; });
static int test_check_search(const char* key, const char* expect)
{
const char* value = (const char*) rb_tree_get(tree, key);
if (!value) return !expect;
if (!expect) return 0;
return strcmp(value, expect) == 0;
}
EXO_TEST(rbtree_search_1, { return test_check_search("one", "1"); });
EXO_TEST(rbtree_search_2, { return test_check_search("two", "2"); });
EXO_TEST(rbtree_search_3, { return test_check_search("three", "3"); });
EXO_TEST(rbtree_search_4, { return test_check_search("four", NULL); });
EXO_TEST(rbtree_remove_1, {
return rb_tree_remove(tree, "one");
});
EXO_TEST(rbtree_size_2, { return rb_tree_size(tree) == 2; });
EXO_TEST(rbtree_remove_2, {
return rb_tree_remove(tree, "two");
});
EXO_TEST(rbtree_remove_3, {
return rb_tree_remove(tree, "three");
});
EXO_TEST(rbtree_remove_3_again, {
return !rb_tree_remove(tree, "three");
});
EXO_TEST(rbtree_search_5, { return test_check_search("one", NULL); });
EXO_TEST(rbtree_search_6, { return test_check_search("two", NULL); });
EXO_TEST(rbtree_search_7, { return test_check_search("three", NULL); });
EXO_TEST(rbtree_search_8, { return test_check_search("four", NULL); });
EXO_TEST(rbtree_size_3, { return rb_tree_size(tree) == 0; });
EXO_TEST(rbtree_insert_10000, {
int i;
for (i = 0; i < MAX_NODES ; i++)
{
const char* key = strdup(uhub_itoa(i));
const char* val = strdup(uhub_itoa(i + 16384));
if (!rb_tree_insert(tree, key, val))
return 0;
}
return 1;
});
EXO_TEST(rbtree_size_4, { return rb_tree_size(tree) == MAX_NODES ; });
EXO_TEST(rbtree_check_10000, {
int i;
for (i = 0; i < MAX_NODES ; i++)
{
char* key = strdup(uhub_itoa(i));
const char* expect = uhub_itoa(i + 16384);
if (!test_check_search(key, expect))
return 0;
hub_free(key);
}
return 1;
});
EXO_TEST(rbtree_iterate_10000, {
int i = 0;
struct rb_node* n = (struct rb_node*) rb_tree_first(tree);
while (n)
{
struct rb_node* p = n;
n = (struct rb_node*) rb_tree_next(tree);
i++;
}
return i == MAX_NODES ;
});
static void free_node(struct rb_node* n)
{
hub_free((void*) n->key);
hub_free((void*) n->value);
}
EXO_TEST(rbtree_remove_5000, {
int i = 0;
struct rb_node* n = (struct rb_node*) rb_tree_first(tree);
for (i = 0; i < MAX_NODES ; i += 2)
{
const char* key = uhub_itoa(i);
rb_tree_remove_node(tree, key, &free_node);
}
return 1;
});
|