2  * Copyright 2014-2015 Olivier Houchard.
3  * Copyright 2012-2015 Samy Al Bahra.
44 #define CK_RHS_PROBE_L1_MASK (CK_RHS_PROBE_L1 - 1)
50 #define CK_RHS_VMA_MASK ((uintptr_t)((1ULL << CK_MD_VMA_BITS) - 1))
56 #define CK_RHS_G_MASK	(CK_RHS_G - 1)
81 	CK_RHS_PROBE_RH,	/* Short-circuit if RH slot found. */
82 	CK_RHS_PROBE_INSERT,	/* Short-circuit on probe bound if tombstone found. */
84 …CK_RHS_PROBE_ROBIN_HOOD,/* Look for the first slot available for the entry we are about to replace…
113 	unsigned int generation[CK_RHS_G];  member
138 	if (map->read_mostly)  in ck_rhs_entry()
139 		return (map->entries.no_entries.entries[offset]);  in ck_rhs_entry()
141 		return (map->entries.descs[offset].entry);  in ck_rhs_entry()
148 	if (map->read_mostly)  in ck_rhs_entry_addr()
149 		return (&map->entries.no_entries.entries[offset]);  in ck_rhs_entry_addr()
151 		return (&map->entries.descs[offset].entry);  in ck_rhs_entry_addr()
158 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_desc()
159 		return ((struct ck_rhs_entry_desc *)(void *)&map->entries.no_entries.descs[offset]);  in ck_rhs_desc()
161 		return (&map->entries.descs[offset]);  in ck_rhs_desc()
168 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_wanted_inc()
169 		map->entries.no_entries.descs[offset].wanted++;  in ck_rhs_wanted_inc()
171 		map->entries.descs[offset].wanted++;  in ck_rhs_wanted_inc()
178 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_probes()
179 		return (map->entries.no_entries.descs[offset].probes);  in ck_rhs_probes()
181 		return (map->entries.descs[offset].probes);  in ck_rhs_probes()
188 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_set_probes()
189 		map->entries.no_entries.descs[offset].probes = value;  in ck_rhs_set_probes()
191 		map->entries.descs[offset].probes = value;  in ck_rhs_set_probes()
198 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_probe_bound()
199 		return (map->entries.no_entries.descs[offset].probe_bound);  in ck_rhs_probe_bound()
201 		return (map->entries.descs[offset].probe_bound);  in ck_rhs_probe_bound()
208 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_probe_bound_addr()
209 		return (&map->entries.no_entries.descs[offset].probe_bound);  in ck_rhs_probe_bound_addr()
211 		return (&map->entries.descs[offset].probe_bound);  in ck_rhs_probe_bound_addr()
219 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_in_rh()
220 		return (map->entries.no_entries.descs[offset].in_rh);  in ck_rhs_in_rh()
222 		return (map->entries.descs[offset].in_rh);  in ck_rhs_in_rh()
229 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_set_rh()
230 		map->entries.no_entries.descs[offset].in_rh = true;  in ck_rhs_set_rh()
232 		map->entries.descs[offset].in_rh = true;  in ck_rhs_set_rh()
239 	if (CK_CC_UNLIKELY(map->read_mostly))  in ck_rhs_unset_rh()
240 		map->entries.no_entries.descs[offset].in_rh = false;  in ck_rhs_unset_rh()
242 		map->entries.descs[offset].in_rh = false;  in ck_rhs_unset_rh()
254 	struct ck_rhs_map *map = hs->map;  in ck_rhs_set_load_factor()
259 	hs->load_factor = load_factor;  in ck_rhs_set_load_factor()
260 	map->max_entries = (map->capacity * (unsigned long)hs->load_factor) / 100;  in ck_rhs_set_load_factor()
261 	while (map->n_entries > map->max_entries) {  in ck_rhs_set_load_factor()
262 		if (ck_rhs_grow(hs, map->capacity << 1) == false)  in ck_rhs_set_load_factor()
264 		map = hs->map;  in ck_rhs_set_load_factor()
273 	iterator->cursor = NULL;  in ck_rhs_iterator_init()
274 	iterator->offset = 0;  in ck_rhs_iterator_init()
281 	struct ck_rhs_map *map = hs->map;  in ck_rhs_next()
284 	if (i->offset >= map->capacity)  in ck_rhs_next()
288 		value = CK_CC_DECONST_PTR(ck_rhs_entry(map, i->offset));  in ck_rhs_next()
291 			if (hs->mode & CK_RHS_MODE_OBJECT)  in ck_rhs_next()
294 			i->offset++;  in ck_rhs_next()
298 	} while (++i->offset < map->capacity);  in ck_rhs_next()
306 	struct ck_rhs_map *map = hs->map;  in ck_rhs_stat()
308 	st->n_entries = map->n_entries;  in ck_rhs_stat()
309 	st->probe_maximum = map->probe_maximum;  in ck_rhs_stat()
317 	return hs->map->n_entries;  in ck_rhs_count()
324 	m->free(map, map->size, defer);  in ck_rhs_map_destroy()
332 	ck_rhs_map_destroy(hs->m, hs->map, false);  in ck_rhs_destroy()
346 	if (hs->mode & CK_RHS_MODE_READ_MOSTLY)  in ck_rhs_map_create()
350 		     2 * CK_MD_CACHELINE - 1);  in ck_rhs_map_create()
354 		     CK_MD_CACHELINE - 1);  in ck_rhs_map_create()
355 	map = hs->m->malloc(size);  in ck_rhs_map_create()
358 	map->read_mostly = !!(hs->mode & CK_RHS_MODE_READ_MOSTLY);  in ck_rhs_map_create()
360 	map->size = size;  in ck_rhs_map_create()
366 	map->probe_limit = (unsigned int)limit;  in ck_rhs_map_create()
367 	map->probe_maximum = 0;  in ck_rhs_map_create()
368 	map->capacity = n_entries;  in ck_rhs_map_create()
369 	map->step = ck_cc_ffsl(n_entries);  in ck_rhs_map_create()
370 	map->mask = n_entries - 1;  in ck_rhs_map_create()
371 	map->n_entries = 0;  in ck_rhs_map_create()
373 	map->max_entries = (map->capacity * (unsigned long)hs->load_factor) / 100;  in ck_rhs_map_create()
375 	if (map->read_mostly) {  in ck_rhs_map_create()
376 		map->entries.no_entries.entries = (void *)(((uintptr_t)&map[1] +  in ck_rhs_map_create()
377 		    CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1));  in ck_rhs_map_create()
378 …->entries.no_entries.descs = (void *)(((uintptr_t)map->entries.no_entries.entries + (sizeof(void *…  in ck_rhs_map_create()
379 		memset(map->entries.no_entries.entries, 0,  in ck_rhs_map_create()
381 		memset(map->entries.no_entries.descs, 0,  in ck_rhs_map_create()
383 		map->offset_mask = (CK_MD_CACHELINE / sizeof(void *)) - 1;  in ck_rhs_map_create()
384 		map->probe_func = ck_rhs_map_probe_rm;  in ck_rhs_map_create()
387 		map->entries.descs = (void *)(((uintptr_t)&map[1] +  in ck_rhs_map_create()
388 		    CK_MD_CACHELINE - 1) & ~(CK_MD_CACHELINE - 1));  in ck_rhs_map_create()
389 		memset(map->entries.descs, 0, sizeof(struct ck_rhs_entry_desc) * n_entries);  in ck_rhs_map_create()
390 		map->offset_mask = (CK_MD_CACHELINE / sizeof(struct ck_rhs_entry_desc)) - 1;  in ck_rhs_map_create()
391 		map->probe_func = ck_rhs_map_probe;  in ck_rhs_map_create()
393 	memset(map->generation, 0, sizeof map->generation);  in ck_rhs_map_create()
405 	previous = hs->map;  in ck_rhs_reset_size()
410 	ck_pr_store_ptr(&hs->map, map);  in ck_rhs_reset_size()
411 	ck_rhs_map_destroy(hs->m, previous, true);  in ck_rhs_reset_size()
420 	previous = hs->map;  in ck_rhs_reset()
421 	return ck_rhs_reset_size(hs, previous->capacity);  in ck_rhs_reset()
430 	if (probes & map->offset_mask) {  in ck_rhs_map_probe_next()
431 		offset = (offset &~ map->offset_mask) +  in ck_rhs_map_probe_next()
432 		    ((offset + 1) & map->offset_mask);  in ck_rhs_map_probe_next()
435 		return (offset + probes) & map->mask;  in ck_rhs_map_probe_next()
443 	if (probes & map->offset_mask) {  in ck_rhs_map_probe_prev()
444 		offset = (offset &~ map->offset_mask) + ((offset - 1) &  in ck_rhs_map_probe_prev()
445 		    map->offset_mask);  in ck_rhs_map_probe_prev()
448 		return ((offset - probes) & map->mask);  in ck_rhs_map_probe_prev()
457 	unsigned long offset = h & m->mask;  in ck_rhs_map_bound_set()
460 	if (n_probes > m->probe_maximum)  in ck_rhs_map_bound_set()
461 		ck_pr_store_uint(&m->probe_maximum, n_probes);  in ck_rhs_map_bound_set()
462 	if (!(m->read_mostly)) {  in ck_rhs_map_bound_set()
463 		desc = &m->entries.descs[offset];  in ck_rhs_map_bound_set()
465 		if (desc->probe_bound < n_probes) {  in ck_rhs_map_bound_set()
469 			CK_RHS_STORE(&desc->probe_bound, n_probes);  in ck_rhs_map_bound_set()
480 	unsigned long offset = h & m->mask;  in ck_rhs_map_bound_get()
483 	if (m->read_mostly)  in ck_rhs_map_bound_get()
484 		r = ck_pr_load_uint(&m->probe_maximum);  in ck_rhs_map_bound_get()
486 		r = CK_RHS_LOAD(&m->entries.descs[offset].probe_bound);  in ck_rhs_map_bound_get()
488 			r = ck_pr_load_uint(&m->probe_maximum);  in ck_rhs_map_bound_get()
502 	map = hs->map;  in ck_rhs_grow()
503 	if (map->capacity > capacity)  in ck_rhs_grow()
510 	for (k = 0; k < map->capacity; k++) {  in ck_rhs_grow()
518 		if (hs->mode & CK_RHS_MODE_OBJECT)  in ck_rhs_grow()
522 		h = hs->hf(previous, hs->seed);  in ck_rhs_grow()
523 		offset = h & update->mask;  in ck_rhs_grow()
529 			if (probes++ == update->probe_limit) {  in ck_rhs_grow()
533 				ck_rhs_map_destroy(hs->m, update, false);  in ck_rhs_grow()
540 				update->n_entries++;  in ck_rhs_grow()
549 				if (hs->mode & CK_RHS_MODE_OBJECT)  in ck_rhs_grow()
554 				h = hs->hf(previous, hs->seed);  in ck_rhs_grow()
557 				probes = old_probes - 1;  in ck_rhs_grow()
567 	ck_pr_store_ptr(&hs->map, update);  in ck_rhs_grow()
568 	ck_rhs_map_destroy(hs->m, map, true);  in ck_rhs_grow()
576 	return ck_rhs_grow(hs, hs->map->capacity);  in ck_rhs_rebuild()
592 	long pr = -1;  in ck_rhs_map_probe_rm()
599 	if (hs->mode & CK_RHS_MODE_OBJECT) {  in ck_rhs_map_probe_rm()
611 		offset = h & map->mask;  in ck_rhs_map_probe_rm()
622 			if (probe_limit == opl || pr != -1) {  in ck_rhs_map_probe_rm()
632 		k = ck_pr_load_ptr(&map->entries.no_entries.entries[offset]);  in ck_rhs_map_probe_rm()
637 			struct ck_rhs_entry_desc *desc = (void *)&map->entries.no_entries.descs[offset];  in ck_rhs_map_probe_rm()
639 			if (pr == -1 &&  in ck_rhs_map_probe_rm()
640 			    desc->in_rh == false && desc->probes < probes) {  in ck_rhs_map_probe_rm()
654 			if (hs->mode & CK_RHS_MODE_OBJECT) {  in ck_rhs_map_probe_rm()
667 			if (hs->compare == NULL) {  in ck_rhs_map_probe_rm()
672 			if (hs->compare(k, key) == true)  in ck_rhs_map_probe_rm()
679 		offset = -1;  in ck_rhs_map_probe_rm()
684 	if (pr == -1)  in ck_rhs_map_probe_rm()
704 	long pr = -1;  in ck_rhs_map_probe()
711 	if (hs->mode & CK_RHS_MODE_OBJECT) {  in ck_rhs_map_probe()
724 		offset = h & map->mask;  in ck_rhs_map_probe()
737 			if (probe_limit == opl || pr != -1) {  in ck_rhs_map_probe()
747 		k = ck_pr_load_ptr(&map->entries.descs[offset].entry);  in ck_rhs_map_probe()
751 			struct ck_rhs_entry_desc *desc = &map->entries.descs[offset];  in ck_rhs_map_probe()
753 			if (pr == -1 &&  in ck_rhs_map_probe()
754 			    desc->in_rh == false && desc->probes < probes) {  in ck_rhs_map_probe()
768 			if (hs->mode & CK_RHS_MODE_OBJECT) {  in ck_rhs_map_probe()
781 			if (hs->compare == NULL) {  in ck_rhs_map_probe()
786 			if (hs->compare(k, key) == true)  in ck_rhs_map_probe()
793 		offset = -1;  in ck_rhs_map_probe()
798 	if (pr == -1)  in ck_rhs_map_probe()
830 	struct ck_rhs_map *map = hs->map;  in ck_rhs_gc()
833 	for (i = 0; i < map->capacity; i++) {  in ck_rhs_gc()
837 	map->probe_maximum = max_probes;  in ck_rhs_gc()
845 	struct ck_rhs_map *map = hs->map;  in ck_rhs_add_wanted()
851 	offset = h & map->mask;  in ck_rhs_add_wanted()
853 	if (old_slot == -1)  in ck_rhs_add_wanted()
860 			if (desc->wanted < CK_RHS_MAX_WANTED)  in ck_rhs_add_wanted()
861 				desc->wanted++;  in ck_rhs_add_wanted()
871 	struct ck_rhs_map *map = hs->map;  in ck_rhs_remove_wanted()
877 		probes--;  in ck_rhs_remove_wanted()
883 			if (desc->wanted != CK_RHS_MAX_WANTED)  in ck_rhs_remove_wanted()
884 				desc->wanted--;  in ck_rhs_remove_wanted()
893 	while (probes > (unsigned long)map->offset_mask + 1) {  in ck_rhs_get_first_offset()
894 		offset -= ((probes - 1) &~ map->offset_mask);  in ck_rhs_get_first_offset()
895 		offset &= map->mask;  in ck_rhs_get_first_offset()
896 		offset = (offset &~ map->offset_mask) +  in ck_rhs_get_first_offset()
897 		    ((offset - map->offset_mask) & map->offset_mask);  in ck_rhs_get_first_offset()
898 		probes -= map->offset_mask + 1;  in ck_rhs_get_first_offset()
900 	return ((offset &~ map->offset_mask) + ((offset - (probes - 1)) & map->offset_mask));  in ck_rhs_get_first_offset()
909 	long slot, first;  in ck_rhs_put_robin_hood()  local
920 	map = hs->map;  in ck_rhs_put_robin_hood()
921 	first = orig_slot;  in ck_rhs_put_robin_hood()
922 	n_probes = desc->probes;  in ck_rhs_put_robin_hood()
924 	key = CK_CC_DECONST_PTR(ck_rhs_entry(map, first));  in ck_rhs_put_robin_hood()
927 	if (hs->mode & CK_RHS_MODE_OBJECT)  in ck_rhs_put_robin_hood()
930 	orig_slot = first;  in ck_rhs_put_robin_hood()
933 	slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,  in ck_rhs_put_robin_hood()
934 	    map->probe_limit, prevs_nb == CK_RHS_MAX_RH ?  in ck_rhs_put_robin_hood()
937 	if (slot == -1 && first == -1) {  in ck_rhs_put_robin_hood()
938 		if (ck_rhs_grow(hs, map->capacity << 1) == false) {  in ck_rhs_put_robin_hood()
939 			desc->in_rh = false;  in ck_rhs_put_robin_hood()
944 			return -1;  in ck_rhs_put_robin_hood()
950 	if (first != -1) {  in ck_rhs_put_robin_hood()
951 		desc = ck_rhs_desc(map, first);  in ck_rhs_put_robin_hood()
952 		int old_probes = desc->probes;  in ck_rhs_put_robin_hood()
954 		desc->probes = n_probes;  in ck_rhs_put_robin_hood()
955 		h = ck_rhs_get_first_offset(map, first, n_probes);  in ck_rhs_put_robin_hood()
966 		ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_put_robin_hood()
969 		desc->in_rh = 0;  in ck_rhs_put_robin_hood()
973 		prev = prevs[--prevs_nb];  in ck_rhs_put_robin_hood()
977 		    desc->probes);  in ck_rhs_put_robin_hood()
979 		ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_put_robin_hood()
982 		desc->in_rh = false;  in ck_rhs_put_robin_hood()
991 	struct ck_rhs_map *map = hs->map;  in ck_rhs_do_backward_shift_delete()
996 	h = ck_rhs_remove_wanted(hs, slot, -1);  in ck_rhs_do_backward_shift_delete()
997 	while (desc->wanted > 0) {  in ck_rhs_do_backward_shift_delete()
1004 		while (wanted_probes < map->probe_maximum) {  in ck_rhs_do_backward_shift_delete()
1007 			while (probe < map->probe_maximum) {  in ck_rhs_do_backward_shift_delete()
1009 				if (new_desc->probes == probe + 1)  in ck_rhs_do_backward_shift_delete()
1015 			if (probe < map->probe_maximum)  in ck_rhs_do_backward_shift_delete()
1019 		if (!(wanted_probes < map->probe_maximum)) {  in ck_rhs_do_backward_shift_delete()
1020 			desc->wanted = 0;  in ck_rhs_do_backward_shift_delete()
1023 		desc->probes = wanted_probes;  in ck_rhs_do_backward_shift_delete()
1027 		ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_do_backward_shift_delete()
1031 			if (hdesc->wanted == 1)  in ck_rhs_do_backward_shift_delete()
1032 				CK_RHS_STORE(&hdesc->probe_bound,  in ck_rhs_do_backward_shift_delete()
1034 			else if (hdesc->probe_bound == CK_RHS_WORD_MAX ||  in ck_rhs_do_backward_shift_delete()
1035 			    hdesc->probe_bound == new_desc->probes) {  in ck_rhs_do_backward_shift_delete()
1037 				if (hdesc->probe_bound == CK_RHS_WORD_MAX)  in ck_rhs_do_backward_shift_delete()
1038 					max_probes = map->probe_maximum;  in ck_rhs_do_backward_shift_delete()
1040 					max_probes = hdesc->probe_bound;  in ck_rhs_do_backward_shift_delete()
1041 					max_probes--;  in ck_rhs_do_backward_shift_delete()
1052 					CK_RHS_STORE(&hdesc->probe_bound,  in ck_rhs_do_backward_shift_delete()
1056 		if (desc->wanted < CK_RHS_MAX_WANTED)  in ck_rhs_do_backward_shift_delete()
1057 			desc->wanted--;  in ck_rhs_do_backward_shift_delete()
1062 	if ((desc->probes - 1) < CK_RHS_WORD_MAX)  in ck_rhs_do_backward_shift_delete()
1064 		    desc->probes - 1);  in ck_rhs_do_backward_shift_delete()
1065 	desc->probes = 0;  in ck_rhs_do_backward_shift_delete()
1074 	long slot, first;  in ck_rhs_fas()  local
1078 	struct ck_rhs_map *map = hs->map;  in ck_rhs_fas()
1083 	slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,  in ck_rhs_fas()
1090 	insert = ck_rhs_marshal(hs->mode, key, h);  in ck_rhs_fas()
1092 	if (first != -1) {  in ck_rhs_fas()
1096 		desc2 = ck_rhs_desc(map, first);  in ck_rhs_fas()
1097 		desc->in_rh = true;  in ck_rhs_fas()
1098 		ret = ck_rhs_put_robin_hood(hs, first, desc2);  in ck_rhs_fas()
1099 		desc->in_rh = false;  in ck_rhs_fas()
1104 		ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);  in ck_rhs_fas()
1105 		ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_fas()
1107 		desc2->probes = n_probes;  in ck_rhs_fas()
1108 		ck_rhs_add_wanted(hs, first, -1, h);  in ck_rhs_fas()
1119  * An apply function takes two arguments. The first argument is a pointer to a
1120  * pre-existing object. The second argument is a pointer to the fifth argument
1121  * passed to ck_hs_apply. If a non-NULL pointer is passed to the first argument
1122  * and the return value of the apply function is NULL, then the pre-existing
1124  * apply function then no changes are made to the hash table.  If the first
1125  * argument is non-NULL and the return pointer is different than that passed to
1126  * the apply function, then the pre-existing value is replaced. For
1140 	long slot, first;  in ck_rhs_apply()  local
1145 	map = hs->map;  in ck_rhs_apply()
1147 …slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_RHS_PROBE…  in ck_rhs_apply()
1148 	if (slot == -1 && first == -1) {  in ck_rhs_apply()
1149 		if (ck_rhs_grow(hs, map->capacity << 1) == false)  in ck_rhs_apply()
1179 	insert = ck_rhs_marshal(hs->mode, delta, h);  in ck_rhs_apply()
1180 	if (first != -1) {  in ck_rhs_apply()
1186 		if (slot != -1) {  in ck_rhs_apply()
1188 			desc->in_rh = true;  in ck_rhs_apply()
1190 		desc2 = ck_rhs_desc(map, first);  in ck_rhs_apply()
1191 		int ret = ck_rhs_put_robin_hood(hs, first, desc2);  in ck_rhs_apply()
1192 		if (slot != -1)  in ck_rhs_apply()
1193 			desc->in_rh = false;  in ck_rhs_apply()
1197 		if (CK_CC_UNLIKELY(ret == -1))  in ck_rhs_apply()
1200 		ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);  in ck_rhs_apply()
1201 		desc2->probes = n_probes;  in ck_rhs_apply()
1209 		ck_rhs_add_wanted(hs, first, -1, h);  in ck_rhs_apply()
1211 			ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_apply()
1223 			ck_rhs_add_wanted(hs, slot, -1, h);  in ck_rhs_apply()
1227 		map->n_entries++;  in ck_rhs_apply()
1228 		if ((map->n_entries ) > map->max_entries)  in ck_rhs_apply()
1229 			ck_rhs_grow(hs, map->capacity << 1);  in ck_rhs_apply()
1240 	long slot, first;  in ck_rhs_set()  local
1249 	map = hs->map;  in ck_rhs_set()
1251 …slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object, map->probe_limit, CK_RHS_PROBE…  in ck_rhs_set()
1252 	if (slot == -1 && first == -1) {  in ck_rhs_set()
1253 		if (ck_rhs_grow(hs, map->capacity << 1) == false)  in ck_rhs_set()
1259 	insert = ck_rhs_marshal(hs->mode, key, h);  in ck_rhs_set()
1261 	if (first != -1) {  in ck_rhs_set()
1263 		if (slot != -1) {  in ck_rhs_set()
1265 			desc->in_rh = true;  in ck_rhs_set()
1267 		desc2 = ck_rhs_desc(map, first);  in ck_rhs_set()
1268 		int ret = ck_rhs_put_robin_hood(hs, first, desc2);  in ck_rhs_set()
1269 		if (slot != -1)  in ck_rhs_set()
1270 			desc->in_rh = false;  in ck_rhs_set()
1274 		if (CK_CC_UNLIKELY(ret == -1))  in ck_rhs_set()
1277 		ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);  in ck_rhs_set()
1278 		desc2->probes = n_probes;  in ck_rhs_set()
1286 		ck_rhs_add_wanted(hs, first, -1, h);  in ck_rhs_set()
1288 			ck_pr_inc_uint(&map->generation[h & CK_RHS_G_MASK]);  in ck_rhs_set()
1301 			ck_rhs_add_wanted(hs, slot, -1, h);  in ck_rhs_set()
1305 		map->n_entries++;  in ck_rhs_set()
1306 		if ((map->n_entries ) > map->max_entries)  in ck_rhs_set()
1307 			ck_rhs_grow(hs, map->capacity << 1);  in ck_rhs_set()
1320 	long slot, first;  in ck_rhs_put_internal()  local
1327 	map = hs->map;  in ck_rhs_put_internal()
1329 	slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,  in ck_rhs_put_internal()
1330 	    map->probe_limit, behavior);  in ck_rhs_put_internal()
1332 	if (slot == -1 && first == -1) {  in ck_rhs_put_internal()
1333 		if (ck_rhs_grow(hs, map->capacity << 1) == false)  in ck_rhs_put_internal()
1344 	insert = ck_rhs_marshal(hs->mode, key, h);  in ck_rhs_put_internal()
1346 	if (first != -1) {  in ck_rhs_put_internal()
1347 		struct ck_rhs_entry_desc *desc = ck_rhs_desc(map, first);  in ck_rhs_put_internal()
1348 		int ret = ck_rhs_put_robin_hood(hs, first, desc);  in ck_rhs_put_internal()
1351 		else if (CK_CC_UNLIKELY(ret == -1))  in ck_rhs_put_internal()
1353 		/* Insert key into first bucket in probe sequence. */  in ck_rhs_put_internal()
1354 		ck_pr_store_ptr(ck_rhs_entry_addr(map, first), insert);  in ck_rhs_put_internal()
1355 		desc->probes = n_probes;  in ck_rhs_put_internal()
1356 		ck_rhs_add_wanted(hs, first, -1, h);  in ck_rhs_put_internal()
1361 		ck_rhs_add_wanted(hs, slot, -1, h);  in ck_rhs_put_internal()
1364 	map->n_entries++;  in ck_rhs_put_internal()
1365 	if ((map->n_entries ) > map->max_entries)  in ck_rhs_put_internal()
1366 		ck_rhs_grow(hs, map->capacity << 1);  in ck_rhs_put_internal()
1393 	long first;  in ck_rhs_get()  local
1398 	unsigned int *generation;  in ck_rhs_get()  local
1401 		map = ck_pr_load_ptr(&hs->map);  in ck_rhs_get()
1402 		generation = &map->generation[h & CK_RHS_G_MASK];  in ck_rhs_get()
1403 		g = ck_pr_load_uint(generation);  in ck_rhs_get()
1407 		first = -1;  in ck_rhs_get()
1408 		map->probe_func(hs, map, &n_probes, &first, h, key, &object, probe, CK_RHS_PROBE_NO_RH);  in ck_rhs_get()
1411 		g_p = ck_pr_load_uint(generation);  in ck_rhs_get()
1422 	long slot, first;  in ck_rhs_remove()  local
1424 	struct ck_rhs_map *map = hs->map;  in ck_rhs_remove()
1427 	slot = map->probe_func(hs, map, &n_probes, &first, h, key, &object,  in ck_rhs_remove()
1432 	map->n_entries--;  in ck_rhs_remove()
1445 	if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)  in ck_rhs_move()
1448 	hs->mode = source->mode;  in ck_rhs_move()
1449 	hs->seed = source->seed;  in ck_rhs_move()
1450 	hs->map = source->map;  in ck_rhs_move()
1451 	hs->load_factor = source->load_factor;  in ck_rhs_move()
1452 	hs->m = m;  in ck_rhs_move()
1453 	hs->hf = hf;  in ck_rhs_move()
1454 	hs->compare = compare;  in ck_rhs_move()
1468 	if (m == NULL || m->malloc == NULL || m->free == NULL || hf == NULL)  in ck_rhs_init()
1471 	hs->m = m;  in ck_rhs_init()
1472 	hs->mode = mode;  in ck_rhs_init()
1473 	hs->seed = seed;  in ck_rhs_init()
1474 	hs->hf = hf;  in ck_rhs_init()
1475 	hs->compare = compare;  in ck_rhs_init()
1476 	hs->load_factor = CK_RHS_DEFAULT_LOAD_FACTOR;  in ck_rhs_init()
1478 	hs->map = ck_rhs_map_create(hs, n_entries);  in ck_rhs_init()
1479 	return hs->map != NULL;  in ck_rhs_init()