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
53struct ck_ht_hash {
54	uint64_t value;
55};
56typedef 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
70struct 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
82typedef 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 */
100typedef void ck_ht_hash_cb_t(ck_ht_hash_t *, const void *, size_t, uint64_t);
101
102struct ck_ht_map;
103struct 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};
110typedef struct ck_ht ck_ht_t;
111
112struct ck_ht_stat {
113	uint64_t probe_maximum;
114	uint64_t n_entries;
115};
116
117struct ck_ht_iterator {
118	struct ck_ht_entry *current;
119	uint64_t offset;
120};
121typedef struct ck_ht_iterator ck_ht_iterator_t;
122
123#define CK_HT_ITERATOR_INITIALIZER { NULL, 0 }
124
125CK_CC_INLINE static void
126ck_ht_iterator_init(struct ck_ht_iterator *iterator)
127{
128
129	iterator->current = NULL;
130	iterator->offset = 0;
131	return;
132}
133
134CK_CC_INLINE static bool
135ck_ht_entry_empty(ck_ht_entry_t *entry)
136{
137
138	return entry->key == CK_HT_KEY_EMPTY;
139}
140
141CK_CC_INLINE static void
142ck_ht_entry_key_set_direct(ck_ht_entry_t *entry, uintptr_t key)
143{
144
145	entry->key = key;
146	return;
147}
148
149CK_CC_INLINE static void
150ck_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
163CK_CC_INLINE static void *
164ck_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
174CK_CC_INLINE static uint16_t
175ck_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
185CK_CC_INLINE static void *
186ck_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
196CK_CC_INLINE static void
197ck_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
217CK_CC_INLINE static void
218ck_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
235CK_CC_INLINE static uintptr_t
236ck_ht_entry_key_direct(ck_ht_entry_t *entry)
237{
238
239	return entry->key;
240}
241
242CK_CC_INLINE static uintptr_t
243ck_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 */
253bool ck_ht_next(ck_ht_t *, ck_ht_iterator_t *, ck_ht_entry_t **entry);
254
255void ck_ht_stat(ck_ht_t *, struct ck_ht_stat *);
256void ck_ht_hash(ck_ht_hash_t *, ck_ht_t *, const void *, uint16_t);
257void ck_ht_hash_direct(ck_ht_hash_t *, ck_ht_t *, uintptr_t);
258bool ck_ht_init(ck_ht_t *, unsigned int, ck_ht_hash_cb_t *,
259    struct ck_malloc *, CK_HT_TYPE, uint64_t);
260void ck_ht_destroy(ck_ht_t *);
261bool ck_ht_set_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
262bool ck_ht_put_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
263bool ck_ht_get_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
264bool ck_ht_gc(struct ck_ht *, unsigned long, unsigned long);
265bool ck_ht_grow_spmc(ck_ht_t *, CK_HT_TYPE);
266bool ck_ht_remove_spmc(ck_ht_t *, ck_ht_hash_t, ck_ht_entry_t *);
267bool ck_ht_reset_spmc(ck_ht_t *);
268bool ck_ht_reset_size_spmc(ck_ht_t *, CK_HT_TYPE);
269CK_HT_TYPE ck_ht_count(ck_ht_t *);
270
271#endif /* CK_HT_H */
272