ckh.h revision 7427525c28d58c423a68930160e3b0fe577fe953 
1/******************************************************************************/
2#ifdef JEMALLOC_H_TYPES
3
4typedef struct ckh_s ckh_t;
5typedef struct ckhc_s ckhc_t;
6
7/* Typedefs to allow easy function pointer passing. */
8typedef void ckh_hash_t (const void *, unsigned, size_t *, size_t *);
9typedef 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. */
27struct ckhc_s {
28	const void	*key;
29	const void	*data;
30};
31
32struct 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
74bool	ckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
75    ckh_keycomp_t *keycomp);
76void	ckh_delete(ckh_t *ckh);
77size_t	ckh_count(ckh_t *ckh);
78bool	ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data);
79bool	ckh_insert(ckh_t *ckh, const void *key, const void *data);
80bool	ckh_remove(ckh_t *ckh, const void *searchkey, void **key,
81    void **data);
82bool	ckh_search(ckh_t *ckh, const void *seachkey, void **key, void **data);
83void	ckh_string_hash(const void *key, unsigned minbits, size_t *hash1,
84    size_t *hash2);
85bool	ckh_string_keycomp(const void *k1, const void *k2);
86void	ckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1,
87    size_t *hash2);
88bool	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/******************************************************************************/
96