deps/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 *, unsigned, size_t *, size_t *);
   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 JEMALLOC_DEBUG
  34 #define CKH_MAGIC       0x3af2489d
  35         uint32_t        magic;
  36 #endif
  37
  38 #ifdef CKH_COUNT
  39         /* Counters used to get an idea of performance. */
  40         uint64_t        ngrows;
  41         uint64_t        nshrinks;
  42         uint64_t        nshrinkfails;
  43         uint64_t        ninserts;
  44         uint64_t        nrelocs;
  45 #endif
  46
  47         /* Used for pseudo-random number generation. */
  48 #define CKH_A           1103515241
  49 #define CKH_C           12347
  50         uint32_t        prn_state;
  51
  52         /* Total number of items. */
  53         size_t          count;
  54
  55         /*
  56          * Minimum and current number of hash table buckets.  There are
  57          * 2^LG_CKH_BUCKET_CELLS cells per bucket.
  58          */
  59         unsigned        lg_minbuckets;
  60         unsigned        lg_curbuckets;
  61
  62         /* Hash and comparison functions. */
  63         ckh_hash_t      *hash;
  64         ckh_keycomp_t   *keycomp;
  65
  66         /* Hash table with 2^lg_curbuckets buckets. */
  67         ckhc_t          *tab;
  68 };
  69
  70 #endif /* JEMALLOC_H_STRUCTS */
  71 /******************************************************************************/
  72 #ifdef JEMALLOC_H_EXTERNS
  73
  74 bool    ckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
  75     ckh_keycomp_t *keycomp);
  76 void    ckh_delete(ckh_t *ckh);
  77 size_t  ckh_count(ckh_t *ckh);
  78 bool    ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
  79 bool    ckh_insert(ckh_t *ckh, const void *key, const void *data);
  80 bool    ckh_remove(ckh_t *ckh, const void *searchkey, void **key,
  81     void **data);
  82 bool    ckh_search(ckh_t *ckh, const void *seachkey, void **key, void **data);
  83 void    ckh_string_hash(const void *key, unsigned minbits, size_t *hash1,
  84     size_t *hash2);
  85 bool    ckh_string_keycomp(const void *k1, const void *k2);
  86 void    ckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1,
  87     size_t *hash2);
  88 bool    ckh_pointer_keycomp(const void *k1, const void *k2);
  89
  90 #endif /* JEMALLOC_H_EXTERNS */
  91 /******************************************************************************/
  92 #ifdef JEMALLOC_H_INLINES
  93
  94 #endif /* JEMALLOC_H_INLINES */
  95 /******************************************************************************/