lib/hash-test.c

   1 /* Tests for hash table routines */
   2
   3 #include "lib/lib.h"
   4 #include "lib/mempool.h"
   5
   6 #include <stdio.h>
   7 #include <string.h>
   8 #include <stdlib.h>
   9
  10 /* TEST 1: integers */
  11
  12 struct node1 {
  13   int key;
  14   int data;
  15 };
  16
  17 #define HASH_NODE struct node1
  18 #define HASH_PREFIX(x) test1_##x
  19 #define HASH_KEY_ATOMIC key
  20 #define HASH_ATOMIC_TYPE int
  21 #define HASH_ZERO_FILL
  22
  23 #define HASH_GIVE_INIT_DATA
  24 static inline void test1_init_data(struct node1 *n)
  25 {
  26   n->data = n->key + 123;
  27 }
  28
  29 #define HASH_WANT_FIND
  30 #define HASH_WANT_LOOKUP
  31 #define HASH_WANT_REMOVE
  32
  33 #include "lib/hashtable.h"
  34
  35 static void test1(void)
  36 {
  37   int i;
  38
  39   test1_init();
  40   for (i=0; i<1024; i++)
  41     {
  42       struct node1 *n = test1_lookup(i);
  43       ASSERT(n->data == i+123);
  44     }
  45   for (i=1; i<1024; i+=2)
  46     {
  47       struct node1 *n = test1_lookup(i);
  48       test1_remove(n);
  49     }
  50   for (i=0; i<1024; i++)
  51     {
  52       struct node1 *n = test1_find(i);
  53       if (!n != (i&1) || (n && n->data != i+123))
  54         die("Inconsistency at i=%d", i);
  55     }
  56   i=0;
  57   HASH_FOR_ALL(test1, n)
  58     {
  59       i += 1 + n->key;
  60     }
  61   HASH_END_FOR;
  62   ASSERT(i == 262144);
  63   puts("OK");
  64 }
  65
  66 /* TEST 2: external strings */
  67
  68 struct node2 {
  69   char *key;
  70   int data;
  71 };
  72
  73 #define HASH_NODE struct node2
  74 #define HASH_PREFIX(x) test2_##x
  75 #define HASH_KEY_STRING key
  76 #define HASH_NOCASE
  77 #define HASH_AUTO_POOL 4096
  78
  79 #define HASH_WANT_FIND
  80 #define HASH_WANT_NEW
  81
  82 #include "lib/hashtable.h"
  83
  84 static void test2(void)
  85 {
  86   int i;
  87
  88   test2_init();
  89   for (i=0; i<1024; i+=2)
  90     {
  91       char x[32];
  92       sprintf(x, "abc%d", i);
  93       test2_new(xstrdup(x));
  94     }
  95   for (i=0; i<1024; i++)
  96     {
  97       char x[32];
  98       struct node2 *n;
  99       sprintf(x, "ABC%d", i);
 100       n = test2_find(x);
 101       if (!n != (i&1))
 102         die("Inconsistency at i=%d", i);
 103     }
 104   puts("OK");
 105 }
 106
 107 /* TEST 3: internal strings + pools */
 108
 109 static struct mempool *pool3;
 110
 111 struct node3 {
 112   int data;
 113   char key[1];
 114 };
 115
 116 #define HASH_NODE struct node3
 117 #define HASH_PREFIX(x) test3_##x
 118 #define HASH_KEY_ENDSTRING key
 119
 120 #define HASH_WANT_FIND
 121 #define HASH_WANT_NEW
 122
 123 #define HASH_USE_POOL pool3
 124
 125 #include "lib/hashtable.h"
 126
 127 static void test3(void)
 128 {
 129   int i;
 130
 131   pool3 = mp_new(16384);
 132   test3_init();
 133   for (i=0; i<1048576; i+=2)
 134     {
 135       char x[32];
 136       sprintf(x, "abc%d", i);
 137       test3_new(x);
 138     }
 139   for (i=0; i<1048576; i++)
 140     {
 141       char x[32];
 142       struct node3 *n;
 143       sprintf(x, "abc%d", i);
 144       n = test3_find(x);
 145       if (!n != (i&1))
 146         die("Inconsistency at i=%d", i);
 147     }
 148   puts("OK");
 149 }
 150
 151 /* TEST 4: complex keys */
 152
 153 #include "lib/hashfunc.h"
 154
 155 struct node4 {
 156   int port;
 157   int data;
 158   char host[1];
 159 };
 160
 161 #define HASH_NODE struct node4
 162 #define HASH_PREFIX(x) test4_##x
 163 #define HASH_KEY_COMPLEX(x) x host, x port
 164 #define HASH_KEY_DECL char *host, int port
 165
 166 #define HASH_WANT_CLEANUP
 167 #define HASH_WANT_FIND
 168 #define HASH_WANT_NEW
 169 #define HASH_WANT_LOOKUP
 170 #define HASH_WANT_DELETE
 171 #define HASH_WANT_REMOVE
 172
 173 #define HASH_GIVE_HASHFN
 174 static uns test4_hash(char *host, int port)
 175 {
 176   return hash_string_nocase(host) ^ hash_u32(port);
 177 }
 178
 179 #define HASH_GIVE_EQ
 180 static inline int test4_eq(char *host1, int port1, char *host2, int port2)
 181 {
 182   return !strcasecmp(host1,host2) && port1 == port2;
 183 }
 184
 185 #define HASH_GIVE_EXTRA_SIZE
 186 static inline uns test4_extra_size(char *host, int port UNUSED)
 187 {
 188   return strlen(host);
 189 }
 190
 191 #define HASH_GIVE_INIT_KEY
 192 static inline void test4_init_key(struct node4 *n, char *host, int port)
 193 {
 194   strcpy(n->host, host);
 195   n->port = port;
 196 }
 197
 198 #include "lib/hashtable.h"
 199
 200 static void test4(void)
 201 {
 202   int i;
 203   char x[32];
 204   struct node4 *n;
 205
 206   test4_init();
 207   for (i=0; i<1024; i++)
 208     if ((i % 3) == 0)
 209       {
 210         sprintf(x, "abc%d", i);
 211         n = test4_new(x, i%10);
 212         n->data = i;
 213       }
 214   for (i=0; i<1024; i++)
 215     {
 216       sprintf(x, "abc%d", i);
 217       n = test4_lookup(x, i%10);
 218       n->data = i;
 219     }
 220   for (i=0; i<1024; i++)
 221     if (i % 2)
 222       {
 223         sprintf(x, "aBc%d", i);
 224         if ((i % 7) < 3)
 225           {
 226             n = test4_find(x, i%10);
 227             ASSERT(n);
 228             test4_remove(n);
 229           }
 230         else
 231           test4_delete(x, i%10);
 232       }
 233   for (i=0; i<1024; i++)
 234     {
 235       sprintf(x, "ABC%d", i);
 236       n = test4_find(x, i%10);
 237       if (!n != (i&1) || (n && n->data != i))
 238         die("Inconsistency at i=%d", i);
 239     }
 240   test4_cleanup();
 241   puts("OK");
 242 }
 243
 244 /* TEST 5: integers again, but this time dynamically */
 245
 246 struct node5 {
 247   int key;
 248   int data;
 249 };
 250
 251 #define HASH_NODE struct node5
 252 #define HASH_PREFIX(x) test5_##x
 253 #define HASH_KEY_ATOMIC key
 254 #define HASH_ATOMIC_TYPE int
 255 #define HASH_TABLE_DYNAMIC
 256
 257 struct test5_table;
 258
 259 #define HASH_GIVE_INIT_DATA
 260 static inline void test5_init_data(struct test5_table *table UNUSED, struct node5 *n)
 261 {
 262   n->data = n->key + 123;
 263 }
 264
 265 #define HASH_WANT_FIND
 266 #define HASH_WANT_NEW
 267 #define HASH_WANT_DELETE
 268
 269 #include "lib/hashtable.h"
 270
 271 static void test5(void)
 272 {
 273   int i;
 274   struct test5_table tab;
 275
 276   test5_init(&tab);
 277   for (i=0; i<1024; i++)
 278     {
 279       struct node5 *n = test5_new(&tab, i);
 280       ASSERT(n->data == i+123);
 281     }
 282   for (i=1; i<1024; i+=2)
 283     test5_delete(&tab, i);
 284   for (i=0; i<1024; i++)
 285     {
 286       struct node5 *n = test5_find(&tab, i);
 287       if (!n != (i&1) || (n && n->data != i+123))
 288         die("Inconsistency at i=%d", i);
 289     }
 290   i=0;
 291   HASH_FOR_ALL_DYNAMIC(test5, &tab, n)
 292     i += 1 + n->key;
 293   HASH_END_FOR;
 294   ASSERT(i == 262144);
 295   puts("OK");
 296 }
 297
 298 int
 299 main(int argc, char **argv)
 300 {
 301   uns m = ~0U;
 302   if (argc > 1)
 303     {
 304       m = 0;
 305       for (int i=1; i<argc; i++)
 306         m |= 1 << atol(argv[i]);
 307     }
 308   if (m & (1 << 1))
 309     test1();
 310   if (m & (1 << 2))
 311     test2();
 312   if (m & (1 << 3))
 313     test3();
 314   if (m & (1 << 4))
 315     test4();
 316   if (m & (1 << 5))
 317     test5();
 318   return 0;
 319 }