1/*
2 * shash.c
3 *
4 * Copyright (C) 2017 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 "shash.h"
28
29#include <stdbool.h>
30#include <stddef.h>
31#include <stdint.h>
32#include <string.h>
33
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// TODO - in_use is wasteful, especially when not first in bucket.
46typedef struct cf_shash_ele_s {
47 struct cf_shash_ele_s *next;
48 bool in_use;
49 uint8_t data[];
50} cf_shash_ele;
51
52
53//==========================================================
54// Forward declarations.
55//
56
57static inline void cf_shash_clear_table(cf_shash *h);
58static inline void cf_shash_destroy_elements(cf_shash *h);
59static inline uint32_t cf_shash_calculate_hash(cf_shash *h, const void *key);
60static inline cf_mutex *cf_shash_lock(cf_shash *h, uint32_t i);
61static inline void cf_shash_unlock(cf_mutex *l);
62static inline cf_shash_ele *cf_shash_get_bucket(cf_shash *h, uint32_t i);
63static inline void cf_shash_fill_element(cf_shash_ele *e, cf_shash *h, const void *key, const void *value);
64static inline void cf_shash_size_incr(cf_shash *h);
65static inline void cf_shash_size_decr(cf_shash *h);
66int cf_shash_delete_or_pop(cf_shash *h, const void *key, void *value);
67
68
69//==========================================================
70// Inlines & macros.
71//
72
73#define ELE_KEY(_h, _e) ((void *)_e->data)
74#define ELE_VALUE(_h, _e) ((void *)(_e->data + _h->key_size))
75
76
77//==========================================================
78// Public API - useful hash functions.
79//
80
81// Interpret first 4 bytes of key as (host-ordered) uint32_t. (Note - caller
82// is responsible for ensuring key size is at least 4 bytes.)
83uint32_t
84cf_shash_fn_u32(const void *key)
85{
86 return *(const uint32_t *)key;
87}
88
89// Useful if key is a pointer.
90uint32_t
91cf_shash_fn_ptr(const void *key)
92{
93 return cf_hash_ptr32(key);
94}
95
96// Useful if key is a null-terminated string. (Note - using fixed-size keys, so
97// key must still be padded to correctly compare keys in a bucket.)
98uint32_t
99cf_shash_fn_zstr(const void *key)
100{
101 return cf_hash_fnv32((const uint8_t *)key, strlen(key));
102}
103
104
105//==========================================================
106// Public API.
107//
108
109cf_shash *
110cf_shash_create(cf_shash_hash_fn h_fn, uint32_t key_size, uint32_t value_size,
111 uint32_t n_buckets, uint32_t flags)
112{
113 cf_assert(h_fn && key_size != 0 && n_buckets != 0, CF_MISC, "bad param");
114 // Note - value_size 0 works, and is used.
115
116 cf_shash *h = cf_malloc(sizeof(cf_shash));
117
118 h->h_fn = h_fn;
119 h->key_size = key_size;
120 h->value_size = value_size;
121 h->ele_size = sizeof(cf_shash_ele) + key_size + value_size;
122 h->n_buckets = n_buckets;
123 h->flags = flags;
124 h->n_elements = 0;
125
126 // Can't have both lock options, but can opt for no locks at all.
127 cf_assert((flags & CF_SHASH_BIG_LOCK) == 0 ||
128 (flags & CF_SHASH_MANY_LOCK) == 0, CF_MISC, "bad flags param");
129
130 h->table = (cf_shash_ele *)cf_malloc(n_buckets * h->ele_size);
131
132 cf_shash_clear_table(h);
133
134 if ((flags & CF_SHASH_BIG_LOCK) != 0) {
135 cf_mutex_init(&h->big_lock);
136 }
137 else if ((flags & CF_SHASH_MANY_LOCK) != 0) {
138 h->bucket_locks = cf_malloc(sizeof(cf_mutex) * n_buckets);
139
140 for (uint32_t i = 0; i < n_buckets; i++) {
141 cf_mutex_init(&h->bucket_locks[i]);
142 }
143 }
144
145 return h;
146}
147
148void
149cf_shash_destroy(cf_shash *h)
150{
151 if (! h) {
152 return;
153 }
154
155 cf_shash_destroy_elements(h);
156
157 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
158 cf_mutex_destroy(&h->big_lock);
159 }
160 else if ((h->flags & CF_SHASH_MANY_LOCK) != 0) {
161 for (uint32_t i = 0; i < h->n_buckets; i++) {
162 cf_mutex_destroy(&h->bucket_locks[i]);
163 }
164
165 cf_free(h->bucket_locks);
166 }
167
168 cf_free(h->table);
169 cf_free(h);
170}
171
172uint32_t
173cf_shash_get_size(cf_shash *h)
174{
175 cf_assert(h, CF_MISC, "bad param");
176
177 // For now, not bothering with different methods per lock mode.
178 return cf_atomic32_get(h->n_elements);
179}
180
181void
182cf_shash_put(cf_shash *h, const void *key, const void *value)
183{
184 cf_assert(h && key && value, CF_MISC, "bad param");
185
186 uint32_t hash = cf_shash_calculate_hash(h, key);
187 cf_mutex *l = cf_shash_lock(h, hash);
188 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
189
190 // Most common case should be insert into empty bucket.
191 if (! e->in_use) {
192 cf_shash_fill_element(e, h, key, value);
193 cf_shash_unlock(l);
194 return;
195 }
196
197 cf_shash_ele *e_head = e;
198
199 while (e) {
200 if (memcmp(ELE_KEY(h, e), key, h->key_size) == 0) {
201 // Replace the previous value with the new value.
202 memcpy(ELE_VALUE(h, e), value, h->value_size);
203 cf_shash_unlock(l);
204 return;
205 }
206
207 e = e->next;
208 }
209
210 e = (cf_shash_ele *)cf_malloc(h->ele_size);
211
212 cf_shash_fill_element(e, h, key, value);
213
214 // Insert just after head.
215 e->next = e_head->next;
216 e_head->next = e;
217
218 cf_shash_unlock(l);
219}
220
221int
222cf_shash_put_unique(cf_shash *h, const void *key, const void *value)
223{
224 cf_assert(h && key && value, CF_MISC, "bad param");
225
226 uint32_t hash = cf_shash_calculate_hash(h, key);
227 cf_mutex *l = cf_shash_lock(h, hash);
228 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
229
230 // Most common case should be insert into empty bucket.
231 if (! e->in_use) {
232 cf_shash_fill_element(e, h, key, value);
233 cf_shash_unlock(l);
234 return CF_SHASH_OK;
235 }
236
237 cf_shash_ele *e_head = e;
238
239 while (e) {
240 if (memcmp(ELE_KEY(h, e), key, h->key_size) == 0) {
241 cf_shash_unlock(l);
242 return CF_SHASH_ERR_FOUND;
243 }
244
245 e = e->next;
246 }
247
248 e = (cf_shash_ele *)cf_malloc(h->ele_size);
249
250 cf_shash_fill_element(e, h, key, value);
251
252 // Insert just after head.
253 e->next = e_head->next;
254 e_head->next = e;
255
256 cf_shash_unlock(l);
257
258 return CF_SHASH_OK;
259}
260
261// FIXME - replace with cf_shash_put_unique_or_get_vlock()?
262void
263cf_shash_update(cf_shash *h, const void *key, void *value_old, void *value_new,
264 cf_shash_update_fn update_fn, void *udata)
265{
266 cf_assert(h && key && update_fn, CF_MISC, "bad param");
267
268 uint32_t hash = cf_shash_calculate_hash(h, key);
269 cf_mutex *l = cf_shash_lock(h, hash);
270 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
271
272 // Insert new value into empty bucket.
273 if (! e->in_use) {
274 (update_fn)(key, NULL, value_new, udata);
275 cf_shash_fill_element(e, h, key, value_new);
276 cf_shash_unlock(l);
277 return;
278 }
279
280 cf_shash_ele *e_head = e;
281
282 while (e) {
283 if (memcmp(ELE_KEY(h, e), key, h->key_size) == 0) {
284 if (value_old) {
285 memcpy(value_old, ELE_VALUE(h, e), h->value_size);
286 }
287
288 (update_fn)(key, value_old, value_new, udata);
289
290 memcpy(ELE_VALUE(h, e), value_new, h->value_size);
291 cf_shash_unlock(l);
292
293 return;
294 }
295
296 e = e->next;
297 }
298
299 (update_fn)(key, NULL, value_new, udata);
300
301 e = (cf_shash_ele *)cf_malloc(h->ele_size);
302
303 cf_shash_fill_element(e, h, key, value_new);
304
305 // Insert just after head.
306 e->next = e_head->next;
307 e_head->next = e;
308
309 cf_shash_unlock(l);
310}
311
312int
313cf_shash_get(cf_shash *h, const void *key, void *value)
314{
315 cf_assert(h && key, CF_MISC, "bad param");
316
317 uint32_t hash = cf_shash_calculate_hash(h, key);
318 cf_mutex *l = cf_shash_lock(h, hash);
319 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
320
321 while (e && e->in_use) {
322 if (memcmp(ELE_KEY(h, e), key, h->key_size) == 0) {
323 if (value) {
324 memcpy(value, ELE_VALUE(h, e), h->value_size);
325 }
326
327 cf_shash_unlock(l);
328 return CF_SHASH_OK;
329 }
330
331 e = e->next;
332 }
333
334 cf_shash_unlock(l);
335
336 return CF_SHASH_ERR_NOT_FOUND;
337}
338
339int
340cf_shash_get_vlock(cf_shash *h, const void *key, void **value_r,
341 cf_mutex **vlock_r)
342{
343 cf_assert(h && key && value_r && vlock_r, CF_MISC, "bad param");
344
345 uint32_t hash = cf_shash_calculate_hash(h, key);
346 cf_mutex *l = cf_shash_lock(h, hash);
347 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
348
349 while (e && e->in_use) {
350 if (memcmp(ELE_KEY(h, e), key, h->key_size) == 0) {
351 *value_r = ELE_VALUE(h, e);
352 *vlock_r = l;
353 return CF_SHASH_OK;
354 }
355
356 e = e->next;
357 }
358
359 cf_shash_unlock(l);
360
361 return CF_SHASH_ERR_NOT_FOUND;
362}
363
364int
365cf_shash_delete(cf_shash *h, const void *key)
366{
367 return cf_shash_delete_or_pop(h, key, NULL);
368}
369
370int
371cf_shash_delete_lockfree(cf_shash *h, const void *key)
372{
373 cf_assert(h && key, CF_MISC, "bad param");
374
375 uint32_t hash = cf_shash_calculate_hash(h, key);
376 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
377
378 cf_shash_ele *e_prev = NULL;
379
380 // Look for the element, remove and release if found.
381 while (e && e->in_use) {
382 if (memcmp(ELE_KEY(h, e), key, h->key_size) != 0) {
383 e_prev = e;
384 e = e->next;
385 continue;
386 }
387 // else - found it, remove from hash, free (if needed).
388
389 // If not at head, patch pointers and free element.
390 if (e_prev) {
391 e_prev->next = e->next;
392 cf_free(e);
393 }
394 // If at head with no next, empty head.
395 else if (! e->next) {
396 e->in_use = false;
397 }
398 // If at head with a next, copy next into head and free next.
399 else {
400 cf_shash_ele *free_e = e->next;
401
402 memcpy(e, e->next, h->ele_size);
403 cf_free(free_e);
404 }
405
406 cf_shash_size_decr(h);
407
408 return CF_SHASH_OK;
409 }
410
411 return CF_SHASH_ERR_NOT_FOUND;
412}
413
414// TODO - Rename to cf_shash_pop()?
415int
416cf_shash_get_and_delete(cf_shash *h, const void *key, void *value)
417{
418 cf_assert(value, CF_MISC, "bad param");
419
420 return cf_shash_delete_or_pop(h, key, value);
421}
422
423void
424cf_shash_delete_all(cf_shash *h)
425{
426 cf_assert(h, CF_MISC, "bad param");
427
428 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
429 cf_mutex_lock(&h->big_lock);
430 }
431
432 uint8_t *bucket = (uint8_t*)h->table;
433
434 for (uint32_t i = 0; i < h->n_buckets; i++) {
435 cf_mutex *bucket_lock = NULL;
436
437 if ((h->flags & CF_SHASH_MANY_LOCK) != 0) {
438 bucket_lock = &h->bucket_locks[i];
439 cf_mutex_lock(bucket_lock);
440 }
441
442 cf_shash_ele *e = ((cf_shash_ele *)bucket)->next;
443
444 while (e) {
445 cf_shash_ele *temp = e->next;
446
447 cf_free(e);
448 e = temp;
449
450 cf_shash_size_decr(h);
451 }
452
453 if (((cf_shash_ele *)bucket)->in_use) {
454 ((cf_shash_ele *)bucket)->in_use = false;
455 ((cf_shash_ele *)bucket)->next = NULL;
456
457 cf_shash_size_decr(h);
458 }
459
460 if (bucket_lock) {
461 cf_mutex_unlock(bucket_lock);
462 }
463
464 bucket += h->ele_size;
465 }
466
467 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
468 cf_mutex_unlock(&h->big_lock);
469 }
470}
471
472int
473cf_shash_reduce(cf_shash *h, cf_shash_reduce_fn reduce_fn, void *udata)
474{
475 cf_assert(h && reduce_fn, CF_MISC, "bad param");
476
477 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
478 cf_mutex_lock(&h->big_lock);
479 }
480
481 uint8_t *bucket = (uint8_t*)h->table;
482
483 for (uint32_t i = 0; i < h->n_buckets; i++) {
484 cf_mutex *bucket_lock = NULL;
485
486 if ((h->flags & CF_SHASH_MANY_LOCK) != 0) {
487 bucket_lock = &h->bucket_locks[i];
488 cf_mutex_lock(bucket_lock);
489 }
490
491 cf_shash_ele *e = (cf_shash_ele *)bucket;
492 cf_shash_ele *e_prev = NULL;
493
494 while (e && e->in_use) {
495 int rv = reduce_fn(ELE_KEY(h, e), ELE_VALUE(h, e), udata);
496
497 if (rv == CF_SHASH_OK) {
498 // Caller says keep going - most common case.
499
500 e_prev = e;
501 e = e->next;
502 }
503 else if (rv == CF_SHASH_REDUCE_DELETE) {
504 // Caller says delete this element and keep going.
505
506 // If not at head, patch pointers and free element.
507 if (e_prev) {
508 e_prev->next = e->next;
509 cf_free(e);
510 e = e_prev->next;
511 }
512 // If at head with no next, empty head.
513 else if (! e->next) {
514 e->in_use = false;
515 }
516 // If at head with a next, copy next into head and free next.
517 else {
518 cf_shash_ele *free_e = e->next;
519
520 memcpy(e, e->next, h->ele_size);
521 cf_free(free_e);
522 }
523
524 cf_shash_size_decr(h);
525 }
526 else {
527 // Caller says stop iterating.
528
529 if (bucket_lock) {
530 cf_mutex_unlock(bucket_lock);
531 }
532
533 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
534 cf_mutex_unlock(&h->big_lock);
535 }
536
537 return rv;
538 }
539 }
540
541 if (bucket_lock) {
542 cf_mutex_unlock(bucket_lock);
543 }
544
545 bucket += h->ele_size;
546 }
547
548 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
549 cf_mutex_unlock(&h->big_lock);
550 }
551
552 return CF_SHASH_OK;
553}
554
555
556//==========================================================
557// Local helpers.
558//
559
560static inline void
561cf_shash_clear_table(cf_shash *h)
562{
563 uint8_t *bucket = (uint8_t*)h->table;
564 uint8_t *end = bucket + (h->n_buckets * h->ele_size);
565
566 while (bucket < end) {
567 ((cf_shash_ele *)bucket)->next = NULL;
568 ((cf_shash_ele *)bucket)->in_use = false;
569 bucket += h->ele_size;
570 }
571}
572
573static inline void
574cf_shash_destroy_elements(cf_shash *h)
575{
576 uint8_t *bucket = (uint8_t*)h->table;
577 uint8_t *end = bucket + (h->n_buckets * h->ele_size);
578
579 while (bucket < end) {
580 cf_shash_ele *e = ((cf_shash_ele *)bucket)->next;
581
582 while (e) {
583 cf_shash_ele *temp = e->next;
584
585 cf_free(e);
586 e = temp;
587 }
588
589 bucket += h->ele_size;
590 }
591}
592
593static inline uint32_t
594cf_shash_calculate_hash(cf_shash *h, const void *key)
595{
596 return h->h_fn(key) % h->n_buckets;
597}
598
599static inline cf_mutex *
600cf_shash_lock(cf_shash *h, uint32_t i)
601{
602 cf_mutex *l = NULL;
603
604 if ((h->flags & CF_SHASH_BIG_LOCK) != 0) {
605 l = &h->big_lock;
606 }
607 else if ((h->flags & CF_SHASH_MANY_LOCK) != 0) {
608 l = &h->bucket_locks[i];
609 }
610
611 if (l) {
612 cf_mutex_lock(l);
613 }
614
615 return l;
616}
617
618static inline void
619cf_shash_unlock(cf_mutex *l)
620{
621 if (l) {
622 cf_mutex_unlock(l);
623 }
624}
625
626static inline cf_shash_ele *
627cf_shash_get_bucket(cf_shash *h, uint32_t i)
628{
629 return (cf_shash_ele *)((uint8_t *)h->table + (h->ele_size * i));
630}
631
632static inline void
633cf_shash_fill_element(cf_shash_ele *e, cf_shash *h, const void *key,
634 const void *value)
635{
636 memcpy(ELE_KEY(h, e), key, h->key_size);
637 memcpy(ELE_VALUE(h, e), value, h->value_size);
638 e->in_use = true;
639 cf_shash_size_incr(h);
640}
641
642static inline void
643cf_shash_size_incr(cf_shash *h)
644{
645 // For now, not bothering with different methods per lock mode.
646 cf_atomic32_incr(&h->n_elements);
647}
648
649static inline void
650cf_shash_size_decr(cf_shash *h)
651{
652 // For now, not bothering with different methods per lock mode.
653 cf_atomic32_decr(&h->n_elements);
654}
655
656int
657cf_shash_delete_or_pop(cf_shash *h, const void *key, void *value)
658{
659 cf_assert(h && key, CF_MISC, "bad param");
660
661 uint32_t hash = cf_shash_calculate_hash(h, key);
662 cf_mutex *l = cf_shash_lock(h, hash);
663 cf_shash_ele *e = cf_shash_get_bucket(h, hash);
664
665 cf_shash_ele *e_prev = NULL;
666
667 // Look for the element, remove and release if found.
668 while (e && e->in_use) {
669 if (memcmp(ELE_KEY(h, e), key, h->key_size) != 0) {
670 e_prev = e;
671 e = e->next;
672 continue;
673 }
674 // else - found it, remove from hash, free (if needed) outside lock.
675
676 // Return value.
677 if (value) {
678 memcpy(value, ELE_VALUE(h, e), h->value_size);
679 }
680
681 // Save pointer to free.
682 cf_shash_ele *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 e->in_use = false;
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, h->ele_size);
697 }
698
699 cf_shash_size_decr(h);
700 cf_shash_unlock(l);
701
702 if (free_e) {
703 cf_free(free_e);
704 }
705
706 return CF_SHASH_OK;
707 }
708
709 cf_shash_unlock(l);
710
711 return CF_SHASH_ERR_NOT_FOUND;
712}
713