test/test_htable.c

   1 /*
   2  * TSM - Hashtable Tests
   3  *
   4  * Copyright (c) 2012-2013 David Herrmann <dh.herrmann@gmail.com>
   5  *
   6  * Permission is hereby granted, free of charge, to any person obtaining
   7  * a copy of this software and associated documentation files
   8  * (the "Software"), to deal in the Software without restriction, including
   9  * without limitation the rights to use, copy, modify, merge, publish,
  10  * distribute, sublicense, and/or sell copies of the Software, and to
  11  * permit persons to whom the Software is furnished to do so, subject to
  12  * the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included
  15  * in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  18  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  19  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  20  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  21  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  22  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  23  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24  */
  25
  26
  27 #include "test_common.h"
  28
  29 static struct shl_htable ht = SHL_HTABLE_INIT_STR(ht);
  30 static struct shl_htable uht = SHL_HTABLE_INIT_ULONG(uht);
  31
  32 struct node {
  33         char huge_padding[16384];
  34         uint8_t v;
  35         char paaaaaadding[16384];
  36         char *key;
  37         unsigned long ul;
  38         char more_padding[32768];
  39         size_t hash;
  40 };
  41
  42 #define to_node(_key) shl_htable_offsetof((_key), struct node, key)
  43 #define ul_to_node(_key) shl_htable_offsetof((_key), struct node, ul)
  44
  45 static struct node o[] = {
  46         { .v = 0, .key = "o0", .ul = 0 },
  47         { .v = 1, .key = "o1", .ul = 1 },
  48         { .v = 2, .key = "o2", .ul = 2 },
  49         { .v = 3, .key = "o3", .ul = 3 },
  50         { .v = 4, .key = "o4", .ul = 4 },
  51         { .v = 5, .key = "o5", .ul = 5 },
  52         { .v = 6, .key = "o6", .ul = 6 },
  53         { .v = 7, .key = "o7", .ul = 7 },
  54 };
  55
  56 static void test_htable_str_cb(char **k, void *ctx)
  57 {
  58         int *num = ctx;
  59
  60         ck_assert(to_node(k)->v == to_node(k)->ul);
  61         ++*num;
  62 }
  63
  64 START_TEST(test_htable_str)
  65 {
  66         int r, i, num;
  67         char **k;
  68         bool b;
  69
  70         /* insert once, remove once, try removing again */
  71
  72         ck_assert(!o[0].hash);
  73         r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash);
  74         ck_assert(!r);
  75         ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL));
  76
  77         b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k);
  78         ck_assert(b);
  79         ck_assert(k != NULL);
  80         ck_assert(to_node(k)->v == 0);
  81
  82         k = NULL;
  83         b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k);
  84         ck_assert(!b);
  85         ck_assert(k == NULL);
  86
  87         /* insert twice, remove twice, try removing again */
  88
  89         r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash);
  90         ck_assert(!r);
  91         ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL));
  92
  93         r = shl_htable_insert_str(&ht, &o[0].key, &o[0].hash);
  94         ck_assert(!r);
  95         ck_assert(o[0].hash == shl_htable_rehash_str(&o[0].key, NULL));
  96
  97         b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k);
  98         ck_assert(b);
  99         ck_assert(k != NULL);
 100         ck_assert(to_node(k)->v == 0);
 101
 102         b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k);
 103         ck_assert(b);
 104         ck_assert(k != NULL);
 105         ck_assert(to_node(k)->v == 0);
 106
 107         k = NULL;
 108         b = shl_htable_remove_str(&ht, o[0].key, &o[0].hash, &k);
 109         ck_assert(!b);
 110         ck_assert(k == NULL);
 111
 112         /* same as before but without hash-cache */
 113
 114         r = shl_htable_insert_str(&ht, &o[0].key, NULL);
 115         ck_assert(!r);
 116
 117         r = shl_htable_insert_str(&ht, &o[0].key, NULL);
 118         ck_assert(!r);
 119
 120         b = shl_htable_remove_str(&ht, o[0].key, NULL, &k);
 121         ck_assert(b);
 122         ck_assert(k != NULL);
 123         ck_assert(to_node(k)->v == 0);
 124
 125         b = shl_htable_remove_str(&ht, o[0].key, NULL, &k);
 126         ck_assert(b);
 127         ck_assert(k != NULL);
 128         ck_assert(to_node(k)->v == 0);
 129
 130         k = NULL;
 131         b = shl_htable_remove_str(&ht, o[0].key, NULL, &k);
 132         ck_assert(!b);
 133         ck_assert(k == NULL);
 134
 135         /* insert all elements and verify empty hash-caches */
 136
 137         o[0].hash = 0;
 138         for (i = 0; i < 8; ++i) {
 139                 ck_assert(!o[i].hash);
 140                 r = shl_htable_insert_str(&ht, &o[i].key, &o[i].hash);
 141                 ck_assert(!r);
 142                 ck_assert(o[i].hash == shl_htable_rehash_str(&o[i].key, NULL));
 143         }
 144
 145         /* verify */
 146
 147         for (i = 0; i < 8; ++i) {
 148                 k = NULL;
 149                 b = shl_htable_lookup_str(&ht, o[i].key, NULL, &k);
 150                 ck_assert(b);
 151                 ck_assert(k != NULL);
 152                 ck_assert(to_node(k)->v == i);
 153         }
 154
 155         /* remove all elements again */
 156
 157         for (i = 0; i < 8; ++i) {
 158                 b = shl_htable_remove_str(&ht, o[i].key, NULL, &k);
 159                 ck_assert(b);
 160                 ck_assert(k != NULL);
 161                 ck_assert(to_node(k)->v == i);
 162         }
 163
 164         /* verify they're gone */
 165
 166         for (i = 0; i < 8; ++i) {
 167                 k = NULL;
 168                 b = shl_htable_remove_str(&ht, o[i].key, NULL, &k);
 169                 ck_assert(!b);
 170                 ck_assert(k == NULL);
 171         }
 172
 173         for (i = 0; i < 8; ++i) {
 174                 k = NULL;
 175                 b = shl_htable_lookup_str(&ht, o[i].key, NULL, &k);
 176                 ck_assert(!b);
 177                 ck_assert(k == NULL);
 178         }
 179
 180         num = 0;
 181         shl_htable_visit_str(&ht, test_htable_str_cb, &num);
 182         ck_assert(num == 0);
 183
 184         num = 0;
 185         shl_htable_clear_str(&ht, test_htable_str_cb, &num);
 186         ck_assert(num == 0);
 187
 188         /* test shl_htable_clear_str() */
 189
 190         for (i = 0; i < 8; ++i) {
 191                 r = shl_htable_insert_str(&ht, &o[i].key, &o[i].hash);
 192                 ck_assert(!r);
 193         }
 194
 195         num = 0;
 196         shl_htable_visit_str(&ht, test_htable_str_cb, &num);
 197         ck_assert(num == 8);
 198
 199         num = 0;
 200         shl_htable_clear_str(&ht, test_htable_str_cb, &num);
 201         ck_assert(num == 8);
 202 }
 203 END_TEST
 204
 205 static void test_htable_ulong_cb(unsigned long *k, void *ctx)
 206 {
 207         int *num = ctx;
 208
 209         ck_assert(ul_to_node(k)->v == ul_to_node(k)->ul);
 210         ++*num;
 211 }
 212
 213 START_TEST(test_htable_ulong)
 214 {
 215         int r, i, num;
 216         unsigned long *k;
 217         bool b;
 218
 219         /* insert once, remove once, try removing again */
 220
 221         r = shl_htable_insert_ulong(&uht, &o[0].ul);
 222         ck_assert(!r);
 223         ck_assert(o[0].ul == shl_htable_rehash_ulong(&o[0].ul, NULL));
 224
 225         b = shl_htable_remove_ulong(&uht, o[0].ul, &k);
 226         ck_assert(b);
 227         ck_assert(k != NULL);
 228         ck_assert(ul_to_node(k)->v == 0);
 229
 230         k = NULL;
 231         b = shl_htable_remove_ulong(&uht, o[0].ul, &k);
 232         ck_assert(!b);
 233         ck_assert(k == NULL);
 234
 235         /* insert all */
 236
 237         for (i = 0; i < 8; ++i) {
 238                 r = shl_htable_insert_ulong(&uht, &o[i].ul);
 239                 ck_assert(!r);
 240         }
 241
 242         /* verify */
 243
 244         for (i = 0; i < 8; ++i) {
 245                 k = NULL;
 246                 b = shl_htable_lookup_ulong(&uht, o[i].ul, &k);
 247                 ck_assert(b);
 248                 ck_assert(k != NULL);
 249         }
 250
 251         /* remove all elements again */
 252
 253         for (i = 0; i < 8; ++i) {
 254                 b = shl_htable_remove_ulong(&uht, o[i].ul, &k);
 255                 ck_assert(b);
 256                 ck_assert(k != NULL);
 257                 ck_assert(ul_to_node(k)->v == i);
 258         }
 259
 260         /* verify they're gone */
 261
 262         for (i = 0; i < 8; ++i) {
 263                 k = NULL;
 264                 b = shl_htable_remove_ulong(&uht, o[i].ul, &k);
 265                 ck_assert(!b);
 266                 ck_assert(k == NULL);
 267         }
 268
 269         for (i = 0; i < 8; ++i) {
 270                 k = NULL;
 271                 b = shl_htable_lookup_ulong(&uht, o[i].ul, &k);
 272                 ck_assert(!b);
 273                 ck_assert(k == NULL);
 274         }
 275
 276         num = 0;
 277         shl_htable_visit_ulong(&uht, test_htable_ulong_cb, &num);
 278         ck_assert(num == 0);
 279
 280         num = 0;
 281         shl_htable_clear_ulong(&uht, test_htable_ulong_cb, &num);
 282         ck_assert(num == 0);
 283
 284         /* test shl_htable_clear_ulong() */
 285
 286         for (i = 0; i < 8; ++i) {
 287                 r = shl_htable_insert_ulong(&uht, &o[i].ul);
 288                 ck_assert(!r);
 289         }
 290
 291         num = 0;
 292         shl_htable_visit_ulong(&uht, test_htable_ulong_cb, &num);
 293         ck_assert(num == 8);
 294
 295         num = 0;
 296         shl_htable_clear_ulong(&uht, test_htable_ulong_cb, &num);
 297         ck_assert(num == 8);
 298 }
 299 END_TEST
 300
 301 TEST_DEFINE_CASE(misc)
 302         TEST(test_htable_str)
 303         TEST(test_htable_ulong)
 304 TEST_END_CASE
 305
 306 TEST_DEFINE(
 307         TEST_SUITE(hashtable,
 308                 TEST_CASE(misc),
 309                 TEST_END
 310         )
 311 )