src/test/test-rbtree.c

	test-rbtree.c revision a0e4cae82065edae47885614d73c534171aa8f7b
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen/***
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  This file is part of systemd. See COPYING for details.
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  systemd is free software; you can redistribute it and/or modify it
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  under the terms of the GNU Lesser General Public License as published by
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  the Free Software Foundation; either version 2.1 of the License, or
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  (at your option) any later version.
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  systemd is distributed in the hope that it will be useful, but
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  WITHOUT ANY WARRANTY; without even the implied warranty of
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  Lesser General Public License for more details.
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  You should have received a copy of the GNU Lesser General Public License
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen  along with systemd; If not, see <http://www.gnu.org/licenses/>.
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen***/
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen/*
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen * Tests for RB-Tree
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen#undef NDEBUG
2a73e0d39a9bec82c3800071e375d27164727e71Tom Gundersen#include <assert.h>
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen#include <stddef.h>
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen#include <stdlib.h>
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen#include "c-rbtree.h"
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
a501033335ed402c8f7e86fe41a15531ba69abd7Tom Gundersen/* verify that all API calls are exported */
a501033335ed402c8f7e86fe41a15531ba69abd7Tom Gundersenstatic void test_api(void) {
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen        CRBTree t = {};
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen        CRBNode n = C_RBNODE_INIT(n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(!c_rbnode_is_linked(&n));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* init, is_linked, add, remove, remove_init */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        c_rbtree_add(&t, NULL, &t.root, &n);
daeb71a36a98834664e4d95773a3629b746f4db8Tom Gundersen        assert(c_rbnode_is_linked(&n));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
3aeb37bc4f32b5edc334f2ac7c5d3c7b0a121328Tom Gundersen        c_rbtree_remove_init(&t, &n);
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen        assert(!c_rbnode_is_linked(&n));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        c_rbtree_add(&t, NULL, &t.root, &n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(c_rbnode_is_linked(&n));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        c_rbtree_remove(&t, &n);
a501033335ed402c8f7e86fe41a15531ba69abd7Tom Gundersen        assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */
a501033335ed402c8f7e86fe41a15531ba69abd7Tom Gundersen
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        c_rbnode_init(&n);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        assert(!c_rbnode_is_linked(&n));
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen        /* first, last, leftmost, rightmost, next, prev */
97f2d76d4f4dfab8b0629c09926a05a1e5621125Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(!c_rbtree_first(&t));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(!c_rbtree_last(&t));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        assert(&n == c_rbnode_leftmost(&n));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        assert(&n == c_rbnode_rightmost(&n));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        assert(!c_rbnode_next(&n));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        assert(!c_rbnode_prev(&n));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek}
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek/* copied from c-rbtree.c, relies on internal representation */
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmekstatic inline _Bool c_rbnode_is_red(CRBNode *n) {
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        return !((unsigned long)n->__parent_and_color & 1UL);
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen}
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen/* copied from c-rbtree.c, relies on internal representation */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersenstatic inline _Bool c_rbnode_is_black(CRBNode *n) {
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen        return !!((unsigned long)n->__parent_and_color & 1UL);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen}
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersenstatic size_t validate(CRBTree *t) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        unsigned int i_black, n_black;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        CRBNode *n, *p, *o;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        size_t count = 0;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(!t->root || c_rbnode_is_black(t->root));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
977085794d2996320e345433403de75f662b0622Tom Gundersen        /* traverse to left-most child, count black nodes */
977085794d2996320e345433403de75f662b0622Tom Gundersen        i_black = 0;
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        n = t->root;
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        while (n && n->left) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                if (c_rbnode_is_black(n))
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen                        ++i_black;
5b9d4dc05560ddda89e48b6b39365824b15e1300Tom Gundersen                n = n->left;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        n_black = i_black;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
977085794d2996320e345433403de75f662b0622Tom Gundersen        /*
977085794d2996320e345433403de75f662b0622Tom Gundersen         * Traverse tree and verify correctness:
977085794d2996320e345433403de75f662b0622Tom Gundersen         *  1) A node is either red or black
977085794d2996320e345433403de75f662b0622Tom Gundersen         *  2) The root is black
977085794d2996320e345433403de75f662b0622Tom Gundersen         *  3) All leaves are black
977085794d2996320e345433403de75f662b0622Tom Gundersen         *  4) Every red node must have two black child nodes
977085794d2996320e345433403de75f662b0622Tom Gundersen         *  5) Every path to a leaf contains the same number of black nodes
977085794d2996320e345433403de75f662b0622Tom Gundersen         *
977085794d2996320e345433403de75f662b0622Tom Gundersen         * Note that NULL nodes are considered black, which is why we don't
977085794d2996320e345433403de75f662b0622Tom Gundersen         * check for 3).
977085794d2996320e345433403de75f662b0622Tom Gundersen         */
977085794d2996320e345433403de75f662b0622Tom Gundersen        o = NULL;
977085794d2996320e345433403de75f662b0622Tom Gundersen        while (n) {
977085794d2996320e345433403de75f662b0622Tom Gundersen                ++count;
977085794d2996320e345433403de75f662b0622Tom Gundersen
977085794d2996320e345433403de75f662b0622Tom Gundersen                /* verify natural order */
977085794d2996320e345433403de75f662b0622Tom Gundersen                assert(n > o);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                o = n;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                /* verify consistency */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                assert(!n->right || c_rbnode_parent(n->right) == n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                assert(!n->left || c_rbnode_parent(n->left) == n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                /* verify 2) */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                if (!c_rbnode_parent(n))
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(c_rbnode_is_black(n));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                if (c_rbnode_is_red(n)) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        /* verify 4) */
d2df0d0ed3a88e491405b403e6022e6619750130Tom Gundersen                        assert(!n->left || c_rbnode_is_black(n->left));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(!n->right || c_rbnode_is_black(n->right));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                } else {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        /* verify 1) */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(c_rbnode_is_black(n));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                /* verify 5) */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                if (!n->left && !n->right)
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(i_black == n_black);
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen                /* get next node */
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen                if (n->right) {
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen                        n = n->right;
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen                        if (c_rbnode_is_black(n))
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                ++i_black;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        while (n->left) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                n = n->left;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                if (c_rbnode_is_black(n))
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                        ++i_black;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                } else {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        while ((p = c_rbnode_parent(n)) && n == p->right) {
2fd069b18e525860514a70d3ea08410ca122d3e2Zbigniew Jędrzejewski-Szmek                                n = p;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                if (c_rbnode_is_black(p->right))
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                        --i_black;
187dc6e554f2d5b4b5a3bee72c73ff5df6418aa6Thomas Hindoe Paaboel Andersen                        }
187dc6e554f2d5b4b5a3bee72c73ff5df6418aa6Thomas Hindoe Paaboel Andersen
187dc6e554f2d5b4b5a3bee72c73ff5df6418aa6Thomas Hindoe Paaboel Andersen                        n = p;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        if (p && c_rbnode_is_black(p->left))
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                                --i_black;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        return count;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen}
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersenstatic void insert(CRBTree *t, CRBNode *n) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        CRBNode **i, *p;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(!c_rbnode_is_linked(n));
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        i = &t->root;
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        p = NULL;
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        while (*i) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                p = *i;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                if (n < *i) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        i = &(*i)->left;
489124365d1d391864898b9869dd668eea5b2e28Dave Reisner                } else {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(n > *i);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        i = &(*i)->right;
98a375f6d5cac24eb80d6d4e00699851324afdecTom Gundersen                }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        c_rbtree_add(t, p, i, n);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen}
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersenstatic void shuffle(void **nodes, size_t n_memb) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        unsigned int i, j;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        void *t;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        for (i = 0; i < n_memb; ++i) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                j = rand() % n_memb;
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                t = nodes[j];
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                nodes[j] = nodes[i];
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                nodes[i] = t;
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        }
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen}
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen/* run some pseudo-random tests on the tree */
74df0fca09b3c31ed19e14ba80f996fdff772417Lennart Poetteringstatic void test_shuffle(void) {
74df0fca09b3c31ed19e14ba80f996fdff772417Lennart Poettering        CRBNode *nodes[256];
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        CRBTree t = {};
74df0fca09b3c31ed19e14ba80f996fdff772417Lennart Poettering        unsigned int i, j;
74df0fca09b3c31ed19e14ba80f996fdff772417Lennart Poettering        size_t n;
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        /* allocate and initialize all nodes */
ff83aac3647e21f31ac5e2b575ec1285dc585f6bTom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                nodes[i] = malloc(sizeof(*nodes[i]));
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                assert(nodes[i]);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                c_rbnode_init(nodes[i]);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        }
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* shuffle nodes and validate *empty* tree */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        n = validate(&t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(n == 0);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* add all nodes and validate after each insertion */
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                insert(&t, nodes[i]);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                n = validate(&t);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen                assert(n == i + 1);
f61942250a43a123580d7bbe5d7873dc5118ed97Tom Gundersen        }
97f2d76d4f4dfab8b0629c09926a05a1e5621125Tom Gundersen
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek        /* shuffle nodes again */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* remove all nodes (in different order) and validate on each round */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                c_rbtree_remove(&t, nodes[i]);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                n = validate(&t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                c_rbnode_init(nodes[i]);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* shuffle nodes and validate *empty* tree again */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        n = validate(&t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        assert(n == 0);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* add all nodes again */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
2ad8416dd057e7e3185169609ca3006e7649f576Zbigniew Jędrzejewski-Szmek                insert(&t, nodes[i]);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                n = validate(&t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                assert(n == i + 1);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        /* 4 times, remove half of the nodes and add them again */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        for (j = 0; j < 4; ++j) {
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                /* shuffle nodes again */
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen                shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                /* remove half of the nodes */
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                        c_rbtree_remove(&t, nodes[i]);
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                        n = validate(&t);
b3e013148603aa670bc2c060ac63d48e54d76fc2Tom Gundersen                        assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen                        c_rbnode_init(nodes[i]);
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen                }
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                /* shuffle the removed half */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes) / 2);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                /* add the removed half again */
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen                        insert(&t, nodes[i]);
be32eb9b7fbcb22e4b648086d644135e38279633Tom Gundersen                        n = validate(&t);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                        assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen                }
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen        }
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* shuffle nodes again */
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* remove all */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                c_rbtree_remove(&t, nodes[i]);
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen                n = validate(&t);
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen                assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen                c_rbnode_init(nodes[i]);
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        }
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* free nodes again */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                free(nodes[i]);
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen}
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersentypedef struct {
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        unsigned long key;
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        CRBNode rb;
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen} Node;
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen#define node_from_rb(_rb) ((Node *)((char *)(_rb) - offsetof(Node, rb)))
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersenstatic int compare(CRBTree *t, void *k, CRBNode *n) {
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        unsigned long key = (unsigned long)k;
f1ac700248f231b7bdac2aafe8c35650efddb89fTom Gundersen        Node *node = node_from_rb(n);
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        return (key < node->key) ? -1 : (key > node->key) ? 1 : 0;
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen}
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen/* run tests against the c_rbtree_find*() helpers */
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poetteringstatic void test_map(void) {
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering        CRBNode **slot, *p;
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        CRBTree t = {};
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering        Node *nodes[2048];
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        unsigned long i;
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering        /* allocate and initialize all nodes */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                nodes[i] = malloc(sizeof(*nodes[i]));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(nodes[i]);
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                nodes[i]->key = i;
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                c_rbnode_init(&nodes[i]->rb);
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        }
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* shuffle nodes */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* add all nodes, and verify that each node is linked */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                assert(!c_rbnode_is_linked(&nodes[i]->rb));
55428d84f31b52da1c50b7469f14e15740547f20Tom Gundersen                assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p);
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(slot);
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                c_rbtree_add(&t, p, slot, &nodes[i]->rb);
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(c_rbnode_is_linked(&nodes[i]->rb));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        }
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* shuffle nodes again */
55428d84f31b52da1c50b7469f14e15740547f20Tom Gundersen        shuffle((void **)nodes, sizeof(nodes) / sizeof(*nodes));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* remove all nodes (in different order) */
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(c_rbnode_is_linked(&nodes[i]->rb));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                c_rbtree_remove_init(&t, &nodes[i]->rb);
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering
9bf3b53533cdc9b95c921b71da755401f223f765Lennart Poettering                assert(!c_rbnode_is_linked(&nodes[i]->rb));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        }
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        /* free nodes again */
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen        for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen                free(nodes[i]);
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen}
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersenint main(int argc, char **argv) {
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen        unsigned int i;
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        /* we want stable tests, so use fixed seed */
5fde13d748749f0e06e2e6cdd15f0980a79ea82cTom Gundersen        srand(0xdeadbeef);
16b9b87aeee9353b5b8dae6089a69752422a5b09Tom Gundersen
43b3a5ef61859f06cdbaf26765cab8e1adac4296Tom Gundersen        test_api();
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen        /*
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen         * The tests are pseudo random; run them multiple times, each run will
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen         * have different orders and thus different results.
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen         */
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen        for (i = 0; i < 4; ++i) {
977085794d2996320e345433403de75f662b0622Tom Gundersen                test_shuffle();
977085794d2996320e345433403de75f662b0622Tom Gundersen                test_map();
977085794d2996320e345433403de75f662b0622Tom Gundersen        }
977085794d2996320e345433403de75f662b0622Tom Gundersen
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen        return 0;
3e137a1b9a0eac2bf43d493d3302c3c959b6ccdbTom Gundersen}
af6f0d422c521374ee6a2dd92df5935a5a476ae5Tom Gundersen