test/test_dn_heap.c

   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  * $Id: test_dn_heap.c 5626 2010-03-04 21:55:22Z luigi $
  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 }