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(); 283