diff options
| -rw-r--r-- | include/jemalloc/internal/ckh.h | 101 | ||||
| -rw-r--r-- | include/jemalloc/internal/ckh_externs.h | 18 | ||||
| -rw-r--r-- | include/jemalloc/internal/ckh_structs.h | 41 | ||||
| -rw-r--r-- | include/jemalloc/internal/ckh_types.h | 22 | ||||
| -rw-r--r-- | include/jemalloc/internal/jemalloc_internal_includes.h | 3 | ||||
| -rw-r--r-- | include/jemalloc/internal/prof_structs.h | 1 | ||||
| -rw-r--r-- | src/ckh.c | 3 | ||||
| -rw-r--r-- | src/prof.c | 1 |
8 files changed, 106 insertions, 84 deletions
diff --git a/include/jemalloc/internal/ckh.h b/include/jemalloc/internal/ckh.h new file mode 100644 index 0000000..96922e0 --- /dev/null +++ b/include/jemalloc/internal/ckh.h @@ -0,0 +1,101 @@ +#ifndef JEMALLOC_INTERNAL_CKH_H +#define JEMALLOC_INTERNAL_CKH_H + +#include "jemalloc/internal/tsd_types.h" + +/* Cuckoo hashing implementation. Skip to the end for the interface. */ + +/******************************************************************************/ +/* INTERNAL DEFINITIONS -- IGNORE */ +/******************************************************************************/ + +/* Maintain counters used to get an idea of performance. */ +/* #define CKH_COUNT */ +/* Print counter values in ckh_delete() (requires CKH_COUNT). */ +/* #define CKH_VERBOSE */ + +/* + * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket. Try to fit + * one bucket per L1 cache line. + */ +#define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1) + +/* Typedefs to allow easy function pointer passing. */ +typedef void ckh_hash_t (const void *, size_t[2]); +typedef bool ckh_keycomp_t (const void *, const void *); + +/* Hash table cell. */ +typedef struct { + const void *key; + const void *data; +} ckhc_t; + +/* The hash table itself. */ +typedef struct { +#ifdef CKH_COUNT + /* Counters used to get an idea of performance. */ + uint64_t ngrows; + uint64_t nshrinks; + uint64_t nshrinkfails; + uint64_t ninserts; + uint64_t nrelocs; +#endif + + /* Used for pseudo-random number generation. */ + uint64_t prng_state; + + /* Total number of items. */ + size_t count; + + /* + * Minimum and current number of hash table buckets. There are + * 2^LG_CKH_BUCKET_CELLS cells per bucket. + */ + unsigned lg_minbuckets; + unsigned lg_curbuckets; + + /* Hash and comparison functions. */ + ckh_hash_t *hash; + ckh_keycomp_t *keycomp; + + /* Hash table with 2^lg_curbuckets buckets. */ + ckhc_t *tab; +} ckh_t; + +/******************************************************************************/ +/* BEGIN PUBLIC API */ +/******************************************************************************/ + +/* Lifetime management. Minitems is the initial capacity. */ +bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, + ckh_keycomp_t *keycomp); +void ckh_delete(tsd_t *tsd, ckh_t *ckh); + +/* Get the number of elements in the set. */ +size_t ckh_count(ckh_t *ckh); + +/* + * To iterate over the elements in the table, initialize *tabind to 0 and call + * this function until it returns true. Each call that returns false will + * update *key and *data to the next element in the table, assuming the pointers + * are non-NULL. + */ +bool ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data); + +/* + * Basic hash table operations -- insert, removal, lookup. For ckh_remove and + * ckh_search, key or data can be NULL. The hash-table only stores pointers to + * the key and value, and doesn't do any lifetime management. + */ +bool ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data); +bool ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, + void **data); +bool ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data); + +/* Some useful hash and comparison functions for strings and pointers. */ +void ckh_string_hash(const void *key, size_t r_hash[2]); +bool ckh_string_keycomp(const void *k1, const void *k2); +void ckh_pointer_hash(const void *key, size_t r_hash[2]); +bool ckh_pointer_keycomp(const void *k1, const void *k2); + +#endif /* JEMALLOC_INTERNAL_CKH_H */ diff --git a/include/jemalloc/internal/ckh_externs.h b/include/jemalloc/internal/ckh_externs.h deleted file mode 100644 index c912f72..0000000 --- a/include/jemalloc/internal/ckh_externs.h +++ /dev/null @@ -1,18 +0,0 @@ -#ifndef JEMALLOC_INTERNAL_CKH_EXTERNS_H -#define JEMALLOC_INTERNAL_CKH_EXTERNS_H - -bool ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, - ckh_keycomp_t *keycomp); -void ckh_delete(tsd_t *tsd, ckh_t *ckh); -size_t ckh_count(ckh_t *ckh); -bool ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data); -bool ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data); -bool ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, - void **data); -bool ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data); -void ckh_string_hash(const void *key, size_t r_hash[2]); -bool ckh_string_keycomp(const void *k1, const void *k2); -void ckh_pointer_hash(const void *key, size_t r_hash[2]); -bool ckh_pointer_keycomp(const void *k1, const void *k2); - -#endif /* JEMALLOC_INTERNAL_CKH_EXTERNS_H */ diff --git a/include/jemalloc/internal/ckh_structs.h b/include/jemalloc/internal/ckh_structs.h deleted file mode 100644 index a800cbc..0000000 --- a/include/jemalloc/internal/ckh_structs.h +++ /dev/null @@ -1,41 +0,0 @@ -#ifndef JEMALLOC_INTERNAL_CKH_STRUCTS_H -#define JEMALLOC_INTERNAL_CKH_STRUCTS_H - -/* Hash table cell. */ -struct ckhc_s { - const void *key; - const void *data; -}; - -struct ckh_s { -#ifdef CKH_COUNT - /* Counters used to get an idea of performance. */ - uint64_t ngrows; - uint64_t nshrinks; - uint64_t nshrinkfails; - uint64_t ninserts; - uint64_t nrelocs; -#endif - - /* Used for pseudo-random number generation. */ - uint64_t prng_state; - - /* Total number of items. */ - size_t count; - - /* - * Minimum and current number of hash table buckets. There are - * 2^LG_CKH_BUCKET_CELLS cells per bucket. - */ - unsigned lg_minbuckets; - unsigned lg_curbuckets; - - /* Hash and comparison functions. */ - ckh_hash_t *hash; - ckh_keycomp_t *keycomp; - - /* Hash table with 2^lg_curbuckets buckets. */ - ckhc_t *tab; -}; - -#endif /* JEMALLOC_INTERNAL_CKH_STRUCTS_H */ diff --git a/include/jemalloc/internal/ckh_types.h b/include/jemalloc/internal/ckh_types.h deleted file mode 100644 index b5911db..0000000 --- a/include/jemalloc/internal/ckh_types.h +++ /dev/null @@ -1,22 +0,0 @@ -#ifndef JEMALLOC_INTERNAL_CKH_TYPES_H -#define JEMALLOC_INTERNAL_CKH_TYPES_H - -typedef struct ckh_s ckh_t; -typedef struct ckhc_s ckhc_t; - -/* Typedefs to allow easy function pointer passing. */ -typedef void ckh_hash_t (const void *, size_t[2]); -typedef bool ckh_keycomp_t (const void *, const void *); - -/* Maintain counters used to get an idea of performance. */ -/* #define CKH_COUNT */ -/* Print counter values in ckh_delete() (requires CKH_COUNT). */ -/* #define CKH_VERBOSE */ - -/* - * There are 2^LG_CKH_BUCKET_CELLS cells in each hash table bucket. Try to fit - * one bucket per L1 cache line. - */ -#define LG_CKH_BUCKET_CELLS (LG_CACHELINE - LG_SIZEOF_PTR - 1) - -#endif /* JEMALLOC_INTERNAL_CKH_TYPES_H */ diff --git a/include/jemalloc/internal/jemalloc_internal_includes.h b/include/jemalloc/internal/jemalloc_internal_includes.h index 8ce7864..f4a1986 100644 --- a/include/jemalloc/internal/jemalloc_internal_includes.h +++ b/include/jemalloc/internal/jemalloc_internal_includes.h @@ -40,7 +40,6 @@ /* TYPES */ /******************************************************************************/ -#include "jemalloc/internal/ckh_types.h" #include "jemalloc/internal/size_classes.h" #include "jemalloc/internal/smoothstep.h" #include "jemalloc/internal/stats_types.h" @@ -62,7 +61,6 @@ /* STRUCTS */ /******************************************************************************/ -#include "jemalloc/internal/ckh_structs.h" #include "jemalloc/internal/witness_structs.h" #include "jemalloc/internal/mutex_structs.h" #include "jemalloc/internal/stats_structs.h" @@ -83,7 +81,6 @@ /******************************************************************************/ #include "jemalloc/internal/jemalloc_internal_externs.h" -#include "jemalloc/internal/ckh_externs.h" #include "jemalloc/internal/stats_externs.h" #include "jemalloc/internal/ctl_externs.h" #include "jemalloc/internal/witness_externs.h" diff --git a/include/jemalloc/internal/prof_structs.h b/include/jemalloc/internal/prof_structs.h index 82080aa..a26a042 100644 --- a/include/jemalloc/internal/prof_structs.h +++ b/include/jemalloc/internal/prof_structs.h @@ -1,6 +1,7 @@ #ifndef JEMALLOC_INTERNAL_PROF_STRUCTS_H #define JEMALLOC_INTERNAL_PROF_STRUCTS_H +#include "jemalloc/internal/ckh.h" #include "jemalloc/internal/prng.h" #include "jemalloc/internal/rb.h" @@ -36,6 +36,9 @@ ******************************************************************************/ #define JEMALLOC_CKH_C_ #include "jemalloc/internal/jemalloc_preamble.h" + +#include "jemalloc/internal/ckh.h" + #include "jemalloc/internal/jemalloc_internal_includes.h" #include "jemalloc/internal/assert.h" @@ -3,6 +3,7 @@ #include "jemalloc/internal/jemalloc_internal_includes.h" #include "jemalloc/internal/assert.h" +#include "jemalloc/internal/ckh.h" #include "jemalloc/internal/malloc_io.h" /******************************************************************************/ |