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