src/jemalloc/include/jemalloc/internal/ckh.h

   1 /******************************************************************************/
   2 #ifdef JEMALLOC_H_TYPES
   3
   4 typedef struct ckh_s ckh_t;
   5 typedef struct ckhc_s ckhc_t;
   6
   7 /* Typedefs to allow easy function pointer passing. */
   8 typedef void ckh_hash_t (const void *, size_t[2]);
   9 typedef bool ckh_keycomp_t (const void *, const void *);
  10
  11 /* Maintain counters used to get an idea of performance. */
  12 /* #define      CKH_COUNT */
  13 /* Print counter values in ckh_delete() (requires CKH_COUNT). */
  14 /* #define      CKH_VERBOSE */
  15
  16 /*
  17  * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket.  Try to fit
  18  * one bucket per L1 cache line.
  19  */
  20 #define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1)
  21
  22 #endif /* JEMALLOC_H_TYPES */
  23 /******************************************************************************/
  24 #ifdef JEMALLOC_H_STRUCTS
  25
  26 /* Hash table cell. */
  27 struct ckhc_s {
  28         const void      *key;
  29         const void      *data;
  30 };
  31
  32 struct ckh_s {
  33 #ifdef CKH_COUNT
  34         /* Counters used to get an idea of performance. */
  35         uint64_t        ngrows;
  36         uint64_t        nshrinks;
  37         uint64_t        nshrinkfails;
  38         uint64_t        ninserts;
  39         uint64_t        nrelocs;
  40 #endif
  41
  42         /* Used for pseudo-random number generation. */
  43         uint64_t        prng_state;
  44
  45         /* Total number of items. */
  46         size_t          count;
  47
  48         /*
  49          * Minimum and current number of hash table buckets.  There are
  50          * 2^LG_CKH_BUCKET_CELLS cells per bucket.
  51          */
  52         unsigned        lg_minbuckets;
  53         unsigned        lg_curbuckets;
  54
  55         /* Hash and comparison functions. */
  56         ckh_hash_t      *hash;
  57         ckh_keycomp_t   *keycomp;
  58
  59         /* Hash table with 2^lg_curbuckets buckets. */
  60         ckhc_t          *tab;
  61 };
  62
  63 #endif /* JEMALLOC_H_STRUCTS */
  64 /******************************************************************************/
  65 #ifdef JEMALLOC_H_EXTERNS
  66
  67 bool    ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
  68     ckh_keycomp_t *keycomp);
  69 void    ckh_delete(tsd_t *tsd, ckh_t *ckh);
  70 size_t  ckh_count(ckh_t *ckh);
  71 bool    ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
  72 bool    ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data);
  73 bool    ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
  74     void **data);
  75 bool    ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data);
  76 void    ckh_string_hash(const void *key, size_t r_hash[2]);
  77 bool    ckh_string_keycomp(const void *k1, const void *k2);
  78 void    ckh_pointer_hash(const void *key, size_t r_hash[2]);
  79 bool    ckh_pointer_keycomp(const void *k1, const void *k2);
  80
  81 #endif /* JEMALLOC_H_EXTERNS */
  82 /******************************************************************************/
  83 #ifdef JEMALLOC_H_INLINES
  84
  85 #endif /* JEMALLOC_H_INLINES */
  86 /******************************************************************************/