1 /*- 2 * Copyright (c) 2015 Nuxi, https://nuxi.nl/ 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 17 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23 * SUCH DAMAGE. 24 */ 25 26 #include <sys/cdefs.h> 27 __FBSDID("$FreeBSD$"); 28 29 #include <atf-c.h> 30 #define _SEARCH_PRIVATE 31 #include <search.h> 32 #include <stdbool.h> 33 #include <stdlib.h> 34 35 /* Validates the integrity of an AVL tree. */ 36 static inline unsigned int 37 tnode_assert(const node_t *n) 38 { 39 unsigned int height_left, height_right; 40 int balance; 41 42 if (n == NULL) 43 return 0; 44 height_left = tnode_assert(n->llink); 45 height_right = tnode_assert(n->rlink); 46 balance = (int)height_left - (int)height_right; 47 ATF_CHECK(balance >= -1); 48 ATF_CHECK(balance <= 1); 49 ATF_CHECK_EQ(balance, n->balance); 50 return (height_left > height_right ? height_left : height_right) + 1; 51 } 52 53 static int 54 compar(const void *a, const void *b) 55 { 56 57 return *(int *)a - *(int *)b; 58 } 59 60 ATF_TC_WITHOUT_HEAD(tsearch_test); 61 ATF_TC_BODY(tsearch_test, tc) 62 { 63 /* 64 * Run the test below in a deterministic fashion to prevent this 65 * test from potentially flapping. We assume that this provides 66 * enough coverage. 67 */ 68 #if 0 69 unsigned short random_state[3]; 70 arc4random_buf(random_state, sizeof(random_state)); 71 #else 72 unsigned short random_state[3] = { 26554, 13330, 3246 }; 73 #endif 74 75 #define NKEYS 1000 76 /* Create 1000 possible keys. */ 77 int keys[NKEYS]; 78 for (int i = 0; i < NKEYS; ++i) 79 keys[i] = i; 80 81 /* Apply random operations on a binary tree and check the results. */ 82 void *root = NULL; 83 bool present[NKEYS] = {}; 84 for (int i = 0; i < NKEYS * 10; ++i) { 85 int key = nrand48(random_state) % NKEYS; 86 switch (nrand48(random_state) % 3) { 87 case 0: /* tdelete(). */ 88 if (present[key]) { 89 ATF_CHECK(tdelete(&key, &root, compar) != NULL); 90 present[key] = false; 91 } else { 92 ATF_CHECK_EQ(NULL, 93 tdelete(&key, &root, compar)); 94 } 95 break; 96 case 1: /* tfind(). */ 97 if (present[key]) { 98 ATF_CHECK_EQ(&keys[key], 99 *(int **)tfind(&key, &root, compar)); 100 } else { 101 ATF_CHECK_EQ(NULL, tfind(&key, &root, compar)); 102 } 103 break; 104 case 2: /* tsearch(). */ 105 if (present[key]) { 106 ATF_CHECK_EQ(&keys[key], 107 *(int **)tsearch(&key, &root, compar)); 108 } else { 109 ATF_CHECK_EQ(&keys[key], *(int **)tsearch( 110 &keys[key], &root, compar)); 111 present[key] = true; 112 } 113 break; 114 } 115 tnode_assert(root); 116 } 117 118 /* Remove all entries from the tree. */ 119 for (int key = 0; key < NKEYS; ++key) 120 if (present[key]) 121 ATF_CHECK(tdelete(&key, &root, compar) != NULL); 122 ATF_CHECK_EQ(NULL, root); 123 } 124 125 ATF_TP_ADD_TCS(tp) 126 { 127 128 ATF_TP_ADD_TC(tp, tsearch_test); 129 130 return (atf_no_error()); 131 } 132