freshlybakedca.ke
Git fork
1/*
2Copyright 2020 Google LLC
3
4Use of this source code is governed by a BSD-style
5license that can be found in the LICENSE file or at
6https://developers.google.com/open-source/licenses/bsd
7*/
8
9#include "unit-test.h"
10#include "reftable/tree.h"
11
12static int t_compare(const void *a, const void *b)
13{
14 return (char *)a - (char *)b;
15}
16
17struct curry {
18 void **arr;
19 size_t len;
20};
21
22static void store(void *arg, void *key)
23{
24 struct curry *c = arg;
25 c->arr[c->len++] = key;
26}
27
28void test_reftable_tree__tree_search(void)
29{
30 struct tree_node *root = NULL;
31 void *values[11] = { 0 };
32 struct tree_node *nodes[11] = { 0 };
33 size_t i = 1;
34
35 /*
36 * Pseudo-randomly insert the pointers for elements between
37 * values[1] and values[10] (inclusive) in the tree.
38 */
39 do {
40 nodes[i] = tree_insert(&root, &values[i], &t_compare);
41 cl_assert(nodes[i] != NULL);
42 i = (i * 7) % 11;
43 } while (i != 1);
44
45 for (i = 1; i < ARRAY_SIZE(nodes); i++) {
46 cl_assert_equal_p(&values[i], nodes[i]->key);
47 cl_assert_equal_p(nodes[i], tree_search(root, &values[i], &t_compare));
48 }
49
50 cl_assert(tree_search(root, values, t_compare) == NULL);
51 tree_free(root);
52}
53
54void test_reftable_tree__infix_walk(void)
55{
56 struct tree_node *root = NULL;
57 void *values[11] = { 0 };
58 void *out[11] = { 0 };
59 struct curry c = {
60 .arr = (void **) &out,
61 };
62 size_t i = 1;
63 size_t count = 0;
64
65 do {
66 struct tree_node *node = tree_insert(&root, &values[i], t_compare);
67 cl_assert(node != NULL);
68 i = (i * 7) % 11;
69 count++;
70 } while (i != 1);
71
72 infix_walk(root, &store, &c);
73 for (i = 1; i < ARRAY_SIZE(values); i++)
74 cl_assert_equal_p(&values[i], out[i - 1]);
75 cl_assert(out[i - 1] == NULL);
76 cl_assert_equal_i(c.len, count);
77 tree_free(root);
78}