1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa 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 AUTHOR AND CONTRIBUTORS ``AS IS'' AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 19 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 20 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 22 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 23 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 24 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 25 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 26 * SUCH DAMAGE. 27 */ 28 29 /* 30 * Userland code for testing binary heaps and hash tables 31 * 32 * $FreeBSD$ 33 */ 34 35 #include <sys/cdefs.h> 36 #include <sys/param.h> 37 38 #include <stdio.h> 39 #include <strings.h> 40 #include <stdlib.h> 41 42 #include "dn_heap.h" 43 #define log(x, arg...) fprintf(stderr, ## arg) 44 #define panic(x...) fprintf(stderr, ## x), exit(1) 45 46 #include <string.h> 47 48 struct x { 49 struct x *ht_link; 50 char buf[0]; 51 }; 52 53 uint32_t hf(uintptr_t key, int flags, void *arg) 54 { 55 return (flags & DNHT_KEY_IS_OBJ) ? 56 ((struct x *)key)->buf[0] : *(char *)key; 57 } 58 59 int matchf(void *obj, uintptr_t key, int flags, void *arg) 60 { 61 char *s = (flags & DNHT_KEY_IS_OBJ) ? 62 ((struct x *)key)->buf : (char *)key; 63 return (strcmp(((struct x *)obj)->buf, s) == 0); 64 } 65 66 void *newfn(uintptr_t key, int flags, void *arg) 67 { 68 char *s = (char *)key; 69 struct x *p = malloc(sizeof(*p) + 1 + strlen(s)); 70 if (p) 71 strcpy(p->buf, s); 72 return p; 73 } 74 75 char *strings[] = { 76 "undici", "unico", "doppio", "devoto", 77 "uno", "due", "tre", "quattro", "cinque", "sei", 78 "uno", "due", "tre", "quattro", "cinque", "sei", 79 NULL, 80 }; 81 82 int doprint(void *_x, void *arg) 83 { 84 struct x *x = _x; 85 printf("found element <%s>\n", x->buf); 86 return (int)arg; 87 } 88 89 static void 90 test_hash() 91 { 92 char **p; 93 struct dn_ht *h; 94 uintptr_t x = 0; 95 uintptr_t x1 = 0; 96 97 /* first, find and allocate */ 98 h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn); 99 100 for (p = strings; *p; p++) { 101 dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT, NULL); 102 } 103 dn_ht_scan(h, doprint, 0); 104 printf("/* second -- find without allocate */\n"); 105 h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL); 106 for (p = strings; *p; p++) { 107 void **y = newfn((uintptr_t)*p, 0, NULL); 108 if (x == 0) 109 x = (uintptr_t)y; 110 else { 111 if (x1 == 0) 112 x1 = (uintptr_t)*p; 113 } 114 dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ, NULL); 115 } 116 dn_ht_scan(h, doprint, 0); 117 printf("remove %p gives %p\n", (void *)x, 118 dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 119 printf("remove %p gives %p\n", (void *)x, 120 dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 121 printf("remove %p gives %p\n", (void *)x, 122 dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 123 printf("remove %p gives %p\n", (void *)x, 124 dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 125 dn_ht_scan(h, doprint, 0); 126 } 127 128 int 129 main(int argc, char *argv[]) 130 { 131 struct dn_heap h; 132 int i, n, n2, n3; 133 134 test_hash(); 135 return 0; 136 137 /* n = elements, n2 = cycles */ 138 n = (argc > 1) ? atoi(argv[1]) : 0; 139 if (n <= 0 || n > 1000000) 140 n = 100; 141 n2 = (argc > 2) ? atoi(argv[2]) : 0; 142 if (n2 <= 0) 143 n = 1000000; 144 n3 = (argc > 3) ? atoi(argv[3]) : 0; 145 bzero(&h, sizeof(h)); 146 heap_init(&h, n, -1); 147 while (n2-- > 0) { 148 uint64_t prevk = 0; 149 for (i=0; i < n; i++) 150 heap_insert(&h, n3 ? n-i: random(), (void *)(100+i)); 151 152 for (i=0; h.elements > 0; i++) { 153 uint64_t k = h.p[0].key; 154 if (k < prevk) 155 panic("wrong sequence\n"); 156 prevk = k; 157 if (0) 158 printf("%d key %llu, val %p\n", 159 i, h.p[0].key, h.p[0].object); 160 heap_extract(&h, NULL); 161 } 162 } 163 return 0; 164 } 165