1/* $NetBSD: ht_test.c,v 1.2 2024/02/21 22:52:50 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/print.h> 32#include <isc/string.h> 33#include <isc/util.h> 34 35#include <tests/isc.h> 36 37/* INCLUDE LAST */ 38 39#define mctx __mctx 40#include "ht.c" 41#undef mctx 42 43static void 44test_ht_full(int bits, uintptr_t count) { 45 isc_ht_t *ht = NULL; 46 isc_result_t result; 47 uintptr_t i; 48 49 isc_ht_init(&ht, mctx, bits, ISC_HT_CASE_SENSITIVE); 50 assert_non_null(ht); 51 52 for (i = 1; i < count; i++) { 53 /* 54 * Note: snprintf() is followed with strlcat() 55 * to ensure we are always filling the 16 byte key. 56 */ 57 unsigned char key[16]; 58 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 59 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 60 result = isc_ht_add(ht, key, 16, (void *)i); 61 assert_int_equal(result, ISC_R_SUCCESS); 62 } 63 64 for (i = 1; i < count; i++) { 65 unsigned char key[16]; 66 void *f = NULL; 67 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 68 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 69 result = isc_ht_find(ht, key, 16, &f); 70 assert_int_equal(result, ISC_R_SUCCESS); 71 assert_ptr_equal((void *)i, (void *)f); 72 } 73 74 for (i = 1; i < count; i++) { 75 unsigned char key[16]; 76 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 77 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 78 result = isc_ht_add(ht, key, 16, (void *)i); 79 assert_int_equal(result, ISC_R_EXISTS); 80 } 81 82 for (i = 1; i < count; i++) { 83 char key[64]; 84 /* 85 * Note: the key size is now strlen(key) which is bigger 86 * then the keys added above. 87 */ 88 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 89 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 90 result = isc_ht_add(ht, (const unsigned char *)key, strlen(key), 91 (void *)i); 92 assert_int_equal(result, ISC_R_SUCCESS); 93 } 94 95 for (i = 1; i < count; i++) { 96 unsigned char key[16]; 97 void *f = NULL; 98 /* 99 * Note: case of KEY is now in capitals, 100 */ 101 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 102 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 103 result = isc_ht_find(ht, key, 16, &f); 104 assert_int_equal(result, ISC_R_NOTFOUND); 105 assert_null(f); 106 } 107 108 for (i = 1; i < count; i++) { 109 char key[64]; 110 void *f = NULL; 111 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 112 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 113 result = isc_ht_find(ht, (const unsigned char *)key, 114 strlen(key), &f); 115 assert_int_equal(result, ISC_R_SUCCESS); 116 assert_ptr_equal(f, (void *)i); 117 } 118 119 for (i = 1; i < count; i++) { 120 unsigned char key[16]; 121 void *f = NULL; 122 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 123 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 124 result = isc_ht_delete(ht, key, 16); 125 assert_int_equal(result, ISC_R_SUCCESS); 126 result = isc_ht_find(ht, key, 16, &f); 127 assert_int_equal(result, ISC_R_NOTFOUND); 128 assert_null(f); 129 } 130 131 for (i = 1; i < count; i++) { 132 unsigned char key[16]; 133 /* 134 * Note: upper case KEY. 135 */ 136 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 137 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 138 result = isc_ht_add(ht, key, 16, (void *)i); 139 assert_int_equal(result, ISC_R_SUCCESS); 140 } 141 142 for (i = 1; i < count; i++) { 143 char key[64]; 144 void *f = NULL; 145 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 146 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 147 result = isc_ht_delete(ht, (const unsigned char *)key, 148 strlen(key)); 149 assert_int_equal(result, ISC_R_SUCCESS); 150 result = isc_ht_find(ht, (const unsigned char *)key, 151 strlen(key), &f); 152 assert_int_equal(result, ISC_R_NOTFOUND); 153 assert_null(f); 154 } 155 156 for (i = 1; i < count; i++) { 157 unsigned char key[16]; 158 void *f = NULL; 159 /* 160 * Note: case of KEY is now in capitals, 161 */ 162 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 163 strlcat((char *)key, " KEY of a raw hashtable!!", sizeof(key)); 164 result = isc_ht_find(ht, key, 16, &f); 165 assert_int_equal(result, ISC_R_SUCCESS); 166 assert_ptr_equal((void *)i, (void *)f); 167 } 168 169 for (i = 1; i < count; i++) { 170 unsigned char key[16]; 171 void *f = NULL; 172 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 173 strlcat((char *)key, " key of a raw hashtable!!", sizeof(key)); 174 result = isc_ht_find(ht, key, 16, &f); 175 assert_int_equal(result, ISC_R_NOTFOUND); 176 assert_null(f); 177 } 178 179 isc_ht_destroy(&ht); 180 assert_null(ht); 181} 182 183static void 184test_ht_iterator(void) { 185 isc_ht_t *ht = NULL; 186 isc_result_t result; 187 isc_ht_iter_t *iter = NULL; 188 uintptr_t i; 189 uintptr_t count = 10000; 190 uint32_t walked; 191 unsigned char key[16]; 192 size_t tksize; 193 194 isc_ht_init(&ht, mctx, 16, ISC_HT_CASE_SENSITIVE); 195 assert_non_null(ht); 196 for (i = 1; i <= count; i++) { 197 /* 198 * Note that the string we're snprintfing is always > 16 bytes 199 * so we are always filling the key. 200 */ 201 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 202 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 203 result = isc_ht_add(ht, key, 16, (void *)i); 204 assert_int_equal(result, ISC_R_SUCCESS); 205 } 206 207 walked = 0; 208 isc_ht_iter_create(ht, &iter); 209 210 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS; 211 result = isc_ht_iter_next(iter)) 212 { 213 unsigned char *tkey = NULL; 214 void *v = NULL; 215 216 isc_ht_iter_current(iter, &v); 217 isc_ht_iter_currentkey(iter, &tkey, &tksize); 218 assert_int_equal(tksize, 16); 219 i = (uintptr_t)v; 220 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 221 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 222 assert_memory_equal(key, tkey, 16); 223 walked++; 224 } 225 assert_int_equal(walked, count); 226 assert_int_equal(result, ISC_R_NOMORE); 227 228 /* erase odd */ 229 walked = 0; 230 result = isc_ht_iter_first(iter); 231 while (result == ISC_R_SUCCESS) { 232 unsigned char *tkey = NULL; 233 void *v = NULL; 234 235 isc_ht_iter_current(iter, &v); 236 isc_ht_iter_currentkey(iter, &tkey, &tksize); 237 assert_int_equal(tksize, 16); 238 i = (uintptr_t)v; 239 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 240 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 241 assert_memory_equal(key, tkey, 16); 242 if ((uintptr_t)v % 2 == 0) { 243 result = isc_ht_iter_delcurrent_next(iter); 244 } else { 245 result = isc_ht_iter_next(iter); 246 } 247 walked++; 248 } 249 assert_int_equal(result, ISC_R_NOMORE); 250 assert_int_equal(walked, count); 251 252 /* erase even */ 253 walked = 0; 254 result = isc_ht_iter_first(iter); 255 while (result == ISC_R_SUCCESS) { 256 unsigned char *tkey = NULL; 257 void *v = NULL; 258 259 isc_ht_iter_current(iter, &v); 260 isc_ht_iter_currentkey(iter, &tkey, &tksize); 261 assert_int_equal(tksize, 16); 262 i = (uintptr_t)v; 263 snprintf((char *)key, sizeof(key), "%u", (unsigned int)i); 264 strlcat((char *)key, "key of a raw hashtable!!", sizeof(key)); 265 assert_memory_equal(key, tkey, 16); 266 if ((uintptr_t)v % 2 == 1) { 267 result = isc_ht_iter_delcurrent_next(iter); 268 } else { 269 result = isc_ht_iter_next(iter); 270 } 271 walked++; 272 } 273 assert_int_equal(result, ISC_R_NOMORE); 274 assert_int_equal(walked, count / 2); 275 276 walked = 0; 277 for (result = isc_ht_iter_first(iter); result == ISC_R_SUCCESS; 278 result = isc_ht_iter_next(iter)) 279 { 280 walked++; 281 } 282 283 assert_int_equal(result, ISC_R_NOMORE); 284 assert_int_equal(walked, 0); 285 286 isc_ht_iter_destroy(&iter); 287 assert_null(iter); 288 289 isc_ht_destroy(&ht); 290 assert_null(ht); 291} 292 293/* 20 bit, 200K elements test */ 294ISC_RUN_TEST_IMPL(isc_ht_20) { 295 UNUSED(state); 296 test_ht_full(20, 200000); 297} 298 299/* 8 bit, 20000 elements crowded test */ 300ISC_RUN_TEST_IMPL(isc_ht_8) { 301 UNUSED(state); 302 test_ht_full(8, 20000); 303} 304 305ISC_RUN_TEST_IMPL(isc_ht_1) { 306 UNUSED(state); 307 test_ht_full(1, 100); 308} 309 310/* test hashtable iterator */ 311 312ISC_RUN_TEST_IMPL(isc_ht_iterator) { 313 UNUSED(state); 314 test_ht_iterator(); 315} 316 317ISC_RUN_TEST_IMPL(isc_ht_case) { 318 isc_ht_t *ht = NULL; 319 void *f = NULL; 320 isc_result_t result = ISC_R_UNSET; 321 322 unsigned char lower[16] = { "test case" }; 323 unsigned char same[16] = { "test case" }; 324 unsigned char upper[16] = { "TEST CASE" }; 325 unsigned char mixed[16] = { "tEsT CaSe" }; 326 327 isc_ht_init(&ht, mctx, 8, ISC_HT_CASE_SENSITIVE); 328 assert_non_null(ht); 329 330 result = isc_ht_add(ht, lower, 16, (void *)lower); 331 assert_int_equal(result, ISC_R_SUCCESS); 332 333 result = isc_ht_add(ht, same, 16, (void *)same); 334 assert_int_equal(result, ISC_R_EXISTS); 335 336 result = isc_ht_add(ht, upper, 16, (void *)upper); 337 assert_int_equal(result, ISC_R_SUCCESS); 338 339 result = isc_ht_find(ht, mixed, 16, &f); 340 assert_int_equal(result, ISC_R_NOTFOUND); 341 assert_null(f); 342 343 isc_ht_destroy(&ht); 344 assert_null(ht); 345 346 isc_ht_init(&ht, mctx, 8, ISC_HT_CASE_INSENSITIVE); 347 assert_non_null(ht); 348 349 result = isc_ht_add(ht, lower, 16, (void *)lower); 350 assert_int_equal(result, ISC_R_SUCCESS); 351 352 result = isc_ht_add(ht, same, 16, (void *)same); 353 assert_int_equal(result, ISC_R_EXISTS); 354 355 result = isc_ht_add(ht, upper, 16, (void *)upper); 356 assert_int_equal(result, ISC_R_EXISTS); 357 358 result = isc_ht_find(ht, mixed, 16, &f); 359 assert_int_equal(result, ISC_R_SUCCESS); 360 assert_ptr_equal(f, &lower); 361 362 isc_ht_destroy(&ht); 363 assert_null(ht); 364} 365 366ISC_TEST_LIST_START 367ISC_TEST_ENTRY(isc_ht_case) 368ISC_TEST_ENTRY(isc_ht_20) 369ISC_TEST_ENTRY(isc_ht_8) 370ISC_TEST_ENTRY(isc_ht_1) 371ISC_TEST_ENTRY(isc_ht_iterator) 372ISC_TEST_LIST_END 373 374ISC_TEST_MAIN 375