[thirdparty/systemd.git] / src / test / test-rbtree.c

/***
  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;
}
Commit	Line	Data
a0e4cae8 DH	1	/***
	2	This file is part of systemd. See COPYING for details.
	3
	4	systemd is free software; you can redistribute it and/or modify it
	5	under the terms of the GNU Lesser General Public License as published by
	6	the Free Software Foundation; either version 2.1 of the License, or
	7	(at your option) any later version.
	8
	9	systemd is distributed in the hope that it will be useful, but
	10	WITHOUT ANY WARRANTY; without even the implied warranty of
	11	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	12	Lesser General Public License for more details.
	13
	14	You should have received a copy of the GNU Lesser General Public License
	15	along with systemd; If not, see <http://www.gnu.org/licenses/>.
	16	***/
	17
	18	/*
	19	* Tests for RB-Tree
	20	*/
	21
	22	#undef NDEBUG
	23	#include <assert.h>
	24	#include <stddef.h>
	25	#include <stdlib.h>
	26	#include "c-rbtree.h"
	27
	28	/* verify that all API calls are exported */
	29	static void test_api(void) {
	30	CRBTree t = {};
	31	CRBNode n = C_RBNODE_INIT(n);
	32
	33	assert(!c_rbnode_is_linked(&n));
	34
	35	/* init, is_linked, add, remove, remove_init */
	36
	37	c_rbtree_add(&t, NULL, &t.root, &n);
	38	assert(c_rbnode_is_linked(&n));
	39
	40	c_rbtree_remove_init(&t, &n);
	41	assert(!c_rbnode_is_linked(&n));
	42
	43	c_rbtree_add(&t, NULL, &t.root, &n);
	44	assert(c_rbnode_is_linked(&n));
	45
	46	c_rbtree_remove(&t, &n);
	47	assert(c_rbnode_is_linked(&n)); /* @n wasn't touched */
	48
	49	c_rbnode_init(&n);
	50	assert(!c_rbnode_is_linked(&n));
	51
	52	/* first, last, leftmost, rightmost, next, prev */
	53
	54	assert(!c_rbtree_first(&t));
	55	assert(!c_rbtree_last(&t));
	56	assert(&n == c_rbnode_leftmost(&n));
	57	assert(&n == c_rbnode_rightmost(&n));
	58	assert(!c_rbnode_next(&n));
	59	assert(!c_rbnode_prev(&n));
	60	}
	61
	62	/* copied from c-rbtree.c, relies on internal representation */
	63	static inline _Bool c_rbnode_is_red(CRBNode *n) {
	64	return !((unsigned long)n->__parent_and_color & 1UL);
65	}
66
67	/* copied from c-rbtree.c, relies on internal representation */
68	static inline _Bool c_rbnode_is_black(CRBNode *n) {
69	return !!((unsigned long)n->__parent_and_color & 1UL);
70	}
71
72	static size_t validate(CRBTree *t) {
73	unsigned int i_black, n_black;
74	CRBNode n, p, *o;
75	size_t count = 0;
76
77	assert(t);
78	assert(!t->root \|\| c_rbnode_is_black(t->root));
79
80	/* traverse to left-most child, count black nodes */
81	i_black = 0;
82	n = t->root;
83	while (n && n->left) {
84	if (c_rbnode_is_black(n))
85	++i_black;
86	n = n->left;
87	}
88	n_black = i_black;
89
90	/*
91	* Traverse tree and verify correctness:
92	* 1) A node is either red or black
93	* 2) The root is black
94	* 3) All leaves are black
95	* 4) Every red node must have two black child nodes
96	* 5) Every path to a leaf contains the same number of black nodes
97	*
98	* Note that NULL nodes are considered black, which is why we don't
99	* check for 3).
100	*/
101	o = NULL;
102	while (n) {
103	++count;
104
105	/* verify natural order */
106	assert(n > o);
107	o = n;
108
109	/* verify consistency */
110	assert(!n->right \|\| c_rbnode_parent(n->right) == n);
111	assert(!n->left \|\| c_rbnode_parent(n->left) == n);
112
113	/* verify 2) */
114	if (!c_rbnode_parent(n))
115	assert(c_rbnode_is_black(n));
116
117	if (c_rbnode_is_red(n)) {
118	/* verify 4) */
119	assert(!n->left \|\| c_rbnode_is_black(n->left));
120	assert(!n->right \|\| c_rbnode_is_black(n->right));
121	} else {
122	/* verify 1) */
123	assert(c_rbnode_is_black(n));
124	}
125
126	/* verify 5) */
127	if (!n->left && !n->right)
128	assert(i_black == n_black);
129
130	/* get next node */
131	if (n->right) {
132	n = n->right;
133	if (c_rbnode_is_black(n))
134	++i_black;
135
136	while (n->left) {
137	n = n->left;
138	if (c_rbnode_is_black(n))
139	++i_black;
140	}
141	} else {
142	while ((p = c_rbnode_parent(n)) && n == p->right) {
143	n = p;
144	if (c_rbnode_is_black(p->right))
145	--i_black;
146	}
147
148	n = p;
149	if (p && c_rbnode_is_black(p->left))
150	--i_black;
151	}
152	}
153
154	return count;
155	}
156
157	static void insert(CRBTree t, CRBNode n) {
158	CRBNode *i, p;
159
160	assert(t);
161	assert(n);
162	assert(!c_rbnode_is_linked(n));
163
164	i = &t->root;
165	p = NULL;
166	while (*i) {
167	p = *i;
168	if (n < *i) {
169	i = &(*i)->left;
170	} else {
171	assert(n > *i);
172	i = &(*i)->right;
173	}
174	}
175
176	c_rbtree_add(t, p, i, n);
177	}
178
179	static void shuffle(void **nodes, size_t n_memb) {
180	unsigned int i, j;
181	void *t;
182
183	for (i = 0; i < n_memb; ++i) {
184	j = rand() % n_memb;
185	t = nodes[j];
186	nodes[j] = nodes[i];
187	nodes[i] = t;
188	}
189	}
190
191	/* run some pseudo-random tests on the tree */
192	static void test_shuffle(void) {
193	CRBNode *nodes[256];
194	CRBTree t = {};
195	unsigned int i, j;
196	size_t n;
197
198	/* allocate and initialize all nodes */
199	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
200	nodes[i] = malloc(sizeof(*nodes[i]));
201	assert(nodes[i]);
202	c_rbnode_init(nodes[i]);
203	}
204
205	/* shuffle nodes and validate empty tree */
206	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
207	n = validate(&t);
208	assert(n == 0);
209
210	/* add all nodes and validate after each insertion */
211	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
212	insert(&t, nodes[i]);
213	n = validate(&t);
214	assert(n == i + 1);
215	}
216
217	/* shuffle nodes again */
218	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
219
220	/* remove all nodes (in different order) and validate on each round */
221	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
222	c_rbtree_remove(&t, nodes[i]);
223	n = validate(&t);
224	assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
225	c_rbnode_init(nodes[i]);
226	}
227
228	/* shuffle nodes and validate empty tree again */
229	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
230	n = validate(&t);
231	assert(n == 0);
232
233	/* add all nodes again */
234	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
235	insert(&t, nodes[i]);
236	n = validate(&t);
237	assert(n == i + 1);
238	}
239
240	/* 4 times, remove half of the nodes and add them again */
241	for (j = 0; j < 4; ++j) {
242	/* shuffle nodes again */
243	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
244
245	/* remove half of the nodes */
246	for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
247	c_rbtree_remove(&t, nodes[i]);
248	n = validate(&t);
249	assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
250	c_rbnode_init(nodes[i]);
251	}
252
253	/* shuffle the removed half */
254	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes) / 2);
255
256	/* add the removed half again */
257	for (i = 0; i < sizeof(nodes) / sizeof(*nodes) / 2; ++i) {
258	insert(&t, nodes[i]);
259	n = validate(&t);
260	assert(n == sizeof(nodes) / sizeof(*nodes) / 2 + i + 1);
261	}
262	}
263
264	/* shuffle nodes again */
265	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
266
267	/* remove all */
268	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
269	c_rbtree_remove(&t, nodes[i]);
270	n = validate(&t);
271	assert(n == sizeof(nodes) / sizeof(*nodes) - i - 1);
272	c_rbnode_init(nodes[i]);
273	}
274
275	/* free nodes again */
276	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
277	free(nodes[i]);
278	}
279
280	typedef struct {
281	unsigned long key;
282	CRBNode rb;
283	} Node;
284
285	#define node_from_rb(_rb) ((Node )((char )(_rb) - offsetof(Node, rb)))
286
287	static int compare(CRBTree t, void k, CRBNode *n) {
288	unsigned long key = (unsigned long)k;
289	Node *node = node_from_rb(n);
290
291	return (key < node->key) ? -1 : (key > node->key) ? 1 : 0;
292	}
293
294	/* run tests against the c_rbtree_find() helpers /
295	static void test_map(void) {
296	CRBNode *slot, p;
297	CRBTree t = {};
298	Node *nodes[2048];
299	unsigned long i;
300
301	/* allocate and initialize all nodes */
302	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
303	nodes[i] = malloc(sizeof(*nodes[i]));
304	assert(nodes[i]);
305	nodes[i]->key = i;
306	c_rbnode_init(&nodes[i]->rb);
307	}
308
309	/* shuffle nodes */
310	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
311
312	/* add all nodes, and verify that each node is linked */
313	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
314	assert(!c_rbnode_is_linked(&nodes[i]->rb));
315	assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
316
317	slot = c_rbtree_find_slot(&t, compare, (void *)nodes[i]->key, &p);
318	assert(slot);
319	c_rbtree_add(&t, p, slot, &nodes[i]->rb);
320
321	assert(c_rbnode_is_linked(&nodes[i]->rb));
322	assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
323	}
324
325	/* shuffle nodes again */
326	shuffle((void *)nodes, sizeof(nodes) / sizeof(nodes));
327
328	/* remove all nodes (in different order) */
329	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i) {
330	assert(c_rbnode_is_linked(&nodes[i]->rb));
331	assert(nodes[i] == c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
332
333	c_rbtree_remove_init(&t, &nodes[i]->rb);
334
335	assert(!c_rbnode_is_linked(&nodes[i]->rb));
336	assert(!c_rbtree_find_entry(&t, compare, (void *)nodes[i]->key, Node, rb));
337	}
338
339	/* free nodes again */
340	for (i = 0; i < sizeof(nodes) / sizeof(*nodes); ++i)
341	free(nodes[i]);
342	}
343
344	int main(int argc, char **argv) {
345	unsigned int i;
346
347	/* we want stable tests, so use fixed seed */
348	srand(0xdeadbeef);
349
350	test_api();
351
352	/*
353	* The tests are pseudo random; run them multiple times, each run will
354	* have different orders and thus different results.
355	*/
356	for (i = 0; i < 4; ++i) {
357	test_shuffle();
358	test_map();
359	}
360
361	return 0;
362	}