test_dn_heap.c revision 204591
1204591Sluigi/*- 2204591Sluigi * Copyright (c) 1998-2002,2010 Luigi Rizzo, Universita` di Pisa 3204591Sluigi * All rights reserved 4204591Sluigi * 5204591Sluigi * Redistribution and use in source and binary forms, with or without 6204591Sluigi * modification, are permitted provided that the following conditions 7204591Sluigi * are met: 8204591Sluigi * 1. Redistributions of source code must retain the above copyright 9204591Sluigi * notice, this list of conditions and the following disclaimer. 10204591Sluigi * 2. Redistributions in binary form must reproduce the above copyright 11204591Sluigi * notice, this list of conditions and the following disclaimer in the 12204591Sluigi * documentation and/or other materials provided with the distribution. 13204591Sluigi * 14204591Sluigi * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15204591Sluigi * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16204591Sluigi * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17204591Sluigi * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18204591Sluigi * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19204591Sluigi * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20204591Sluigi * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21204591Sluigi * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22204591Sluigi * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23204591Sluigi * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24204591Sluigi * SUCH DAMAGE. 25204591Sluigi */ 26204591Sluigi 27204591Sluigi/* 28204591Sluigi * Userland code for testing binary heaps and hash tables 29204591Sluigi * 30204591Sluigi * $FreeBSD: head/sys/netinet/ipfw/test/test_dn_heap.c 204591 2010-03-02 17:40:48Z luigi $ 31204591Sluigi */ 32204591Sluigi 33204591Sluigi#include <sys/cdefs.h> 34204591Sluigi#include <sys/param.h> 35204591Sluigi 36204591Sluigi#include <stdio.h> 37204591Sluigi#include <strings.h> 38204591Sluigi#include <stdlib.h> 39204591Sluigi 40204591Sluigi#include "dn_heap.h" 41204591Sluigi#define log(x, arg...) fprintf(stderr, ## arg) 42204591Sluigi#define panic(x...) fprintf(stderr, ## x), exit(1) 43204591Sluigi 44204591Sluigi#include <string.h> 45204591Sluigi 46204591Sluigistruct x { 47204591Sluigi struct x *ht_link; 48204591Sluigi char buf[0]; 49204591Sluigi}; 50204591Sluigi 51204591Sluigiuint32_t hf(uintptr_t key, int flags, void *arg) 52204591Sluigi{ 53204591Sluigi return (flags & DNHT_KEY_IS_OBJ) ? 54204591Sluigi ((struct x *)key)->buf[0] : *(char *)key; 55204591Sluigi} 56204591Sluigi 57204591Sluigiint matchf(void *obj, uintptr_t key, int flags, void *arg) 58204591Sluigi{ 59204591Sluigi char *s = (flags & DNHT_KEY_IS_OBJ) ? 60204591Sluigi ((struct x *)key)->buf : (char *)key; 61204591Sluigi return (strcmp(((struct x *)obj)->buf, s) == 0); 62204591Sluigi} 63204591Sluigi 64204591Sluigivoid *newfn(uintptr_t key, int flags, void *arg) 65204591Sluigi{ 66204591Sluigi char *s = (char *)key; 67204591Sluigi struct x *p = malloc(sizeof(*p) + 1 + strlen(s)); 68204591Sluigi if (p) 69204591Sluigi strcpy(p->buf, s); 70204591Sluigi return p; 71204591Sluigi} 72204591Sluigi 73204591Sluigichar *strings[] = { 74204591Sluigi "undici", "unico", "doppio", "devoto", 75204591Sluigi "uno", "due", "tre", "quattro", "cinque", "sei", 76204591Sluigi "uno", "due", "tre", "quattro", "cinque", "sei", 77204591Sluigi NULL, 78204591Sluigi}; 79204591Sluigi 80204591Sluigiint doprint(void *_x, void *arg) 81204591Sluigi{ 82204591Sluigi struct x *x = _x; 83204591Sluigi printf("found element <%s>\n", x->buf); 84204591Sluigi return (int)arg; 85204591Sluigi} 86204591Sluigi 87204591Sluigistatic void 88204591Sluigitest_hash() 89204591Sluigi{ 90204591Sluigi char **p; 91204591Sluigi struct dn_ht *h; 92204591Sluigi uintptr_t x = 0; 93204591Sluigi uintptr_t x1 = 0; 94204591Sluigi 95204591Sluigi /* first, find and allocate */ 96204591Sluigi h = dn_ht_init(NULL, 10, 0, hf, matchf, newfn); 97204591Sluigi 98204591Sluigi for (p = strings; *p; p++) { 99204591Sluigi dn_ht_find(h, (uintptr_t)*p, DNHT_INSERT, NULL); 100204591Sluigi } 101204591Sluigi dn_ht_scan(h, doprint, 0); 102204591Sluigi printf("/* second -- find without allocate */\n"); 103204591Sluigi h = dn_ht_init(NULL, 10, 0, hf, matchf, NULL); 104204591Sluigi for (p = strings; *p; p++) { 105204591Sluigi void **y = newfn((uintptr_t)*p, 0, NULL); 106204591Sluigi if (x == 0) 107204591Sluigi x = (uintptr_t)y; 108204591Sluigi else { 109204591Sluigi if (x1 == 0) 110204591Sluigi x1 = (uintptr_t)*p; 111204591Sluigi } 112204591Sluigi dn_ht_find(h, (uintptr_t)y, DNHT_INSERT | DNHT_KEY_IS_OBJ, NULL); 113204591Sluigi } 114204591Sluigi dn_ht_scan(h, doprint, 0); 115204591Sluigi printf("remove %p gives %p\n", (void *)x, 116204591Sluigi dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 117204591Sluigi printf("remove %p gives %p\n", (void *)x, 118204591Sluigi dn_ht_find(h, x, DNHT_KEY_IS_OBJ | DNHT_REMOVE, NULL)); 119204591Sluigi printf("remove %p gives %p\n", (void *)x, 120204591Sluigi dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 121204591Sluigi printf("remove %p gives %p\n", (void *)x, 122204591Sluigi dn_ht_find(h, x1, DNHT_REMOVE, NULL)); 123204591Sluigi dn_ht_scan(h, doprint, 0); 124204591Sluigi} 125204591Sluigi 126204591Sluigiint 127204591Sluigimain(int argc, char *argv[]) 128204591Sluigi{ 129204591Sluigi struct dn_heap h; 130204591Sluigi int i, n, n2, n3; 131204591Sluigi 132204591Sluigi test_hash(); 133204591Sluigi return 0; 134204591Sluigi 135204591Sluigi /* n = elements, n2 = cycles */ 136204591Sluigi n = (argc > 1) ? atoi(argv[1]) : 0; 137204591Sluigi if (n <= 0 || n > 1000000) 138204591Sluigi n = 100; 139204591Sluigi n2 = (argc > 2) ? atoi(argv[2]) : 0; 140204591Sluigi if (n2 <= 0) 141204591Sluigi n = 1000000; 142204591Sluigi n3 = (argc > 3) ? atoi(argv[3]) : 0; 143204591Sluigi bzero(&h, sizeof(h)); 144204591Sluigi heap_init(&h, n, -1); 145204591Sluigi while (n2-- > 0) { 146204591Sluigi uint64_t prevk = 0; 147204591Sluigi for (i=0; i < n; i++) 148204591Sluigi heap_insert(&h, n3 ? n-i: random(), (void *)(100+i)); 149204591Sluigi 150204591Sluigi for (i=0; h.elements > 0; i++) { 151204591Sluigi uint64_t k = h.p[0].key; 152204591Sluigi if (k < prevk) 153204591Sluigi panic("wrong sequence\n"); 154204591Sluigi prevk = k; 155204591Sluigi if (0) 156204591Sluigi printf("%d key %llu, val %p\n", 157204591Sluigi i, h.p[0].key, h.p[0].object); 158204591Sluigi heap_extract(&h, NULL); 159204591Sluigi } 160204591Sluigi } 161204591Sluigi return 0; 162204591Sluigi} 163