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 33 #include <sys/param.h> 34 35 #include <stdio.h> 36 #include <strings.h> 37 #include <stdlib.h> 38 39 #include "dn_heap.h" 40 #define log(x, arg...) fprintf(stderr, ## arg) 41 #define panic(x...) fprintf(stderr, ## x), exit(1) 42 43 #include <string.h> 44 45 struct x { 46 struct x *ht_link; 47 char buf[0]; 48 }; 49 50 uint32_t hf(uintptr_t key, int flags, void *arg) 51 { 52 return (flags & DNHT_KEY_IS_OBJ) ? 53 ((struct x *)key)->buf[0] : *(char *)key; 54 } 55 56 int matchf(void *obj, uintptr_t key, int flags, void *arg) 57 { 58 char *s = (flags & DNHT_KEY_IS_OBJ) ? 59 ((struct x *)key)->buf : (char *)key; 60 return (strcmp(((struct x *)obj)->buf, s) == 0); 61 } 62 63 void *newfn(uintptr_t key, int flags, void *arg) 64 { 65 char *s = (char *)key; 66 struct x *p = malloc(sizeof(*p) + 1 + strlen(s)); 67 if (p) 68 strcpy(p->buf, s); 69 return p; 70 } 71 72 char *strings[] = { 73 "undici", "unico", "doppio", "devoto", 74 "uno", "due", "tre", "quattro", "cinque", "sei", 75 "uno", "due", "tre", "quattro", "cinque", "sei", 76 NULL, 77 }; 78 79 int doprint(void *_x, void *arg) 80 { 81 struct x *x = _x; 82 printf("found element <%s>\n", x->buf); 83 return (int)arg; 84 } 85 86 static void 87 test_hash() 88 { 89 char **p; 90 struct dn_ht *h; 91 uintptr_t x = 0; 92 uintptr_t x1 = 0; 93 94 /* first, find and allocate */ 95 h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn); 96 97 for (p = strings; *p; p++) { 98 dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT, NULL); 99 } 100 dn_ht_scan(h, doprint, 0); 101 printf("/* second -- find without allocate */\n"); 102 h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL); 103 for (p = strings; *p; p++) { 104 void **y = newfn((uintptr_t)*p, 0, NULL); 105 if (x == 0) 106 x = (uintptr_t)y; 107 else { 108 if (x1 == 0) 109 x1 = (uintptr_t)*p; 110 } 111 dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ, NULL); 112 } 113 dn_ht_scan(h, doprint, 0); 114 printf("remove %p gives %p\n", (void *)x, 115 dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 116 printf("remove %p gives %p\n", (void *)x, 117 dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 118 printf("remove %p gives %p\n", (void *)x, 119 dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 120 printf("remove %p gives %p\n", (void *)x, 121 dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 122 dn_ht_scan(h, doprint, 0); 123 } 124 125 int 126 main(int argc, char *argv[]) 127 { 128 struct dn_heap h; 129 int i, n, n2, n3; 130 131 test_hash(); 132 return 0; 133 134 /* n = elements, n2 = cycles */ 135 n = (argc > 1) ? atoi(argv[1]) : 0; 136 if (n <= 0 || n > 1000000) 137 n = 100; 138 n2 = (argc > 2) ? atoi(argv[2]) : 0; 139 if (n2 <= 0) 140 n = 1000000; 141 n3 = (argc > 3) ? atoi(argv[3]) : 0; 142 bzero(&h, sizeof(h)); 143 heap_init(&h, n, -1); 144 while (n2-- > 0) { 145 uint64_t prevk = 0; 146 for (i=0; i < n; i++) 147 heap_insert(&h, n3 ? n-i: random(), (void *)(100+i)); 148 149 for (i=0; h.elements > 0; i++) { 150 uint64_t k = h.p[0].key; 151 if (k < prevk) 152 panic("wrong sequence\n"); 153 prevk = k; 154 if (0) 155 printf("%d key %llu, val %p\n", 156 i, h.p[0].key, h.p[0].object); 157 heap_extract(&h, NULL); 158 } 159 } 160 return 0; 161 } 162