testsuite/test-hash.c

   1 /*
   2  * Copyright (C)  2014 Intel Corporation. All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16  */
  17
  18 #include <errno.h>
  19 #include <stddef.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <unistd.h>
  24
  25 #include <shared/hash.h>
  26 #include <shared/util.h>
  27
  28 #include "testsuite.h"
  29
  30 static int freecount;
  31
  32 static void countfreecalls(void *v)
  33 {
  34         freecount++;
  35 }
  36
  37 static int test_hash_new(const struct test *t)
  38 {
  39         struct hash *h = hash_new(8, NULL);
  40         assert_return(h != NULL, EXIT_FAILURE);
  41         hash_free(h);
  42         return 0;
  43 }
  44 DEFINE_TEST(test_hash_new,
  45                 .description = "test hash_new");
  46
  47
  48 static int test_hash_get_count(const struct test *t)
  49 {
  50         struct hash *h = hash_new(8, NULL);
  51         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
  52         const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
  53
  54         hash_add(h, k1, v1);
  55         hash_add(h, k2, v2);
  56         hash_add(h, k3, v3);
  57
  58         assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
  59
  60         hash_free(h);
  61         return 0;
  62 }
  63 DEFINE_TEST(test_hash_get_count,
  64                 .description = "test hash_add / hash_get_count");
  65
  66
  67 static int test_hash_replace(const struct test *t)
  68 {
  69         struct hash *h = hash_new(8, countfreecalls);
  70         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
  71         const char *v1 = "v1", *v2 = "v2", *v3 = "v3", *v4 = "v4";
  72         const char *v;
  73         int r = 0;
  74
  75         r |= hash_add(h, k1, v1);
  76         r |= hash_add(h, k2, v2);
  77         r |= hash_add(h, k3, v3);
  78
  79         /* replace v1 */
  80         r |= hash_add(h, k1, v4);
  81
  82         assert_return(r == 0, EXIT_FAILURE);
  83         assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
  84
  85         v = hash_find(h, "k1");
  86         assert_return(streq(v, v4), EXIT_FAILURE);
  87
  88         assert_return(freecount == 1, EXIT_FAILURE);
  89
  90         hash_free(h);
  91         return 0;
  92 }
  93 DEFINE_TEST(test_hash_replace,
  94                 .description = "test hash_add replacing existing value");
  95
  96
  97 static int test_hash_replace_failing(const struct test *t)
  98 {
  99         struct hash *h = hash_new(8, countfreecalls);
 100         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
 101         const char *v1 = "v1", *v2 = "v2", *v3 = "v3", *v4 = "v4";
 102         const char *v;
 103         int r = 0;
 104
 105         r |= hash_add(h, k1, v1);
 106         r |= hash_add(h, k2, v2);
 107         r |= hash_add(h, k3, v3);
 108
 109         assert_return(r == 0, EXIT_FAILURE);
 110
 111         /* replace v1 */
 112         r = hash_add_unique(h, k1, v4);
 113         assert_return(r != 0, EXIT_FAILURE);
 114         assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
 115
 116         v = hash_find(h, "k1");
 117         assert_return(streq(v, v1), EXIT_FAILURE);
 118
 119         assert_return(freecount == 0, EXIT_FAILURE);
 120
 121         hash_free(h);
 122         return 0;
 123 }
 124 DEFINE_TEST(test_hash_replace_failing,
 125                 .description = "test hash_add_unique failing to replace existing value");
 126
 127
 128 static int test_hash_iter(const struct test *t)
 129 {
 130         struct hash *h = hash_new(8, NULL);
 131         struct hash *h2 = hash_new(8, NULL);
 132         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
 133         const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
 134         struct hash_iter iter;
 135         const char *k, *v;
 136
 137         hash_add(h, k1, v1);
 138         hash_add(h2, k1, v1);
 139         hash_add(h, k2, v2);
 140         hash_add(h2, k2, v2);
 141         hash_add(h, k3, v3);
 142         hash_add(h2, k3, v3);
 143
 144         for (hash_iter_init(h, &iter);
 145              hash_iter_next(&iter, &k, (const void **) &v);) {
 146                 v2 = hash_find(h2, k);
 147                 assert_return(v2 != NULL, EXIT_FAILURE);
 148                 hash_del(h2, k);
 149         }
 150
 151         assert_return(hash_get_count(h) == 3, EXIT_FAILURE);
 152         assert_return(hash_get_count(h2) == 0, EXIT_FAILURE);
 153
 154         hash_free(h);
 155         hash_free(h2);
 156         return 0;
 157 }
 158 DEFINE_TEST(test_hash_iter,
 159                 .description = "test hash_iter");
 160
 161
 162 static int test_hash_iter_after_del(const struct test *t)
 163 {
 164         struct hash *h = hash_new(8, NULL);
 165         struct hash *h2 = hash_new(8, NULL);
 166         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
 167         const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
 168         struct hash_iter iter;
 169         const char *k, *v;
 170
 171         hash_add(h, k1, v1);
 172         hash_add(h2, k1, v1);
 173         hash_add(h, k2, v2);
 174         hash_add(h2, k2, v2);
 175         hash_add(h, k3, v3);
 176         hash_add(h2, k3, v3);
 177
 178         hash_del(h, k1);
 179
 180         for (hash_iter_init(h, &iter);
 181              hash_iter_next(&iter, &k, (const void **) &v);) {
 182                 v2 = hash_find(h2, k);
 183                 assert_return(v2 != NULL, EXIT_FAILURE);
 184                 hash_del(h2, k);
 185         }
 186
 187         assert_return(hash_get_count(h) == 2, EXIT_FAILURE);
 188         assert_return(hash_get_count(h2) == 1, EXIT_FAILURE);
 189
 190         hash_free(h);
 191         hash_free(h2);
 192         return 0;
 193 }
 194 DEFINE_TEST(test_hash_iter_after_del,
 195                 .description = "test hash_iter, after deleting element");
 196
 197
 198 static int test_hash_free(const struct test *t)
 199 {
 200         struct hash *h = hash_new(8, countfreecalls);
 201         const char *k1 = "k1", *k2 = "k2", *k3 = "k3";
 202         const char *v1 = "v1", *v2 = "v2", *v3 = "v3";
 203
 204         hash_add(h, k1, v1);
 205         hash_add(h, k2, v2);
 206         hash_add(h, k3, v3);
 207
 208         hash_del(h, k1);
 209
 210         assert_return(freecount == 1, EXIT_FAILURE);
 211
 212         assert_return(hash_get_count(h) == 2, EXIT_FAILURE);
 213
 214         hash_free(h);
 215
 216         assert_return(freecount == 3, EXIT_FAILURE);
 217
 218         return 0;
 219 }
 220 DEFINE_TEST(test_hash_free,
 221                 .description = "test hash_free calling free function for all values");
 222
 223
 224 static int test_hash_add_unique(const struct test *t)
 225 {
 226         const char *k[] = { "k1", "k2", "k3", "k4", "k5" };
 227         const char *v[] = { "v1", "v2", "v3", "v4", "v5" };
 228         unsigned int i, j, N;
 229
 230         N = ARRAY_SIZE(k);
 231         for (i = 0; i < N; i++) {
 232                 /* With N - 1 buckets, there'll be a bucket with more than one key. */
 233                 struct hash *h = hash_new(N - 1, NULL);
 234
 235                 /* Add the keys in different orders. */
 236                 for (j = 0; j < N; j++) {
 237                         unsigned int idx = (j + i) % N;
 238                         hash_add_unique(h, k[idx], v[idx]);
 239                 }
 240
 241                 assert_return(hash_get_count(h) == N, EXIT_FAILURE);
 242                 hash_free(h);
 243         }
 244         return 0;
 245 }
 246 DEFINE_TEST(test_hash_add_unique,
 247                 .description = "test hash_add_unique with different key orders")
 248
 249
 250 static int test_hash_massive_add_del(const struct test *t)
 251 {
 252         char buf[1024 * 8];
 253         char *k;
 254         struct hash *h;
 255         unsigned int i, N = 1024;
 256
 257         h = hash_new(8, NULL);
 258
 259         k = &buf[0];
 260         for (i = 0; i < N; i++) {
 261                 snprintf(k, 8, "k%d", i);
 262                 hash_add(h, k, k);
 263                 k += 8;
 264         }
 265
 266         assert_return(hash_get_count(h) == N, EXIT_FAILURE);
 267
 268         k = &buf[0];
 269         for (i = 0; i < N; i++) {
 270                 hash_del(h, k);
 271                 k += 8;
 272         }
 273
 274         assert_return(hash_get_count(h) == 0, EXIT_FAILURE);
 275
 276         hash_free(h);
 277         return 0;
 278 }
 279 DEFINE_TEST(test_hash_massive_add_del,
 280                 .description = "test multiple adds followed by multiple dels")
 281
 282 TESTSUITE_MAIN();