1#include "structures/tests/test_internal.h"
2
3TEST_GROUP_DECLARE(radix);
4
5struct test_item {
6 uint64_t key;
7 uint64_t val;
8};
9
10static uint64_t test_item_key(const void *item) {
11 return ((const struct test_item *) item)->key;
12}
13
14TEST_DECLARE_UNIT(radix, insert_lookup_delete) {
15 struct radix_tree tree;
16 radix_tree_init(r: &tree, kfn: test_item_key, height: 2);
17
18 struct test_item items[6] = {
19 {.key = 0, .val = 100}, {.key = 1, .val = 101},
20 {.key = 63, .val = 163}, {.key = 64, .val = 164},
21 {.key = 4095, .val = 4095}, {.key = 250, .val = 1250},
22 };
23
24 for (size_t i = 0; i < 6; i++)
25 TEST_ASSERT_EQ(radix_insert(&tree, &items[i]), 0);
26
27 /* Duplicate insert must return ERR_EXIST without clobbering slots. */
28 struct test_item dup = {.key = 64, .val = 999};
29 TEST_ASSERT_EQ_S(radix_insert(&tree, &dup), ERR_EXIST);
30
31 for (size_t i = 0; i < 6; i++) {
32 struct test_item *found = radix_lookup(tree: &tree, key: items[i].key);
33 TEST_ASSERT_NONNULL(found);
34 TEST_ASSERT_EQ(found->val, items[i].val);
35 }
36
37 TEST_ASSERT_NULL(radix_lookup(&tree, 2));
38 TEST_ASSERT_NULL(radix_lookup(&tree, 65));
39
40 /* Deleting must return the original pointer */
41 for (size_t i = 0; i < 6; i++) {
42 struct test_item *del = radix_delete(tree: &tree, key: items[i].key);
43 TEST_ASSERT_PTR_EQ(del, &items[i]);
44 TEST_ASSERT_NULL(radix_lookup(&tree, items[i].key));
45 }
46
47 /* Prune up must free empty nodes and zero root when empty */
48 TEST_ASSERT_NULL(tree.root);
49
50 return TEST_SUCCESS;
51}
52
53TEST_DECLARE_UNIT(radix, multilevel_sparse) {
54 struct radix_tree tree;
55 radix_tree_init(r: &tree, kfn: test_item_key, height: 3);
56
57 struct test_item items[4] = {
58 {.key = 0, .val = 10},
59 {.key = 1000, .val = 20},
60 {.key = 50000, .val = 30},
61 {.key = 200000, .val = 40},
62 };
63
64 for (size_t i = 0; i < 4; i++)
65 TEST_ASSERT_EQ(radix_insert(&tree, &items[i]), 0);
66
67 for (size_t i = 0; i < 4; i++) {
68 struct test_item *found = radix_lookup(tree: &tree, key: items[i].key);
69 TEST_ASSERT_PTR_EQ(found, &items[i]);
70 }
71
72 for (size_t i = 0; i < 4; i++)
73 TEST_ASSERT_PTR_EQ(radix_delete(&tree, items[i].key), &items[i]);
74
75 TEST_ASSERT_NULL(tree.root);
76
77 return TEST_SUCCESS;
78}
79