98 ck_hs_map_signal(struct ck_hs_map *map, unsigned long h)  in ck_hs_map_signal()  argument
102 	ck_pr_store_uint(&map->generation[h],  in ck_hs_map_signal()
103 	    map->generation[h] + 1);  in ck_hs_map_signal()
109 _ck_hs_next(struct ck_hs *hs, struct ck_hs_map *map,  in _ck_hs_next()  argument
114 	if (i->offset >= map->capacity)  in _ck_hs_next()
118 		value = CK_CC_DECONST_PTR(map->entries[i->offset]);  in _ck_hs_next()
130 	} while (++i->offset < map->capacity);  in _ck_hs_next()
141 	iterator->map = NULL;  in ck_hs_iterator_init()
149 	return _ck_hs_next(hs, hs->map, i, key);  in ck_hs_next()
155 	struct ck_hs_map *m = i->map;  in ck_hs_next_spmc()
158 		m = i->map = ck_pr_load_ptr(&hs->map);  in ck_hs_next_spmc()
167 	struct ck_hs_map *map = hs->map;  in ck_hs_stat()  local
169 	st->n_entries = map->n_entries;  in ck_hs_stat()
170 	st->tombstones = map->tombstones;  in ck_hs_stat()
171 	st->probe_maximum = map->probe_maximum;  in ck_hs_stat()
179 	return hs->map->n_entries;  in ck_hs_count()
183 ck_hs_map_destroy(struct ck_malloc *m, struct ck_hs_map *map, bool defer)  in ck_hs_map_destroy()  argument
186 	m->free(map, map->size, defer);  in ck_hs_map_destroy()
194 	ck_hs_map_destroy(hs->m, hs->map, false);  in ck_hs_destroy()
201 	struct ck_hs_map *map;  in ck_hs_map_create()  local
217 	map = hs->m->malloc(size);  in ck_hs_map_create()
218 	if (map == NULL)  in ck_hs_map_create()
221 	map->size = size;  in ck_hs_map_create()
228 	map->probe_limit = (unsigned int)limit;  in ck_hs_map_create()
229 	map->probe_maximum = 0;  in ck_hs_map_create()
230 	map->capacity = n_entries;  in ck_hs_map_create()
231 	map->step = ck_cc_ffsl(n_entries);  in ck_hs_map_create()
232 	map->mask = n_entries - 1;  in ck_hs_map_create()
233 	map->n_entries = 0;  in ck_hs_map_create()
235 	/* Align map allocation to cache line. */  in ck_hs_map_create()
236 	map->entries = (void *)(((uintptr_t)&map[1] + prefix +  in ck_hs_map_create()
239 	memset(map->entries, 0, sizeof(void *) * n_entries);  in ck_hs_map_create()
240 	memset(map->generation, 0, sizeof map->generation);  in ck_hs_map_create()
243 		map->probe_bound = (CK_HS_WORD *)&map[1];  in ck_hs_map_create()
244 		memset(map->probe_bound, 0, prefix);  in ck_hs_map_create()
246 		map->probe_bound = NULL;  in ck_hs_map_create()
249 	/* Commit entries purge with respect to map publication. */  in ck_hs_map_create()
251 	return map;  in ck_hs_map_create()
257 	struct ck_hs_map *map, *previous;  in ck_hs_reset_size()  local
259 	previous = hs->map;  in ck_hs_reset_size()
260 	map = ck_hs_map_create(hs, capacity);  in ck_hs_reset_size()
261 	if (map == NULL)  in ck_hs_reset_size()
264 	ck_pr_store_ptr(&hs->map, map);  in ck_hs_reset_size()
274 	previous = hs->map;  in ck_hs_reset()
279 ck_hs_map_probe_next(struct ck_hs_map *map,  in ck_hs_map_probe_next()  argument
287 	r = (h >> map->step) >> level;  in ck_hs_map_probe_next()
291 	    (stride | CK_HS_PROBE_L1)) & map->mask;  in ck_hs_map_probe_next()
336 	struct ck_hs_map *map, *update;  in ck_hs_grow()  local
341 	map = hs->map;  in ck_hs_grow()
342 	if (map->capacity > capacity)  in ck_hs_grow()
349 	for (k = 0; k < map->capacity; k++) {  in ck_hs_grow()
352 		previous = map->entries[k];  in ck_hs_grow()
375 					*cursor = map->entries[k];  in ck_hs_grow()
391 			 * We have hit the probe limit, map needs to be even larger.  in ck_hs_grow()
400 	ck_pr_store_ptr(&hs->map, update);  in ck_hs_grow()
401 	ck_hs_map_destroy(hs->m, map, true);  in ck_hs_grow()
406 ck_hs_map_postinsert(struct ck_hs *hs, struct ck_hs_map *map)  in ck_hs_map_postinsert()  argument
409 	map->n_entries++;  in ck_hs_map_postinsert()
410 	if ((map->n_entries << 1) > map->capacity)  in ck_hs_map_postinsert()
411 		ck_hs_grow(hs, map->capacity << 1);  in ck_hs_map_postinsert()
420 	return ck_hs_grow(hs, hs->map->capacity);  in ck_hs_rebuild()
425     struct ck_hs_map *map,  in ck_hs_map_probe()  argument
452 	offset = h & map->mask;  in ck_hs_map_probe()
458 		probe_limit = ck_hs_map_bound_get(map, h);  in ck_hs_map_probe()
461 		bucket = (const void **)((uintptr_t)&map->entries[offset] & ~(CK_MD_CACHELINE - 1));  in ck_hs_map_probe()
516 		offset = ck_hs_map_probe_next(map, offset, h, i++, probes);  in ck_hs_map_probe()
560 	struct ck_hs_map *map = hs->map;  in ck_hs_gc()  local
564 	if (map->n_entries == 0) {  in ck_hs_gc()
565 		ck_pr_store_uint(&map->probe_maximum, 0);  in ck_hs_gc()
566 		if (map->probe_bound != NULL)  in ck_hs_gc()
567 			memset(map->probe_bound, 0, sizeof(CK_HS_WORD) * map->capacity);  in ck_hs_gc()
575 		if (map->probe_bound != NULL) {  in ck_hs_gc()
576 			size = sizeof(CK_HS_WORD) * map->capacity;  in ck_hs_gc()
584 		maximum = map->probe_maximum;  in ck_hs_gc()
587 	for (i = 0; i < map->capacity; i++) {  in ck_hs_gc()
591 		entry = map->entries[(i + seed) & map->mask];  in ck_hs_gc()
601 		offset = h & map->mask;  in ck_hs_gc()
603 		slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, entry, &object,  in ck_hs_gc()
604 		    ck_hs_map_bound_get(map, h), CK_HS_PROBE);  in ck_hs_gc()
610 			ck_hs_map_signal(map, h);  in ck_hs_gc()
631 	if (maximum != map->probe_maximum)  in ck_hs_gc()
632 		ck_pr_store_uint(&map->probe_maximum, maximum);  in ck_hs_gc()
635 		for (i = 0; i < map->capacity; i++)  in ck_hs_gc()
636 			CK_HS_STORE(&map->probe_bound[i], bounds[i]);  in ck_hs_gc()
651 	struct ck_hs_map *map = hs->map;  in ck_hs_fas()  local
655 	slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,  in ck_hs_fas()
656 	    ck_hs_map_bound_get(map, h), CK_HS_PROBE);  in ck_hs_fas()
666 		ck_hs_map_signal(map, h);  in ck_hs_fas()
697 	struct ck_hs_map *map;  in ck_hs_apply()  local
700 	map = hs->map;  in ck_hs_apply()
702 …slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_…  in ck_hs_apply()
704 		if (ck_hs_grow(hs, map->capacity << 1) == false)  in ck_hs_apply()
721 		map->n_entries--;  in ck_hs_apply()
722 		map->tombstones++;  in ck_hs_apply()
731 	ck_hs_map_bound_set(map, h, n_probes);  in ck_hs_apply()
742 			ck_hs_map_signal(map, h);  in ck_hs_apply()
754 		ck_hs_map_postinsert(hs, map);  in ck_hs_apply()
767 	struct ck_hs_map *map;  in ck_hs_set()  local
772 	map = hs->map;  in ck_hs_set()
774 …slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_HS_PROBE_…  in ck_hs_set()
776 		if (ck_hs_grow(hs, map->capacity << 1) == false)  in ck_hs_set()
782 	ck_hs_map_bound_set(map, h, n_probes);  in ck_hs_set()
797 			ck_hs_map_signal(map, h);  in ck_hs_set()
809 		ck_hs_map_postinsert(hs, map);  in ck_hs_set()
823 	struct ck_hs_map *map;  in ck_hs_put_internal()  local
826 	map = hs->map;  in ck_hs_put_internal()
828 	slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,  in ck_hs_put_internal()
829 	    map->probe_limit, behavior);  in ck_hs_put_internal()
832 		if (ck_hs_grow(hs, map->capacity << 1) == false)  in ck_hs_put_internal()
842 	ck_hs_map_bound_set(map, h, n_probes);  in ck_hs_put_internal()
853 	ck_hs_map_postinsert(hs, map);  in ck_hs_put_internal()
881 	struct ck_hs_map *map;  in ck_hs_get()  local
887 		map = ck_pr_load_ptr(&hs->map);  in ck_hs_get()
888 		generation = &map->generation[h & CK_HS_G_MASK];  in ck_hs_get()
890 		probe  = ck_hs_map_bound_get(map, h);  in ck_hs_get()
893 		ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object, probe, CK_HS_PROBE);  in ck_hs_get()
908 	struct ck_hs_map *map = hs->map;  in ck_hs_remove()  local
911 	slot = ck_hs_map_probe(hs, map, &n_probes, &first, h, key, &object,  in ck_hs_remove()
912 	    ck_hs_map_bound_get(map, h), CK_HS_PROBE);  in ck_hs_remove()
917 	map->n_entries--;  in ck_hs_remove()
918 	map->tombstones++;  in ck_hs_remove()
935 	hs->map = source->map;  in ck_hs_move()
961 	hs->map = ck_hs_map_create(hs, n_entries);  in ck_hs_init()
962 	return hs->map != NULL;  in ck_hs_init()