contrib/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 #define CKH_A           1103515241
  44 #define CKH_C           12347
  45         uint32_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 };
  64
  65 #endif /* JEMALLOC_H_STRUCTS */
  66 /******************************************************************************/
  67 #ifdef JEMALLOC_H_EXTERNS
  68
  69 bool    ckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
  70     ckh_keycomp_t *keycomp);
  71 void    ckh_delete(ckh_t *ckh);
  72 size_t  ckh_count(ckh_t *ckh);
  73 bool    ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
  74 bool    ckh_insert(ckh_t *ckh, const void *key, const void *data);
  75 bool    ckh_remove(ckh_t *ckh, const void *searchkey, void **key,
  76     void **data);
  77 bool    ckh_search(ckh_t *ckh, const void *seachkey, void **key, void **data);
  78 void    ckh_string_hash(const void *key, size_t r_hash[2]);
  79 bool    ckh_string_keycomp(const void *k1, const void *k2);
  80 void    ckh_pointer_hash(const void *key, size_t r_hash[2]);
  81 bool    ckh_pointer_keycomp(const void *k1, const void *k2);
  82
  83 #endif /* JEMALLOC_H_EXTERNS */
  84 /******************************************************************************/
  85 #ifdef JEMALLOC_H_INLINES
  86
  87 #endif /* JEMALLOC_H_INLINES */
  88 /******************************************************************************/