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 | |