1272343Sngie/* $NetBSD: t_tree.c,v 1.1 2011/05/05 13:36:05 jruoho Exp $ */ 2272343Sngie 3272343Sngie/*- 4272343Sngie * Copyright (c) 2010, 2011 The NetBSD Foundation, Inc. 5272343Sngie * All rights reserved. 6272343Sngie * 7272343Sngie * Redistribution and use in source and binary forms, with or without 8272343Sngie * modification, are permitted provided that the following conditions 9272343Sngie * are met: 10272343Sngie * 1. Redistributions of source code must retain the above copyright 11272343Sngie * notice, this list of conditions and the following disclaimer. 12272343Sngie * 2. Redistributions in binary form must reproduce the above copyright 13272343Sngie * notice, this list of conditions and the following disclaimer in the 14272343Sngie * documentation and/or other materials provided with the distribution. 15272343Sngie * 16272343Sngie * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 17272343Sngie * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 18272343Sngie * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 19272343Sngie * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 20272343Sngie * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 21272343Sngie * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 22272343Sngie * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 23272343Sngie * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 24272343Sngie * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 25272343Sngie * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 26272343Sngie * POSSIBILITY OF SUCH DAMAGE. 27272343Sngie */ 28272343Sngie 29272343Sngie#include <sys/cdefs.h> 30272343Sngie#include <sys/tree.h> 31272343Sngie 32272343Sngie#include <atf-c.h> 33272343Sngie#include <stdlib.h> 34272343Sngie#include <stdio.h> 35272343Sngie 36272343Sngiestruct mist { 37272343Sngie RB_ENTRY(mist) rbentry; 38272343Sngie int key; 39272343Sngie}; 40272343SngieRB_HEAD(head, mist) tt; 41272343Sngie 42272343Sngiestatic int 43272343Sngiemistcmp(struct mist *a, struct mist *b) 44272343Sngie{ 45272343Sngie#if 0 46272343Sngie return (b->key - a->key); /* wrong, can overflow */ 47272343Sngie#else 48272343Sngie if (b->key > a->key) 49272343Sngie return 1; 50272343Sngie else if (b->key < a->key) 51272343Sngie return (-1); 52272343Sngie else 53272343Sngie return 0; 54272343Sngie#endif 55272343Sngie} 56272343Sngie 57272343SngieRB_PROTOTYPE(head, mist, rbentry, mistcmp) 58272343SngieRB_GENERATE(head, mist, rbentry, mistcmp) 59272343Sngie 60272343Sngiestatic struct mist * 61272343Sngieaddmist(int key) 62272343Sngie{ 63272343Sngie struct mist *m; 64272343Sngie 65272343Sngie m = malloc(sizeof(struct mist)); 66272343Sngie m->key = key; 67272343Sngie RB_INSERT(head, &tt, m); 68272343Sngie return m; 69272343Sngie} 70272343Sngie 71272343Sngiestatic int 72272343Sngiefindmist(struct mist *m) 73272343Sngie{ 74272343Sngie 75272343Sngie return (!!RB_FIND(head, &tt, m)); 76272343Sngie} 77272343Sngie 78272343Sngie#define N 1000 79272343Sngiestatic int 80272343Sngietest(void) 81272343Sngie{ 82272343Sngie struct mist *m[N]; 83272343Sngie int fail, i, j; 84272343Sngie 85272343Sngie RB_INIT(&tt); 86272343Sngie fail = 0; 87272343Sngie for (i = 0; i < N; i++) { 88272343Sngie m[i] = addmist(random() << 1); /* use all 32 bits */ 89272343Sngie for (j = 0; j <= i; j++) 90272343Sngie if (!findmist(m[j])) 91272343Sngie fail++; 92272343Sngie } 93272343Sngie return fail; 94272343Sngie} 95272343Sngie 96272343SngieATF_TC(tree_rbstress); 97272343SngieATF_TC_HEAD(tree_rbstress, tc) 98272343Sngie{ 99272343Sngie 100272343Sngie atf_tc_set_md_var(tc, "descr", "rb-tree stress test"); 101272343Sngie} 102272343Sngie 103272343SngieATF_TC_BODY(tree_rbstress, tc) 104272343Sngie{ 105272343Sngie int i, fail, f; 106272343Sngie 107272343Sngie srandom(4711); 108272343Sngie fail = 0; 109272343Sngie for (i = 0; i < 10; i++) { 110272343Sngie f = test(); 111272343Sngie if (f) { 112272343Sngie atf_tc_fail_nonfatal("loop %d: %d errors\n", i, f); 113272343Sngie fail += f; 114272343Sngie } 115272343Sngie } 116272343Sngie} 117272343Sngie 118272343SngieATF_TP_ADD_TCS(tp) 119272343Sngie{ 120272343Sngie 121272343Sngie ATF_TP_ADD_TC(tp, tree_rbstress); 122272343Sngie 123272343Sngie return atf_no_error(); 124272343Sngie} 125