123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 |
- #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 */
|