Lines Matching full:map
98 struct ck_ht_map *map = table->map; in ck_ht_stat() local
100 st->n_entries = map->n_entries; in ck_ht_stat()
101 st->probe_maximum = map->probe_maximum; in ck_ht_stat()
140 struct ck_ht_map *map; in ck_ht_map_create() local
159 map = table->m->malloc(size); in ck_ht_map_create()
160 if (map == NULL) in ck_ht_map_create()
163 map->mode = table->mode; in ck_ht_map_create()
164 map->size = size; in ck_ht_map_create()
165 map->probe_limit = ck_internal_max_64(n_entries >> in ck_ht_map_create()
168 map->deletions = 0; in ck_ht_map_create()
169 map->probe_maximum = 0; in ck_ht_map_create()
170 map->capacity = n_entries; in ck_ht_map_create()
171 map->step = ck_cc_ffsll(map->capacity); in ck_ht_map_create()
172 map->mask = map->capacity - 1; in ck_ht_map_create()
173 map->n_entries = 0; in ck_ht_map_create()
174 map->entries = (struct ck_ht_entry *)(((uintptr_t)&map[1] + prefix + in ck_ht_map_create()
178 map->probe_bound = (CK_HT_WORD *)&map[1]; in ck_ht_map_create()
179 memset(map->probe_bound, 0, prefix); in ck_ht_map_create()
181 map->probe_bound = NULL; in ck_ht_map_create()
184 memset(map->entries, 0, sizeof(struct ck_ht_entry) * n_entries); in ck_ht_map_create()
186 return map; in ck_ht_map_create()
228 ck_ht_map_destroy(struct ck_malloc *m, struct ck_ht_map *map, bool defer) in ck_ht_map_destroy() argument
231 m->free(map, map->size, defer); in ck_ht_map_destroy()
236 ck_ht_map_probe_next(struct ck_ht_map *map, size_t offset, ck_ht_hash_t h, size_t probes) in ck_ht_map_probe_next() argument
242 r.value = (h.value >> map->step) >> level; in ck_ht_map_probe_next()
247 (stride | CK_HT_BUCKET_LENGTH)) & map->mask; in ck_ht_map_probe_next()
272 table->map = ck_ht_map_create(table, entries); in ck_ht_init()
273 return table->map != NULL; in ck_ht_init()
277 ck_ht_map_probe_wr(struct ck_ht_map *map, in ck_ht_map_probe_wr() argument
293 limit = ck_ht_map_bound_get(map, h); in ck_ht_map_probe_wr()
298 offset = h.value & map->mask; in ck_ht_map_probe_wr()
299 for (i = 0; i < map->probe_limit; i++) { in ck_ht_map_probe_wr()
305 bucket = (void *)((uintptr_t)(map->entries + offset) & in ck_ht_map_probe_wr()
336 if (map->mode & CK_HT_MODE_BYTESTRING) { in ck_ht_map_probe_wr()
361 offset = ck_ht_map_probe_next(map, offset, h, probes); in ck_ht_map_probe_wr()
386 struct ck_ht_map *map = ht->map; in ck_ht_gc() local
390 if (map->n_entries == 0) { in ck_ht_gc()
391 CK_HT_TYPE_STORE(&map->probe_maximum, 0); in ck_ht_gc()
392 if (map->probe_bound != NULL) in ck_ht_gc()
393 memset(map->probe_bound, 0, sizeof(CK_HT_WORD) * map->capacity); in ck_ht_gc()
401 if (map->probe_bound != NULL) { in ck_ht_gc()
402 size = sizeof(CK_HT_WORD) * map->capacity; in ck_ht_gc()
410 maximum = map->probe_maximum; in ck_ht_gc()
413 for (i = 0; i < map->capacity; i++) { in ck_ht_gc()
419 entry = &map->entries[(i + seed) & map->mask]; in ck_ht_gc()
432 entry = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_gc()
442 entry = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_gc()
448 offset = h.value & map->mask; in ck_ht_gc()
451 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_gc()
461 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_gc()
480 if (maximum != map->probe_maximum) in ck_ht_gc()
481 CK_HT_TYPE_STORE(&map->probe_maximum, maximum); in ck_ht_gc()
484 for (i = 0; i < map->capacity; i++) in ck_ht_gc()
485 CK_HT_STORE(&map->probe_bound[i], bounds[i]); in ck_ht_gc()
494 ck_ht_map_probe_rd(struct ck_ht_map *map, in ck_ht_map_probe_rd() argument
511 probe_maximum = ck_ht_map_bound_get(map, h); in ck_ht_map_probe_rd()
512 offset = h.value & map->mask; in ck_ht_map_probe_rd()
514 for (i = 0; i < map->probe_limit; i++) { in ck_ht_map_probe_rd()
520 bucket = (void *)((uintptr_t)(map->entries + offset) & in ck_ht_map_probe_rd()
536 d = CK_HT_TYPE_LOAD(&map->deletions); in ck_ht_map_probe_rd()
558 if (map->mode & CK_HT_MODE_BYTESTRING) { in ck_ht_map_probe_rd()
575 d_prime = CK_HT_TYPE_LOAD(&map->deletions); in ck_ht_map_probe_rd()
591 offset = ck_ht_map_probe_next(map, offset, h, probes); in ck_ht_map_probe_rd()
603 struct ck_ht_map *map = ck_pr_load_ptr(&table->map); in ck_ht_count() local
605 return CK_HT_TYPE_LOAD(&map->n_entries); in ck_ht_count()
613 struct ck_ht_map *map = table->map; in ck_ht_next() local
616 if (i->offset >= map->capacity) in ck_ht_next()
620 key = map->entries[i->offset].key; in ck_ht_next()
623 } while (++i->offset < map->capacity); in ck_ht_next()
625 if (i->offset >= map->capacity) in ck_ht_next()
628 *entry = map->entries + i->offset++; in ck_ht_next()
635 struct ck_ht_map *map, *update; in ck_ht_reset_size_spmc() local
637 map = table->map; in ck_ht_reset_size_spmc()
642 ck_pr_store_ptr_unsafe(&table->map, update); in ck_ht_reset_size_spmc()
643 ck_ht_map_destroy(table->m, map, true); in ck_ht_reset_size_spmc()
650 struct ck_ht_map *map = table->map; in ck_ht_reset_spmc() local
652 return ck_ht_reset_size_spmc(table, map->capacity); in ck_ht_reset_spmc()
658 struct ck_ht_map *map, *update; in ck_ht_grow_spmc() local
665 map = table->map; in ck_ht_grow_spmc()
667 if (map->capacity >= capacity) in ck_ht_grow_spmc()
674 for (k = 0; k < map->capacity; k++) { in ck_ht_grow_spmc()
675 previous = &map->entries[k]; in ck_ht_grow_spmc()
728 * We have hit the probe limit, the map needs to be even in ck_ht_grow_spmc()
738 ck_pr_store_ptr_unsafe(&table->map, update); in ck_ht_grow_spmc()
739 ck_ht_map_destroy(table->m, map, true); in ck_ht_grow_spmc()
748 struct ck_ht_map *map; in ck_ht_remove_spmc() local
751 map = table->map; in ck_ht_remove_spmc()
754 candidate = ck_ht_map_probe_rd(map, h, &snapshot, in ck_ht_remove_spmc()
758 candidate = ck_ht_map_probe_rd(map, h, &snapshot, in ck_ht_remove_spmc()
771 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries - 1); in ck_ht_remove_spmc()
781 struct ck_ht_map *map; in ck_ht_get_spmc() local
785 map = ck_pr_load_ptr(&table->map); in ck_ht_get_spmc()
791 d = CK_HT_TYPE_LOAD(&map->deletions); in ck_ht_get_spmc()
794 candidate = ck_ht_map_probe_rd(map, h, &snapshot, in ck_ht_get_spmc()
797 candidate = ck_ht_map_probe_rd(map, h, &snapshot, in ck_ht_get_spmc()
801 d_prime = CK_HT_TYPE_LOAD(&map->deletions); in ck_ht_get_spmc()
824 struct ck_ht_map *map; in ck_ht_set_spmc() local
829 map = table->map; in ck_ht_set_spmc()
832 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_set_spmc()
837 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_set_spmc()
851 if (ck_ht_grow_spmc(table, map->capacity << 1) == false) in ck_ht_set_spmc()
882 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_set_spmc()
895 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_set_spmc()
912 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_set_spmc()
934 * of entries associated with map. in ck_ht_set_spmc()
937 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries + 1); in ck_ht_set_spmc()
940 ck_ht_map_bound_set(map, h, probes); in ck_ht_set_spmc()
943 if (map->n_entries * 2 > map->capacity) in ck_ht_set_spmc()
944 ck_ht_grow_spmc(table, map->capacity << 1); in ck_ht_set_spmc()
961 struct ck_ht_map *map; in ck_ht_put_spmc() local
965 map = table->map; in ck_ht_put_spmc()
968 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_put_spmc()
973 candidate = ck_ht_map_probe_wr(map, h, &snapshot, &priority, in ck_ht_put_spmc()
982 if (ck_ht_grow_spmc(table, map->capacity << 1) == false) in ck_ht_put_spmc()
988 CK_HT_TYPE_STORE(&map->deletions, map->deletions + 1); in ck_ht_put_spmc()
1004 ck_ht_map_bound_set(map, h, probes); in ck_ht_put_spmc()
1018 CK_HT_TYPE_STORE(&map->n_entries, map->n_entries + 1); in ck_ht_put_spmc()
1021 if (map->n_entries * 2 > map->capacity) in ck_ht_put_spmc()
1022 ck_ht_grow_spmc(table, map->capacity << 1); in ck_ht_put_spmc()
1031 ck_ht_map_destroy(table->m, table->map, false); in ck_ht_destroy()