ckh.h 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101
  1. #ifndef JEMALLOC_INTERNAL_CKH_H
  2. #define JEMALLOC_INTERNAL_CKH_H
  3. #include "jemalloc/internal/tsd.h"
  4. /* Cuckoo hashing implementation. Skip to the end for the interface. */
  5. /******************************************************************************/
  6. /* INTERNAL DEFINITIONS -- IGNORE */
  7. /******************************************************************************/
  8. /* Maintain counters used to get an idea of performance. */
  9. /* #define CKH_COUNT */
  10. /* Print counter values in ckh_delete() (requires CKH_COUNT). */
  11. /* #define CKH_VERBOSE */
  12. /*
  13. * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket. Try to fit
  14. * one bucket per L1 cache line.
  15. */
  16. #define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1)
  17. /* Typedefs to allow easy function pointer passing. */
  18. typedef void ckh_hash_t (const void *, size_t[2]);
  19. typedef bool ckh_keycomp_t (const void *, const void *);
  20. /* Hash table cell. */
  21. typedef struct {
  22. const void *key;
  23. const void *data;
  24. } ckhc_t;
  25. /* The hash table itself. */
  26. typedef struct {
  27. #ifdef CKH_COUNT
  28. /* Counters used to get an idea of performance. */
  29. uint64_t ngrows;
  30. uint64_t nshrinks;
  31. uint64_t nshrinkfails;
  32. uint64_t ninserts;
  33. uint64_t nrelocs;
  34. #endif
  35. /* Used for pseudo-random number generation. */
  36. uint64_t prng_state;
  37. /* Total number of items. */
  38. size_t count;
  39. /*
  40. * Minimum and current number of hash table buckets. There are
  41. * 2^LG_CKH_BUCKET_CELLS cells per bucket.
  42. */
  43. unsigned lg_minbuckets;
  44. unsigned lg_curbuckets;
  45. /* Hash and comparison functions. */
  46. ckh_hash_t *hash;
  47. ckh_keycomp_t *keycomp;
  48. /* Hash table with 2^lg_curbuckets buckets. */
  49. ckhc_t *tab;
  50. } ckh_t;
  51. /******************************************************************************/
  52. /* BEGIN PUBLIC API */
  53. /******************************************************************************/
  54. /* Lifetime management. Minitems is the initial capacity. */
  55. bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
  56. ckh_keycomp_t *keycomp);
  57. void ckh_delete(tsd_t *tsd, ckh_t *ckh);
  58. /* Get the number of elements in the set. */
  59. size_t ckh_count(ckh_t *ckh);
  60. /*
  61. * To iterate over the elements in the table, initialize *tabind to 0 and call
  62. * this function until it returns true. Each call that returns false will
  63. * update *key and *data to the next element in the table, assuming the pointers
  64. * are non-NULL.
  65. */
  66. bool ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
  67. /*
  68. * Basic hash table operations -- insert, removal, lookup. For ckh_remove and
  69. * ckh_search, key or data can be NULL. The hash-table only stores pointers to
  70. * the key and value, and doesn't do any lifetime management.
  71. */
  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. /* Some useful hash and comparison functions for strings and pointers. */
  77. void ckh_string_hash(const void *key, size_t r_hash[2]);
  78. bool ckh_string_keycomp(const void *k1, const void *k2);
  79. void ckh_pointer_hash(const void *key, size_t r_hash[2]);
  80. bool ckh_pointer_keycomp(const void *k1, const void *k2);
  81. #endif /* JEMALLOC_INTERNAL_CKH_H */