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