Lines Matching refs:idx
374 static struct hashmap_base_entry* bucket_at(HashmapBase *h, unsigned idx) { in bucket_at() argument
376 ((uint8_t*) storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size); in bucket_at()
379 static struct plain_hashmap_entry* plain_bucket_at(Hashmap *h, unsigned idx) { in plain_bucket_at() argument
380 return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx); in plain_bucket_at()
383 static struct ordered_hashmap_entry* ordered_bucket_at(OrderedHashmap *h, unsigned idx) { in ordered_bucket_at() argument
384 return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx); in ordered_bucket_at()
387 static struct set_entry *set_bucket_at(Set *h, unsigned idx) { in set_bucket_at() argument
388 return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx); in set_bucket_at()
391 static struct ordered_hashmap_entry* bucket_at_swap(struct swap_entries *swap, unsigned idx) { in bucket_at_swap() argument
392 return &swap->e[idx - _IDX_SWAP_BEGIN]; in bucket_at_swap()
398 unsigned idx) { in bucket_at_virtual() argument
399 if (idx < _IDX_SWAP_BEGIN) in bucket_at_virtual()
400 return bucket_at(h, idx); in bucket_at_virtual()
402 if (idx < _IDX_SWAP_END) in bucket_at_virtual()
403 return &bucket_at_swap(swap, idx)->p.b; in bucket_at_virtual()
413 static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) { in bucket_distance() argument
414 return idx >= from ? idx - from in bucket_distance()
415 : n_buckets(h) + idx - from; in bucket_distance()
418 static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) { in bucket_calculate_dib() argument
437 initial_bucket = bucket_hash(h, bucket_at(h, idx)->key); in bucket_calculate_dib()
438 return bucket_distance(h, idx, initial_bucket); in bucket_calculate_dib()
441 static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) { in bucket_set_dib() argument
442 dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE; in bucket_set_dib()
445 static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) { in skip_free_buckets() argument
450 for ( ; idx < n_buckets(h); idx++) in skip_free_buckets()
451 if (dibs[idx] != DIB_RAW_FREE) in skip_free_buckets()
452 return idx; in skip_free_buckets()
457 static void bucket_mark_free(HashmapBase *h, unsigned idx) { in bucket_mark_free() argument
458 memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size); in bucket_mark_free()
459 bucket_set_dib(h, idx, DIB_FREE); in bucket_mark_free()
498 static unsigned next_idx(HashmapBase *h, unsigned idx) { in next_idx() argument
499 return (idx + 1U) % n_buckets(h); in next_idx()
502 static unsigned prev_idx(HashmapBase *h, unsigned idx) { in prev_idx() argument
503 return (n_buckets(h) + idx - 1U) % n_buckets(h); in prev_idx()
521 static void base_remove_entry(HashmapBase *h, unsigned idx) { in base_remove_entry() argument
526 assert(dibs[idx] != DIB_RAW_FREE); in base_remove_entry()
530 h->debug.last_rem_idx = idx; in base_remove_entry()
533 left = idx; in base_remove_entry()
548 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx); in base_remove_entry()
574 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx) argument
578 unsigned idx; in hashmap_iterate_in_insertion_order() local
583 if (i->idx == IDX_NIL) in hashmap_iterate_in_insertion_order()
586 if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL) in hashmap_iterate_in_insertion_order()
589 if (i->idx == IDX_FIRST) { in hashmap_iterate_in_insertion_order()
590 idx = h->iterate_list_head; in hashmap_iterate_in_insertion_order()
591 e = ordered_bucket_at(h, idx); in hashmap_iterate_in_insertion_order()
593 idx = i->idx; in hashmap_iterate_in_insertion_order()
594 e = ordered_bucket_at(h, idx); in hashmap_iterate_in_insertion_order()
602 idx = prev_idx(HASHMAP_BASE(h), idx); in hashmap_iterate_in_insertion_order()
603 e = ordered_bucket_at(h, idx); in hashmap_iterate_in_insertion_order()
609 i->prev_idx = idx; in hashmap_iterate_in_insertion_order()
614 i->idx = e->iterate_next; in hashmap_iterate_in_insertion_order()
615 n = ordered_bucket_at(h, i->idx); in hashmap_iterate_in_insertion_order()
618 i->idx = IDX_NIL; in hashmap_iterate_in_insertion_order()
620 return idx; in hashmap_iterate_in_insertion_order()
623 i->idx = IDX_NIL; in hashmap_iterate_in_insertion_order()
628 unsigned idx; in hashmap_iterate_in_internal_order() local
633 if (i->idx == IDX_NIL) in hashmap_iterate_in_internal_order()
636 if (i->idx == IDX_FIRST) { in hashmap_iterate_in_internal_order()
639 i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry); in hashmap_iterate_in_internal_order()
640 h->indirect.idx_lowest_entry = i->idx; in hashmap_iterate_in_internal_order()
642 i->idx = skip_free_buckets(h, 0); in hashmap_iterate_in_internal_order()
644 if (i->idx == IDX_NIL) in hashmap_iterate_in_internal_order()
649 assert(i->idx > 0); in hashmap_iterate_in_internal_order()
651 e = bucket_at(h, i->idx); in hashmap_iterate_in_internal_order()
659 e = bucket_at(h, --i->idx); in hashmap_iterate_in_internal_order()
664 idx = i->idx; in hashmap_iterate_in_internal_order()
666 i->prev_idx = idx; in hashmap_iterate_in_internal_order()
669 i->idx = skip_free_buckets(h, i->idx + 1); in hashmap_iterate_in_internal_order()
670 if (i->idx != IDX_NIL) in hashmap_iterate_in_internal_order()
671 i->next_key = bucket_at(h, i->idx)->key; in hashmap_iterate_in_internal_order()
673 i->idx = IDX_NIL; in hashmap_iterate_in_internal_order()
675 return idx; in hashmap_iterate_in_internal_order()
678 i->idx = IDX_NIL; in hashmap_iterate_in_internal_order()
684 i->idx = IDX_NIL; in hashmap_iterate_entry()
689 if (i->idx == IDX_FIRST) { in hashmap_iterate_entry()
711 unsigned idx; in _hashmap_iterate() local
713 idx = hashmap_iterate_entry(h, i); in _hashmap_iterate()
714 if (idx == IDX_NIL) { in _hashmap_iterate()
723 e = bucket_at(h, idx); in _hashmap_iterate()
733 #define HASHMAP_FOREACH_IDX(idx, h, i) \ argument
734 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
735 (idx != IDX_NIL); \
736 (idx) = hashmap_iterate_entry((h), &(i)))
951 static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx, in hashmap_put_robin_hood() argument
963 raw_dib = dibs[idx]; in hashmap_put_robin_hood()
966 bucket_move_entry(h, swap, idx, IDX_TMP); in hashmap_put_robin_hood()
968 if (h->has_indirect && h->indirect.idx_lowest_entry > idx) in hashmap_put_robin_hood()
969 h->indirect.idx_lowest_entry = idx; in hashmap_put_robin_hood()
971 bucket_set_dib(h, idx, distance); in hashmap_put_robin_hood()
972 bucket_move_entry(h, swap, IDX_PUT, idx); in hashmap_put_robin_hood()
981 dib = bucket_calculate_dib(h, idx, raw_dib); in hashmap_put_robin_hood()
985 bucket_set_dib(h, idx, distance); in hashmap_put_robin_hood()
988 bucket_move_entry(h, swap, idx, IDX_TMP); in hashmap_put_robin_hood()
989 bucket_move_entry(h, swap, IDX_PUT, idx); in hashmap_put_robin_hood()
995 idx = next_idx(h, idx); in hashmap_put_robin_hood()
1009 static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx, in hashmap_base_put_boldly() argument
1014 assert(idx < n_buckets(h)); in hashmap_base_put_boldly()
1023 idx = bucket_hash(h, new_entry->p.b.key); in hashmap_base_put_boldly()
1046 assert_se(hashmap_put_robin_hood(h, idx, swap) == false); in hashmap_base_put_boldly()
1057 #define hashmap_put_boldly(h, idx, swap, may_resize) \ argument
1058 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1070 unsigned idx, optimal_idx; in resize_buckets() local
1143 for (idx = 0; idx < old_n_buckets; idx++) { in resize_buckets()
1144 assert(old_dibs[idx] != DIB_RAW_REHASH); in resize_buckets()
1145 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE in resize_buckets()
1159 for (idx = 0; idx < old_n_buckets; idx++) { in resize_buckets()
1160 if (new_dibs[idx] != DIB_RAW_REHASH) in resize_buckets()
1163 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key); in resize_buckets()
1169 if (optimal_idx == idx) { in resize_buckets()
1170 new_dibs[idx] = 0; in resize_buckets()
1175 new_dibs[idx] = DIB_RAW_FREE; in resize_buckets()
1176 bucket_move_entry(h, &swap, idx, IDX_PUT); in resize_buckets()
1178 memzero(bucket_at(h, idx), hi->entry_size); in resize_buckets()
1203 static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) { in base_bucket_scan() argument
1208 assert(idx < n_buckets(h)); in base_bucket_scan()
1211 if (dibs[idx] == DIB_RAW_FREE) in base_bucket_scan()
1214 dib = bucket_calculate_dib(h, idx, dibs[idx]); in base_bucket_scan()
1219 e = bucket_at(h, idx); in base_bucket_scan()
1221 return idx; in base_bucket_scan()
1224 idx = next_idx(h, idx); in base_bucket_scan()
1227 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key) argument
1232 unsigned hash, idx; in hashmap_put() local
1237 idx = bucket_scan(h, hash, key); in hashmap_put()
1238 if (idx != IDX_NIL) { in hashmap_put()
1239 e = plain_bucket_at(h, idx); in hashmap_put()
1254 unsigned hash, idx; in set_put() local
1259 idx = bucket_scan(s, hash, key); in set_put()
1260 if (idx != IDX_NIL) in set_put()
1295 unsigned hash, idx; in hashmap_replace() local
1300 idx = bucket_scan(h, hash, key); in hashmap_replace()
1301 if (idx != IDX_NIL) { in hashmap_replace()
1302 e = plain_bucket_at(h, idx); in hashmap_replace()
1310 h->b.debug.last_rem_idx = idx; in hashmap_replace()
1328 unsigned hash, idx; in hashmap_update() local
1333 idx = bucket_scan(h, hash, key); in hashmap_update()
1334 if (idx == IDX_NIL) in hashmap_update()
1337 e = plain_bucket_at(h, idx); in hashmap_update()
1346 unsigned hash, idx; in _hashmap_get() local
1352 idx = bucket_scan(h, hash, key); in _hashmap_get()
1353 if (idx == IDX_NIL) in _hashmap_get()
1356 e = bucket_at(h, idx); in _hashmap_get()
1362 unsigned hash, idx; in hashmap_get2() local
1368 idx = bucket_scan(h, hash, key); in hashmap_get2()
1369 if (idx == IDX_NIL) in hashmap_get2()
1372 e = plain_bucket_at(h, idx); in hashmap_get2()
1391 unsigned hash, idx; in _hashmap_remove() local
1398 idx = bucket_scan(h, hash, key); in _hashmap_remove()
1399 if (idx == IDX_NIL) in _hashmap_remove()
1402 e = bucket_at(h, idx); in _hashmap_remove()
1404 remove_entry(h, idx); in _hashmap_remove()
1411 unsigned hash, idx; in hashmap_remove2() local
1421 idx = bucket_scan(h, hash, key); in hashmap_remove2()
1422 if (idx == IDX_NIL) { in hashmap_remove2()
1428 e = plain_bucket_at(h, idx); in hashmap_remove2()
1433 remove_entry(h, idx); in hashmap_remove2()
1441 unsigned old_hash, new_hash, idx; in hashmap_remove_and_put() local
1447 idx = bucket_scan(h, old_hash, old_key); in hashmap_remove_and_put()
1448 if (idx == IDX_NIL) in hashmap_remove_and_put()
1455 remove_entry(h, idx); in hashmap_remove_and_put()
1468 unsigned old_hash, new_hash, idx; in set_remove_and_put() local
1474 idx = bucket_scan(s, old_hash, old_key); in set_remove_and_put()
1475 if (idx == IDX_NIL) in set_remove_and_put()
1482 remove_entry(s, idx); in set_remove_and_put()
1529 unsigned hash, idx; in _hashmap_remove_value() local
1535 idx = bucket_scan(h, hash, key); in _hashmap_remove_value()
1536 if (idx == IDX_NIL) in _hashmap_remove_value()
1539 e = bucket_at(h, idx); in _hashmap_remove_value()
1543 remove_entry(h, idx); in _hashmap_remove_value()
1560 unsigned idx; in _hashmap_first_key_and_value() local
1562 idx = find_first_entry(h); in _hashmap_first_key_and_value()
1563 if (idx == IDX_NIL) { in _hashmap_first_key_and_value()
1569 e = bucket_at(h, idx); in _hashmap_first_key_and_value()
1574 remove_entry(h, idx); in _hashmap_first_key_and_value()
1598 unsigned idx; in _hashmap_merge() local
1602 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) { in _hashmap_merge()
1603 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx); in _hashmap_merge()
1616 unsigned idx; in set_merge() local
1620 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) { in set_merge()
1621 struct set_entry *se = set_bucket_at(other, idx); in set_merge()
1654 unsigned idx; in _hashmap_move() local
1674 HASHMAP_FOREACH_IDX(idx, other, i) { in _hashmap_move()
1677 e = bucket_at(other, idx); in _hashmap_move()
1689 remove_entry(other, idx); in _hashmap_move()
1697 unsigned h_hash, other_hash, idx; in _hashmap_move_one() local
1713 idx = bucket_scan(other, other_hash, key); in _hashmap_move_one()
1714 if (idx == IDX_NIL) in _hashmap_move_one()
1717 e = bucket_at(other, idx); in _hashmap_move_one()
1728 remove_entry(other, idx); in _hashmap_move_one()
1763 unsigned idx, n; in _hashmap_get_strv() local
1773 HASHMAP_FOREACH_IDX(idx, h, i) in _hashmap_get_strv()
1774 sv[n++] = entry_value(h, bucket_at(h, idx)); in _hashmap_get_strv()
1782 unsigned hash, idx; in ordered_hashmap_next() local
1788 idx = bucket_scan(h, hash, key); in ordered_hashmap_next()
1789 if (idx == IDX_NIL) in ordered_hashmap_next()
1792 e = ordered_bucket_at(h, idx); in ordered_hashmap_next()
1957 unsigned i, idx; in iterated_cache_get() local
1961 HASHMAP_FOREACH_IDX(idx, cache->hashmap, iter) { in iterated_cache_get()
1964 e = bucket_at(cache->hashmap, idx); in iterated_cache_get()