contrib/jemalloc/include/jemalloc/internal/ckh.h

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