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