Lines Matching refs:idx
402 static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
404 (storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
407 static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
408 return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
411 static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
412 return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
415 static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
416 return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
419 static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
420 return &swap->e[idx - _IDX_SWAP_BEGIN];
423 /* Returns a pointer to the bucket at index idx.
426 unsigned idx) {
427 if (idx < _IDX_SWAP_BEGIN)
428 return bucket_at(h, idx);
430 if (idx < _IDX_SWAP_END)
431 return &bucket_at_swap(swap, idx)->p.b;
441 static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
442 return idx >= from ? idx - from
443 : n_buckets(h) + idx - from;
446 static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
465 initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
466 return bucket_distance(h, idx, initial_bucket);
469 static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
470 dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
473 static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
478 for ( ; idx < n_buckets(h); idx++)
479 if (dibs[idx] != DIB_RAW_FREE)
480 return idx;
485 static void bucket_mark_free(HashmapBase *h, unsigned idx) {
486 memset(bucket_at(h, idx), 0, hashmap_type_info[h->type].entry_size);
487 bucket_set_dib(h, idx, DIB_FREE);
526 static unsigned next_idx(HashmapBase *h, unsigned idx) {
527 return (idx + 1U) % n_buckets(h);
530 static unsigned prev_idx(HashmapBase *h, unsigned idx) {
531 return (n_buckets(h) + idx - 1U) % n_buckets(h);
549 static void base_remove_entry(HashmapBase *h, unsigned idx) {
554 assert(dibs[idx] != DIB_RAW_FREE);
558 h->debug.last_rem_idx = idx;
561 left = idx;
576 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
601 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
605 unsigned idx;
610 if (i->idx == IDX_NIL)
613 if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
616 if (i->idx == IDX_FIRST) {
617 idx = h->iterate_list_head;
618 e = ordered_bucket_at(h, idx);
620 idx = i->idx;
621 e = ordered_bucket_at(h, idx);
629 idx = prev_idx(HASHMAP_BASE(h), idx);
630 e = ordered_bucket_at(h, idx);
636 i->prev_idx = idx;
641 i->idx = e->iterate_next;
642 n = ordered_bucket_at(h, i->idx);
645 i->idx = IDX_NIL;
647 return idx;
650 i->idx = IDX_NIL;
655 unsigned idx;
660 if (i->idx == IDX_NIL)
663 if (i->idx == IDX_FIRST) {
666 i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
667 h->indirect.idx_lowest_entry = i->idx;
669 i->idx = skip_free_buckets(h, 0);
671 if (i->idx == IDX_NIL)
676 assert(i->idx > 0);
678 e = bucket_at(h, i->idx);
686 e = bucket_at(h, --i->idx);
691 idx = i->idx;
693 i->prev_idx = idx;
696 i->idx = skip_free_buckets(h, i->idx + 1);
697 if (i->idx != IDX_NIL)
698 i->next_key = bucket_at(h, i->idx)->key;
700 i->idx = IDX_NIL;
702 return idx;
705 i->idx = IDX_NIL;
711 i->idx = IDX_NIL;
716 if (i->idx == IDX_FIRST) {
738 unsigned idx;
740 idx = hashmap_iterate_entry(h, i);
741 if (idx == IDX_NIL) {
748 e = bucket_at(h, idx);
760 #define HASHMAP_FOREACH_IDX(idx, h, i) \
761 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
762 (idx != IDX_NIL); \
763 (idx) = hashmap_iterate_entry((h), &(i)))
924 unsigned idx;
929 for (idx = skip_free_buckets(h, 0); idx != IDX_NIL;
930 idx = skip_free_buckets(h, idx + 1))
931 free(entry_value(h, bucket_at(h, idx)));
937 unsigned idx;
942 for (idx = skip_free_buckets(HASHMAP_BASE(h), 0); idx != IDX_NIL;
943 idx = skip_free_buckets(HASHMAP_BASE(h), idx + 1)) {
944 struct plain_hashmap_entry *e = plain_bucket_at(h, idx);
955 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
963 static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
975 raw_dib = dibs[idx];
978 bucket_move_entry(h, swap, idx, IDX_TMP);
980 if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
981 h->indirect.idx_lowest_entry = idx;
983 bucket_set_dib(h, idx, distance);
984 bucket_move_entry(h, swap, IDX_PUT, idx);
993 dib = bucket_calculate_dib(h, idx, raw_dib);
997 bucket_set_dib(h, idx, distance);
1000 bucket_move_entry(h, swap, idx, IDX_TMP);
1001 bucket_move_entry(h, swap, IDX_PUT, idx);
1007 idx = next_idx(h, idx);
1021 static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
1026 assert(idx < n_buckets(h));
1035 idx = bucket_hash(h, new_entry->p.b.key);
1058 assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1067 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1068 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1080 unsigned idx, optimal_idx;
1153 for (idx = 0; idx < old_n_buckets; idx++) {
1154 assert(old_dibs[idx] != DIB_RAW_REHASH);
1155 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1169 for (idx = 0; idx < old_n_buckets; idx++) {
1170 if (new_dibs[idx] != DIB_RAW_REHASH)
1173 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1179 if (optimal_idx == idx) {
1180 new_dibs[idx] = 0;
1185 new_dibs[idx] = DIB_RAW_FREE;
1186 bucket_move_entry(h, &swap, idx, IDX_PUT);
1188 memset(bucket_at(h, idx), 0, hi->entry_size);
1213 static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1218 assert(idx < n_buckets(h));
1221 if (dibs[idx] == DIB_RAW_FREE)
1224 dib = bucket_calculate_dib(h, idx, dibs[idx]);
1229 e = bucket_at(h, idx);
1231 return idx;
1234 idx = next_idx(h, idx);
1237 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1242 unsigned hash, idx;
1247 idx = bucket_scan(h, hash, key);
1248 if (idx != IDX_NIL) {
1249 e = plain_bucket_at(h, idx);
1264 unsigned hash, idx;
1269 idx = bucket_scan(s, hash, key);
1270 if (idx != IDX_NIL)
1281 unsigned hash, idx;
1286 idx = bucket_scan(h, hash, key);
1287 if (idx != IDX_NIL) {
1288 e = plain_bucket_at(h, idx);
1296 h->b.debug.last_rem_idx = idx;
1312 unsigned hash, idx;
1317 idx = bucket_scan(h, hash, key);
1318 if (idx == IDX_NIL)
1321 e = plain_bucket_at(h, idx);
1328 unsigned hash, idx;
1334 idx = bucket_scan(h, hash, key);
1335 if (idx == IDX_NIL)
1338 e = bucket_at(h, idx);
1344 unsigned hash, idx;
1350 idx = bucket_scan(h, hash, key);
1351 if (idx == IDX_NIL)
1354 e = plain_bucket_at(h, idx);
1373 unsigned hash, idx;
1380 idx = bucket_scan(h, hash, key);
1381 if (idx == IDX_NIL)
1384 e = bucket_at(h, idx);
1386 remove_entry(h, idx);
1393 unsigned hash, idx;
1403 idx = bucket_scan(h, hash, key);
1404 if (idx == IDX_NIL) {
1410 e = plain_bucket_at(h, idx);
1415 remove_entry(h, idx);
1423 unsigned old_hash, new_hash, idx;
1429 idx = bucket_scan(h, old_hash, old_key);
1430 if (idx == IDX_NIL)
1437 remove_entry(h, idx);
1450 unsigned old_hash, new_hash, idx;
1456 idx = bucket_scan(s, old_hash, old_key);
1457 if (idx == IDX_NIL)
1464 remove_entry(s, idx);
1511 unsigned hash, idx;
1517 idx = bucket_scan(h, hash, key);
1518 if (idx == IDX_NIL)
1521 e = plain_bucket_at(h, idx);
1525 remove_entry(h, idx);
1540 unsigned idx;
1542 idx = find_first_entry(h);
1543 if (idx == IDX_NIL)
1546 return entry_value(h, bucket_at(h, idx));
1551 unsigned idx;
1553 idx = find_first_entry(h);
1554 if (idx == IDX_NIL)
1557 e = bucket_at(h, idx);
1564 unsigned idx;
1566 idx = find_first_entry(h);
1567 if (idx == IDX_NIL)
1570 e = bucket_at(h, idx);
1572 remove_entry(h, idx);
1580 unsigned idx;
1582 idx = find_first_entry(h);
1583 if (idx == IDX_NIL)
1586 e = bucket_at(h, idx);
1588 remove_entry(h, idx);
1611 unsigned idx;
1615 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1616 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1629 unsigned idx;
1633 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1634 struct set_entry *se = set_bucket_at(other, idx);
1667 unsigned idx;
1687 HASHMAP_FOREACH_IDX(idx, other, i) {
1690 e = bucket_at(other, idx);
1702 remove_entry(other, idx);
1710 unsigned h_hash, other_hash, idx;
1726 idx = bucket_scan(other, other_hash, key);
1727 if (idx == IDX_NIL)
1730 e = bucket_at(other, idx);
1741 remove_entry(other, idx);
1778 unsigned idx, n;
1785 HASHMAP_FOREACH_IDX(idx, h, i)
1786 sv[n++] = entry_value(h, bucket_at(h, idx));
1794 unsigned hash, idx;
1802 idx = bucket_scan(h, hash, key);
1803 if (idx == IDX_NIL)
1806 e = ordered_bucket_at(h, idx);