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