1292613Sed/*- 2292613Sed * Copyright (c) 2015 Nuxi, https://nuxi.nl/ 3292613Sed * 4292613Sed * Redistribution and use in source and binary forms, with or without 5292613Sed * modification, are permitted provided that the following conditions 6292613Sed * are met: 7292613Sed * 1. Redistributions of source code must retain the above copyright 8292613Sed * notice, this list of conditions and the following disclaimer. 9292613Sed * 2. Redistributions in binary form must reproduce the above copyright 10292613Sed * notice, this list of conditions and the following disclaimer in the 11292613Sed * documentation and/or other materials provided with the distribution. 12292613Sed * 13292613Sed * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 14292613Sed * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15292613Sed * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 16292613Sed * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 17292613Sed * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 18292613Sed * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 19292613Sed * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 20292613Sed * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 21292613Sed * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 22292613Sed * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 23292613Sed * SUCH DAMAGE. 24292613Sed */ 25292613Sed 26292613Sed#include <sys/cdefs.h> 27292613Sed__FBSDID("$FreeBSD: stable/11/lib/libc/tests/stdlib/tsearch_test.c 308090 2016-10-29 14:41:22Z ed $"); 28292613Sed 29292613Sed#include <atf-c.h> 30292613Sed#define _SEARCH_PRIVATE 31292613Sed#include <search.h> 32292613Sed#include <stdbool.h> 33292613Sed#include <stdlib.h> 34292613Sed 35292613Sed/* Validates the integrity of an AVL tree. */ 36292613Sedstatic inline unsigned int 37308090Sedtnode_assert(const posix_tnode *n) 38292613Sed{ 39292613Sed unsigned int height_left, height_right; 40292613Sed int balance; 41292613Sed 42292613Sed if (n == NULL) 43292613Sed return 0; 44292613Sed height_left = tnode_assert(n->llink); 45292613Sed height_right = tnode_assert(n->rlink); 46292613Sed balance = (int)height_left - (int)height_right; 47292613Sed ATF_CHECK(balance >= -1); 48292613Sed ATF_CHECK(balance <= 1); 49292613Sed ATF_CHECK_EQ(balance, n->balance); 50292613Sed return (height_left > height_right ? height_left : height_right) + 1; 51292613Sed} 52292613Sed 53292613Sedstatic int 54292613Sedcompar(const void *a, const void *b) 55292613Sed{ 56292613Sed 57292613Sed return *(int *)a - *(int *)b; 58292613Sed} 59292613Sed 60292613SedATF_TC_WITHOUT_HEAD(tsearch_test); 61292613SedATF_TC_BODY(tsearch_test, tc) 62292613Sed{ 63292613Sed /* 64292613Sed * Run the test below in a deterministic fashion to prevent this 65292613Sed * test from potentially flapping. We assume that this provides 66292613Sed * enough coverage. 67292613Sed */ 68292613Sed#if 0 69292613Sed unsigned short random_state[3]; 70292613Sed arc4random_buf(random_state, sizeof(random_state)); 71292613Sed#else 72292613Sed unsigned short random_state[3] = { 26554, 13330, 3246 }; 73292613Sed#endif 74292613Sed 75292613Sed#define NKEYS 1000 76292613Sed /* Create 1000 possible keys. */ 77292613Sed int keys[NKEYS]; 78292613Sed for (int i = 0; i < NKEYS; ++i) 79292613Sed keys[i] = i; 80292613Sed 81292613Sed /* Apply random operations on a binary tree and check the results. */ 82308090Sed posix_tnode *root = NULL; 83292613Sed bool present[NKEYS] = {}; 84292613Sed for (int i = 0; i < NKEYS * 10; ++i) { 85292613Sed int key = nrand48(random_state) % NKEYS; 86292613Sed switch (nrand48(random_state) % 3) { 87292613Sed case 0: /* tdelete(). */ 88292613Sed if (present[key]) { 89292613Sed ATF_CHECK(tdelete(&key, &root, compar) != NULL); 90292613Sed present[key] = false; 91292613Sed } else { 92292613Sed ATF_CHECK_EQ(NULL, 93292613Sed tdelete(&key, &root, compar)); 94292613Sed } 95292613Sed break; 96292613Sed case 1: /* tfind(). */ 97292613Sed if (present[key]) { 98292613Sed ATF_CHECK_EQ(&keys[key], 99292613Sed *(int **)tfind(&key, &root, compar)); 100292613Sed } else { 101292613Sed ATF_CHECK_EQ(NULL, tfind(&key, &root, compar)); 102292613Sed } 103292613Sed break; 104292613Sed case 2: /* tsearch(). */ 105292613Sed if (present[key]) { 106292613Sed ATF_CHECK_EQ(&keys[key], 107292613Sed *(int **)tsearch(&key, &root, compar)); 108292613Sed } else { 109292613Sed ATF_CHECK_EQ(&keys[key], *(int **)tsearch( 110292613Sed &keys[key], &root, compar)); 111292613Sed present[key] = true; 112292613Sed } 113292613Sed break; 114292613Sed } 115292613Sed tnode_assert(root); 116292613Sed } 117292613Sed 118292613Sed /* Remove all entries from the tree. */ 119292613Sed for (int key = 0; key < NKEYS; ++key) 120292613Sed if (present[key]) 121292613Sed ATF_CHECK(tdelete(&key, &root, compar) != NULL); 122292613Sed ATF_CHECK_EQ(NULL, root); 123292613Sed} 124292613Sed 125292613SedATF_TP_ADD_TCS(tp) 126292613Sed{ 127292613Sed 128292613Sed ATF_TP_ADD_TC(tp, tsearch_test); 129292613Sed 130292613Sed return (atf_no_error()); 131292613Sed} 132