sys/netpfil/ipfw/test/test_dn_heap.c

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