hash_table.h (21554B)
1 /* Copyright (C) 2013-2023, 2025 Vincent Forest (vaplv@free.fr) 2 * 3 * The RSys library is free software: you can redistribute it and/or modify 4 * it under the terms of the GNU General Public License as published 5 * by the Free Software Foundation, either version 3 of the License, or 6 * (at your option) any later version. 7 * 8 * The RSys library is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 * GNU General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public License 14 * along with the RSys library. If not, see <http://www.gnu.org/licenses/>. */ 15 16 #if !defined(HTABLE_NAME) && !defined(HTABLE_KEY) && !defined(HTABLE_DATA) 17 #ifndef HASH_TABLE_H 18 #define HASH_TABLE_H 19 20 /* Pre include required headers */ 21 #include "dynamic_array_char.h" 22 #include "hash.h" 23 #include "mem_allocator.h" 24 #include "math.h" 25 #include "rsys.h" 26 #include <string.h> 27 28 #endif /* HASH_TABLE_H */ 29 #else 30 /* 31 * Generate the hash table data types and functions with respect to the 32 * following macros: 33 * - HTABLE_NAME: prefix of the hash table functions & types; 34 * - HTABLE_DATA: type of the data registered into the hash table; 35 * - HTABLE_KEY: type of the key indexing the hash table data; 36 * - HTABLE_KEY_FUNCTOR_HASH: hash functor on HTABLE_KEY. If not defined, use 37 * the default function that hashes the bytes of HTABLE_KEY; 38 * - HTABLE_KEY_FUNCTOR_EQ: equality functor on 2 HTABLE_KEY; 39 * - HTABLE_<DATA|KEY>_FUNCTOR_INIT: init functor on HTABLE_<DATA|KEY>. If not 40 * defined, no specific treatment is performed on the created data; 41 * - HTABLE_<DATA|KEY>_FUNCTOR_COPY: copy functor on HTABLE_<DATA|KEY>. If not 42 * defined a bitwise copy is used instead; 43 * - HTABLE_<DATA|KEY>_FUNCTOR_RELEASE: release functor on HTABLE_<DATA|KEY>. 44 * If not defined nothing is done on the release of an element; 45 * - HTABLE_<DATA|KEY>_FUNCTOR_COPY_AND_RELEASE: Copy and release of a 46 * HTABLE_<DATA|KEY>. If not defined the copy and the release functors is 47 * used. 48 * 49 * The name of the generated types are: 50 * struct htable_<HTABLE_NAME>[_pair|_iterator] 51 * 52 * while the generated functions are: 53 * htable_<HTABLE_NAME>_<FUNCTION_NAME> 54 * 55 * The hash table collisions are resolved by the "open addressing" strategy 56 * with a fixed linear probing of one. 57 */ 58 #if !defined( HTABLE_NAME ) 59 # error "Undefined HTABLE_NAME macro defining the hash table suffix" 60 #endif 61 #if !defined( HTABLE_KEY) 62 # error "Undefined HTABLE_KEY macro defining the hash key type" 63 #endif 64 #if !defined( HTABLE_DATA ) 65 # error "Undefined HTABLE_DATA macro defining the hash data type" 66 #endif 67 68 #define HTABLE__ CONCAT(htable_, HTABLE_NAME) 69 #define HTABLE_PAIR__ CONCAT(CONCAT(HTABLE__, _), pair) 70 #define HTABLE_ITERATOR__ CONCAT(CONCAT(HTABLE__, _), iterator) 71 #define HTABLE_FUNC__(Func) \ 72 CONCAT(CONCAT(CONCAT(CONCAT(htable, _), HTABLE_NAME), _), Func) 73 74 /* Internal data structure */ 75 struct HTABLE_PAIR__ { 76 HTABLE_DATA data; 77 HTABLE_KEY key; 78 }; 79 80 /******************************************************************************* 81 * Internal default functions 82 ******************************************************************************/ 83 #ifndef HTABLE_DATA_FUNCTOR_INIT 84 static FINLINE void 85 HTABLE_FUNC__(data_functor_init__) 86 (struct mem_allocator* alloc, HTABLE_DATA* data) 87 { ASSERT(data); (void)alloc, (void)data; } 88 #define HTABLE_DATA_FUNCTOR_INIT HTABLE_FUNC__(data_functor_init__) 89 #endif 90 91 #ifndef HTABLE_KEY_FUNCTOR_INIT 92 static FINLINE void 93 HTABLE_FUNC__(key_functor_init__)(struct mem_allocator* alloc, HTABLE_KEY* key) 94 { ASSERT(key); (void)alloc, (void)key; } 95 #define HTABLE_KEY_FUNCTOR_INIT HTABLE_FUNC__(key_functor_init__) 96 #endif 97 98 #ifndef HTABLE_DATA_FUNCTOR_RELEASE 99 static FINLINE void 100 HTABLE_FUNC__(data_functor_release__)(HTABLE_DATA* data) 101 { ASSERT(data); (void)data; } 102 #define HTABLE_DATA_FUNCTOR_RELEASE HTABLE_FUNC__(data_functor_release__) 103 #endif 104 105 #ifndef HTABLE_KEY_FUNCTOR_RELEASE 106 static FINLINE void 107 HTABLE_FUNC__(key_functor_release__)(HTABLE_KEY* key) 108 { ASSERT(key); (void)key; } 109 #define HTABLE_KEY_FUNCTOR_RELEASE HTABLE_FUNC__(key_functor_release__) 110 #endif 111 112 #ifndef HTABLE_DATA_FUNCTOR_COPY 113 static FINLINE res_T 114 HTABLE_FUNC__(data_functor_cp__)(HTABLE_DATA* dst, HTABLE_DATA const* src) 115 { ASSERT(dst && src); *dst = *src; return RES_OK; } 116 #define HTABLE_DATA_FUNCTOR_COPY HTABLE_FUNC__(data_functor_cp__) 117 #endif 118 119 #ifndef HTABLE_KEY_FUNCTOR_COPY 120 static FINLINE res_T 121 HTABLE_FUNC__(key_functor_cp__)(HTABLE_KEY* dst, HTABLE_KEY const* src) 122 { ASSERT(dst && src); *dst = *src; return RES_OK; } 123 #define HTABLE_KEY_FUNCTOR_COPY HTABLE_FUNC__(key_functor_cp__) 124 #endif 125 126 #ifndef HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE 127 static FINLINE res_T 128 HTABLE_FUNC__(data_functor_cp_and_release__)(HTABLE_DATA* dst, HTABLE_DATA* src) 129 { 130 const res_T res = HTABLE_DATA_FUNCTOR_COPY(dst, src); 131 HTABLE_DATA_FUNCTOR_RELEASE(src); 132 return res; 133 } 134 #define HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE \ 135 HTABLE_FUNC__(data_functor_cp_and_release__) 136 #endif 137 138 #ifndef HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE 139 static FINLINE res_T 140 HTABLE_FUNC__(key_functor_cp_and_release__)(HTABLE_KEY* dst, HTABLE_KEY* src) 141 { 142 const res_T res = HTABLE_KEY_FUNCTOR_COPY(dst, src); 143 HTABLE_KEY_FUNCTOR_RELEASE(src); 144 return res; 145 } 146 #define HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE \ 147 HTABLE_FUNC__(key_functor_cp_and_release__) 148 #endif 149 150 #ifndef HTABLE_KEY_FUNCTOR_HASH 151 static INLINE size_t 152 HTABLE_FUNC__(key_functor_hash__)(HTABLE_KEY const* key) 153 { 154 #ifdef ARCH_32BITS 155 return (size_t)hash_fnv32(key, sizeof(HTABLE_KEY)); 156 #elif defined(ARCH_64BITS) 157 return (size_t)hash_fnv64(key, sizeof(HTABLE_KEY)); 158 #else 159 #error "Unexpected architecture" 160 #endif 161 } 162 #define HTABLE_KEY_FUNCTOR_HASH HTABLE_FUNC__(key_functor_hash__) 163 #endif 164 165 #ifndef HTABLE_KEY_FUNCTOR_EQ 166 static INLINE char 167 HTABLE_FUNC__(key_functor_eq__)(HTABLE_KEY const* a, HTABLE_KEY const* b) 168 { 169 ASSERT(a && b); 170 return *a == *b; 171 } 172 #define HTABLE_KEY_FUNCTOR_EQ HTABLE_FUNC__(key_functor_eq__) 173 #endif 174 175 /******************************************************************************* 176 * Pair functor 177 ******************************************************************************/ 178 static INLINE void 179 HTABLE_FUNC__(pair_init__) 180 (struct mem_allocator* allocator, struct HTABLE_PAIR__* pair) 181 { 182 ASSERT(pair); 183 HTABLE_KEY_FUNCTOR_INIT(allocator, &pair->key); 184 HTABLE_DATA_FUNCTOR_INIT(allocator, &pair->data); 185 } 186 187 static INLINE void 188 HTABLE_FUNC__(pair_release__)(struct HTABLE_PAIR__* pair) 189 { 190 ASSERT(pair); 191 HTABLE_KEY_FUNCTOR_RELEASE(&pair->key); 192 HTABLE_DATA_FUNCTOR_RELEASE(&pair->data); 193 } 194 195 static INLINE res_T 196 HTABLE_FUNC__(pair_copy__) 197 (struct HTABLE_PAIR__* dst, struct HTABLE_PAIR__ const* src) 198 { 199 res_T res; 200 ASSERT(dst && src); 201 if(RES_OK != (res = HTABLE_KEY_FUNCTOR_COPY(&dst->key, &src->key))) 202 return res; 203 res = HTABLE_DATA_FUNCTOR_COPY(&dst->data, &src->data); 204 return res; 205 } 206 207 static INLINE res_T 208 HTABLE_FUNC__(pair_copy_and_release__) 209 (struct HTABLE_PAIR__* dst, struct HTABLE_PAIR__* src) 210 { 211 res_T res; 212 ASSERT(dst && src); 213 if(RES_OK != (res = HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE(&dst->key, &src->key))) 214 return res; 215 res = HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE(&dst->data, &src->data); 216 return res; 217 } 218 219 /******************************************************************************* 220 * Data types 221 ******************************************************************************/ 222 #define DARRAY_NAME CONCAT(HTABLE_NAME, __) 223 #define DARRAY_DATA struct HTABLE_PAIR__ 224 #define DARRAY_FUNCTOR_INIT HTABLE_FUNC__(pair_init__) 225 #define DARRAY_FUNCTOR_RELEASE HTABLE_FUNC__(pair_release__) 226 #define DARRAY_FUNCTOR_COPY HTABLE_FUNC__(pair_copy__) 227 #define DARRAY_FUNCTOR_COPY_AND_RELEASE HTABLE_FUNC__(pair_copy_and_release__) 228 #include "dynamic_array.h" 229 230 #define HTABLE_DATA__ CONCAT(CONCAT(darray_, HTABLE_NAME), __) 231 #define HTABLE_DATA_FUNC__(Func) CONCAT(CONCAT(HTABLE_DATA__, _), Func) 232 233 struct HTABLE__ { 234 struct HTABLE_DATA__ table; 235 struct darray_char table_slot_is_used; 236 size_t table_size_in_use; /* #slots in used */ 237 struct mem_allocator* allocator; 238 }; 239 240 struct HTABLE_ITERATOR__ { 241 struct HTABLE__* hash_table; 242 size_t slot; 243 size_t entries_scanned; /* Used to early stop the next procedure */ 244 }; 245 246 /******************************************************************************* 247 * Internal helper functions 248 ******************************************************************************/ 249 static INLINE size_t 250 HTABLE_FUNC__(find_slot__)(const struct HTABLE__* htbl, HTABLE_KEY const* key) 251 { 252 size_t slot = 0; 253 const struct HTABLE_PAIR__* pairs = NULL; 254 const char* used_pairs = NULL; 255 ASSERT(htbl && key); 256 /* The tbl size must be a pow of 2 */ 257 ASSERT(IS_POW2(HTABLE_DATA_FUNC__(size_get)(&htbl->table))); 258 /* The tbl is not full */ 259 ASSERT(htbl->table_size_in_use < HTABLE_DATA_FUNC__(size_get)(&htbl->table)); 260 261 pairs = HTABLE_DATA_FUNC__(cdata_get)(&htbl->table); 262 used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used); 263 slot = /* slot = hash % size */ 264 HTABLE_KEY_FUNCTOR_HASH(key) 265 & (HTABLE_DATA_FUNC__(size_get)(&htbl->table) - 1); 266 267 while(used_pairs[slot] && !HTABLE_KEY_FUNCTOR_EQ(key, &pairs[slot].key)) { 268 /* slot = (slot + 1) % size */ 269 slot = (slot + 1) & (HTABLE_DATA_FUNC__(size_get)(&htbl->table) - 1); 270 } 271 return slot; 272 } 273 274 /******************************************************************************* 275 * Hash table API 276 ******************************************************************************/ 277 static INLINE void 278 HTABLE_FUNC__(init) 279 ( /* May be NULL <=> use default allocator */ 280 struct mem_allocator* allocator, 281 struct HTABLE__* htbl) 282 { 283 ASSERT(htbl); 284 HTABLE_DATA_FUNC__(init)(allocator, &htbl->table); 285 darray_char_init(allocator, &htbl->table_slot_is_used); 286 htbl->table_size_in_use = 0; 287 htbl->allocator = allocator ? allocator : &mem_default_allocator; 288 } 289 290 static INLINE void 291 HTABLE_FUNC__(clear)(struct HTABLE__* htbl) 292 { 293 size_t islot = 0, in_use = 0; 294 ASSERT(htbl); 295 296 FOR_EACH(islot, 0, HTABLE_DATA_FUNC__(size_get)(&htbl->table)) { 297 struct HTABLE_PAIR__* pair = NULL; 298 if(in_use == htbl->table_size_in_use) 299 break; /* Early stop the clear since there is no more slot in htbl */ 300 301 if(!darray_char_cdata_get(&htbl->table_slot_is_used)[islot]) 302 continue; 303 304 darray_char_data_get(&htbl->table_slot_is_used)[islot] = 0; 305 pair = HTABLE_DATA_FUNC__(data_get)(&htbl->table) + islot; 306 /* Release the pair data and re-init it since it must stay valid for 307 * subsequent uses */ 308 HTABLE_FUNC__(pair_release__)(pair); 309 HTABLE_FUNC__(pair_init__)(htbl->allocator, pair); 310 ++in_use; 311 } 312 htbl->table_size_in_use = 0; 313 } 314 315 static INLINE void 316 HTABLE_FUNC__(release)(struct HTABLE__* htbl) 317 { 318 ASSERT(htbl); 319 HTABLE_FUNC__(clear)(htbl); 320 HTABLE_DATA_FUNC__(release)(&htbl->table); 321 darray_char_release(&htbl->table_slot_is_used); 322 } 323 324 /* Clean up the hash table and, unlike the clear function, ensure that the 325 * memory used to store the data is effectively released */ 326 static INLINE void 327 HTABLE_FUNC__(purge)(struct HTABLE__* htbl) 328 { 329 struct mem_allocator* allocator; 330 ASSERT(htbl); 331 allocator = htbl->allocator; 332 HTABLE_FUNC__(release)(htbl); 333 HTABLE_FUNC__(init)(allocator, htbl); 334 } 335 336 static res_T 337 HTABLE_FUNC__(reserve)(struct HTABLE__* htbl, const size_t size_submitted) 338 { 339 struct HTABLE_DATA__ tbl; 340 struct darray_char tbl_slot_is_used; 341 struct HTABLE_PAIR__* old_pairs = NULL; 342 struct HTABLE_PAIR__* new_pairs = NULL; 343 const char* old_used_pairs = NULL; 344 char* new_used_pairs = NULL; 345 size_t islot = 0; 346 size_t in_use = 0; 347 size_t size = 0; 348 res_T res = RES_OK; 349 ASSERT(htbl); 350 351 size = round_up_pow2(size_submitted); 352 if(size <= HTABLE_DATA_FUNC__(size_get)(&htbl->table)) 353 goto exit; 354 355 darray_char_init(htbl->allocator, &tbl_slot_is_used); 356 357 HTABLE_DATA_FUNC__(init)(htbl->allocator, &tbl); 358 if(RES_OK != (res = HTABLE_DATA_FUNC__(resize)(&tbl, size))) 359 goto error; 360 361 if(RES_OK != (res = darray_char_resize(&tbl_slot_is_used, size))) 362 goto error; 363 memset(darray_char_data_get(&tbl_slot_is_used), 0, size*sizeof(char)); 364 365 /* Rehash the hash table */ 366 old_pairs = HTABLE_DATA_FUNC__(data_get)(&htbl->table); 367 new_pairs = HTABLE_DATA_FUNC__(data_get)(&tbl); 368 old_used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used); 369 new_used_pairs = darray_char_data_get(&tbl_slot_is_used); 370 FOR_EACH(islot, 0, HTABLE_DATA_FUNC__(size_get)(&htbl->table)) { 371 size_t islot_new = 0; 372 373 if(in_use == htbl->table_size_in_use) 374 break; /* Early stop the rehasing since there is no more slot in htbl */ 375 376 if(!old_used_pairs[islot]) 377 continue; 378 379 islot_new = HTABLE_KEY_FUNCTOR_HASH(&old_pairs[islot].key) & (size - 1); 380 while(new_used_pairs[islot_new]) { 381 /* There is at most 1 entry for a given key */ 382 ASSERT(!HTABLE_KEY_FUNCTOR_EQ 383 (&new_pairs[islot_new].key, &old_pairs[islot].key )); 384 islot_new = (islot_new + 1) & (size - 1); /* (islot_new + 1) % size */ 385 } 386 387 /* Transfer ownership of old_pairs[islot] data to new_pairs[islot_new]. 388 * Re-init the old_pairs[islot] structure since it must stay valid */ 389 HTABLE_FUNC__(pair_copy_and_release__) 390 (&new_pairs[islot_new], &old_pairs[islot]); 391 HTABLE_FUNC__(pair_init__)(htbl->allocator, &old_pairs[islot]); 392 393 new_used_pairs[islot_new] = 1; 394 ++in_use; 395 } 396 397 HTABLE_DATA_FUNC__(copy_and_release)(&htbl->table, &tbl); 398 darray_char_copy_and_release(&htbl->table_slot_is_used, &tbl_slot_is_used); 399 400 exit: 401 return res; 402 error: 403 HTABLE_DATA_FUNC__(release)(&tbl); 404 darray_char_release(&tbl_slot_is_used); 405 goto exit; 406 } 407 408 static INLINE res_T 409 HTABLE_FUNC__(set) 410 ( struct HTABLE__* htbl, 411 HTABLE_KEY const* key, 412 HTABLE_DATA const* data ) 413 { 414 struct HTABLE_PAIR__* pair = NULL; 415 size_t tbl_size = 0; 416 size_t i = 0; 417 res_T res = RES_OK; 418 ASSERT(htbl && key && data); 419 420 /* Increase hash table size when the load factor is too high */ 421 tbl_size = HTABLE_DATA_FUNC__(size_get)(&htbl->table); 422 if(htbl->table_size_in_use >= tbl_size * 3/4) { 423 if(!tbl_size) { 424 res = HTABLE_FUNC__(reserve)(htbl, 32); 425 } else { 426 res = HTABLE_FUNC__(reserve)(htbl, tbl_size * 2 ); 427 } 428 if(res != RES_OK) 429 return res; 430 } 431 432 i = HTABLE_FUNC__(find_slot__)(htbl, key); 433 pair = HTABLE_DATA_FUNC__(data_get)(&htbl->table) + i; 434 if(darray_char_cdata_get(&htbl->table_slot_is_used)[i]) { 435 res = HTABLE_DATA_FUNCTOR_COPY(&pair->data, data); 436 if(res != RES_OK) { 437 darray_char_data_get(&htbl->table_slot_is_used)[i] = 0; 438 --htbl->table_size_in_use; 439 } 440 } else { 441 res = HTABLE_KEY_FUNCTOR_COPY(&pair->key, key); 442 if(res == RES_OK) { 443 res = HTABLE_DATA_FUNCTOR_COPY(&pair->data, data); 444 if(res == RES_OK) { 445 darray_char_data_get(&htbl->table_slot_is_used)[i] = 1; 446 ++htbl->table_size_in_use; 447 } 448 } 449 } 450 return res; 451 } 452 453 /* Return the number of erased elements, i.e. 0 or 1 */ 454 static INLINE size_t 455 HTABLE_FUNC__(erase)(struct HTABLE__* htbl, HTABLE_KEY const* key) 456 { 457 size_t i = 0, j = 0, tbl_size = 0; 458 struct HTABLE_PAIR__* pairs = NULL; 459 char* used_pairs = NULL; 460 ASSERT(htbl && key); 461 462 pairs = HTABLE_DATA_FUNC__(data_get)(&htbl->table); 463 tbl_size = HTABLE_DATA_FUNC__(size_get)(&htbl->table); 464 if(!tbl_size) 465 return 0; 466 ASSERT(IS_POW2(tbl_size)); 467 468 used_pairs = darray_char_data_get(&htbl->table_slot_is_used); 469 i = HTABLE_FUNC__(find_slot__)(htbl, key); 470 if(!used_pairs[i]) 471 return 0; /* No entry */ 472 473 /* Remove the entry but does not release it */ 474 used_pairs[i] = 0; 475 --htbl->table_size_in_use; 476 477 for(j = (i + 1) & (tbl_size - 1); /* <=> j = (i+1) % size */ 478 used_pairs[j]; 479 j = (j + 1) & (tbl_size - 1)) { /* <=> j = (j+1) % size */ 480 const size_t k = HTABLE_KEY_FUNCTOR_HASH(&pairs[j].key) & (tbl_size- 1); 481 482 if(i <= j ? (i < k && k <= j) : (i < k || k <= j)) 483 continue; 484 485 /* Transfer ownership of pairs[j] data to pairs[i]. Re-init pairs[j] since 486 * it must stay valid for subsequent uses */ 487 HTABLE_FUNC__(pair_copy_and_release__)(&pairs[i], &pairs[j]); 488 HTABLE_FUNC__(pair_init__)(htbl->allocator, &pairs[j]); 489 used_pairs[i] = 1; 490 used_pairs[j] = 0; 491 i = j; 492 } 493 return 1; 494 } 495 496 static INLINE char 497 HTABLE_FUNC__(is_empty)(const struct HTABLE__* htbl) 498 { 499 ASSERT(htbl); 500 return htbl->table_size_in_use == 0; 501 } 502 503 static INLINE HTABLE_DATA* 504 HTABLE_FUNC__(find)(struct HTABLE__* htbl, HTABLE_KEY const* key) 505 { 506 size_t i = 0; 507 ASSERT(htbl && key); 508 if(HTABLE_FUNC__(is_empty)(htbl)) 509 return NULL; 510 511 i = HTABLE_FUNC__(find_slot__)(htbl, key); 512 if(darray_char_cdata_get(&htbl->table_slot_is_used)[i]) { 513 return &HTABLE_DATA_FUNC__(data_get)(&htbl->table)[i].data; 514 } else { 515 return NULL; 516 } 517 } 518 519 static INLINE size_t 520 HTABLE_FUNC__(size_get)(const struct HTABLE__* htbl) 521 { 522 ASSERT(htbl); 523 return htbl->table_size_in_use; 524 } 525 526 static INLINE res_T 527 HTABLE_FUNC__(copy)(struct HTABLE__* dst, const struct HTABLE__* src) 528 { 529 res_T res = RES_OK; 530 ASSERT(dst && src); 531 532 res = HTABLE_DATA_FUNC__(copy)(&dst->table, &src->table); 533 if(res != RES_OK) goto error; 534 535 res = darray_char_copy(&dst->table_slot_is_used, &src->table_slot_is_used); 536 if(res != RES_OK) goto error; 537 538 dst->table_size_in_use = src->table_size_in_use; 539 540 exit: 541 return res; 542 error: 543 HTABLE_FUNC__(clear)(dst); 544 goto exit; 545 } 546 547 static INLINE res_T 548 HTABLE_FUNC__(copy_and_clear)(struct HTABLE__* dst, struct HTABLE__* src) 549 { 550 res_T res = RES_OK; 551 ASSERT(dst && src); 552 if(dst == src) { 553 HTABLE_FUNC__(clear)(dst); 554 return RES_OK; 555 } 556 557 res = HTABLE_DATA_FUNC__(copy_and_clear)(&dst->table, &src->table); 558 if(res != RES_OK) goto error; 559 560 res = darray_char_copy_and_clear 561 (&dst->table_slot_is_used, &src->table_slot_is_used); 562 if(res != RES_OK) goto error; 563 564 dst->table_size_in_use = src->table_size_in_use; 565 src->table_size_in_use = 0; 566 567 exit: 568 return res; 569 error: 570 HTABLE_FUNC__(clear)(dst); 571 goto exit; 572 } 573 574 static INLINE res_T 575 HTABLE_FUNC__(copy_and_release)(struct HTABLE__*dst, struct HTABLE__* src) 576 { 577 res_T res = RES_OK; 578 ASSERT(dst && src); 579 if(dst == src) { 580 HTABLE_FUNC__(release)(dst); 581 } else { 582 res = HTABLE_FUNC__(copy_and_clear)(dst, src); 583 if(res == RES_OK) 584 HTABLE_FUNC__(release)(src); 585 } 586 return res; 587 } 588 589 static INLINE void 590 HTABLE_FUNC__(begin) 591 (struct HTABLE__* htbl, 592 struct HTABLE_ITERATOR__* it) 593 { 594 const char* used_pairs = NULL; 595 size_t i = 0; 596 size_t tbl_size = 0; 597 ASSERT(htbl && it); 598 599 tbl_size = HTABLE_DATA_FUNC__(size_get)(&htbl->table); 600 used_pairs = darray_char_cdata_get(&htbl->table_slot_is_used); 601 602 it->slot = it->entries_scanned = 0; 603 for(i = 0; i < tbl_size && !used_pairs[i]; ++i) {} 604 it->slot = i; 605 it->entries_scanned = i < tbl_size; 606 it->hash_table = htbl; 607 } 608 609 static INLINE void 610 HTABLE_FUNC__(end) 611 (struct HTABLE__* htbl, 612 struct HTABLE_ITERATOR__* it) 613 { 614 ASSERT(htbl && it); 615 it->slot = HTABLE_DATA_FUNC__(size_get)(&htbl->table); 616 it->entries_scanned = htbl->table_size_in_use; 617 it->hash_table = htbl; 618 } 619 620 static INLINE void 621 HTABLE_FUNC__(find_iterator) 622 (struct HTABLE__* htbl, 623 HTABLE_KEY const* key, 624 struct HTABLE_ITERATOR__* it) 625 { 626 size_t i = 0; 627 ASSERT(htbl && key && it); 628 if(HTABLE_FUNC__(is_empty)(htbl)) { 629 HTABLE_FUNC__(end)(htbl, it); 630 return; 631 } 632 633 i = HTABLE_FUNC__(find_slot__)(htbl, key); 634 if(!darray_char_cdata_get(&htbl->table_slot_is_used)[i]) { 635 HTABLE_FUNC__(end)(htbl, it); 636 } else { 637 it->slot = i; 638 it->hash_table = htbl; 639 it->entries_scanned = 0; 640 } 641 } 642 643 static INLINE void 644 HTABLE_FUNC__(iterator_next)(struct HTABLE_ITERATOR__* it) 645 { 646 size_t tbl_size = 0; 647 ASSERT(it); 648 649 tbl_size = HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table); 650 if(it->entries_scanned >= it->hash_table->table_size_in_use) {/* Early stop */ 651 it->slot = tbl_size; 652 } else { 653 size_t i = 0; 654 FOR_EACH(i, it->slot + 1, tbl_size) 655 if(darray_char_cdata_get(&it->hash_table->table_slot_is_used)[i]) break; 656 it->slot = i; 657 it->entries_scanned += i < tbl_size; 658 } 659 } 660 661 static INLINE char 662 HTABLE_FUNC__(iterator_eq) 663 (const struct HTABLE_ITERATOR__* it0, 664 const struct HTABLE_ITERATOR__* it1) 665 { 666 ASSERT(it0 && it1); 667 /* Do not compare the 'entries_scanned' field used only to early stop the 668 * iterator_next function in some situations */ 669 return 670 it0->slot == it1->slot 671 && it0->hash_table == it1->hash_table; 672 } 673 674 static INLINE HTABLE_KEY* 675 HTABLE_FUNC__(iterator_key_get)(const struct HTABLE_ITERATOR__* it) 676 { 677 ASSERT(it && it->slot < HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table)); 678 return &HTABLE_DATA_FUNC__(data_get)(&it->hash_table->table)[it->slot].key; 679 } 680 681 static INLINE HTABLE_DATA* 682 HTABLE_FUNC__(iterator_data_get)(const struct HTABLE_ITERATOR__* it) 683 { 684 ASSERT(it && it->slot < HTABLE_DATA_FUNC__(size_get)(&it->hash_table->table)); 685 return &HTABLE_DATA_FUNC__(data_get)(&it->hash_table->table)[it->slot].data; 686 } 687 688 #undef HTABLE_KEY 689 #undef HTABLE_KEY_FUNCTOR_COPY 690 #undef HTABLE_KEY_FUNCTOR_COPY_AND_RELEASE 691 #undef HTABLE_KEY_FUNCTOR_EQ 692 #undef HTABLE_KEY_FUNCTOR_HASH 693 #undef HTABLE_KEY_FUNCTOR_INIT 694 #undef HTABLE_KEY_FUNCTOR_RELEASE 695 #undef HTABLE_DATA 696 #undef HTABLE_DATA_FUNCTOR_COPY 697 #undef HTABLE_DATA_FUNCTOR_COPY_AND_RELEASE 698 #undef HTABLE_DATA_FUNCTOR_INIT 699 #undef HTABLE_DATA_FUNCTOR_RELEASE 700 #undef HTABLE_NAME 701 #undef HTABLE__ 702 #undef HTABLE_PAIR__ 703 #undef HTABLE_ITERATOR__ 704 #undef HTABLE_FUNC__ 705 706 #undef HTABLE_DATA__ 707 #undef HTABLE_DATA_FUNC__ 708 709 #endif /* !HTABLE_NAME || !HTABLE_KEY || !HTABLE_DATA */