1 /* $NetBSD: ht_test.c,v 1.3 2025/01/26 16:25:49 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 #include <inttypes.h> 17 #include <sched.h> /* IWYU pragma: keep */ 18 #include <setjmp.h> 19 #include <stdarg.h> 20 #include <stddef.h> 21 #include <stdio.h> 22 #include <stdlib.h> 23 #include <string.h> 24 25 #define UNIT_TESTING 26 #include <cmocka.h> 27 28 #include <isc/hash.h> 29 #include <isc/ht.h> 30 #include <isc/mem.h> 31 #include <isc/string.h> 32 #include <isc/util.h> 33 34 #include <tests/isc.h> 35 36 /* INCLUDE LAST */ 37 38 #define mctx __mctx 39 #include "ht.c" 40 #undef mctx 41 42 static void 43 test_ht_full(uint8_t init_bits, uintptr_t count) { 44 isc_ht_t *ht = NULL; 45 isc_result_t result; 46 uintptr_t i; 47 48 isc_ht_init(&ht, mctx, init_bits, ISC_HT_CASE_SENSITIVE); 49 assert_non_null(ht); 50 51 for (i = 1; i < count; i++) { 52 /* 53 * Note: snprintf() is followed with strlcat() 54 * to ensure we are always filling the 16 byte key. 55 */ 56 unsigned char key[16]; 57 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 58 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 59 result = isc_ht_add(ht, key, 16, (void *)i); 60 assert_int_equal(result, ISC_R_SUCCESS); 61 } 62 63 for (i = 1; i < count; i++) { 64 unsigned char key[16]; 65 void *f = NULL; 66 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 67 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 68 result = isc_ht_find(ht, key, 16, &f); 69 assert_int_equal(result, ISC_R_SUCCESS); 70 assert_ptr_equal((void *)i, (void *)f); 71 } 72 73 for (i = 1; i < count; i++) { 74 unsigned char key[16]; 75 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 76 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 77 result = isc_ht_add(ht, key, 16, (void *)i); 78 assert_int_equal(result, ISC_R_EXISTS); 79 } 80 81 for (i = 1; i < count; i++) { 82 char key[64]; 83 /* 84 * Note: the key size is now strlen(key) which is bigger 85 * then the keys added above. 86 */ 87 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 88 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 89 result = isc_ht_add(ht, (const unsigned char *)key, strlen(key), 90 (void *)i); 91 assert_int_equal(result, ISC_R_SUCCESS); 92 } 93 94 for (i = 1; i < count; i++) { 95 unsigned char key[16]; 96 void *f = NULL; 97 /* 98 * Note: case of KEY is now in capitals, 99 */ 100 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 101 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 102 result = isc_ht_find(ht, key, 16, &f); 103 assert_int_equal(result, ISC_R_NOTFOUND); 104 assert_null(f); 105 } 106 107 for (i = 1; i < count; i++) { 108 char key[64]; 109 void *f = NULL; 110 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 111 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 112 result = isc_ht_find(ht, (const unsigned char *)key, 113 strlen(key), &f); 114 assert_int_equal(result, ISC_R_SUCCESS); 115 assert_ptr_equal(f, (void *)i); 116 } 117 118 for (i = 1; i < count; i++) { 119 unsigned char key[16]; 120 void *f = NULL; 121 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 122 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 123 result = isc_ht_delete(ht, key, 16); 124 assert_int_equal(result, ISC_R_SUCCESS); 125 result = isc_ht_find(ht, key, 16, &f); 126 assert_int_equal(result, ISC_R_NOTFOUND); 127 assert_null(f); 128 } 129 130 for (i = 1; i < count; i++) { 131 unsigned char key[16]; 132 /* 133 * Note: upper case KEY. 134 */ 135 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 136 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 137 result = isc_ht_add(ht, key, 16, (void *)i); 138 assert_int_equal(result, ISC_R_SUCCESS); 139 } 140 141 for (i = 1; i < count; i++) { 142 char key[64]; 143 void *f = NULL; 144 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 145 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 146 result = isc_ht_delete(ht, (const unsigned char *)key, 147 strlen(key)); 148 assert_int_equal(result, ISC_R_SUCCESS); 149 result = isc_ht_find(ht, (const unsigned char *)key, 150 strlen(key), &f); 151 assert_int_equal(result, ISC_R_NOTFOUND); 152 assert_null(f); 153 } 154 155 for (i = 1; i < count; i++) { 156 unsigned char key[16]; 157 void *f = NULL; 158 /* 159 * Note: case of KEY is now in capitals, 160 */ 161 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 162 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 163 result = isc_ht_find(ht, key, 16, &f); 164 assert_int_equal(result, ISC_R_SUCCESS); 165 assert_ptr_equal((void *)i, (void *)f); 166 } 167 168 for (i = 1; i < count; i++) { 169 unsigned char key[16]; 170 void *f = NULL; 171 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 172 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 173 result = isc_ht_find(ht, key, 16, &f); 174 assert_int_equal(result, ISC_R_NOTFOUND); 175 assert_null(f); 176 } 177 178 isc_ht_destroy(&ht); 179 assert_null(ht); 180 } 181 182 static void 183 test_ht_iterator(void) { 184 isc_ht_t *ht = NULL; 185 isc_result_t result; 186 isc_ht_iter_t *iter = NULL; 187 uintptr_t i; 188 uintptr_t count = 7600; 189 uint32_t walked; 190 unsigned char key[16]; 191 size_t tksize; 192 193 isc_ht_init(&ht, mctx, HT_MIN_BITS, ISC_HT_CASE_SENSITIVE); 194 assert_non_null(ht); 195 for (i = 1; i <= count; i++) { 196 /* 197 * Note that the string we're snprintfing is always > 16 bytes 198 * so we are always filling the key. 199 */ 200 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 201 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 202 result = isc_ht_add(ht, key, 16, (void *)i); 203 assert_int_equal(result, ISC_R_SUCCESS); 204 } 205 206 /* We want to iterate while rehashing is in progress */ 207 assert_true(rehashing_in_progress(ht)); 208 209 walked = 0; 210 isc_ht_iter_create(ht, &iter); 211 212 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS; 213 result = isc_ht_iter_next(iter)) 214 { 215 unsigned char *tkey = NULL; 216 void *v = NULL; 217 218 isc_ht_iter_current(iter, &v); 219 isc_ht_iter_currentkey(iter, &tkey, &tksize); 220 assert_int_equal(tksize, 16); 221 i = (uintptr_t)v; 222 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 223 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 224 assert_memory_equal(key, tkey, 16); 225 walked++; 226 } 227 assert_int_equal(walked, count); 228 assert_int_equal(result, ISC_R_NOMORE); 229 230 /* erase odd */ 231 walked = 0; 232 result = isc_ht_iter_first(iter); 233 while (result == ISC_R_SUCCESS) { 234 unsigned char *tkey = NULL; 235 void *v = NULL; 236 237 isc_ht_iter_current(iter, &v); 238 isc_ht_iter_currentkey(iter, &tkey, &tksize); 239 assert_int_equal(tksize, 16); 240 i = (uintptr_t)v; 241 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 242 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 243 assert_memory_equal(key, tkey, 16); 244 if ((uintptr_t)v % 2 == 0) { 245 result = isc_ht_iter_delcurrent_next(iter); 246 } else { 247 result = isc_ht_iter_next(iter); 248 } 249 walked++; 250 } 251 assert_int_equal(result, ISC_R_NOMORE); 252 assert_int_equal(walked, count); 253 254 /* erase even */ 255 walked = 0; 256 result = isc_ht_iter_first(iter); 257 while (result == ISC_R_SUCCESS) { 258 unsigned char *tkey = NULL; 259 void *v = NULL; 260 261 isc_ht_iter_current(iter, &v); 262 isc_ht_iter_currentkey(iter, &tkey, &tksize); 263 assert_int_equal(tksize, 16); 264 i = (uintptr_t)v; 265 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 266 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 267 assert_memory_equal(key, tkey, 16); 268 if ((uintptr_t)v % 2 == 1) { 269 result = isc_ht_iter_delcurrent_next(iter); 270 } else { 271 result = isc_ht_iter_next(iter); 272 } 273 walked++; 274 } 275 assert_int_equal(result, ISC_R_NOMORE); 276 assert_int_equal(walked, count / 2); 277 278 walked = 0; 279 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS; 280 result = isc_ht_iter_next(iter)) 281 { 282 walked++; 283 } 284 285 assert_int_equal(result, ISC_R_NOMORE); 286 assert_int_equal(walked, 0); 287 288 /* Iterator doesn't progress rehashing */ 289 assert_true(rehashing_in_progress(ht)); 290 291 isc_ht_iter_destroy(&iter); 292 assert_null(iter); 293 294 isc_ht_destroy(&ht); 295 assert_null(ht); 296 } 297 298 /* 1 bit, 120 elements test, full rehashing */ 299 ISC_RUN_TEST_IMPL(isc_ht_1_120) { 300 test_ht_full(1, 120); 301 return; 302 } 303 304 /* 6 bit, 1000 elements test, full rehashing */ 305 ISC_RUN_TEST_IMPL(isc_ht_6_1000) { 306 test_ht_full(6, 1000); 307 return; 308 } 309 310 /* 24 bit, 200K elements test, no rehashing */ 311 ISC_RUN_TEST_IMPL(isc_ht_24_200000) { 312 UNUSED(state); 313 test_ht_full(24, 200000); 314 } 315 316 /* 15 bit, 45K elements test, full rehashing */ 317 ISC_RUN_TEST_IMPL(isc_ht_1_48000) { 318 UNUSED(state); 319 test_ht_full(1, 48000); 320 } 321 322 /* 8 bit, 20k elements test, partial rehashing */ 323 ISC_RUN_TEST_IMPL(isc_ht_8_20000) { 324 UNUSED(state); 325 test_ht_full(8, 20000); 326 } 327 328 /* test hashtable iterator */ 329 330 ISC_RUN_TEST_IMPL(isc_ht_iterator) { 331 UNUSED(state); 332 test_ht_iterator(); 333 } 334 335 ISC_RUN_TEST_IMPL(isc_ht_case) { 336 isc_ht_t *ht = NULL; 337 void *f = NULL; 338 isc_result_t result = ISC_R_UNSET; 339 340 unsigned char lower[16] = { "test case" }; 341 unsigned char same[16] = { "test case" }; 342 unsigned char upper[16] = { "TEST CASE" }; 343 unsigned char mixed[16] = { "tEsT CaSe" }; 344 345 isc_ht_init(&ht, mctx, 8, ISC_HT_CASE_SENSITIVE); 346 assert_non_null(ht); 347 348 result = isc_ht_add(ht, lower, 16, (void *)lower); 349 assert_int_equal(result, ISC_R_SUCCESS); 350 351 result = isc_ht_add(ht, same, 16, (void *)same); 352 assert_int_equal(result, ISC_R_EXISTS); 353 354 result = isc_ht_add(ht, upper, 16, (void *)upper); 355 assert_int_equal(result, ISC_R_SUCCESS); 356 357 result = isc_ht_find(ht, mixed, 16, &f); 358 assert_int_equal(result, ISC_R_NOTFOUND); 359 assert_null(f); 360 361 isc_ht_destroy(&ht); 362 assert_null(ht); 363 364 isc_ht_init(&ht, mctx, 8, ISC_HT_CASE_INSENSITIVE); 365 assert_non_null(ht); 366 367 result = isc_ht_add(ht, lower, 16, (void *)lower); 368 assert_int_equal(result, ISC_R_SUCCESS); 369 370 result = isc_ht_add(ht, same, 16, (void *)same); 371 assert_int_equal(result, ISC_R_EXISTS); 372 373 result = isc_ht_add(ht, upper, 16, (void *)upper); 374 assert_int_equal(result, ISC_R_EXISTS); 375 376 result = isc_ht_find(ht, mixed, 16, &f); 377 assert_int_equal(result, ISC_R_SUCCESS); 378 assert_ptr_equal(f, &lower); 379 380 isc_ht_destroy(&ht); 381 assert_null(ht); 382 } 383 384 ISC_TEST_LIST_START 385 ISC_TEST_ENTRY(isc_ht_case) 386 ISC_TEST_ENTRY(isc_ht_1_120) 387 ISC_TEST_ENTRY(isc_ht_6_1000) 388 ISC_TEST_ENTRY(isc_ht_24_200000) 389 ISC_TEST_ENTRY(isc_ht_1_48000) 390 ISC_TEST_ENTRY(isc_ht_8_20000) 391 ISC_TEST_ENTRY(isc_ht_iterator) 392 ISC_TEST_LIST_END 393 394 ISC_TEST_MAIN 395