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