Lines Matching defs:idx
348 static struct hashmap_base_entry *bucket_at(HashmapBase *h, unsigned idx) {
350 (storage_ptr(h) + idx * hashmap_type_info[h->type].entry_size);
353 static struct plain_hashmap_entry *plain_bucket_at(Hashmap *h, unsigned idx) {
354 return (struct plain_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
357 static struct ordered_hashmap_entry *ordered_bucket_at(OrderedHashmap *h, unsigned idx) {
358 return (struct ordered_hashmap_entry*) bucket_at(HASHMAP_BASE(h), idx);
361 static struct set_entry *set_bucket_at(Set *h, unsigned idx) {
362 return (struct set_entry*) bucket_at(HASHMAP_BASE(h), idx);
365 static struct ordered_hashmap_entry *bucket_at_swap(struct swap_entries *swap, unsigned idx) {
366 return &swap->e[idx - _IDX_SWAP_BEGIN];
369 /* Returns a pointer to the bucket at index idx.
372 unsigned idx) {
373 if (idx < _IDX_SWAP_BEGIN)
374 return bucket_at(h, idx);
376 if (idx < _IDX_SWAP_END)
377 return &bucket_at_swap(swap, idx)->p.b;
387 static unsigned bucket_distance(HashmapBase *h, unsigned idx, unsigned from) {
388 return idx >= from ? idx - from
389 : n_buckets(h) + idx - from;
392 static unsigned bucket_calculate_dib(HashmapBase *h, unsigned idx, dib_raw_t raw_dib) {
411 initial_bucket = bucket_hash(h, bucket_at(h, idx)->key);
412 return bucket_distance(h, idx, initial_bucket);
415 static void bucket_set_dib(HashmapBase *h, unsigned idx, unsigned dib) {
416 dib_raw_ptr(h)[idx] = dib != DIB_FREE ? MIN(dib, DIB_RAW_OVERFLOW) : DIB_RAW_FREE;
419 static unsigned skip_free_buckets(HashmapBase *h, unsigned idx) {
424 for ( ; idx < n_buckets(h); idx++)
425 if (dibs[idx] != DIB_RAW_FREE)
426 return idx;
431 static void bucket_mark_free(HashmapBase *h, unsigned idx) {
432 memzero(bucket_at(h, idx), hashmap_type_info[h->type].entry_size);
433 bucket_set_dib(h, idx, DIB_FREE);
472 static unsigned next_idx(HashmapBase *h, unsigned idx) {
473 return (idx + 1U) % n_buckets(h);
476 static unsigned prev_idx(HashmapBase *h, unsigned idx) {
477 return (n_buckets(h) + idx - 1U) % n_buckets(h);
495 static void base_remove_entry(HashmapBase *h, unsigned idx) {
500 assert(dibs[idx] != DIB_RAW_FREE);
504 h->debug.last_rem_idx = idx;
507 left = idx;
522 struct ordered_hashmap_entry *le = ordered_bucket_at(lh, idx);
547 #define remove_entry(h, idx) base_remove_entry(HASHMAP_BASE(h), idx)
551 unsigned idx;
556 if (i->idx == IDX_NIL)
559 if (i->idx == IDX_FIRST && h->iterate_list_head == IDX_NIL)
562 if (i->idx == IDX_FIRST) {
563 idx = h->iterate_list_head;
564 e = ordered_bucket_at(h, idx);
566 idx = i->idx;
567 e = ordered_bucket_at(h, idx);
575 idx = prev_idx(HASHMAP_BASE(h), idx);
576 e = ordered_bucket_at(h, idx);
582 i->prev_idx = idx;
587 i->idx = e->iterate_next;
588 n = ordered_bucket_at(h, i->idx);
591 i->idx = IDX_NIL;
593 return idx;
596 i->idx = IDX_NIL;
601 unsigned idx;
606 if (i->idx == IDX_NIL)
609 if (i->idx == IDX_FIRST) {
612 i->idx = skip_free_buckets(h, h->indirect.idx_lowest_entry);
613 h->indirect.idx_lowest_entry = i->idx;
615 i->idx = skip_free_buckets(h, 0);
617 if (i->idx == IDX_NIL)
622 assert(i->idx > 0);
624 e = bucket_at(h, i->idx);
632 e = bucket_at(h, --i->idx);
637 idx = i->idx;
639 i->prev_idx = idx;
642 i->idx = skip_free_buckets(h, i->idx + 1);
643 if (i->idx != IDX_NIL)
644 i->next_key = bucket_at(h, i->idx)->key;
646 i->idx = IDX_NIL;
648 return idx;
651 i->idx = IDX_NIL;
657 i->idx = IDX_NIL;
662 if (i->idx == IDX_FIRST) {
684 unsigned idx;
686 idx = hashmap_iterate_entry(h, i);
687 if (idx == IDX_NIL) {
696 e = bucket_at(h, idx);
710 #define HASHMAP_FOREACH_IDX(idx, h, i) \
711 for ((i) = ITERATOR_FIRST, (idx) = hashmap_iterate_entry((h), &(i)); \
712 (idx != IDX_NIL); \
713 (idx) = hashmap_iterate_entry((h), &(i)))
878 unsigned idx;
883 for (idx = skip_free_buckets(h, 0); idx != IDX_NIL;
884 idx = skip_free_buckets(h, idx + 1))
885 free(entry_value(h, bucket_at(h, idx)));
891 unsigned idx;
896 for (idx = skip_free_buckets(HASHMAP_BASE(h), 0); idx != IDX_NIL;
897 idx = skip_free_buckets(HASHMAP_BASE(h), idx + 1)) {
898 struct plain_hashmap_entry *e = plain_bucket_at(h, idx);
909 * Finds an empty bucket to put an entry into, starting the scan at 'idx'.
917 static bool hashmap_put_robin_hood(HashmapBase *h, unsigned idx,
929 raw_dib = dibs[idx];
932 bucket_move_entry(h, swap, idx, IDX_TMP);
934 if (h->has_indirect && h->indirect.idx_lowest_entry > idx)
935 h->indirect.idx_lowest_entry = idx;
937 bucket_set_dib(h, idx, distance);
938 bucket_move_entry(h, swap, IDX_PUT, idx);
947 dib = bucket_calculate_dib(h, idx, raw_dib);
951 bucket_set_dib(h, idx, distance);
954 bucket_move_entry(h, swap, idx, IDX_TMP);
955 bucket_move_entry(h, swap, IDX_PUT, idx);
961 idx = next_idx(h, idx);
975 static int hashmap_base_put_boldly(HashmapBase *h, unsigned idx,
980 assert(idx < n_buckets(h));
989 idx = bucket_hash(h, new_entry->p.b.key);
1012 assert_se(hashmap_put_robin_hood(h, idx, swap) == false);
1021 #define hashmap_put_boldly(h, idx, swap, may_resize) \
1022 hashmap_base_put_boldly(HASHMAP_BASE(h), idx, swap, may_resize)
1034 unsigned idx, optimal_idx;
1107 for (idx = 0; idx < old_n_buckets; idx++) {
1108 assert(old_dibs[idx] != DIB_RAW_REHASH);
1109 new_dibs[idx] = old_dibs[idx] == DIB_RAW_FREE ? DIB_RAW_FREE
1123 for (idx = 0; idx < old_n_buckets; idx++) {
1124 if (new_dibs[idx] != DIB_RAW_REHASH)
1127 optimal_idx = bucket_hash(h, bucket_at(h, idx)->key);
1133 if (optimal_idx == idx) {
1134 new_dibs[idx] = 0;
1139 new_dibs[idx] = DIB_RAW_FREE;
1140 bucket_move_entry(h, &swap, idx, IDX_PUT);
1142 memzero(bucket_at(h, idx), hi->entry_size);
1167 static unsigned base_bucket_scan(HashmapBase *h, unsigned idx, const void *key) {
1172 assert(idx < n_buckets(h));
1175 if (dibs[idx] == DIB_RAW_FREE)
1178 dib = bucket_calculate_dib(h, idx, dibs[idx]);
1183 e = bucket_at(h, idx);
1185 return idx;
1188 idx = next_idx(h, idx);
1191 #define bucket_scan(h, idx, key) base_bucket_scan(HASHMAP_BASE(h), idx, key)
1196 unsigned hash, idx;
1201 idx = bucket_scan(h, hash, key);
1202 if (idx != IDX_NIL) {
1203 e = plain_bucket_at(h, idx);
1218 unsigned hash, idx;
1223 idx = bucket_scan(s, hash, key);
1224 if (idx != IDX_NIL)
1235 unsigned hash, idx;
1240 idx = bucket_scan(h, hash, key);
1241 if (idx != IDX_NIL) {
1242 e = plain_bucket_at(h, idx);
1250 h->b.debug.last_rem_idx = idx;
1266 unsigned hash, idx;
1271 idx = bucket_scan(h, hash, key);
1272 if (idx == IDX_NIL)
1275 e = plain_bucket_at(h, idx);
1282 unsigned hash, idx;
1288 idx = bucket_scan(h, hash, key);
1289 if (idx == IDX_NIL)
1292 e = bucket_at(h, idx);
1298 unsigned hash, idx;
1304 idx = bucket_scan(h, hash, key);
1305 if (idx == IDX_NIL)
1308 e = plain_bucket_at(h, idx);
1327 unsigned hash, idx;
1334 idx = bucket_scan(h, hash, key);
1335 if (idx == IDX_NIL)
1338 e = bucket_at(h, idx);
1340 remove_entry(h, idx);
1347 unsigned hash, idx;
1357 idx = bucket_scan(h, hash, key);
1358 if (idx == IDX_NIL) {
1364 e = plain_bucket_at(h, idx);
1369 remove_entry(h, idx);
1377 unsigned old_hash, new_hash, idx;
1383 idx = bucket_scan(h, old_hash, old_key);
1384 if (idx == IDX_NIL)
1391 remove_entry(h, idx);
1404 unsigned old_hash, new_hash, idx;
1410 idx = bucket_scan(s, old_hash, old_key);
1411 if (idx == IDX_NIL)
1418 remove_entry(s, idx);
1465 unsigned hash, idx;
1471 idx = bucket_scan(h, hash, key);
1472 if (idx == IDX_NIL)
1475 e = plain_bucket_at(h, idx);
1479 remove_entry(h, idx);
1494 unsigned idx;
1496 idx = find_first_entry(h);
1497 if (idx == IDX_NIL)
1500 return entry_value(h, bucket_at(h, idx));
1505 unsigned idx;
1507 idx = find_first_entry(h);
1508 if (idx == IDX_NIL)
1511 e = bucket_at(h, idx);
1518 unsigned idx;
1520 idx = find_first_entry(h);
1521 if (idx == IDX_NIL)
1524 e = bucket_at(h, idx);
1526 remove_entry(h, idx);
1534 unsigned idx;
1536 idx = find_first_entry(h);
1537 if (idx == IDX_NIL)
1540 e = bucket_at(h, idx);
1542 remove_entry(h, idx);
1565 unsigned idx;
1569 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1570 struct plain_hashmap_entry *pe = plain_bucket_at(other, idx);
1583 unsigned idx;
1587 HASHMAP_FOREACH_IDX(idx, HASHMAP_BASE(other), i) {
1588 struct set_entry *se = set_bucket_at(other, idx);
1621 unsigned idx;
1641 HASHMAP_FOREACH_IDX(idx, other, i) {
1644 e = bucket_at(other, idx);
1656 remove_entry(other, idx);
1664 unsigned h_hash, other_hash, idx;
1680 idx = bucket_scan(other, other_hash, key);
1681 if (idx == IDX_NIL)
1684 e = bucket_at(other, idx);
1695 remove_entry(other, idx);
1732 unsigned idx, n;
1739 HASHMAP_FOREACH_IDX(idx, h, i)
1740 sv[n++] = entry_value(h, bucket_at(h, idx));
1748 unsigned hash, idx;
1754 idx = bucket_scan(h, hash, key);
1755 if (idx == IDX_NIL)
1758 e = ordered_bucket_at(h, idx);