1/*
2 * rchash.c
3 *
4 * Copyright (C) 2018 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23//==========================================================
24// Includes.
25//
26
27#include "rchash.h"
28
29#include <stddef.h>
30#include <stdint.h>
31#include <string.h>
32
33#include "aerospike/as_atomic.h"
34#include "citrusleaf/alloc.h"
35#include "citrusleaf/cf_hash_math.h"
36
37#include "cf_mutex.h"
38#include "fault.h"
39
40
41//==========================================================
42// Typedefs & constants.
43//
44
45// Used when key-size is fixed.
46typedef struct cf_rchash_ele_f_s {
47 struct cf_rchash_ele_f_s *next;
48 void *object; // this is a reference counted object
49 uint8_t key[];
50} cf_rchash_ele_f;
51
52// Used when key-size is variable.
53typedef struct cf_rchash_ele_v_s {
54 struct cf_rchash_ele_v_s *next;
55 void *object; // this is a reference counted object
56 uint32_t key_size;
57 void *key;
58} cf_rchash_ele_v;
59
60
61//==========================================================
62// Forward declarations.
63//
64
65// Variable key size public API.
66void cf_rchash_put_v(cf_rchash *h, const void *key, uint32_t key_size, void *object);
67int cf_rchash_put_unique_v(cf_rchash *h, const void *key, uint32_t key_size, void *object);
68int cf_rchash_get_v(cf_rchash *h, const void *key, uint32_t key_size, void **object_r);
69int cf_rchash_delete_object_v(cf_rchash *h, const void *key, uint32_t key_size, void *object);
70int cf_rchash_reduce_v(cf_rchash *h, cf_rchash_reduce_fn reduce_fn, void *udata);
71
72// Generic utilities.
73static inline void cf_rchash_destroy_elements(cf_rchash *h);
74static inline void cf_rchash_destroy_elements_v(cf_rchash *h);
75static inline uint32_t cf_rchash_calculate_hash(cf_rchash *h, const void *key, uint32_t key_size);
76static inline cf_mutex *cf_rchash_lock(cf_rchash *h, uint32_t i);
77static inline void cf_rchash_unlock(cf_mutex *l);
78static inline cf_rchash_ele_f *cf_rchash_get_bucket(cf_rchash *h, uint32_t i);
79static inline cf_rchash_ele_v *cf_rchash_get_bucket_v(cf_rchash *h, uint32_t i);
80static inline void cf_rchash_fill_element(cf_rchash_ele_f *e, cf_rchash *h, const void *key, void *object);
81static inline void cf_rchash_fill_element_v(cf_rchash_ele_v *e, cf_rchash *h, const void *key, uint32_t key_size, void *object);
82static inline void cf_rchash_size_incr(cf_rchash *h);
83static inline void cf_rchash_size_decr(cf_rchash *h);
84static inline void cf_rchash_release_object(cf_rchash *h, void *object);
85
86
87//==========================================================
88// Public API - useful hash functions.
89//
90
91// Interpret first 4 bytes of key as (host-ordered) uint32_t. (Note - caller is
92// responsible for ensuring key size is at least 4 bytes.)
93uint32_t
94cf_rchash_fn_u32(const void *key, uint32_t key_size)
95{
96 (void)key_size;
97
98 return *(const uint32_t *)key;
99}
100
101// Hash all bytes of key using 32-bit Fowler-Noll-Vo method.
102uint32_t
103cf_rchash_fn_fnv32(const void *key, uint32_t key_size)
104{
105 return cf_hash_fnv32((const uint8_t *)key, (size_t)key_size);
106}
107
108// Useful if key is a null-terminated string. (Note - if using fixed-size keys,
109// key must still be padded to correctly compare keys in a bucket.)
110uint32_t
111cf_rchash_fn_zstr(const void *key, uint32_t key_size)
112{
113 (void)key_size;
114
115 return cf_hash_fnv32((const uint8_t *)key, strlen(key));
116}
117
118
119//==========================================================
120// Public API.
121//
122
123// TODO - change API to just return pointer?
124cf_rchash *
125cf_rchash_create(cf_rchash_hash_fn h_fn, cf_rchash_destructor_fn d_fn,
126 uint32_t key_size, uint32_t n_buckets, uint32_t flags)
127{
128 cf_assert(h_fn && n_buckets != 0 &&
129 // Can't have both lock options, but can opt for no locks at all.
130 ((flags & CF_RCHASH_BIG_LOCK) == 0 ||
131 (flags & CF_RCHASH_MANY_LOCK) == 0), CF_MISC, "bad param");
132
133 cf_rchash *h = cf_malloc(sizeof(cf_rchash));
134
135 h->h_fn = h_fn;
136 h->d_fn = d_fn;
137 h->key_size = key_size;
138 h->n_buckets = n_buckets;
139 h->flags = flags;
140 h->n_elements = 0;
141
142 // key_size == 0 always serves as flag to use variable key size public API.
143 if (key_size == 0) {
144 h->table = cf_calloc(n_buckets, sizeof(cf_rchash_ele_v));
145 }
146 else {
147 h->table = cf_calloc(n_buckets, sizeof(cf_rchash_ele_f) + key_size);
148 }
149
150 if ((flags & CF_RCHASH_BIG_LOCK) != 0) {
151 cf_mutex_init(&h->big_lock);
152 }
153 else if ((flags & CF_RCHASH_MANY_LOCK) != 0) {
154 h->bucket_locks = cf_malloc(sizeof(cf_mutex) * n_buckets);
155
156 for (uint32_t i = 0; i < n_buckets; i++) {
157 cf_mutex_init(&h->bucket_locks[i]);
158 }
159 }
160
161 return h;
162}
163
164void
165cf_rchash_destroy(cf_rchash *h)
166{
167 if (! h) {
168 return;
169 }
170
171 if (h->key_size == 0) {
172 cf_rchash_destroy_elements_v(h);
173 }
174 else {
175 cf_rchash_destroy_elements(h);
176 }
177
178 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
179 cf_mutex_destroy(&h->big_lock);
180 }
181 else if ((h->flags & CF_RCHASH_MANY_LOCK) != 0) {
182 for (uint32_t i = 0; i < h->n_buckets; i++) {
183 cf_mutex_destroy(&h->bucket_locks[i]);
184 }
185
186 cf_free(h->bucket_locks);
187 }
188
189 cf_free(h->table);
190 cf_free(h);
191}
192
193uint32_t
194cf_rchash_get_size(const cf_rchash *h)
195{
196 cf_assert(h, CF_MISC, "bad param");
197
198 // For now, not bothering with different methods per lock mode.
199 return as_load_uint32(&h->n_elements);
200}
201
202// If key is not already in hash, insert it with specified rc_malloc'd object.
203// If key is already in hash, replace (and release) existing object.
204void
205cf_rchash_put(cf_rchash *h, const void *key, uint32_t key_size, void *object)
206{
207 cf_assert(h && key && object, CF_MISC, "bad param");
208
209 if (h->key_size == 0) {
210 cf_rchash_put_v(h, key, key_size, object);
211 return;
212 }
213
214 cf_assert(key_size == h->key_size, CF_MISC, "bad param");
215
216 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
217 cf_mutex *l = cf_rchash_lock(h, hash);
218 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, hash);
219
220 // Most common case should be insert into empty bucket.
221 if (! e->object) {
222 cf_rchash_fill_element(e, h, key, object);
223 cf_rchash_unlock(l);
224 return;
225 }
226
227 cf_rchash_ele_f *e_head = e;
228
229 while (e) {
230 if (memcmp(e->key, key, key_size) != 0) {
231 e = e->next;
232 continue;
233 }
234
235 // In this case we're replacing the previous object with the new object.
236 void *free_object = e->object;
237
238 e->object = object;
239
240 cf_rchash_unlock(l);
241 cf_rchash_release_object(h, free_object);
242
243 return;
244 }
245
246 e = (cf_rchash_ele_f *)cf_malloc(sizeof(cf_rchash_ele_f) + key_size);
247
248 cf_rchash_fill_element(e, h, key, object);
249
250 // Insert just after head.
251 e->next = e_head->next;
252 e_head->next = e;
253
254 cf_rchash_unlock(l);
255}
256
257// Like cf_rchash_put(), but if key is already in hash, fail.
258int
259cf_rchash_put_unique(cf_rchash *h, const void *key, uint32_t key_size,
260 void *object)
261{
262 cf_assert(h && key && object, CF_MISC, "bad param");
263
264 if (h->key_size == 0) {
265 return cf_rchash_put_unique_v(h, key, key_size, object);
266 }
267
268 cf_assert(key_size == h->key_size, CF_MISC, "bad param");
269
270 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
271 cf_mutex *l = cf_rchash_lock(h, hash);
272 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, hash);
273
274 // Most common case should be insert into empty bucket.
275 if (! e->object) {
276 cf_rchash_fill_element(e, h, key, object);
277 cf_rchash_unlock(l);
278 return CF_RCHASH_OK;
279 }
280
281 cf_rchash_ele_f *e_head = e;
282
283 // Check for uniqueness of key - if not unique, fail!
284 while (e) {
285 if (memcmp(e->key, key, key_size) == 0) {
286 cf_rchash_unlock(l);
287 return CF_RCHASH_ERR_FOUND;
288 }
289
290 e = e->next;
291 }
292
293 e = (cf_rchash_ele_f *)cf_malloc(sizeof(cf_rchash_ele_f) + key_size);
294
295 cf_rchash_fill_element(e, h, key, object);
296
297 // Insert just after head.
298 e->next = e_head->next;
299 e_head->next = e;
300
301 cf_rchash_unlock(l);
302
303 return CF_RCHASH_OK;
304}
305
306// If key is found, object is returned with extra ref-count. When finished with
307// it, caller must always release the returned object, and must destroy and free
308// the object if the ref-count hits 0 - i.e. caller should do the equivalent of
309// cf_rchash_release_object().
310//
311// Or, caller may pass NULL object_r to use this method as an existence check.
312int
313cf_rchash_get(cf_rchash *h, const void *key, uint32_t key_size, void **object_r)
314{
315 cf_assert(h && key, CF_MISC, "bad param");
316
317 if (h->key_size == 0) {
318 return cf_rchash_get_v(h, key, key_size, object_r);
319 }
320
321 cf_assert(key_size == h->key_size, CF_MISC, "bad param");
322
323 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
324 cf_mutex *l = cf_rchash_lock(h, hash);
325 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, hash);
326
327 while (e && e->object) {
328 if (memcmp(key, e->key, key_size) != 0) {
329 e = e->next;
330 continue;
331 }
332
333 if (object_r) {
334 cf_rc_reserve(e->object);
335 *object_r = e->object;
336 }
337
338 cf_rchash_unlock(l);
339
340 return CF_RCHASH_OK;
341 }
342
343 cf_rchash_unlock(l);
344
345 return CF_RCHASH_ERR_NOT_FOUND;
346}
347
348// Removes the key and object from the hash, releasing the "original" ref-count.
349// If this causes the ref-count to hit 0, the object destructor is called and
350// the object is freed.
351int
352cf_rchash_delete(cf_rchash *h, const void *key, uint32_t key_size)
353{
354 // No check to verify the object.
355 return cf_rchash_delete_object(h, key, key_size, NULL);
356}
357
358// Like cf_rchash_delete() but checks that object found matches that specified.
359// Threads may race to delete and release the same object - they may be doing a
360// typical get ... delete, release sequence, or a reduce that deletes. While
361// ref-counts ensure only the *last* release destroys the object, the *first*
362// delete removes the object from the hash. If a new object is then immediately
363// inserted with the same key, other threads' deletes would mistakenly remove
364// this new element from the hash if they do not verify the object.
365int
366cf_rchash_delete_object(cf_rchash *h, const void *key, uint32_t key_size,
367 void *object)
368{
369 cf_assert(h && key, CF_MISC, "bad param");
370
371 if (h->key_size == 0) {
372 return cf_rchash_delete_object_v(h, key, key_size, object);
373 }
374
375 cf_assert(key_size == h->key_size, CF_MISC, "bad param");
376
377 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
378 cf_mutex *l = cf_rchash_lock(h, hash);
379 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, hash);
380
381 cf_rchash_ele_f *e_prev = NULL;
382
383 // Look for the element, remove and release if found.
384 while (e && e->object) {
385 if (memcmp(e->key, key, key_size) != 0) {
386 e_prev = e;
387 e = e->next;
388 continue;
389 }
390 // else - found it, remove from hash and release outside lock...
391
392 // ... unless it's the wrong object.
393 if (object && object != e->object) {
394 cf_rchash_unlock(l);
395 return CF_RCHASH_ERR_NOT_FOUND;
396 }
397
398 // Save pointers to release & free.
399 void *free_object = e->object;
400 cf_rchash_ele_f *free_e = NULL;
401
402 // If not at head, patch pointers and free element.
403 if (e_prev) {
404 e_prev->next = e->next;
405 free_e = e;
406 }
407 // If at head with no next, empty head.
408 else if (! e->next) {
409 e->object = NULL;
410 }
411 // If at head with a next, copy next into head and free next.
412 else {
413 free_e = e->next;
414 memcpy(e, e->next, sizeof(cf_rchash_ele_f) + key_size);
415 }
416
417 cf_rchash_size_decr(h);
418 cf_rchash_unlock(l);
419
420 cf_rchash_release_object(h, free_object);
421
422 if (free_e) {
423 cf_free(free_e);
424 }
425
426 return CF_RCHASH_OK;
427 }
428
429 cf_rchash_unlock(l);
430
431 return CF_RCHASH_ERR_NOT_FOUND;
432}
433
434// Call the given function (reduce_fn) for every element in the tree.
435//
436// The value returned by reduce_fn governs behavior as follows:
437// - CF_RCHASH_OK - continue iterating
438// - CF_RCHASH_REDUCE_DELETE - delete the current element, continue iterating
439// - anything else (e.g. CF_RCHASH_ERR) - stop iterating and return reduce_fn's
440// returned value
441//
442// If deleting an element causes the object ref-count to hit 0, the object
443// destructor is called and the object is freed.
444int
445cf_rchash_reduce(cf_rchash *h, cf_rchash_reduce_fn reduce_fn, void *udata)
446{
447 cf_assert(h && reduce_fn, CF_MISC, "bad param");
448
449 if (h->key_size == 0) {
450 return cf_rchash_reduce_v(h, reduce_fn, udata);
451 }
452
453 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
454 cf_mutex_lock(&h->big_lock);
455 }
456
457 for (uint32_t i = 0; i < h->n_buckets; i++) {
458 cf_mutex *bucket_lock = NULL;
459
460 if ((h->flags & CF_RCHASH_MANY_LOCK) != 0) {
461 bucket_lock = &h->bucket_locks[i];
462 cf_mutex_lock(bucket_lock);
463 }
464
465 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, i);
466 cf_rchash_ele_f *e_prev = NULL;
467
468 while (e && e->object) {
469 int rv = reduce_fn(e->key, h->key_size, e->object, udata);
470
471 if (rv == CF_RCHASH_OK) {
472 // Caller says keep going - most common case.
473
474 e_prev = e;
475 e = e->next;
476 }
477 else if (rv == CF_RCHASH_REDUCE_DELETE) {
478 // Caller says delete this element and keep going.
479
480 cf_rchash_release_object(h, e->object);
481 cf_rchash_size_decr(h);
482
483 // If not at head, patch pointers and free element.
484 if (e_prev) {
485 e_prev->next = e->next;
486 cf_free(e);
487 e = e_prev->next;
488 }
489 // If at head with no next, empty head.
490 else if (! e->next) {
491 e->object = NULL;
492 }
493 // If at head with a next, copy next into head and free next.
494 else {
495 cf_rchash_ele_f *free_e = e->next;
496
497 memcpy(e, e->next, sizeof(cf_rchash_ele_f) + h->key_size);
498 cf_free(free_e);
499 }
500 }
501 else {
502 // Caller says stop iterating.
503
504 if (bucket_lock) {
505 cf_mutex_unlock(bucket_lock);
506 }
507
508 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
509 cf_mutex_unlock(&h->big_lock);
510 }
511
512 return rv;
513 }
514 }
515
516 if (bucket_lock) {
517 cf_mutex_unlock(bucket_lock);
518 }
519 }
520
521 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
522 cf_mutex_unlock(&h->big_lock);
523 }
524
525 return CF_RCHASH_OK;
526}
527
528
529//==========================================================
530// Local helpers - variable key size public API.
531//
532
533void
534cf_rchash_put_v(cf_rchash *h, const void *key, uint32_t key_size, void *object)
535{
536 cf_assert(key_size != 0, CF_MISC, "bad param");
537
538 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
539 cf_mutex *l = cf_rchash_lock(h, hash);
540 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, hash);
541
542 // Most common case should be insert into empty bucket.
543 if (! e->object) {
544 cf_rchash_fill_element_v(e, h, key, key_size, object);
545 cf_rchash_unlock(l);
546 return;
547 }
548
549 cf_rchash_ele_v *e_head = e;
550
551 while (e) {
552 if (key_size != e->key_size || memcmp(e->key, key, key_size) != 0) {
553 e = e->next;
554 continue;
555 }
556
557 // In this case we're replacing the previous object with the new object.
558 void *free_object = e->object;
559
560 e->object = object;
561
562 cf_rchash_unlock(l);
563 cf_rchash_release_object(h, free_object);
564
565 return;
566 }
567
568 e = (cf_rchash_ele_v *)cf_malloc(sizeof(cf_rchash_ele_v));
569
570 cf_rchash_fill_element_v(e, h, key, key_size, object);
571
572 // Insert just after head.
573 e->next = e_head->next;
574 e_head->next = e;
575
576 cf_rchash_unlock(l);
577}
578
579int
580cf_rchash_put_unique_v(cf_rchash *h, const void *key, uint32_t key_size,
581 void *object)
582{
583 cf_assert(key_size != 0, CF_MISC, "bad param");
584
585 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
586 cf_mutex *l = cf_rchash_lock(h, hash);
587 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, hash);
588
589 // Most common case should be insert into empty bucket.
590 if (! e->object) {
591 cf_rchash_fill_element_v(e, h, key, key_size, object);
592 cf_rchash_unlock(l);
593 return CF_RCHASH_OK;
594 }
595
596 cf_rchash_ele_v *e_head = e;
597
598 // Check for uniqueness of key - if not unique, fail!
599 while (e) {
600 if (key_size == e->key_size && memcmp(e->key, key, key_size) == 0) {
601 cf_rchash_unlock(l);
602 return CF_RCHASH_ERR_FOUND;
603 }
604
605 e = e->next;
606 }
607
608 e = (cf_rchash_ele_v *)cf_malloc(sizeof(cf_rchash_ele_v));
609
610 cf_rchash_fill_element_v(e, h, key, key_size, object);
611
612 // Insert just after head.
613 e->next = e_head->next;
614 e_head->next = e;
615
616 cf_rchash_unlock(l);
617
618 return CF_RCHASH_OK;
619}
620
621int
622cf_rchash_get_v(cf_rchash *h, const void *key, uint32_t key_size,
623 void **object_r)
624{
625 cf_assert(key_size != 0, CF_MISC, "bad param");
626
627 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
628 cf_mutex *l = cf_rchash_lock(h, hash);
629 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, hash);
630
631 while (e && e->object) {
632 if (key_size != e->key_size || memcmp(key, e->key, key_size) != 0) {
633 e = e->next;
634 continue;
635 }
636
637 if (object_r) {
638 cf_rc_reserve(e->object);
639 *object_r = e->object;
640 }
641
642 cf_rchash_unlock(l);
643
644 return CF_RCHASH_OK;
645 }
646
647 cf_rchash_unlock(l);
648
649 return CF_RCHASH_ERR_NOT_FOUND;
650}
651
652int
653cf_rchash_delete_object_v(cf_rchash *h, const void *key, uint32_t key_size,
654 void *object)
655{
656 cf_assert(key_size != 0, CF_MISC, "bad param");
657
658 uint32_t hash = cf_rchash_calculate_hash(h, key, key_size);
659 cf_mutex *l = cf_rchash_lock(h, hash);
660 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, hash);
661
662 cf_rchash_ele_v *e_prev = NULL;
663
664 // Look for the element, remove and release if found.
665 while (e && e->object) {
666 if (key_size != e->key_size || memcmp(e->key, key, key_size) != 0) {
667 e_prev = e;
668 e = e->next;
669 continue;
670 }
671 // else - found it, remove from hash and release outside lock...
672
673 // ... unless it's the wrong object.
674 if (object && object != e->object) {
675 cf_rchash_unlock(l);
676 return CF_RCHASH_ERR_NOT_FOUND;
677 }
678
679 // Save pointers to release & free.
680 void *free_key = e->key;
681 void *free_object = e->object;
682 cf_rchash_ele_v *free_e = NULL;
683
684 // If not at head, patch pointers and free element.
685 if (e_prev) {
686 e_prev->next = e->next;
687 free_e = e;
688 }
689 // If at head with no next, empty head.
690 else if (! e->next) {
691 memset(e, 0, sizeof(cf_rchash_ele_v));
692 }
693 // If at head with a next, copy next into head and free next.
694 else {
695 free_e = e->next;
696 memcpy(e, e->next, sizeof(cf_rchash_ele_v));
697 }
698
699 cf_rchash_size_decr(h);
700 cf_rchash_unlock(l);
701
702 cf_free(free_key);
703 cf_rchash_release_object(h, free_object);
704
705 if (free_e) {
706 cf_free(free_e);
707 }
708
709 return CF_RCHASH_OK;
710 }
711
712 cf_rchash_unlock(l);
713
714 return CF_RCHASH_ERR_NOT_FOUND;
715}
716
717int
718cf_rchash_reduce_v(cf_rchash *h, cf_rchash_reduce_fn reduce_fn, void *udata)
719{
720 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
721 cf_mutex_lock(&h->big_lock);
722 }
723
724 for (uint32_t i = 0; i < h->n_buckets; i++) {
725 cf_mutex *bucket_lock = NULL;
726
727 if ((h->flags & CF_RCHASH_MANY_LOCK) != 0) {
728 bucket_lock = &h->bucket_locks[i];
729 cf_mutex_lock(bucket_lock);
730 }
731
732 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, i);
733 cf_rchash_ele_v *e_prev = NULL;
734
735 while (e && e->object) {
736 int rv = reduce_fn(e->key, e->key_size, e->object, udata);
737
738 if (rv == CF_RCHASH_OK) {
739 // Caller says keep going - most common case.
740
741 e_prev = e;
742 e = e->next;
743 }
744 else if (rv == CF_RCHASH_REDUCE_DELETE) {
745 // Caller says delete this element and keep going.
746
747 cf_free(e->key);
748 cf_rchash_release_object(h, e->object);
749
750 cf_rchash_size_decr(h);
751
752 // If not at head, patch pointers and free element.
753 if (e_prev) {
754 e_prev->next = e->next;
755 cf_free(e);
756 e = e_prev->next;
757 }
758 // If at head with no next, empty head.
759 else if (! e->next) {
760 memset(e, 0, sizeof(cf_rchash_ele_v));
761 }
762 // If at head with a next, copy next into head and free next.
763 else {
764 cf_rchash_ele_v *free_e = e->next;
765
766 memcpy(e, e->next, sizeof(cf_rchash_ele_v));
767 cf_free(free_e);
768 }
769 }
770 else {
771 // Caller says stop iterating.
772
773 if (bucket_lock) {
774 cf_mutex_unlock(bucket_lock);
775 }
776
777 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
778 cf_mutex_unlock(&h->big_lock);
779 }
780
781 return rv;
782 }
783 }
784
785 if (bucket_lock) {
786 cf_mutex_unlock(bucket_lock);
787 }
788 }
789
790 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
791 cf_mutex_unlock(&h->big_lock);
792 }
793
794 return CF_RCHASH_OK;
795}
796
797
798//==========================================================
799// Local helpers - generic utilities.
800//
801
802static inline void
803cf_rchash_destroy_elements(cf_rchash *h)
804{
805 for (uint32_t i = 0; i < h->n_buckets; i++) {
806 cf_rchash_ele_f *e = cf_rchash_get_bucket(h, i);
807
808 if (! e->object) {
809 continue;
810 }
811
812 cf_rchash_release_object(h, e->object);
813 e = e->next; // skip the first, it's in place
814
815 while (e) {
816 cf_rchash_ele_f *temp = e->next;
817
818 cf_rchash_release_object(h, e->object);
819 cf_free(e);
820 e = temp;
821 }
822 }
823}
824
825static inline void
826cf_rchash_destroy_elements_v(cf_rchash *h)
827{
828 for (uint32_t i = 0; i < h->n_buckets; i++) {
829 cf_rchash_ele_v *e = cf_rchash_get_bucket_v(h, i);
830
831 if (! e->object) {
832 continue;
833 }
834
835 cf_rchash_release_object(h, e->object);
836 cf_free(e->key);
837 e = e->next; // skip the first, it's in place
838
839 while (e) {
840 cf_rchash_ele_v *temp = e->next;
841
842 cf_rchash_release_object(h, e->object);
843 cf_free(e->key);
844 cf_free(e);
845 e = temp;
846 }
847 }
848}
849
850static inline uint32_t
851cf_rchash_calculate_hash(cf_rchash *h, const void *key, uint32_t key_size)
852{
853 return h->h_fn(key, key_size) % h->n_buckets;
854}
855
856static inline cf_mutex *
857cf_rchash_lock(cf_rchash *h, uint32_t i)
858{
859 cf_mutex *l = NULL;
860
861 if ((h->flags & CF_RCHASH_BIG_LOCK) != 0) {
862 l = &h->big_lock;
863 }
864 else if ((h->flags & CF_RCHASH_MANY_LOCK) != 0) {
865 l = &h->bucket_locks[i];
866 }
867
868 if (l) {
869 cf_mutex_lock(l);
870 }
871
872 return l;
873}
874
875static inline void
876cf_rchash_unlock(cf_mutex *l)
877{
878 if (l) {
879 cf_mutex_unlock(l);
880 }
881}
882
883static inline cf_rchash_ele_f *
884cf_rchash_get_bucket(cf_rchash *h, uint32_t i)
885{
886 return (cf_rchash_ele_f *)((uint8_t *)h->table +
887 ((sizeof(cf_rchash_ele_f) + h->key_size) * i));
888}
889
890static inline cf_rchash_ele_v *
891cf_rchash_get_bucket_v(cf_rchash *h, uint32_t i)
892{
893 return (cf_rchash_ele_v *)((uint8_t *)h->table +
894 (sizeof(cf_rchash_ele_v) * i));
895}
896
897static inline void
898cf_rchash_fill_element(cf_rchash_ele_f *e, cf_rchash *h, const void *key,
899 void *object)
900{
901 memcpy(e->key, key, h->key_size);
902 e->object = object;
903 cf_rchash_size_incr(h);
904}
905
906static inline void
907cf_rchash_fill_element_v(cf_rchash_ele_v *e, cf_rchash *h, const void *key,
908 uint32_t key_size, void *object)
909{
910 e->key = cf_malloc(key_size);
911
912 memcpy(e->key, key, key_size);
913 e->key_size = key_size;
914
915 e->object = object;
916
917 cf_rchash_size_incr(h);
918}
919
920static inline void
921cf_rchash_size_incr(cf_rchash *h)
922{
923 // For now, not bothering with different methods per lock mode.
924 as_incr_int32(&h->n_elements);
925}
926
927static inline void
928cf_rchash_size_decr(cf_rchash *h)
929{
930 // For now, not bothering with different methods per lock mode.
931 as_decr_int32(&h->n_elements);
932}
933
934static inline void
935cf_rchash_release_object(cf_rchash *h, void *object)
936{
937 if (cf_rc_release(object) == 0) {
938 if (h->d_fn) {
939 (h->d_fn)(object);
940 }
941
942 cf_rc_free(object);
943 }
944}
945