#ifndef JEMALLOC_INTERNAL_CKH_H #define JEMALLOC_INTERNAL_CKH_H #include "jemalloc/internal/tsd.h" /* Cuckoo hashing implementation. Skip to the end for the interface. */ /******************************************************************************/ /* INTERNAL DEFINITIONS -- IGNORE */ /******************************************************************************/ /* Maintain counters used to get an idea of performance. */ /* #define CKH_COUNT */ /* Print counter values in ckh_delete() (requires CKH_COUNT). */ /* #define CKH_VERBOSE */ /* * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket. Try to fit * one bucket per L1 cache line. */ #define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1) /* Typedefs to allow easy function pointer passing. */ typedef void ckh_hash_t (const void *, size_t[2]); typedef bool ckh_keycomp_t (const void *, const void *); /* Hash table cell. */ typedef struct { const void *key; const void *data; } ckhc_t; /* The hash table itself. */ typedef struct { #ifdef CKH_COUNT /* Counters used to get an idea of performance. */ uint64_t ngrows; uint64_t nshrinks; uint64_t nshrinkfails; uint64_t ninserts; uint64_t nrelocs; #endif /* Used for pseudo-random number generation. */ uint64_t prng_state; /* Total number of items. */ size_t count; /* * Minimum and current number of hash table buckets. There are * 2^LG_CKH_BUCKET_CELLS cells per bucket. */ unsigned lg_minbuckets; unsigned lg_curbuckets; /* Hash and comparison functions. */ ckh_hash_t *hash; ckh_keycomp_t *keycomp; /* Hash table with 2^lg_curbuckets buckets. */ ckhc_t *tab; } ckh_t; /******************************************************************************/ /* BEGIN PUBLIC API */ /******************************************************************************/ /* Lifetime management. Minitems is the initial capacity. */ bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp); void ckh_delete(tsd_t *tsd, ckh_t *ckh); /* Get the number of elements in the set. */ size_t ckh_count(ckh_t *ckh); /* * To iterate over the elements in the table, initialize *tabind to 0 and call * this function until it returns true. Each call that returns false will * update *key and *data to the next element in the table, assuming the pointers * are non-NULL. */ bool ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data); /* * Basic hash table operations -- insert, removal, lookup. For ckh_remove and * ckh_search, key or data can be NULL. The hash-table only stores pointers to * the key and value, and doesn't do any lifetime management. */ bool ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data); bool ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, void **data); bool ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data); /* Some useful hash and comparison functions for strings and pointers. */ void ckh_string_hash(const void *key, size_t r_hash[2]); bool ckh_string_keycomp(const void *k1, const void *k2); void ckh_pointer_hash(const void *key, size_t r_hash[2]); bool ckh_pointer_keycomp(const void *k1, const void *k2); #endif /* JEMALLOC_INTERNAL_CKH_H */ |