diff options
author | Lennart Poettering <lennart@poettering.net> | 2016-04-07 19:22:24 +0200 |
---|---|---|
committer | Lennart Poettering <lennart@poettering.net> | 2016-04-12 13:43:32 +0200 |
commit | 4c310c073aec5a31a7e626ea8ceb86d3a28291aa (patch) | |
tree | 2042b0dcbec90df52ce5e39f4c3dc46d76698b6a /src/test/test-rbtree.c | |
parent | 5ae87056e3dc1162c2088daf0cb5affb0480ae54 (diff) |
basic: remove rbtree code, it's unused
it's unused, and should we need it one day we can always resurrect it from git
history.
Diffstat (limited to 'src/test/test-rbtree.c')
-rw-r--r-- | src/test/test-rbtree.c | 362 |
1 files changed, 0 insertions, 362 deletions
diff --git a/src/test/test-rbtree.c b/src/test/test-rbtree.c deleted file mode 100644 index 8ae416c557..0000000000 --- a/src/test/test-rbtree.c +++ /dev/null @@ -1,362 +0,0 @@ -/*** - This file is part of systemd. See COPYING for details. - - systemd is free software; you can redistribute it and/or modify it - under the terms of the GNU Lesser General Public License as published by - the Free Software Foundation; either version 2.1 of the License, or - (at your option) any later version. - - systemd is distributed in the hope that it will be useful, but - WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public License - along with systemd; If not, see <http://www.gnu.org/licenses/>. -***/ - -/* - * Tests for RB-Tree - */ - -#undef NDEBUG -#include <assert.h> -#include <stddef.h> -#include <stdlib.h> -#include "c-rbtree.h" - -/* verify that all API calls are exported */ -static void test_api(void) { - CRBTree t = {}; - CRBNode n = C_RBNODE_INIT(n); - - assert(!c_rbnode_is_linked(&n)); - - /* init, is_linked, add, remove, remove_init */ - - c_rbtree_add(&t, NULL, &t.root, &n); - assert(c_rbnode_is_linked(&n)); - - c_rbtree_remove_init(&t, &n); - assert(!c_rbnode_is_linked(&n)); - - c_rbtree_add(&t, NULL, &t.root, &n); - assert(c_rbnode_is_linked(&n)); - - c_rbtree_remove(&t, &n); - assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */ - - c_rbnode_init(&n); - assert(!c_rbnode_is_linked(&n)); - - /* first, last, leftmost, rightmost, next, prev */ - - assert(!c_rbtree_first(&t)); - assert(!c_rbtree_last(&t)); - assert(&n == c_rbnode_leftmost(&n)); - assert(&n == c_rbnode_rightmost(&n)); - assert(!c_rbnode_next(&n)); - assert(!c_rbnode_prev(&n)); -} - -/* copied from c-rbtree.c, relies on internal representation */ -static inline _Bool c_rbnode_is_red(CRBNode *n) { - return !((unsigned long)n->__parent_and_color & 1UL); -} - -/* copied from c-rbtree.c, relies on internal representation */ -static inline _Bool c_rbnode_is_black(CRBNode *n) { - return !!((unsigned long)n->__parent_and_color & 1UL); -} - -static size_t validate(CRBTree *t) { - unsigned int i_black, n_black; - CRBNode *n, *p, *o; - size_t count = 0; - - assert(t); - assert(!t->root || c_rbnode_is_black(t->root)); - - /* traverse to left-most child, count black nodes */ - i_black = 0; - n = t->root; - while (n && n->left) { - if (c_rbnode_is_black(n)) - ++i_black; - n = n->left; - } - n_black = i_black; - - /* - * Traverse tree and verify correctness: - * 1) A node is either red or black - * 2) The root is black - * 3) All leaves are black - * 4) Every red node must have two black child nodes - * 5) Every path to a leaf contains the same number of black nodes - * - * Note that NULL nodes are considered black, which is why we don't - * check for 3). - */ - o = NULL; - while (n) { - ++count; - - /* verify natural order */ - assert(n > o); - o = n; - - /* verify consistency */ - assert(!n->right || c_rbnode_parent(n->right) == n); - assert(!n->left || c_rbnode_parent(n->left) == n); - - /* verify 2) */ - if (!c_rbnode_parent(n)) - assert(c_rbnode_is_black(n)); - - if (c_rbnode_is_red(n)) { - /* verify 4) */ - assert(!n->left || c_rbnode_is_black(n->left)); - assert(!n->right || c_rbnode_is_black(n->right)); - } else { - /* verify 1) */ - assert(c_rbnode_is_black(n)); - } - - /* verify 5) */ - if (!n->left && !n->right) - assert(i_black == n_black); - - /* get next node */ - if (n->right) { - n = n->right; - if (c_rbnode_is_black(n)) - ++i_black; - - while (n->left) { - n = n->left; - if (c_rbnode_is_black(n)) - ++i_black; - } - } else { - while ((p = c_rbnode_parent(n)) && n == p->right) { - n = p; - if (c_rbnode_is_black(p->right)) - --i_black; - } - - n = p; - if (p && c_rbnode_is_black(p->left)) - --i_black; - } - } - - return count; -} - -static void insert(CRBTree *t, CRBNode *n) { - CRBNode **i, *p; - - assert(t); - assert(n); - assert(!c_rbnode_is_linked(n)); - - i = &t->root; - p = NULL; - while (*i) { - p = *i; - if (n < *i) { - i = &(*i)->left; - } else { - assert(n > *i); - i = &(*i)->right; - } - } - - c_rbtree_add(t, p, i, n); -} - -static void shuffle(void **nodes, size_t n_memb) { - unsigned int i, j; - void *t; - - for (i = 0; i < n_memb; ++i) { - j = rand() % n_memb; - t = nodes[j]; - nodes[j] = nodes[i]; - nodes[i] = t; - } -} - -/* run some pseudo-random tests on the tree */ -static void test_shuffle(void) { - CRBNode *nodes[256]; - CRBTree t = {}; - unsigned int i, j; - size_t n; - - /* allocate and initialize all nodes */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - nodes[i] = malloc(sizeof(*nodes[i])); - assert(nodes[i]); - c_rbnode_init(nodes[i]); - } - - /* shuffle nodes and validate *empty* tree */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - n = validate(&t); - assert(n == 0); - - /* add all nodes and validate after each insertion */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - insert(&t, nodes[i]); - n = validate(&t); - assert(n == i + 1); - } - - /* shuffle nodes again */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - - /* remove all nodes (in different order) and validate on each round */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - c_rbtree_remove(&t, nodes[i]); - n = validate(&t); - assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); - c_rbnode_init(nodes[i]); - } - - /* shuffle nodes and validate *empty* tree again */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - n = validate(&t); - assert(n == 0); - - /* add all nodes again */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - insert(&t, nodes[i]); - n = validate(&t); - assert(n == i + 1); - } - - /* 4 times, remove half of the nodes and add them again */ - for (j = 0; j < 4; ++j) { - /* shuffle nodes again */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - - /* remove half of the nodes */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) { - c_rbtree_remove(&t, nodes[i]); - n = validate(&t); - assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); - c_rbnode_init(nodes[i]); - } - - /* shuffle the removed half */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes) / 2); - - /* add the removed half again */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) { - insert(&t, nodes[i]); - n = validate(&t); - assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1); - } - } - - /* shuffle nodes again */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - - /* remove all */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - c_rbtree_remove(&t, nodes[i]); - n = validate(&t); - assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1); - c_rbnode_init(nodes[i]); - } - - /* free nodes again */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) - free(nodes[i]); -} - -typedef struct { - unsigned long key; - CRBNode rb; -} Node; - -#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb))) - -static int compare(CRBTree *t, void *k, CRBNode *n) { - unsigned long key = (unsigned long)k; - Node *node = node_from_rb(n); - - return (key < node->key) ? -1 : (key > node->key) ? 1 : 0; -} - -/* run tests against the c_rbtree_find*() helpers */ -static void test_map(void) { - CRBNode **slot, *p; - CRBTree t = {}; - Node *nodes[2048]; - unsigned long i; - - /* allocate and initialize all nodes */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - nodes[i] = malloc(sizeof(*nodes[i])); - assert(nodes[i]); - nodes[i]->key = i; - c_rbnode_init(&nodes[i]->rb); - } - - /* shuffle nodes */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - - /* add all nodes, and verify that each node is linked */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - assert(!c_rbnode_is_linked(&nodes[i]->rb)); - assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb)); - - slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p); - assert(slot); - c_rbtree_add(&t, p, slot, &nodes[i]->rb); - - assert(c_rbnode_is_linked(&nodes[i]->rb)); - assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb)); - } - - /* shuffle nodes again */ - shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes)); - - /* remove all nodes (in different order) */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) { - assert(c_rbnode_is_linked(&nodes[i]->rb)); - assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb)); - - c_rbtree_remove_init(&t, &nodes[i]->rb); - - assert(!c_rbnode_is_linked(&nodes[i]->rb)); - assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb)); - } - - /* free nodes again */ - for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) - free(nodes[i]); -} - -int main(int argc, char **argv) { - unsigned int i; - - /* we want stable tests, so use fixed seed */ - srand(0xdeadbeef); - - test_api(); - - /* - * The tests are pseudo random; run them multiple times, each run will - * have different orders and thus different results. - */ - for (i = 0; i < 4; ++i) { - test_shuffle(); - test_map(); - } - - return 0; -} |