1 /* 2 * Copyright 2012-2015 Samy Al Bahra. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27 #ifndef CK_HT_H 28 #define CK_HT_H 29 30 #include <ck_pr.h> 31 32 #define CK_F_HT 33 #if defined(CK_F_PR_LOAD_64) && defined(CK_F_PR_STORE_64) 34 #define CK_HT_TYPE uint64_t 35 #define CK_HT_TYPE_LOAD ck_pr_load_64 36 #define CK_HT_TYPE_STORE ck_pr_store_64 37 #define CK_HT_TYPE_MAX UINT64_MAX 38 #else 39 #define CK_HT_TYPE uint32_t 40 #define CK_HT_TYPE_LOAD ck_pr_load_32 41 #define CK_HT_TYPE_STORE ck_pr_store_32 42 #define CK_HT_TYPE_MAX UINT32_MAX 43 #endif 44 45 46 #include <ck_cc.h> 47 #include <ck_malloc.h> 48 #include <ck_md.h> 49 #include <ck_stdint.h> 50 #include <ck_stdbool.h> 51 #include <ck_stddef.h> 52 53 struct ck_ht_hash { 54 uint64_t value; 55 }; 56 typedef struct ck_ht_hash ck_ht_hash_t; 57 58 #define CK_HT_MODE_DIRECT 1U 59 #define CK_HT_MODE_BYTESTRING 2U 60 #define CK_HT_WORKLOAD_DELETE 4U 61 62 #if defined(CK_MD_POINTER_PACK_ENABLE) && defined(CK_MD_VMA_BITS) 63 #define CK_HT_PP 64 #define CK_HT_KEY_LENGTH ((sizeof(void *) * 8) - CK_MD_VMA_BITS) 65 #define CK_HT_KEY_MASK ((1U << CK_HT_KEY_LENGTH) - 1) 66 #else 67 #define CK_HT_KEY_LENGTH 65535U 68 #endif 69 70 struct ck_ht_entry { 71 #ifdef CK_HT_PP 72 uintptr_t key; 73 uintptr_t value CK_CC_PACKED; 74 } CK_CC_ALIGN(16); 75 #else 76 uintptr_t key; 77 uintptr_t value; 78 CK_HT_TYPE key_length; 79 CK_HT_TYPE hash; 80 } CK_CC_ALIGN(32); 81 #endif 82 typedef struct ck_ht_entry ck_ht_entry_t; 83 84 /* 85 * The user is free to define their own stub values. 86 */ 87 #ifndef CK_HT_KEY_EMPTY 88 #define CK_HT_KEY_EMPTY ((uintptr_t)0) 89 #endif 90 91 #ifndef CK_HT_KEY_TOMBSTONE 92 #define CK_HT_KEY_TOMBSTONE (~CK_HT_KEY_EMPTY) 93 #endif 94 95 /* 96 * Hash callback function. First argument is updated to contain a hash value, 97 * second argument is the key, third argument is key length and final argument 98 * is the hash table seed value. 99 */ 100 typedef void ck_ht_hash_cb_t(ck_ht_hash_t *, const void *, size_t, uint64_t); 101 102 struct ck_ht_map; 103 struct ck_ht { 104 struct ck_malloc *m; 105 struct ck_ht_map *map; 106 unsigned int mode; 107 uint64_t seed; 108 ck_ht_hash_cb_t *h; 109 }; 110 typedef struct ck_ht ck_ht_t; 111 112 struct ck_ht_stat { 113 uint64_t probe_maximum; 114 uint64_t n_entries; 115 }; 116 117 struct ck_ht_iterator { 118 struct ck_ht_entry *current; 119 uint64_t offset; 120 }; 121 typedef struct ck_ht_iterator ck_ht_iterator_t; 122 123 #define CK_HT_ITERATOR_INITIALIZER { NULL, 0 } 124 125 CK_CC_INLINE static void 126 ck_ht_iterator_init(struct ck_ht_iterator *iterator) 127 { 128 129 iterator->current = NULL; 130 iterator->offset = 0; 131 return; 132 } 133 134 CK_CC_INLINE static bool 135 ck_ht_entry_empty(ck_ht_entry_t *entry) 136 { 137 138 return entry->key == CK_HT_KEY_EMPTY; 139 } 140 141 CK_CC_INLINE static void 142 ck_ht_entry_key_set_direct(ck_ht_entry_t *entry, uintptr_t key) 143 { 144 145 entry->key = key; 146 return; 147 } 148 149 CK_CC_INLINE static void 150 ck_ht_entry_key_set(ck_ht_entry_t *entry, const void *key, uint16_t key_length) 151 { 152 153 #ifdef CK_HT_PP 154 entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS); 155 #else 156 entry->key = (uintptr_t)key; 157 entry->key_length = key_length; 158 #endif 159 160 return; 161 } 162 163 CK_CC_INLINE static void * 164 ck_ht_entry_key(ck_ht_entry_t *entry) 165 { 166 167 #ifdef CK_HT_PP 168 return (void *)(entry->key & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1)); 169 #else 170 return (void *)entry->key; 171 #endif 172 } 173 174 CK_CC_INLINE static uint16_t 175 ck_ht_entry_key_length(ck_ht_entry_t *entry) 176 { 177 178 #ifdef CK_HT_PP 179 return entry->key >> CK_MD_VMA_BITS; 180 #else 181 return entry->key_length; 182 #endif 183 } 184 185 CK_CC_INLINE static void * 186 ck_ht_entry_value(ck_ht_entry_t *entry) 187 { 188 189 #ifdef CK_HT_PP 190 return (void *)(entry->value & (((uintptr_t)1 << CK_MD_VMA_BITS) - 1)); 191 #else 192 return (void *)entry->value; 193 #endif 194 } 195 196 CK_CC_INLINE static void 197 ck_ht_entry_set(struct ck_ht_entry *entry, 198 ck_ht_hash_t h, 199 const void *key, 200 uint16_t key_length, 201 const void *value) 202 { 203 204 #ifdef CK_HT_PP 205 entry->key = (uintptr_t)key | ((uintptr_t)key_length << CK_MD_VMA_BITS); 206 entry->value = (uintptr_t)value | ((uintptr_t)(h.value >> 32) << CK_MD_VMA_BITS); 207 #else 208 entry->key = (uintptr_t)key; 209 entry->value = (uintptr_t)value; 210 entry->key_length = key_length; 211 entry->hash = h.value; 212 #endif 213 214 return; 215 } 216 217 CK_CC_INLINE static void 218 ck_ht_entry_set_direct(struct ck_ht_entry *entry, 219 ck_ht_hash_t h, 220 uintptr_t key, 221 uintptr_t value) 222 { 223 224 entry->key = key; 225 entry->value = value; 226 227 #ifndef CK_HT_PP 228 entry->hash = h.value; 229 #else 230 (void)h; 231 #endif 232 return; 233 } 234 235 CK_CC_INLINE static uintptr_t 236 ck_ht_entry_key_direct(ck_ht_entry_t *entry) 237 { 238 239 return entry->key; 240 } 241 242 CK_CC_INLINE static uintptr_t 243 ck_ht_entry_value_direct(ck_ht_entry_t *entry) 244 { 245 246 return entry->value; 247 } 248 249 /* 250 * Iteration must occur without any concurrent mutations on 251 * the hash table. 252 */ 253 bool ck_ht_next(ck_ht_t *, ck_ht_iterator_t *, ck_ht_entry_t **entry); 254 255 void ck_ht_stat(ck_ht_t *, struct ck_ht_stat *); 256 void ck_ht_hash(ck_ht_hash_t *, ck_ht_t *, const void *, uint16_t); 257 void ck_ht_hash_direct(ck_ht_hash_t *, ck_ht_t *, uintptr_t); 258 bool ck_ht_init(ck_ht_t *, unsigned int, ck_ht_hash_cb_t *, 259 struct ck_malloc *, CK_HT_TYPE, uint64_t); 260 void ck_ht_destroy(ck_ht_t *); 261 bool ck_ht_set_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); 262 bool ck_ht_put_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); 263 bool ck_ht_get_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); 264 bool ck_ht_gc(struct ck_ht *, unsigned long, unsigned long); 265 bool ck_ht_grow_spmc(ck_ht_t *, CK_HT_TYPE); 266 bool ck_ht_remove_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *); 267 bool ck_ht_reset_spmc(ck_ht_t *); 268 bool ck_ht_reset_size_spmc(ck_ht_t *, CK_HT_TYPE); 269 CK_HT_TYPE ck_ht_count(ck_ht_t *); 270 271 #endif /* CK_HT_H */ 272