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