Deleted Added
sdiff udiff text old ( 234370 ) new ( 245868 )
full compact
ckh.c (234370) ckh.c (245868)
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

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

65}
66
67/*
68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
69 */
70JEMALLOC_INLINE size_t
71ckh_isearch(ckh_t *ckh, const void *key)
72{
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

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

65}
66
67/*
68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
69 */
70JEMALLOC_INLINE size_t
71ckh_isearch(ckh_t *ckh, const void *key)
72{
73 size_t hash1, hash2, bucket, cell;
73 size_t hashes[2], bucket, cell;
74
75 assert(ckh != NULL);
76
74
75 assert(ckh != NULL);
76
77 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2);
77 ckh->hash(key, hashes);
78
79 /* Search primary bucket. */
78
79 /* Search primary bucket. */
80 bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1);
80 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
81 cell = ckh_bucket_search(ckh, bucket, key);
82 if (cell != SIZE_T_MAX)
83 return (cell);
84
85 /* Search secondary bucket. */
81 cell = ckh_bucket_search(ckh, bucket, key);
82 if (cell != SIZE_T_MAX)
83 return (cell);
84
85 /* Search secondary bucket. */
86 bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1);
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
92ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
93 const void *data)
94{

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

121 * eviction/relocation bucket cycle.
122 */
123JEMALLOC_INLINE 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;
87 cell = ckh_bucket_search(ckh, bucket, key);
88 return (cell);
89}
90
91JEMALLOC_INLINE bool
92ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
93 const void *data)
94{

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

121 * eviction/relocation bucket cycle.
122 */
123JEMALLOC_INLINE 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 hash1, hash2, bucket, tbucket;
129 size_t hashes[2], bucket, tbucket;
130 unsigned i;
131
132 bucket = argbucket;
133 key = *argkey;
134 data = *argdata;
135 while (true) {
136 /*
137 * Choose a random item within the bucket to evict. This is

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

150 cell->key = key; cell->data = data;
151 key = tkey; data = tdata;
152
153#ifdef CKH_COUNT
154 ckh->nrelocs++;
155#endif
156
157 /* Find the alternate bucket for the evicted item. */
130 unsigned i;
131
132 bucket = argbucket;
133 key = *argkey;
134 data = *argdata;
135 while (true) {
136 /*
137 * Choose a random item within the bucket to evict. This is

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

150 cell->key = key; cell->data = data;
151 key = tkey; data = tdata;
152
153#ifdef CKH_COUNT
154 ckh->nrelocs++;
155#endif
156
157 /* Find the alternate bucket for the evicted item. */
158 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2);
159 tbucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1);
158 ckh->hash(key, hashes);
159 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
160 if (tbucket == bucket) {
160 if (tbucket == bucket) {
161 tbucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1);
161 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets)
162 - 1);
162 /*
163 * It may be that (tbucket == bucket) still, if the
164 * item's hashes both indicate this bucket. However,
165 * we are guaranteed to eventually escape this bucket
166 * during iteration, assuming pseudo-random item
167 * selection (true randomness would make infinite
168 * looping a remote possibility). The reason we can
169 * never get trapped forever is that there are two

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

187 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
188 return (false);
189 }
190}
191
192JEMALLOC_INLINE bool
193ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
194{
163 /*
164 * It may be that (tbucket == bucket) still, if the
165 * item's hashes both indicate this bucket. However,
166 * we are guaranteed to eventually escape this bucket
167 * during iteration, assuming pseudo-random item
168 * selection (true randomness would make infinite
169 * looping a remote possibility). The reason we can
170 * never get trapped forever is that there are two

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

188 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
189 return (false);
190 }
191}
192
193JEMALLOC_INLINE bool
194ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
195{
195 size_t hash1, hash2, bucket;
196 size_t hashes[2], bucket;
196 const void *key = *argkey;
197 const void *data = *argdata;
198
197 const void *key = *argkey;
198 const void *data = *argdata;
199
199 ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2);
200 ckh->hash(key, hashes);
200
201 /* Try to insert in primary bucket. */
201
202 /* Try to insert in primary bucket. */
202 bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1);
203 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
203 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
204 return (false);
205
206 /* Try to insert in secondary bucket. */
204 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
205 return (false);
206
207 /* Try to insert in secondary bucket. */
207 bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1);
208 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
208 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
209 return (false);
210
211 /*
212 * Try to find a place for this item via iterative eviction/relocation.
213 */
214 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
215}

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

