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
ck_ht_iterator_init(struct ck_ht_iterator * iterator)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
ck_ht_entry_empty(ck_ht_entry_t * entry)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
ck_ht_entry_key_set_direct(ck_ht_entry_t * entry,uintptr_t key)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
ck_ht_entry_key_set(ck_ht_entry_t * entry,const void * key,uint16_t key_length)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 *
ck_ht_entry_key(ck_ht_entry_t * entry)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
ck_ht_entry_key_length(ck_ht_entry_t * entry)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 *
ck_ht_entry_value(ck_ht_entry_t * entry)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
ck_ht_entry_set(struct ck_ht_entry * entry,ck_ht_hash_t h,const void * key,uint16_t key_length,const void * value)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
ck_ht_entry_set_direct(struct ck_ht_entry * entry,ck_ht_hash_t h,uintptr_t key,uintptr_t value)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
ck_ht_entry_key_direct(ck_ht_entry_t * entry)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
ck_ht_entry_value_direct(ck_ht_entry_t * entry)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