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. */
24 typedef void ckh_hash_t (const void *, size_t[2]);
25 typedef bool ckh_keycomp_t (const void *, const void *);
26 
27 /* Hash table cell. */
28 typedef struct {
29 	const void *key;
30 	const void *data;
31 } ckhc_t;
32 
33 /* The hash table itself. */
34 typedef 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. */
70 bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
71     ckh_keycomp_t *keycomp);
72 void ckh_delete(tsd_t *tsd, ckh_t *ckh);
73 
74 /* Get the number of elements in the set. */
75 size_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  */
83 bool 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  */
90 bool ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data);
91 bool ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
92     void **data);
93 bool ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data);
94 
95 /* Some useful hash and comparison functions for strings and pointers. */
96 void ckh_string_hash(const void *key, size_t r_hash[2]);
97 bool ckh_string_keycomp(const void *k1, const void *k2);
98 void ckh_pointer_hash(const void *key, size_t r_hash[2]);
99 bool ckh_pointer_keycomp(const void *k1, const void *k2);
100 
101 #endif /* JEMALLOC_INTERNAL_CKH_H */
102