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