1#ifndef JEMALLOC_INTERNAL_CKH_H
2#define JEMALLOC_INTERNAL_CKH_H
3
4#include "jemalloc/internal/tsd.h"
5
6/* Cuckoo hashing implementation. Skip to the end for the interface. */
7
8/******************************************************************************/
9/* INTERNAL DEFINITIONS -- IGNORE */
10/******************************************************************************/
11
12/* Maintain counters used to get an idea of performance. */
13/* #define CKH_COUNT */
14/* Print counter values in ckh_delete() (requires CKH_COUNT). */
15/* #define CKH_VERBOSE */
16
17/*
18 * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket. Try to fit
19 * one bucket per L1 cache line.
20 */
21#define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1)
22
23/* Typedefs to allow easy function pointer passing. */
24typedef void ckh_hash_t (const void *, size_t[2]);
25typedef bool ckh_keycomp_t (const void *, const void *);
26
27/* Hash table cell. */
28typedef struct {
29 const void *key;
30 const void *data;
31} ckhc_t;
32
33/* The hash table itself. */
34typedef struct {
35#ifdef CKH_COUNT
36 /* Counters used to get an idea of performance. */
37 uint64_t ngrows;
38 uint64_t nshrinks;
39 uint64_t nshrinkfails;
40 uint64_t ninserts;
41 uint64_t nrelocs;
42#endif
43
44 /* Used for pseudo-random number generation. */
45 uint64_t prng_state;
46
47 /* Total number of items. */
48 size_t count;
49
50 /*
51 * Minimum and current number of hash table buckets. There are
52 * 2^LG_CKH_BUCKET_CELLS cells per bucket.
53 */
54 unsigned lg_minbuckets;
55 unsigned lg_curbuckets;
56
57 /* Hash and comparison functions. */
58 ckh_hash_t *hash;
59 ckh_keycomp_t *keycomp;
60
61 /* Hash table with 2^lg_curbuckets buckets. */
62 ckhc_t *tab;
63} ckh_t;
64
65/******************************************************************************/
66/* BEGIN PUBLIC API */
67/******************************************************************************/
68
69/* Lifetime management. Minitems is the initial capacity. */
70bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
71 ckh_keycomp_t *keycomp);
72void ckh_delete(tsd_t *tsd, ckh_t *ckh);
73
74/* Get the number of elements in the set. */
75size_t ckh_count(ckh_t *ckh);
76
77/*
78 * To iterate over the elements in the table, initialize *tabind to 0 and call
79 * this function until it returns true. Each call that returns false will
80 * update *key and *data to the next element in the table, assuming the pointers
81 * are non-NULL.
82 */
83bool ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
84
85/*
86 * Basic hash table operations -- insert, removal, lookup. For ckh_remove and
87 * ckh_search, key or data can be NULL. The hash-table only stores pointers to
88 * the key and value, and doesn't do any lifetime management.
89 */
90bool ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data);
91bool ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
92 void **data);
93bool ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data);
94
95/* Some useful hash and comparison functions for strings and pointers. */
96void ckh_string_hash(const void *key, size_t r_hash[2]);
97bool ckh_string_keycomp(const void *k1, const void *k2);
98void ckh_pointer_hash(const void *key, size_t r_hash[2]);
99bool ckh_pointer_keycomp(const void *k1, const void *k2);
100
101#endif /* JEMALLOC_INTERNAL_CKH_H */
102