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