shotgun/external_libs/libcchash/tester.c

   1 /* Copyright (C) 2002, 2004 Christopher Clark <firstname.lastname@cl.cam.ac.uk> */
   2
   3 #include "hashtable.h"
   4 #include "hashtable_itr.h"
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7 #include <string.h> /* for memcmp */
   8
   9 static const int ITEM_COUNT = 4000;
  10
  11 typedef unsigned int uint32_t;
  12 typedef unsigned short uint16_t;
  13
  14 /*****************************************************************************/
  15 struct key
  16 {
  17     uint32_t one_ip; uint32_t two_ip; uint16_t one_port; uint16_t two_port;
  18 };
  19
  20 struct value
  21 {
  22     char *id;
  23 };
  24
  25 DEFINE_HASHTABLE_INSERT(insert_some, struct key, struct value);
  26 DEFINE_HASHTABLE_SEARCH(search_some, struct key, struct value);
  27 DEFINE_HASHTABLE_REMOVE(remove_some, struct key, struct value);
  28 DEFINE_HASHTABLE_ITERATOR_SEARCH(search_itr_some, struct key);
  29
  30
  31 /*****************************************************************************/
  32 static unsigned int
  33 hashfromkey(void *ky)
  34 {
  35     struct key *k = (struct key *)ky;
  36     return (((k->one_ip << 17) | (k->one_ip >> 15)) ^ k->two_ip) +
  37             (k->one_port * 17) + (k->two_port * 13 * 29);
  38 }
  39
  40 static int
  41 equalkeys(void *k1, void *k2)
  42 {
  43     return (0 == memcmp(k1,k2,sizeof(struct key)));
  44 }
  45
  46 /*****************************************************************************/
  47 int
  48 main(int argc, char **argv)
  49 {
  50     struct key *k, *kk;
  51     struct value *v, *found;
  52     struct hashtable *h;
  53     struct hashtable_itr itr;
  54     int i;
  55
  56     h = create_hashtable(16, hashfromkey, equalkeys);
  57     if (NULL == h) exit(-1); /*oom*/
  58
  59
  60 /*****************************************************************************/
  61 /* Insertion */
  62     for (i = 0; i < ITEM_COUNT; i++)
  63     {
  64         k = (struct key *)malloc(sizeof(struct key));
  65         if (NULL == k) {
  66             printf("ran out of memory allocating a key\n");
  67             return 1;
  68         }
  69         k->one_ip = 0xcfccee40 + i;
  70         k->two_ip = 0xcf0cee67 - (5 * i);
  71         k->one_port = 22 + (7 * i);
  72         k->two_port = 5522 - (3 * i);
  73
  74         v = (struct value *)malloc(sizeof(struct value));
  75         v->id = "a value";
  76
  77         if (!insert_some(h,k,v)) exit(-1); /*oom*/
  78     }
  79     printf("After insertion, hashtable contains %u items.\n",
  80             hashtable_count(h));
  81
  82 /*****************************************************************************/
  83 /* Hashtable search */
  84     k = (struct key *)malloc(sizeof(struct key));
  85     if (NULL == k) {
  86         printf("ran out of memory allocating a key\n");
  87         return 1;
  88     }
  89
  90     for (i = 0; i < ITEM_COUNT; i++)
  91     {
  92         k->one_ip = 0xcfccee40 + i;
  93         k->two_ip = 0xcf0cee67 - (5 * i);
  94         k->one_port = 22 + (7 * i);
  95         k->two_port = 5522 - (3 * i);
  96
  97         if (NULL == (found = search_some(h,k))) {
  98             printf("BUG: key not found\n");
  99         }
 100     }
 101
 102 /*****************************************************************************/
 103 /* Hashtable iteration */
 104     /* Iterator constructor only returns a valid iterator if
 105      * the hashtable is not empty */
 106     hashtable_iterator_init(&itr, h);
 107     i = 0;
 108     if (hashtable_count(h) > 0)
 109     {
 110         do {
 111             kk = hashtable_iterator_key(&itr);
 112             v = hashtable_iterator_value(&itr);
 113             /* here (kk,v) are a valid (key, value) pair */
 114             /* We could call 'hashtable_remove(h,kk)' - and this operation
 115              * 'free's kk. However, the iterator is then broken.
 116              * This is why hashtable_iterator_remove exists - see below.
 117              */
 118             i++;
 119
 120         } while (hashtable_iterator_advance(&itr));
 121     }
 122     printf("Iterated through %u entries.\n", i);
 123
 124 /*****************************************************************************/
 125 /* Hashtable iterator search */
 126
 127     /* Try the search some method */
 128     for (i = 0; i < ITEM_COUNT; i++)
 129     {
 130         k->one_ip = 0xcfccee40 + i;
 131         k->two_ip = 0xcf0cee67 - (5 * i);
 132         k->one_port = 22 + (7 * i);
 133         k->two_port = 5522 - (3 * i);
 134
 135         if (0 == search_itr_some(&itr,h,k)) {
 136             printf("BUG: key not found searching with iterator");
 137         }
 138     }
 139
 140 /*****************************************************************************/
 141 /* Hashtable removal */
 142
 143     for (i = 0; i < ITEM_COUNT; i++)
 144     {
 145         k->one_ip = 0xcfccee40 + i;
 146         k->two_ip = 0xcf0cee67 - (5 * i);
 147         k->one_port = 22 + (7 * i);
 148         k->two_port = 5522 - (3 * i);
 149
 150         if (NULL == (found = remove_some(h,k))) {
 151             printf("BUG: key not found for removal\n");
 152         }
 153     }
 154     printf("After removal, hashtable contains %u items.\n",
 155             hashtable_count(h));
 156
 157 /*****************************************************************************/
 158 /* Hashtable destroy and create */
 159
 160     hashtable_destroy(h, 1);
 161     h = NULL;
 162     free(k);
 163
 164     h = create_hashtable(160, hashfromkey, equalkeys);
 165     if (NULL == h) {
 166         printf("out of memory allocating second hashtable\n");
 167         return 1;
 168     }
 169
 170 /*****************************************************************************/
 171 /* Hashtable insertion */
 172
 173     for (i = 0; i < ITEM_COUNT; i++)
 174     {
 175         k = (struct key *)malloc(sizeof(struct key));
 176         k->one_ip = 0xcfccee40 + i;
 177         k->two_ip = 0xcf0cee67 - (5 * i);
 178         k->one_port = 22 + (7 * i);
 179         k->two_port = 5522 - (3 * i);
 180
 181         v = (struct value *)malloc(sizeof(struct value));
 182         v->id = "a value";
 183
 184         if (!insert_some(h,k,v))
 185         {
 186             printf("out of memory inserting into second hashtable\n");
 187             return 1;
 188         }
 189     }
 190     printf("After insertion, hashtable contains %u items.\n",
 191             hashtable_count(h));
 192
 193 /*****************************************************************************/
 194 /* Hashtable iterator search and iterator remove */
 195
 196     k = (struct key *)malloc(sizeof(struct key));
 197     if (NULL == k) {
 198         printf("ran out of memory allocating a key\n");
 199         return 1;
 200     }
 201
 202     for (i = ITEM_COUNT - 1; i >= 0; i = i - 7)
 203     {
 204         k->one_ip = 0xcfccee40 + i;
 205         k->two_ip = 0xcf0cee67 - (5 * i);
 206         k->one_port = 22 + (7 * i);
 207         k->two_port = 5522 - (3 * i);
 208
 209         if (0 == search_itr_some(&itr, h, k)) {
 210             printf("BUG: key %u not found for search preremoval using iterator\n", i);
 211             return 1;
 212         }
 213         if (0 == hashtable_iterator_remove(&itr)) {
 214             printf("BUG: key not found for removal using iterator\n");
 215             return 1;
 216         }
 217     }
 218
 219 /*****************************************************************************/
 220 /* Hashtable iterator remove and advance */
 221
 222     for (hashtable_iterator_init(&itr, h);
 223          hashtable_iterator_remove(&itr) != 0; ) {
 224         ;
 225     }
 226     printf("After removal, hashtable contains %u items.\n",
 227             hashtable_count(h));
 228
 229 /*****************************************************************************/
 230 /* Hashtable destroy */
 231
 232     hashtable_destroy(h, 1);
 233     free(k);
 234     return 0;
 235 }
 236
 237 /*
 238  * Copyright (c) 2002, 2004, Christopher Clark
 239  * All rights reserved.
 240  *
 241  * Redistribution and use in source and binary forms, with or without
 242  * modification, are permitted provided that the following conditions
 243  * are met:
 244  *
 245  * * Redistributions of source code must retain the above copyright
 246  * notice, this list of conditions and the following disclaimer.
 247  *
 248  * * Redistributions in binary form must reproduce the above copyright
 249  * notice, this list of conditions and the following disclaimer in the
 250  * documentation and/or other materials provided with the distribution.
 251  *
 252  * * Neither the name of the original author; nor the names of any contributors
 253  * may be used to endorse or promote products derived from this software
 254  * without specific prior written permission.
 255  *
 256  *
 257  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 258  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 259  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 260  * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER
 261  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 262  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 263  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 264  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 265  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 266  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 267  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 268 */