| 1 | /* |
| 2 | Copyright 2020 Google LLC |
| 3 | |
| 4 | Use of this source code is governed by a BSD-style |
| 5 | license that can be found in the LICENSE file or at |
| 6 | https://developers.google.com/open-source/licenses/bsd |
| 7 | */ |
| 8 | |
| 9 | #include "unit-test.h" |
| 10 | #include "reftable/tree.h" |
| 11 | |
| 12 | static int t_compare(const void *a, const void *b) |
| 13 | { |
| 14 | return (char *)a - (char *)b; |
| 15 | } |
| 16 | |
| 17 | struct curry { |
| 18 | void **arr; |
| 19 | size_t len; |
| 20 | }; |
| 21 | |
| 22 | static void store(void *arg, void *key) |
| 23 | { |
| 24 | struct curry *c = arg; |
| 25 | c->arr[c->len++] = key; |
| 26 | } |
| 27 | |
| 28 | void 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 | |
| 54 | void 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 | } |