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