19615Spchelko/*- 214851Sgoetz * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa 39615Spchelko * All rights reserved 49615Spchelko * 59615Spchelko * Redistribution and use in source and binary forms, with or without 69615Spchelko * modification, are permitted provided that the following conditions 79615Spchelko * are met: 89615Spchelko * 1. Redistributions of source code must retain the above copyright 99615Spchelko * notice, this list of conditions and the following disclaimer. 109615Spchelko * 2. Redistributions in binary form must reproduce the above copyright 119615Spchelko * notice, this list of conditions and the following disclaimer in the 129615Spchelko * documentation and/or other materials provided with the distribution. 139615Spchelko * 149615Spchelko * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 159615Spchelko * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 169615Spchelko * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 179615Spchelko * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 189615Spchelko * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 199615Spchelko * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 209615Spchelko * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 219615Spchelko * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 229615Spchelko * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 239615Spchelko * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 249615Spchelko * SUCH DAMAGE. 259615Spchelko */ 2614851Sgoetz 279615Spchelko/* 289615Spchelko * Userland code for testing binary heaps and hash tables 2911127Syan * 309615Spchelko * $FreeBSD$ 3111127Syan */ 329615Spchelko 339615Spchelko#include <sys/cdefs.h> 349615Spchelko#include <sys/param.h> 359615Spchelko 369615Spchelko#include <stdio.h> 379615Spchelko#include <strings.h> 3811127Syan#include <stdlib.h> 399615Spchelko 409615Spchelko#include "dn_heap.h" 419615Spchelko#define log(x, arg...) fprintf(stderr, ## arg) 429615Spchelko#define panic(x...) fprintf(stderr, ## x), exit(1) 439615Spchelko 449615Spchelko#include <string.h> 459615Spchelko 469615Spchelkostruct x { 479615Spchelko struct x *ht_link; 489615Spchelko char buf[0]; 499615Spchelko}; 509615Spchelko 519615Spchelkouint32_t hf(uintptr_t key, int flags, void *arg) 529615Spchelko{ 539615Spchelko return (flags & DNHT_KEY_IS_OBJ) ? 549615Spchelko ((struct x *)key)->buf[0] : *(char *)key; 559615Spchelko} 569615Spchelko 579615Spchelkoint matchf(void *obj, uintptr_t key, int flags, void *arg) 589615Spchelko{ 599615Spchelko char *s = (flags & DNHT_KEY_IS_OBJ) ? 609615Spchelko ((struct x *)key)->buf : (char *)key; 619615Spchelko return (strcmp(((struct x *)obj)->buf, s) == 0); 629615Spchelko} 639615Spchelko 649615Spchelkovoid *newfn(uintptr_t key, int flags, void *arg) 659615Spchelko{ 669615Spchelko char *s = (char *)key; 679615Spchelko struct x *p = malloc(sizeof(*p) + 1 + strlen(s)); 689615Spchelko if (p) 699615Spchelko strcpy(p->buf, s); 709615Spchelko return p; 719615Spchelko} 729615Spchelko 739615Spchelkochar *strings[] = { 749615Spchelko "undici", "unico", "doppio", "devoto", 759615Spchelko "uno", "due", "tre", "quattro", "cinque", "sei", 769615Spchelko "uno", "due", "tre", "quattro", "cinque", "sei", 779615Spchelko NULL, 789615Spchelko}; 799615Spchelko 809615Spchelkoint doprint(void *_x, void *arg) 819615Spchelko{ 829615Spchelko struct x *x = _x; 839615Spchelko printf("found element <%s>\n", x->buf); 849615Spchelko return (int)arg; 859615Spchelko} 869615Spchelko 879615Spchelkostatic void 889615Spchelkotest_hash() 899615Spchelko{ 909615Spchelko char **p; 919615Spchelko struct dn_ht *h; 929615Spchelko uintptr_t x = 0; 939615Spchelko uintptr_t x1 = 0; 949615Spchelko 959615Spchelko /* first, find and allocate */ 969615Spchelko h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn); 979615Spchelko 989615Spchelko for (p = strings; *p; p++) { 999615Spchelko dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT, NULL); 1009615Spchelko } 1019615Spchelko dn_ht_scan(h, doprint, 0); 1029615Spchelko printf("/* second -- find without allocate */\n"); 1039615Spchelko h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL); 1049615Spchelko for (p = strings; *p; p++) { 1059615Spchelko void **y = newfn((uintptr_t)*p, 0, NULL); 1069615Spchelko if (x == 0) 1079615Spchelko x = (uintptr_t)y; 1089615Spchelko else { 10911127Syan if (x1 == 0) 1109615Spchelko x1 = (uintptr_t)*p; 1119615Spchelko } 11211127Syan dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ, NULL); 11311127Syan } 11411127Syan dn_ht_scan(h, doprint, 0); 11511127Syan printf("remove %p gives %p\n", (void *)x, 1169615Spchelko dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 11711127Syan printf("remove %p gives %p\n", (void *)x, 1189615Spchelko dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 1199615Spchelko printf("remove %p gives %p\n", (void *)x, 1209615Spchelko dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 1219615Spchelko printf("remove %p gives %p\n", (void *)x, 1229615Spchelko dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 1239615Spchelko dn_ht_scan(h, doprint, 0); 1249615Spchelko} 1259615Spchelko 1269615Spchelkoint 1279615Spchelkomain(int argc, char *argv[]) 1289615Spchelko{ 1299615Spchelko struct dn_heap h; 1309615Spchelko int i, n, n2, n3; 1319615Spchelko 1329615Spchelko test_hash(); 1339615Spchelko return 0; 1349615Spchelko 1359615Spchelko /* n = elements, n2 = cycles */ 1369615Spchelko n = (argc > 1) ? atoi(argv[1]) : 0; 1379615Spchelko if (n <= 0 || n > 1000000) 1389615Spchelko n = 100; 1399615Spchelko n2 = (argc > 2) ? atoi(argv[2]) : 0; 1409615Spchelko if (n2 <= 0) 1419615Spchelko n = 1000000; 1429615Spchelko n3 = (argc > 3) ? atoi(argv[3]) : 0; 1439615Spchelko bzero(&h, sizeof(h)); 1449615Spchelko heap_init(&h, n, -1); 1459615Spchelko while (n2-- > 0) { 1469615Spchelko uint64_t prevk = 0; 1479615Spchelko for (i=0; i < n; i++) 1489615Spchelko heap_insert(&h, n3 ? n-i: random(), (void *)(100+i)); 1499615Spchelko 1509615Spchelko for (i=0; h.elements > 0; i++) { 1519615Spchelko uint64_t k = h.p[0].key; 1529615Spchelko if (k < prevk) 1539615Spchelko panic("wrong sequence\n"); 1549615Spchelko prevk = k; 1559615Spchelko if (0) 1569615Spchelko printf("%d key %llu, val %p\n", 1579615Spchelko i, h.p[0].key, h.p[0].object); 1589615Spchelko heap_extract(&h, NULL); 1599615Spchelko } 1609615Spchelko } 1619615Spchelko return 0; 1629615Spchelko} 1639615Spchelko