412 (unsigned long long)ckh->ngrows,
413 (unsigned long long)ckh->nshrinks,
414 (unsigned long long)ckh->nshrinkfails,
415 (unsigned long long)ckh->ninserts,
416 (unsigned long long)ckh->nrelocs);
417#endif
418
419 idalloc(ckh->tab);
209 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false)
210 return (false);
211
212 /*
213 * Try to find a place for this item via iterative eviction/relocation.
214 */
215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
216}

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

413 (unsigned long long)ckh->ngrows,
414 (unsigned long long)ckh->nshrinks,
415 (unsigned long long)ckh->nshrinkfails,
416 (unsigned long long)ckh->ninserts,
417 (unsigned long long)ckh->nrelocs);
418#endif
419
420 idalloc(ckh->tab);
420#ifdef JEMALLOC_DEBUG
421 memset(ckh, 0x5a, sizeof(ckh_t));
422#endif
421 if (config_debug)
422 memset(ckh, 0x5a, sizeof(ckh_t));
423}
424
425size_t
426ckh_count(ckh_t *ckh)
427{
428
429 assert(ckh != NULL);
430

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

521 *data = (void *)ckh->tab[cell].data;
522 return (false);
523 }
524
525 return (true);
526}
527
528void
423}
424
425size_t
426ckh_count(ckh_t *ckh)
427{
428
429 assert(ckh != NULL);
430

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

521 *data = (void *)ckh->tab[cell].data;
522 return (false);
523 }
524
525 return (true);
526}
527
528void
529ckh_string_hash(const void *key, unsigned minbits, size_t *hash1, size_t *hash2)
529ckh_string_hash(const void *key, size_t r_hash[2])
530{
530{
531 size_t ret1, ret2;
532 uint64_t h;
533
531
534 assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64));
535 assert(hash1 != NULL);
536 assert(hash2 != NULL);
537
538 h = hash(key, strlen((const char *)key), UINT64_C(0x94122f335b332aea));
539 if (minbits <= 32) {
540 /*
541 * Avoid doing multiple hashes, since a single hash provides
542 * enough bits.
543 */
544 ret1 = h & ZU(0xffffffffU);
545 ret2 = h >> 32;
546 } else {
547 ret1 = h;
548 ret2 = hash(key, strlen((const char *)key),
549 UINT64_C(0x8432a476666bbc13));
550 }
551
552 *hash1 = ret1;
553 *hash2 = ret2;
532 hash(key, strlen((const char *)key), 0x94122f33U, r_hash);
554}
555
556bool
557ckh_string_keycomp(const void *k1, const void *k2)
558{
559
560 assert(k1 != NULL);
561 assert(k2 != NULL);
562
563 return (strcmp((char *)k1, (char *)k2) ? false : true);
564}
565
566void
533}
534
535bool
536ckh_string_keycomp(const void *k1, const void *k2)
537{
538
539 assert(k1 != NULL);
540 assert(k2 != NULL);
541
542 return (strcmp((char *)k1, (char *)k2) ? false : true);
543}
544
545void
567ckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1,
568 size_t *hash2)
546ckh_pointer_hash(const void *key, size_t r_hash[2])
569{
547{
570 size_t ret1, ret2;
571 uint64_t h;
572 union {
573 const void *v;
548 union {
549 const void *v;
574 uint64_t i;
550 size_t i;
575 } u;
576
551 } u;
552
577 assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64));
578 assert(hash1 != NULL);
579 assert(hash2 != NULL);
580
581 assert(sizeof(u.v) == sizeof(u.i));
553 assert(sizeof(u.v) == sizeof(u.i));
582#if (LG_SIZEOF_PTR != LG_SIZEOF_INT)
583 u.i = 0;
584#endif
585 u.v = key;
554 u.v = key;
586 h = hash(&u.i, sizeof(u.i), UINT64_C(0xd983396e68886082));
587 if (minbits <= 32) {
588 /*
589 * Avoid doing multiple hashes, since a single hash provides
590 * enough bits.
591 */
592 ret1 = h & ZU(0xffffffffU);
593 ret2 = h >> 32;
594 } else {
595 assert(SIZEOF_PTR == 8);
596 ret1 = h;
597 ret2 = hash(&u.i, sizeof(u.i), UINT64_C(0x5e2be9aff8709a5d));
598 }
599
600 *hash1 = ret1;
601 *hash2 = ret2;
555 hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash);
602}
603
604bool
605ckh_pointer_keycomp(const void *k1, const void *k2)
606{
607
608 return ((k1 == k2) ? true : false);
609}
556}
557
558bool
559ckh_pointer_keycomp(const void *k1, const void *k2)
560{
561
562 return ((k1 == k2) ? true : false);
563}