hash_test.c (11288B)
1 /* 2 * The MIT License (MIT) 3 * 4 * Copyright (c) 2015 Mikkel F. Jørgensen, dvide.com 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining a copy 7 * of this software and associated documentation files (the "Software"), to deal 8 * in the Software without restriction, including without limitation the rights 9 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 10 * copies of the Software, and to permit persons to whom the Software is 11 * furnished to do so, subject to the following conditions: 12 * 13 * The above copyright notice and this permission notice shall be included in all 14 * copies or substantial portions of the Software. 15 * 16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 21 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 22 * SOFTWARE. 23 */ 24 25 #include <stdio.h> 26 #include <string.h> 27 #include <stdlib.h> 28 #include <assert.h> 29 30 /* Not used here, just included to catch compiler errors and warnings. */ 31 #include "hash.h" 32 33 #include "str_set.h" 34 #include "token_map.h" 35 #include "ht64.h" 36 #include "ht32.h" 37 #include "ht64rh.h" 38 #include "ht32rh.h" 39 40 #include "ht_trace.h" 41 42 #define test_assert(x) if (!(x)) { printf("Test failed at %s:%d\n", __FILE__, __LINE__); assert(0); exit(1); } 43 44 45 str_set_t S; 46 token_map_t TM; 47 48 char *keys[] = { 49 "foo", 50 "bar", 51 "baz", 52 "gimli", 53 "bofur" 54 }; 55 56 struct token tokens[5]; 57 58 void free_key(void *context, char *key) { 59 free(key); 60 } 61 62 void test_str_set() 63 { 64 int i; 65 char *s, *s0, *s1; 66 unsigned int n = sizeof(keys)/sizeof(keys[0]); 67 68 /* We rely on zero initialization here. */ 69 test_assert(str_set_count(&S) == 0); 70 for (i = 0; i < n; ++i) { 71 s = keys[i]; 72 /* We don't have to use strdup, but we test the 73 * allocation management and item replacement. */ 74 s = str_set_insert(&S, s, strlen(s), strdup(s), ht_keep); 75 test_assert(str_set_count(&S) == i + 1); 76 test_assert(s == 0); 77 } 78 test_assert(n == 5); 79 for (i = 0; i < n; ++i) { 80 s = keys[i]; 81 s = str_set_find(&S, s, strlen(s)); 82 test_assert(strcmp(s, keys[i]) == 0); 83 } 84 s = str_set_remove(&S, "gimlibofur", 5); 85 test_assert(strcmp(s, "gimli") == 0); 86 free(s); 87 test_assert(str_set_count(&S) == n - 1); 88 s = str_set_remove(&S, "gimlibofur", 5); 89 test_assert(s == 0); 90 test_assert(str_set_count(&S) == n - 1); 91 s = str_set_insert(&S, "foobarbaz", 6, 92 (s0 = strndup("foobarbaz", 6)), ht_keep); 93 test_assert(s == 0); 94 test_assert(str_set_count(&S) == n); 95 s = str_set_insert(&S, "foobarbaz", 6, 96 (s1 = strndup("foobarbaz", 6)), ht_keep); 97 test_assert(s == s0); 98 free(s1); 99 test_assert(str_set_count(&S) == n); 100 s = str_set_find(&S, "foobar", 6); 101 test_assert(s == s0); 102 s = str_set_insert(&S, "foobarbaz", 6, 103 (s1 = strndup("foobarbaz", 6)), ht_replace); 104 test_assert(s == s0); 105 free(s); 106 s = str_set_find(&S, "foobar", 6); 107 test_assert(s == s1); 108 s = str_set_find(&S, "foobarbaz", 9); 109 test_assert(s == 0); 110 str_set_destroy(&S, free_key, 0); 111 s = str_set_find(&S, "foobar", 6); 112 test_assert(s == 0); 113 for (i = 0; i < n; ++i) { 114 s = keys[i]; 115 s = str_set_find(&S, s, strlen(s)); 116 test_assert(s == 0); 117 } 118 } 119 120 void test_str_set2() 121 { 122 int i; 123 char *s, *s1; 124 unsigned int n = sizeof(keys)/sizeof(keys[0]); 125 126 for (i = 0; i < n; ++i) { 127 s = keys[i]; 128 str_set_insert(&S, s, strlen(s), s, ht_unique); 129 } 130 test_assert(str_set_count(&S) == n); 131 for (i = 0; i < n; ++i) { 132 s = keys[i]; 133 /* 134 * Unique and multi are the same logically, but different 135 * intentionally. 136 */ 137 str_set_insert(&S, s, strlen(s), s, ht_multi); 138 } 139 test_assert(str_set_count(&S) == 2 * n); 140 ht_trace_buckets(&S, "after double insert", 0, 8); 141 for (i = 0; i < n; ++i) { 142 s = keys[i]; 143 s1 = str_set_find(&S, s, strlen(s)); 144 test_assert(strcmp(s, s1) == 0); 145 } 146 for (i = 0; i < n; ++i) { 147 s = keys[i]; 148 s1 = str_set_remove(&S, s, strlen(s)); 149 test_assert(strcmp(s, s1) == 0); 150 test_assert(str_set_count(&S) == 2 * n - i - 1); 151 ht_trace_buckets(&S, "after single", 8, 8); 152 } 153 ht_trace_buckets(&S, "after first remove", 0, 8); 154 for (i = 0; i < n; ++i) { 155 s = keys[i]; 156 s1 = str_set_remove(&S, s, strlen(s)); 157 test_assert(strcmp(s, s1) == 0); 158 test_assert(str_set_count(&S) == n - i - 1); 159 } 160 ht_trace_buckets(&S, "efter second remove", 0, 8); 161 for (i = 0; i < n; ++i) { 162 s = keys[i]; 163 s1 = str_set_remove(&S, s, strlen(s)); 164 test_assert(s1 == 0); 165 test_assert(str_set_count(&S) == 0); 166 } 167 str_set_clear(&S); 168 } 169 170 void test_str_set3() 171 { 172 int i; 173 char *s, *s1; 174 unsigned int n = sizeof(keys)/sizeof(keys[0]); 175 176 for (i = 0; i < n; ++i) { 177 s = keys[i]; 178 str_set_insert_item(&S, s, ht_unique); 179 } 180 test_assert(str_set_count(&S) == n); 181 for (i = 0; i < n; ++i) { 182 s = keys[i]; 183 str_set_insert_item(&S, s, ht_keep); 184 } 185 test_assert(str_set_count(&S) == n); 186 for (i = 0; i < n; ++i) { 187 s = keys[i]; 188 s1 = str_set_find_item(&S, s); 189 test_assert(strcmp(s, s1) == 0); 190 } 191 s = keys[1]; 192 s1 = str_set_remove_item(&S, s); 193 /* 194 * This doesn't always hold, but here we 195 * are sure because of how we inserted data. 196 */ 197 test_assert(s == s1); 198 s1 = str_set_find_item(&S, s); 199 test_assert(s1 == 0); 200 str_set_clear(&S); 201 } 202 203 void test_str_set4() 204 { 205 char *s, *s1; 206 207 s = "dumble"; 208 str_set_insert_item(&S, "dumble", ht_keep); 209 s1 = str_set_find_item(&S, s); 210 /* TMnsert without replace. */ 211 str_set_insert_item(&S, "2dumble" + 1, ht_keep); 212 test_assert(s == s1); 213 s1 = str_set_find_item(&S, s); 214 test_assert(s == s1); 215 /* TMnsert with replace. */ 216 s1 = str_set_insert_item(&S, "2dumble" + 1, ht_replace); 217 /* Old value still returned. */ 218 test_assert(s == s1); 219 s1 = str_set_find_item(&S, s); 220 test_assert(s != s1); 221 /* New item returned. */ 222 test_assert(strcmp(s1 - 1, "2dumble") == 0); 223 str_set_clear(&S); 224 } 225 226 void visit_item_set(void *context, token_map_item_t item) 227 { 228 int *count = context; 229 ++*count; 230 } 231 232 void test_token_map() 233 { 234 int i, count; 235 token_map_item_t item; 236 unsigned int n = sizeof(keys)/sizeof(keys[0]); 237 238 test_assert(sizeof(tokens)/sizeof(item[0]) == n); 239 240 for (i = 0; i < n; ++i) { 241 tokens[i].token = keys[i]; 242 tokens[i].len = strlen(keys[i]); 243 } 244 for (i = 0; i < n; ++i) { 245 item = &tokens[i]; 246 token_map_insert(&TM, item->token, item->len, item, ht_unique); 247 } 248 count = 0; 249 token_map_visit(&TM, visit_item_set, &count); 250 test_assert(count == n); 251 252 for (i = 0; i < n; ++i) { 253 item = token_map_find(&TM, keys[i], strlen(keys[i])); 254 test_assert(item->type == 0); 255 item->type = 1; 256 } 257 for (i = 0; i < n; ++i) { 258 item = token_map_find_item(&TM, &tokens[i]); 259 test_assert(item->type == 1); 260 item->type = 2; 261 } 262 } 263 264 void test_ht32() 265 { 266 uint32_t keys[100]; 267 int i, j; 268 ht32_t ht; 269 uint32_t *x, *y; 270 271 ht32_init(&ht, 10); 272 for (i = 0; i < 100; ++i) { 273 keys[i] = i + 3398; 274 } 275 for (i = 0; i < 100; ++i) { 276 x = ht32_insert_item(&ht, &keys[i], ht_unique); 277 } 278 for (i = 0; i < 100; ++i) { 279 x = ht32_find_item(&ht, &keys[i]); 280 test_assert(x != 0); 281 test_assert(*x == i + 3398); 282 } 283 for (i = 0; i < 100; ++i) { 284 y = ht32_remove_item(&ht, &keys[i]); 285 test_assert(y != ht32_missing); 286 for (j = 0; j < 100; ++j) { 287 x = ht32_find_item(&ht, &keys[j]); 288 if (j > i) { 289 test_assert(x != ht32_missing); 290 test_assert(*x == j + 3398); 291 } else { 292 test_assert(x == ht32_missing); 293 } 294 } 295 } 296 ht32_clear(&ht); 297 } 298 299 void test_ht64() 300 { 301 uint64_t keys[100]; 302 int i, j; 303 ht64_t ht; 304 uint64_t *x, *y; 305 306 ht64_init(&ht, 10); 307 for (i = 0; i < 100; ++i) { 308 keys[i] = i + 3398; 309 } 310 for (i = 0; i < 100; ++i) { 311 x = ht64_insert_item(&ht, &keys[i], ht_unique); 312 } 313 for (i = 0; i < 100; ++i) { 314 x = ht64_find_item(&ht, &keys[i]); 315 test_assert(x != 0); 316 test_assert(*x == i + 3398); 317 } 318 for (i = 0; i < 100; ++i) { 319 y = ht64_remove_item(&ht, &keys[i]); 320 test_assert(y != ht64_missing); 321 for (j = 0; j < 100; ++j) { 322 x = ht64_find_item(&ht, &keys[j]); 323 if (j > i) { 324 test_assert(x != ht64_missing); 325 test_assert(*x == j + 3398); 326 } else { 327 test_assert(x == ht64_missing); 328 } 329 } 330 } 331 ht64_clear(&ht); 332 } 333 334 void test_ht32rh() 335 { 336 uint32_t keys[100]; 337 int i, j; 338 ht32rh_t ht; 339 uint32_t *x, *y; 340 341 ht32rh_init(&ht, 10); 342 for (i = 0; i < 100; ++i) { 343 keys[i] = i + 3398; 344 } 345 for (i = 0; i < 100; ++i) { 346 x = ht32rh_insert_item(&ht, &keys[i], ht_unique); 347 } 348 for (i = 0; i < 100; ++i) { 349 x = ht32rh_find_item(&ht, &keys[i]); 350 test_assert(x != 0); 351 test_assert(*x == i + 3398); 352 } 353 for (i = 0; i < 100; ++i) { 354 y = ht32rh_remove_item(&ht, &keys[i]); 355 test_assert(y != ht32rh_missing); 356 for (j = 0; j < 100; ++j) { 357 x = ht32rh_find_item(&ht, &keys[j]); 358 if (j > i) { 359 test_assert(x != ht32rh_missing); 360 test_assert(*x == j + 3398); 361 } else { 362 test_assert(x == ht32rh_missing); 363 } 364 } 365 } 366 ht32rh_clear(&ht); 367 } 368 369 void test_ht64rh() 370 { 371 uint64_t keys[100]; 372 int i, j; 373 ht64rh_t ht; 374 uint64_t *x, *y; 375 376 ht64rh_init(&ht, 10); 377 for (i = 0; i < 100; ++i) { 378 keys[i] = i + 3398; 379 } 380 for (i = 0; i < 100; ++i) { 381 x = ht64rh_insert_item(&ht, &keys[i], ht_unique); 382 } 383 for (i = 0; i < 100; ++i) { 384 x = ht64rh_find_item(&ht, &keys[i]); 385 test_assert(x != 0); 386 test_assert(*x == i + 3398); 387 } 388 for (i = 0; i < 100; ++i) { 389 y = ht64rh_remove_item(&ht, &keys[i]); 390 test_assert(y != ht64rh_missing); 391 for (j = 0; j < 100; ++j) { 392 x = ht64rh_find_item(&ht, &keys[j]); 393 if (j > i) { 394 test_assert(x != ht64rh_missing); 395 test_assert(*x == j + 3398); 396 } else { 397 test_assert(x == ht64rh_missing); 398 } 399 } 400 } 401 ht64rh_clear(&ht); 402 } 403 404 int main(int argc, char *argv[]) 405 { 406 test_str_set(); 407 test_str_set2(); 408 test_str_set3(); 409 test_str_set4(); 410 test_token_map(); 411 test_ht32(); 412 test_ht64(); 413 test_ht32rh(); 414 test_ht64rh(); 415 416 printf("all tests passed\n"); 417 418 return 0; 419 }