Deleted Added
sdiff udiff text old ( 245868 ) new ( 261071 )
full compact
ckh.c (245868) ckh.c (261071)
1/*
2 *******************************************************************************
3 * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each
4 * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash
5 * functions are employed. The original cuckoo hashing algorithm was described
6 * in:
7 *
8 * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms

--- 35 unchanged lines hidden (view full) ---

44static void ckh_shrink(ckh_t *ckh);
45
46/******************************************************************************/
47
48/*
49 * Search bucket for key and return the cell number if found; SIZE_T_MAX
50 * otherwise.
51 */
1/*
2 *******************************************************************************
3 * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each
4 * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash
5 * functions are employed. The original cuckoo hashing algorithm was described
6 * in:
7 *
8 * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms

--- 35 unchanged lines hidden (view full) ---

44static void ckh_shrink(ckh_t *ckh);
45
46/******************************************************************************/
47
48/*
49 * Search bucket for key and return the cell number if found; SIZE_T_MAX
50 * otherwise.
51 */
52JEMALLOC_INLINE size_t
52JEMALLOC_INLINE_C size_t
53ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key)
54{
55 ckhc_t *cell;
56 unsigned i;
57
58 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) {
59 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
60 if (cell->key != NULL && ckh->keycomp(key, cell->key))
61 return ((bucket << LG_CKH_BUCKET_CELLS) + i);
62 }
63
64 return (SIZE_T_MAX);
65}
66
67/*
68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
69 */
53ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key)
54{
55 ckhc_t *cell;
56 unsigned i;
57
58 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) {
59 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
60 if (cell->key != NULL && ckh->keycomp(key, cell->key))
61 return ((bucket << LG_CKH_BUCKET_CELLS) + i);
62 }
63
64 return (SIZE_T_MAX);
65}
66
67/*
68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
69 */
70JEMALLOC_INLINE size_t
70JEMALLOC_INLINE_C size_t
71ckh_isearch(ckh_t *ckh, const void *key)
72{
73 size_t hashes[2], bucket, cell;
74
75 assert(ckh != NULL);
76
77 ckh->hash(key, hashes);
78

--- 4 unchanged lines hidden (view full) ---

83 return (cell);
84
85 /* Search secondary bucket. */
86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
87 cell = ckh_bucket_search(ckh, bucket, key);
88 return (cell);
89}
90
71ckh_isearch(ckh_t *ckh, const void *key)
72{
73 size_t hashes[2], bucket, cell;
74
75 assert(ckh != NULL);
76
77 ckh->hash(key, hashes);
78

--- 4 unchanged lines hidden (view full) ---

83 return (cell);
84
85 /* Search secondary bucket. */
86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
87 cell = ckh_bucket_search(ckh, bucket, key);
88 return (cell);
89}
90
91JEMALLOC_INLINE bool
91JEMALLOC_INLINE_C bool
92ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
93 const void *data)
94{
95 ckhc_t *cell;
96 unsigned offset, i;
97
98 /*
99 * Cycle through the cells in the bucket, starting at a random position.

--- 15 unchanged lines hidden (view full) ---

115}
116
117/*
118 * No space is available in bucket. Randomly evict an item, then try to find an
119 * alternate location for that item. Iteratively repeat this
120 * eviction/relocation procedure until either success or detection of an
121 * eviction/relocation bucket cycle.
122 */
92ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
93 const void *data)
94{
95 ckhc_t *cell;
96 unsigned offset, i;
97
98 /*
99 * Cycle through the cells in the bucket, starting at a random position.

--- 15 unchanged lines hidden (view full) ---

115}
116
117/*
118 * No space is available in bucket. Randomly evict an item, then try to find an
119 * alternate location for that item. Iteratively repeat this
120 * eviction/relocation procedure until either success or detection of an
121 * eviction/relocation bucket cycle.
122 */
123JEMALLOC_INLINE bool
123JEMALLOC_INLINE_C bool
124ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey,
125 void const **argdata)
126{
127 const void *key, *data, *tkey, *tdata;
128 ckhc_t *cell;
129 size_t hashes[2], bucket, tbucket;
130 unsigned i;
131

--- 53 unchanged lines hidden (view full) ---

185 }
186
187 bucket = tbucket;
188 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
189 return (false);
190 }
191}
192
124ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey,
125 void const **argdata)
126{
127 const void *key, *data, *tkey, *tdata;
128 ckhc_t *cell;
129 size_t hashes[2], bucket, tbucket;
130 unsigned i;
131

--- 53 unchanged lines hidden (view full) ---

185 }
186
187 bucket = tbucket;
188 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
189 return (false);
190 }
191}
192
193JEMALLOC_INLINE bool
193JEMALLOC_INLINE_C bool
194ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
195{
196 size_t hashes[2], bucket;
197 const void *key = *argkey;
198 const void *data = *argdata;
199
200 ckh->hash(key, hashes);
201

--- 12 unchanged lines hidden (view full) ---

214 */
215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
216}
217
218/*
219 * Try to rebuild the hash table from scratch by inserting all items from the
220 * old table into the new.
221 */
194ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
195{
196 size_t hashes[2], bucket;
197 const void *key = *argkey;
198 const void *data = *argdata;
199
200 ckh->hash(key, hashes);
201

--- 12 unchanged lines hidden (view full) ---

214 */
215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
216}
217
218/*
219 * Try to rebuild the hash table from scratch by inserting all items from the
220 * old table into the new.
221 */
222JEMALLOC_INLINE bool
222JEMALLOC_INLINE_C bool
223ckh_rebuild(ckh_t *ckh, ckhc_t *aTab)
224{
225 size_t count, i, nins;
226 const void *key, *data;
227
228 count = ckh->count;
229 ckh->count = 0;
230 for (i = nins = 0; nins < count; i++) {

--- 333 unchanged lines hidden --- 		223ckh_rebuild(ckh_t *ckh, ckhc_t *aTab)
224{
225 size_t count, i, nins;
226 const void *key, *data;
227
228 count = ckh->count;
229 ckh->count = 0;
230 for (i = nins = 0; nins < count; i++) {

--- 333 unchanged lines hidden ---