Lines Matching +full:1 +full:- +full:cell
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
9 * 51(2):122-144.
20 * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006)
25 * #hashes | 1 | 2 | 4 | 8 |
26 * --------+-------+-------+-------+-------+
27 * 1 | 0.006 | 0.006 | 0.03 | 0.12 |
33 * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing,
51 /* Function prototypes for non-inline static functions. */
59 * Search bucket for key and return the cell number if found; SIZE_T_MAX
64 ckhc_t *cell; in ckh_bucket_search() local
67 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { in ckh_bucket_search()
68 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_bucket_search()
69 if (cell->key != NULL && ckh->keycomp(key, cell->key)) { in ckh_bucket_search()
78 * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
82 size_t hashes[2], bucket, cell; in ckh_isearch() local
86 ckh->hash(key, hashes); in ckh_isearch()
89 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
90 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
91 if (cell != SIZE_T_MAX) { in ckh_isearch()
92 return cell; in ckh_isearch()
96 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
97 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
98 return cell; in ckh_isearch()
104 ckhc_t *cell; in ckh_try_bucket_insert() local
109 * The randomness avoids worst-case search overhead as buckets fill up. in ckh_try_bucket_insert()
111 offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_try_bucket_insert()
113 for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { in ckh_try_bucket_insert()
114 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + in ckh_try_bucket_insert()
115 ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; in ckh_try_bucket_insert()
116 if (cell->key == NULL) { in ckh_try_bucket_insert()
117 cell->key = key; in ckh_try_bucket_insert()
118 cell->data = data; in ckh_try_bucket_insert()
119 ckh->count++; in ckh_try_bucket_insert()
137 ckhc_t *cell; in ckh_evict_reloc_insert() local
153 i = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_evict_reloc_insert()
155 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_evict_reloc_insert()
156 assert(cell->key != NULL); in ckh_evict_reloc_insert()
158 /* Swap cell->{key,data} and {key,data} (evict). */ in ckh_evict_reloc_insert()
159 tkey = cell->key; tdata = cell->data; in ckh_evict_reloc_insert()
160 cell->key = key; cell->data = data; in ckh_evict_reloc_insert()
164 ckh->nrelocs++; in ckh_evict_reloc_insert()
168 ckh->hash(key, hashes); in ckh_evict_reloc_insert()
169 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_evict_reloc_insert()
171 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) in ckh_evict_reloc_insert()
172 - 1); in ckh_evict_reloc_insert()
177 * during iteration, assuming pseudo-random item in ckh_evict_reloc_insert()
183 * 1) This bucket == argbucket, so we will quickly in ckh_evict_reloc_insert()
210 ckh->hash(key, hashes); in ckh_try_insert()
213 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
219 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
239 count = ckh->count; in ckh_rebuild()
240 ckh->count = 0; in ckh_rebuild()
246 ckh->count = count; in ckh_rebuild()
263 ckh->ngrows++; in ckh_grow()
271 lg_prevbuckets = ckh->lg_curbuckets; in ckh_grow()
272 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; in ckh_grow()
290 ttab = ckh->tab; in ckh_grow()
291 ckh->tab = tab; in ckh_grow()
293 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_grow()
301 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_grow()
302 ckh->tab = tab; in ckh_grow()
303 ckh->lg_curbuckets = lg_prevbuckets; in ckh_grow()
321 lg_prevbuckets = ckh->lg_curbuckets; in ckh_shrink()
322 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; in ckh_shrink()
337 ttab = ckh->tab; in ckh_shrink()
338 ckh->tab = tab; in ckh_shrink()
340 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_shrink()
345 ckh->nshrinks++; in ckh_shrink()
351 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_shrink()
352 ckh->tab = tab; in ckh_shrink()
353 ckh->lg_curbuckets = lg_prevbuckets; in ckh_shrink()
355 ckh->nshrinkfails++; in ckh_shrink()
371 ckh->ngrows = 0; in ckh_new()
372 ckh->nshrinks = 0; in ckh_new()
373 ckh->nshrinkfails = 0; in ckh_new()
374 ckh->ninserts = 0; in ckh_new()
375 ckh->nrelocs = 0; in ckh_new()
377 ckh->prng_state = 42; /* Value doesn't really matter. */ in ckh_new()
378 ckh->count = 0; in ckh_new()
388 mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; in ckh_new()
390 (ZU(1) << lg_mincells) < mincells; in ckh_new()
394 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
395 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
396 ckh->hash = hash; in ckh_new()
397 ckh->keycomp = keycomp; in ckh_new()
404 ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, in ckh_new()
406 if (ckh->tab == NULL) { in ckh_new()
425 (unsigned long long)ckh->ngrows, in ckh_delete()
426 (unsigned long long)ckh->nshrinks, in ckh_delete()
427 (unsigned long long)ckh->nshrinkfails, in ckh_delete()
428 (unsigned long long)ckh->ninserts, in ckh_delete()
429 (unsigned long long)ckh->nrelocs); in ckh_delete()
432 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_delete()
442 return ckh->count; in ckh_count()
449 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + in ckh_iter()
451 if (ckh->tab[i].key != NULL) { in ckh_iter()
453 *key = (void *)ckh->tab[i].key; in ckh_iter()
456 *data = (void *)ckh->tab[i].data; in ckh_iter()
458 *tabind = i + 1; in ckh_iter()
474 ckh->ninserts++; in ckh_insert()
492 size_t cell; in ckh_remove() local
496 cell = ckh_isearch(ckh, searchkey); in ckh_remove()
497 if (cell != SIZE_T_MAX) { in ckh_remove()
499 *key = (void *)ckh->tab[cell].key; in ckh_remove()
502 *data = (void *)ckh->tab[cell].data; in ckh_remove()
504 ckh->tab[cell].key = NULL; in ckh_remove()
505 ckh->tab[cell].data = NULL; /* Not necessary. */ in ckh_remove()
507 ckh->count--; in ckh_remove()
508 /* Try to halve the table if it is less than 1/4 full. */ in ckh_remove()
509 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets in ckh_remove()
510 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets in ckh_remove()
511 > ckh->lg_minbuckets) { in ckh_remove()
524 size_t cell; in ckh_search() local
528 cell = ckh_isearch(ckh, searchkey); in ckh_search()
529 if (cell != SIZE_T_MAX) { in ckh_search()
531 *key = (void *)ckh->tab[cell].key; in ckh_search()
534 *data = (void *)ckh->tab[cell].data; in ckh_search()