src/libstrongswan/tests/test_hashtable.c

   1 /*
   2  * Copyright (C) 2010-2013 Tobias Brunner
   3  * Hochschule fuer Technik Rapperswil
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; either version 2 of the License, or (at your
   8  * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * for more details.
  14  */
  15
  16 #include "test_suite.h"
  17
  18 #include <collections/hashtable.h>
  19 #include <utils/chunk.h>
  20
  21 /*******************************************************************************
  22  * string hash table functions
  23  */
  24
  25 static u_int hash(char *key)
  26 {
  27         return chunk_hash(chunk_from_str(key));
  28 }
  29
  30 static bool equals(char *key1, char *key2)
  31 {
  32         return streq(key1, key2);
  33 }
  34
  35 /*******************************************************************************
  36  * test fixture
  37  */
  38
  39 static hashtable_t *ht;
  40
  41 START_SETUP(setup_ht)
  42 {
  43         ht = hashtable_create((hashtable_hash_t)hash,
  44                                                   (hashtable_equals_t)equals, 0);
  45         ck_assert_int_eq(ht->get_count(ht), 0);
  46 }
  47 END_SETUP
  48
  49 START_TEARDOWN(teardown_ht)
  50 {
  51         ht->destroy(ht);
  52 }
  53 END_TEARDOWN
  54
  55 /*******************************************************************************
  56  * put/get
  57  */
  58
  59 START_TEST(test_put_get)
  60 {
  61         char *k1 = "key1", *k2 = "key2", *k3 = "key3";
  62         char *v1 = "val1", *v2 = "val2", *v3 = "val3", *value;
  63
  64         value = ht->put(ht, k1, v1);
  65         ck_assert_int_eq(ht->get_count(ht), 1);
  66         ck_assert(streq(ht->get(ht, k1), v1));
  67         ck_assert(ht->get(ht, k2) == NULL);
  68         ck_assert(ht->get(ht, k3) == NULL);
  69         ck_assert(value == NULL);
  70
  71         ht->put(ht, k2, v2);
  72         ht->put(ht, k3, v3);
  73         ck_assert_int_eq(ht->get_count(ht), 3);
  74         ck_assert(streq(ht->get(ht, k1), v1));
  75         ck_assert(streq(ht->get(ht, k2), v2));
  76         ck_assert(streq(ht->get(ht, k3), v3));
  77
  78         value = ht->put(ht, k2, v1);
  79         ck_assert_int_eq(ht->get_count(ht), 3);
  80         ck_assert(streq(value, v2));
  81         ck_assert(streq(ht->get(ht, k2), v1));
  82 }
  83 END_TEST
  84
  85 /*******************************************************************************
  86  * get_match
  87  */
  88
  89 static u_int hash_match(char *key)
  90 {
  91         return chunk_hash(chunk_create(key, 4));
  92 }
  93
  94 static bool equal_match(char *key1, char *key2)
  95 {
  96         if (!strneq(key1, key2, 4))
  97         {
  98                 return FALSE;
  99         }
 100         /* look for an item with a key < than what we look for */
 101         return strcmp(key1, key2) >= 0;
 102 }
 103
 104 START_TEST(test_get_match)
 105 {
 106         char *k1 = "key1_a", *k2 = "key2", *k3 = "key1_b", *k4 = "key1_c";
 107         char *v1 = "val1", *v2 = "val2", *v3 = "val3", *value;
 108
 109         ht = hashtable_create((hashtable_hash_t)hash_match,
 110                                                   (hashtable_equals_t)equals, 0);
 111
 112         ht->put(ht, k1, v1);
 113         ht->put(ht, k2, v2);
 114         value = ht->put(ht, k3, v3);
 115         ck_assert_int_eq(ht->get_count(ht), 3);
 116         ck_assert(streq(ht->get(ht, k1), v1));
 117         ck_assert(streq(ht->get(ht, k2), v2));
 118         ck_assert(streq(ht->get(ht, k3), v3));
 119         ck_assert(value == NULL);
 120
 121         value = ht->get_match(ht, k1, (hashtable_equals_t)equal_match);
 122         ck_assert(value != NULL);
 123         ck_assert(streq(value, v1));
 124         value = ht->get_match(ht, k2, (hashtable_equals_t)equal_match);
 125         ck_assert(value != NULL);
 126         ck_assert(streq(value, v2));
 127         value = ht->get_match(ht, k3, (hashtable_equals_t)equal_match);
 128         ck_assert(value != NULL);
 129         ck_assert(streq(value, v1));
 130         value = ht->get_match(ht, k4, (hashtable_equals_t)equal_match);
 131         ck_assert(value != NULL);
 132         ck_assert(streq(value, v1));
 133
 134         ht->destroy(ht);
 135 }
 136 END_TEST
 137
 138 /*******************************************************************************
 139  * remove
 140  */
 141
 142 static void do_remove(char *k1, char *k2, char *k3)
 143 {
 144         char *v1 = "val1", *v2 = "val2", *v3 = "val3", *value;
 145
 146         ht->put(ht, k1, v1);
 147         ht->put(ht, k2, v2);
 148         ht->put(ht, k3, v3);
 149
 150         value = ht->remove(ht, k2);
 151         ck_assert_int_eq(ht->get_count(ht), 2);
 152         ck_assert(streq(ht->get(ht, k1), v1));
 153         ck_assert(streq(ht->get(ht, k3), v3));
 154         ck_assert(streq(value, v2));
 155         ck_assert(ht->get(ht, k2) == NULL);
 156
 157         value = ht->remove(ht, k2);
 158         ck_assert_int_eq(ht->get_count(ht), 2);
 159         ck_assert(value == NULL);
 160
 161         value = ht->remove(ht, k1);
 162         value = ht->remove(ht, k3);
 163         ck_assert_int_eq(ht->get_count(ht), 0);
 164         ck_assert(ht->get(ht, k1) == NULL);
 165         ck_assert(ht->get(ht, k2) == NULL);
 166         ck_assert(ht->get(ht, k3) == NULL);
 167 }
 168
 169 START_TEST(test_remove)
 170 {
 171         char *k1 = "key1", *k2 = "key2", *k3 = "key3";
 172
 173         do_remove(k1, k2, k3);
 174 }
 175 END_TEST
 176
 177 START_TEST(test_remove_one_bucket)
 178 {
 179         char *k1 = "key1_a", *k2 = "key1_b", *k3 = "key1_c";
 180
 181         ht->destroy(ht);
 182         /* set a capacity to avoid rehashing, which would change the items' order */
 183         ht = hashtable_create((hashtable_hash_t)hash_match,
 184                                                   (hashtable_equals_t)equals, 8);
 185
 186         do_remove(k1, k2, k3);
 187 }
 188 END_TEST
 189
 190 /*******************************************************************************
 191  * enumerator
 192  */
 193
 194 START_TEST(test_enumerator)
 195 {
 196         char *k1 = "key1", *k2 = "key2", *k3 = "key3", *key;
 197         char *v1 = "val1", *v2 = "val2", *v3 = "val3", *value;
 198         enumerator_t *enumerator;
 199         int count;
 200
 201         ht->put(ht, k1, v1);
 202         ht->put(ht, k2, v2);
 203         ht->put(ht, k3, v3);
 204
 205         count = 0;
 206         enumerator = ht->create_enumerator(ht);
 207         while (enumerator->enumerate(enumerator, &key, &value))
 208         {
 209                 ck_assert(streq(key, k1) || streq(key, k2) || streq(key, k3));
 210                 ck_assert(streq(value, v1) || streq(value, v2) || streq(value, v3));
 211                 ck_assert(!streq(key, k1) || streq(value, v1));
 212                 ck_assert(!streq(key, k2) || streq(value, v2));
 213                 ck_assert(!streq(key, k3) || streq(value, v3));
 214                 count++;
 215         }
 216         enumerator->destroy(enumerator);
 217         ck_assert_int_eq(count, 3);
 218
 219         count = 0;
 220         enumerator = ht->create_enumerator(ht);
 221         while (enumerator->enumerate(enumerator, NULL, NULL))
 222         {
 223                 count++;
 224         }
 225         enumerator->destroy(enumerator);
 226         ck_assert_int_eq(count, 3);
 227
 228         value = ht->remove(ht, k1);
 229         value = ht->remove(ht, k2);
 230         value = ht->remove(ht, k3);
 231
 232         count = 0;
 233         enumerator = ht->create_enumerator(ht);
 234         while (enumerator->enumerate(enumerator, &key, &value))
 235         {
 236                 count++;
 237         }
 238         enumerator->destroy(enumerator);
 239         ck_assert_int_eq(count, 0);
 240 }
 241 END_TEST
 242
 243 /*******************************************************************************
 244  * remove_at
 245  */
 246
 247 static void do_remove_at(char *k1, char *k2, char *k3)
 248 {
 249         char *v1 = "val1", *v2 = "val2", *v3 = "val3", *value, *key;
 250         enumerator_t *enumerator;
 251
 252         ht->put(ht, k1, v1);
 253         ht->put(ht, k2, v2);
 254         ht->put(ht, k3, v3);
 255
 256         enumerator = ht->create_enumerator(ht);
 257         ht->remove_at(ht, enumerator);
 258         while (enumerator->enumerate(enumerator, &key, &value))
 259         {
 260                 if (streq(key, k2))
 261                 {
 262                         ht->remove_at(ht, enumerator);
 263                 }
 264         }
 265         enumerator->destroy(enumerator);
 266
 267         ck_assert_int_eq(ht->get_count(ht), 2);
 268         ck_assert(ht->get(ht, k1) != NULL);
 269         ck_assert(ht->get(ht, k3) != NULL);
 270         ck_assert(ht->get(ht, k2) == NULL);
 271
 272         ht->put(ht, k2, v2);
 273
 274         ck_assert_int_eq(ht->get_count(ht), 3);
 275         ck_assert(ht->get(ht, k1) != NULL);
 276         ck_assert(ht->get(ht, k2) != NULL);
 277         ck_assert(ht->get(ht, k3) != NULL);
 278
 279         enumerator = ht->create_enumerator(ht);
 280         while (enumerator->enumerate(enumerator, &key, &value))
 281         {
 282                 ht->remove_at(ht, enumerator);
 283         }
 284         enumerator->destroy(enumerator);
 285
 286         ck_assert_int_eq(ht->get_count(ht), 0);
 287         ck_assert(ht->get(ht, k1) == NULL);
 288         ck_assert(ht->get(ht, k2) == NULL);
 289         ck_assert(ht->get(ht, k3) == NULL);
 290 }
 291
 292 START_TEST(test_remove_at)
 293 {
 294         char *k1 = "key1", *k2 = "key2", *k3 = "key3";
 295
 296         do_remove_at(k1, k2, k3);
 297 }
 298 END_TEST
 299
 300 START_TEST(test_remove_at_one_bucket)
 301 {
 302         char *k1 = "key1_a", *k2 = "key1_b", *k3 = "key1_c";
 303
 304         ht->destroy(ht);
 305         /* set a capacity to avoid rehashing, which would change the items' order */
 306         ht = hashtable_create((hashtable_hash_t)hash_match,
 307                                                   (hashtable_equals_t)equals, 8);
 308         do_remove_at(k1, k2, k3);
 309 }
 310 END_TEST
 311
 312 Suite *hashtable_suite_create()
 313 {
 314         Suite *s;
 315         TCase *tc;
 316
 317         s = suite_create("hashtable");
 318
 319         tc = tcase_create("put/get");
 320         tcase_add_checked_fixture(tc, setup_ht, teardown_ht);
 321         tcase_add_test(tc, test_put_get);
 322         suite_add_tcase(s, tc);
 323
 324         tc = tcase_create("get_match");
 325         tcase_add_test(tc, test_get_match);
 326         suite_add_tcase(s, tc);
 327
 328         tc = tcase_create("remove");
 329         tcase_add_checked_fixture(tc, setup_ht, teardown_ht);
 330         tcase_add_test(tc, test_remove);
 331         tcase_add_test(tc, test_remove_one_bucket);
 332         suite_add_tcase(s, tc);
 333
 334         tc = tcase_create("enumerator");
 335         tcase_add_checked_fixture(tc, setup_ht, teardown_ht);
 336         tcase_add_test(tc, test_enumerator);
 337         suite_add_tcase(s, tc);
 338
 339         tc = tcase_create("remove_at");
 340         tcase_add_checked_fixture(tc, setup_ht, teardown_ht);
 341         tcase_add_test(tc, test_remove_at);
 342         tcase_add_test(tc, test_remove_at_one_bucket);
 343         suite_add_tcase(s, tc);
 344
 345         return s;
 346 }