| /* |
| * Copyright 2012-2015 Samy Al Bahra. |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND |
| * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
| * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
| * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
| * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
| * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
| * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
| * SUCH DAMAGE. |
| */ |
| |
| #ifndef CK_HT_H |
| #define CK_HT_H |
| |
| #include <ck_pr.h> |
| |
| #define CK_F_HT |
| #if defined(CK_F_PR_LOAD_64) && defined(CK_F_PR_STORE_64) |
| #define CK_HT_TYPE uint64_t |
| #define CK_HT_TYPE_LOAD ck_pr_load_64 |
| #define CK_HT_TYPE_STORE ck_pr_store_64 |
| #define CK_HT_TYPE_MAX UINT64_MAX |
| #else |
| #define CK_HT_TYPE uint32_t |
| #define CK_HT_TYPE_LOAD ck_pr_load_32 |
| #define CK_HT_TYPE_STORE ck_pr_store_32 |
| #define CK_HT_TYPE_MAX UINT32_MAX |
| #endif |
| |
| |
| #include <ck_cc.h> |
| #include <ck_malloc.h> |
| #include <ck_md.h> |
| #include <ck_stdint.h> |
| #include <ck_stdbool.h> |
| #include <ck_stddef.h> |
| |
| struct ck_ht_hash { |
| uint64_t value; |
| }; |
| typedef struct ck_ht_hash ck_ht_hash_t; |
| |
| #define CK_HT_MODE_DIRECT 1U |
| #define CK_HT_MODE_BYTESTRING 2U |
| #define CK_HT_WORKLOAD_DELETE 4U |
| |
| #if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS) |
| #define CK_HT_PP |
| #define CK_HT_KEY_LENGTH ((sizeof(void *) * 8) - CK_MD_VMA_BITS) |
| #define CK_HT_KEY_MASK ((1U << CK_HT_KEY_LENGTH) - 1) |
| #else |
| #define CK_HT_KEY_LENGTH 65535U |
| #endif |
| |
| struct ck_ht_entry { |
| #ifdef CK_HT_PP |
| uintptr_t key; |
| uintptr_t value CK_CC_PACKED; |
| } CK_CC_ALIGN(16); |
| #else |
| uintptr_t key; |
| uintptr_t value; |
| CK_HT_TYPE key_length; |
| CK_HT_TYPE hash; |
| } CK_CC_ALIGN(32); |
| #endif |
| typedef struct ck_ht_entry ck_ht_entry_t; |
| |
| /* |
| * The user is free to define their own stub values. |
| */ |
| #ifndef CK_HT_KEY_EMPTY |
| #define CK_HT_KEY_EMPTY ((uintptr_t)0) |
| #endif |
| |
| #ifndef CK_HT_KEY_TOMBSTONE |
| #define CK_HT_KEY_TOMBSTONE (~CK_HT_KEY_EMPTY) |
| #endif |
| |
| /* |
| * Hash callback function. First argument is updated to contain a hash value, |
| * second argument is the key, third argument is key length and final argument |
| * is the hash table seed value. |
| */ |
| typedef void ck_ht_hash_cb_t(ck_ht_hash_t *, const void *, size_t, uint64_t); |
| |
| struct ck_ht_map; |
| struct ck_ht { |
| struct ck_malloc *m; |
| struct ck_ht_map *map; |
| unsigned int mode; |
| uint64_t seed; |
| ck_ht_hash_cb_t *h; |
| }; |
| typedef struct ck_ht ck_ht_t; |
| |
| struct ck_ht_stat { |
| uint64_t probe_maximum; |
| uint64_t n_entries; |
| }; |
| |
| struct ck_ht_iterator { |
| struct ck_ht_entry *current; |
| uint64_t offset; |
| }; |
| typedef struct ck_ht_iterator ck_ht_iterator_t; |
| |
| #define CK_HT_ITERATOR_INITIALIZER { NULL, 0 } |
| |
| CK_CC_INLINE static void |
| ck_ht_iterator_init(struct ck_ht_iterator *iterator) |
| { |
| |
| iterator->current = NULL; |
| iterator->offset = 0; |
| return; |
| } |
| |
| CK_CC_INLINE static bool |
| ck_ht_entry_empty(ck_ht_entry_t *entry) |
| { |
| |
| return entry->key == CK_HT_KEY_EMPTY; |
| } |
| |
| CK_CC_INLINE static void |
| ck_ht_entry_key_set_direct(ck_ht_entry_t *entry, uintptr_t key) |
| { |
| |
| entry->key = key; |
| return; |
| } |
| |
| CK_CC_INLINE static void |
| ck_ht_entry_key_set(ck_ht_entry_t *entry, const void *key, uint16_t key_length) |
| { |
| |
| #ifdef CK_HT_PP |
| entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS); |
| #else |
| entry->key = (uintptr_t)key; |
| entry->key_length = key_length; |
| #endif |
| |
| return; |
| } |
| |
| CK_CC_INLINE static void * |
| ck_ht_entry_key(ck_ht_entry_t *entry) |
| { |
| |
| #ifdef CK_HT_PP |
| return (void *)(entry->key & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1)); |
| #else |
| return (void *)entry->key; |
| #endif |
| } |
| |
| CK_CC_INLINE static uint16_t |
| ck_ht_entry_key_length(ck_ht_entry_t *entry) |
| { |
| |
| #ifdef CK_HT_PP |
| return entry->key >> CK_MD_VMA_BITS; |
| #else |
| return entry->key_length; |
| #endif |
| } |
| |
| CK_CC_INLINE static void * |
| ck_ht_entry_value(ck_ht_entry_t *entry) |
| { |
| |
| #ifdef CK_HT_PP |
| return (void *)(entry->value & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1)); |
| #else |
| return (void *)entry->value; |
| #endif |
| } |
| |
| CK_CC_INLINE static void |
| ck_ht_entry_set(struct ck_ht_entry *entry, |
| ck_ht_hash_t h, |
| const void *key, |
| uint16_t key_length, |
| const void *value) |
| { |
| |
| #ifdef CK_HT_PP |
| entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS); |
| entry->value = (uintptr_t)value | ((uintptr_t)(h.value >> 32) << CK_MD_VMA_BITS); |
| #else |
| entry->key = (uintptr_t)key; |
| entry->value = (uintptr_t)value; |
| entry->key_length = key_length; |
| entry->hash = h.value; |
| #endif |
| |
| return; |
| } |
| |
| CK_CC_INLINE static void |
| ck_ht_entry_set_direct(struct ck_ht_entry *entry, |
| ck_ht_hash_t h, |
| uintptr_t key, |
| uintptr_t value) |
| { |
| |
| entry->key = key; |
| entry->value = value; |
| |
| #ifndef CK_HT_PP |
| entry->hash = h.value; |
| #else |
| (void)h; |
| #endif |
| return; |
| } |
| |
| CK_CC_INLINE static uintptr_t |
| ck_ht_entry_key_direct(ck_ht_entry_t *entry) |
| { |
| |
| return entry->key; |
| } |
| |
| CK_CC_INLINE static uintptr_t |
| ck_ht_entry_value_direct(ck_ht_entry_t *entry) |
| { |
| |
| return entry->value; |
| } |
| |
| /* |
| * Iteration must occur without any concurrent mutations on |
| * the hash table. |
| */ |
| bool ck_ht_next(ck_ht_t *, ck_ht_iterator_t *, ck_ht_entry_t **entry); |
| |
| void ck_ht_stat(ck_ht_t *, struct ck_ht_stat *); |
| void ck_ht_hash(ck_ht_hash_t *, ck_ht_t *, const void *, uint16_t); |
| void ck_ht_hash_direct(ck_ht_hash_t *, ck_ht_t *, uintptr_t); |
| bool ck_ht_init(ck_ht_t *, unsigned int, ck_ht_hash_cb_t *, |
| struct ck_malloc *, CK_HT_TYPE, uint64_t); |
| void ck_ht_destroy(ck_ht_t *); |
| bool ck_ht_set_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); |
| bool ck_ht_put_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); |
| bool ck_ht_get_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); |
| bool ck_ht_gc(struct ck_ht *, unsigned long, unsigned long); |
| bool ck_ht_grow_spmc(ck_ht_t *, CK_HT_TYPE); |
| bool ck_ht_remove_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); |
| bool ck_ht_reset_spmc(ck_ht_t *); |
| bool ck_ht_reset_size_spmc(ck_ht_t *, CK_HT_TYPE); |
| CK_HT_TYPE ck_ht_count(ck_ht_t *); |
| |
| #endif /* CK_HT_H */ |