xref: /minix3/tests/include/sys/t_tree.c (revision 11be35a165022172ed3cea20f2b5df0307540b0e)
1*11be35a1SLionel Sambuc /* $NetBSD: t_tree.c,v 1.1 2011/05/05 13:36:05 jruoho Exp $ */
2*11be35a1SLionel Sambuc 
3*11be35a1SLionel Sambuc /*-
4*11be35a1SLionel Sambuc  * Copyright (c) 2010, 2011 The NetBSD Foundation, Inc.
5*11be35a1SLionel Sambuc  * All rights reserved.
6*11be35a1SLionel Sambuc  *
7*11be35a1SLionel Sambuc  * Redistribution and use in source and binary forms, with or without
8*11be35a1SLionel Sambuc  * modification, are permitted provided that the following conditions
9*11be35a1SLionel Sambuc  * are met:
10*11be35a1SLionel Sambuc  * 1. Redistributions of source code must retain the above copyright
11*11be35a1SLionel Sambuc  *    notice, this list of conditions and the following disclaimer.
12*11be35a1SLionel Sambuc  * 2. Redistributions in binary form must reproduce the above copyright
13*11be35a1SLionel Sambuc  *    notice, this list of conditions and the following disclaimer in the
14*11be35a1SLionel Sambuc  *    documentation and/or other materials provided with the distribution.
15*11be35a1SLionel Sambuc  *
16*11be35a1SLionel Sambuc  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17*11be35a1SLionel Sambuc  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18*11be35a1SLionel Sambuc  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19*11be35a1SLionel Sambuc  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20*11be35a1SLionel Sambuc  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21*11be35a1SLionel Sambuc  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22*11be35a1SLionel Sambuc  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23*11be35a1SLionel Sambuc  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24*11be35a1SLionel Sambuc  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25*11be35a1SLionel Sambuc  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26*11be35a1SLionel Sambuc  * POSSIBILITY OF SUCH DAMAGE.
27*11be35a1SLionel Sambuc  */
28*11be35a1SLionel Sambuc 
29*11be35a1SLionel Sambuc #include <sys/cdefs.h>
30*11be35a1SLionel Sambuc #include <sys/tree.h>
31*11be35a1SLionel Sambuc 
32*11be35a1SLionel Sambuc #include <atf-c.h>
33*11be35a1SLionel Sambuc #include <stdlib.h>
34*11be35a1SLionel Sambuc #include <stdio.h>
35*11be35a1SLionel Sambuc 
36*11be35a1SLionel Sambuc struct mist {
37*11be35a1SLionel Sambuc 	RB_ENTRY(mist) rbentry;
38*11be35a1SLionel Sambuc 	int key;
39*11be35a1SLionel Sambuc };
40*11be35a1SLionel Sambuc RB_HEAD(head, mist) tt;
41*11be35a1SLionel Sambuc 
42*11be35a1SLionel Sambuc static int
mistcmp(struct mist * a,struct mist * b)43*11be35a1SLionel Sambuc mistcmp(struct mist *a, struct mist *b)
44*11be35a1SLionel Sambuc {
45*11be35a1SLionel Sambuc #if 0
46*11be35a1SLionel Sambuc 	return (b->key - a->key); /* wrong, can overflow */
47*11be35a1SLionel Sambuc #else
48*11be35a1SLionel Sambuc 	if (b->key > a->key)
49*11be35a1SLionel Sambuc 		return 1;
50*11be35a1SLionel Sambuc 	else if (b->key < a->key)
51*11be35a1SLionel Sambuc 		return (-1);
52*11be35a1SLionel Sambuc 	else
53*11be35a1SLionel Sambuc 		return 0;
54*11be35a1SLionel Sambuc #endif
55*11be35a1SLionel Sambuc }
56*11be35a1SLionel Sambuc 
RB_PROTOTYPE(head,mist,rbentry,mistcmp)57*11be35a1SLionel Sambuc RB_PROTOTYPE(head, mist, rbentry, mistcmp)
58*11be35a1SLionel Sambuc RB_GENERATE(head, mist, rbentry, mistcmp)
59*11be35a1SLionel Sambuc 
60*11be35a1SLionel Sambuc static struct mist *
61*11be35a1SLionel Sambuc addmist(int key)
62*11be35a1SLionel Sambuc {
63*11be35a1SLionel Sambuc 	struct mist *m;
64*11be35a1SLionel Sambuc 
65*11be35a1SLionel Sambuc 	m = malloc(sizeof(struct mist));
66*11be35a1SLionel Sambuc 	m->key = key;
67*11be35a1SLionel Sambuc 	RB_INSERT(head, &tt, m);
68*11be35a1SLionel Sambuc 	return m;
69*11be35a1SLionel Sambuc }
70*11be35a1SLionel Sambuc 
71*11be35a1SLionel Sambuc static int
findmist(struct mist * m)72*11be35a1SLionel Sambuc findmist(struct mist *m)
73*11be35a1SLionel Sambuc {
74*11be35a1SLionel Sambuc 
75*11be35a1SLionel Sambuc 	return (!!RB_FIND(head, &tt, m));
76*11be35a1SLionel Sambuc }
77*11be35a1SLionel Sambuc 
78*11be35a1SLionel Sambuc #define N 1000
79*11be35a1SLionel Sambuc static int
test(void)80*11be35a1SLionel Sambuc test(void)
81*11be35a1SLionel Sambuc {
82*11be35a1SLionel Sambuc 	struct mist *m[N];
83*11be35a1SLionel Sambuc 	int fail, i, j;
84*11be35a1SLionel Sambuc 
85*11be35a1SLionel Sambuc 	RB_INIT(&tt);
86*11be35a1SLionel Sambuc 	fail = 0;
87*11be35a1SLionel Sambuc 	for (i = 0; i < N; i++) {
88*11be35a1SLionel Sambuc 		m[i] = addmist(random() << 1); /* use all 32 bits */
89*11be35a1SLionel Sambuc 		for (j = 0; j <= i; j++)
90*11be35a1SLionel Sambuc 			if (!findmist(m[j]))
91*11be35a1SLionel Sambuc 				fail++;
92*11be35a1SLionel Sambuc 	}
93*11be35a1SLionel Sambuc 	return fail;
94*11be35a1SLionel Sambuc }
95*11be35a1SLionel Sambuc 
96*11be35a1SLionel Sambuc ATF_TC(tree_rbstress);
ATF_TC_HEAD(tree_rbstress,tc)97*11be35a1SLionel Sambuc ATF_TC_HEAD(tree_rbstress, tc)
98*11be35a1SLionel Sambuc {
99*11be35a1SLionel Sambuc 
100*11be35a1SLionel Sambuc 	atf_tc_set_md_var(tc, "descr", "rb-tree stress test");
101*11be35a1SLionel Sambuc }
102*11be35a1SLionel Sambuc 
ATF_TC_BODY(tree_rbstress,tc)103*11be35a1SLionel Sambuc ATF_TC_BODY(tree_rbstress, tc)
104*11be35a1SLionel Sambuc {
105*11be35a1SLionel Sambuc 	int i, fail, f;
106*11be35a1SLionel Sambuc 
107*11be35a1SLionel Sambuc 	srandom(4711);
108*11be35a1SLionel Sambuc 	fail = 0;
109*11be35a1SLionel Sambuc 	for (i = 0; i < 10; i++) {
110*11be35a1SLionel Sambuc 		f = test();
111*11be35a1SLionel Sambuc 		if (f) {
112*11be35a1SLionel Sambuc 			atf_tc_fail_nonfatal("loop %d: %d errors\n", i, f);
113*11be35a1SLionel Sambuc 			fail += f;
114*11be35a1SLionel Sambuc 		}
115*11be35a1SLionel Sambuc 	}
116*11be35a1SLionel Sambuc }
117*11be35a1SLionel Sambuc 
ATF_TP_ADD_TCS(tp)118*11be35a1SLionel Sambuc ATF_TP_ADD_TCS(tp)
119*11be35a1SLionel Sambuc {
120*11be35a1SLionel Sambuc 
121*11be35a1SLionel Sambuc 	ATF_TP_ADD_TC(tp, tree_rbstress);
122*11be35a1SLionel Sambuc 
123*11be35a1SLionel Sambuc 	return atf_no_error();
124*11be35a1SLionel Sambuc }
125