rehash_inline_no_resize()

template<typename Key, typename T, typename Hash = Hash<Key>, typename KeyEqual = EqualTo<Key>, int INLINED_COUNT = FASTLED_HASHMAP_INLINED_COUNT>

FL_DISABLE_WARNING_PUSH FL_DISABLE_WARNING_NULL_DEREFERENCE void fl::unordered_map< Key, T, Hash, KeyEqual, INLINED_COUNT >::rehash_inline_no_resize ( )

inlineprivate

Definition at line 939 of file unordered_map.h.

                                                {
        // filter out tombstones and compact
        fl::size cap = _buckets.size();
        fl::size pos = 0;
        // compact live elements to the left.
        for (fl::size i = 0; i < cap; ++i) {
            if (is_occupied(i)) {
                if (pos != i) {
                    _buckets[pos] = fl::move(_buckets[i]);
                    mark_empty(i);
                    mark_occupied(pos);
                }
                ++pos;
            } else if (is_deleted(i)) {
                mark_empty(i);
            }
        }
 
        fl::bitset<1024> occupied; // Preallocate a bitset of size 1024
        // swap the components, this will happen at most N times,
        // use the occupied bitset to track which entries are occupied
        // in the array rather than just copied in.
        fl::optional<Entry> tmp;
        for (fl::size i = 0; i < _size; ++i) {
            const bool already_finished = occupied.test(i);
            if (already_finished) {
                continue;
            }
            auto &e = _buckets[i];
            // FASTLED_ASSERT(e.state == EntryState::Occupied,
            //                "unordered_map::rehash_inline_no_resize: invalid
            //                state");
 
            fl::size idx = find_unoccupied_index_using_bitset(e.key, occupied);
            if (idx == npos()) {
                // no more space
                FASTLED_ASSERT(
                    false, "unordered_map::rehash_inline_no_resize: invalid index");
                return;
            }
            // if idx < pos then we are moving the entry to a new location
            FASTLED_ASSERT(!tmp,
                           "unordered_map::rehash_inline_no_resize: invalid tmp");
            if (idx >= _size) {
                // directly move it now
                _buckets[idx] = fl::move(e);
                continue;
            }
            tmp = fl::move(e);
            occupied.set(idx);
            _buckets[idx] = fl::move(*tmp.ptr());
            while (!tmp.empty()) {
                // we have to find a place for temp.
                // find new position for tmp.
                auto key = tmp.ptr()->key;
                fl::size new_idx =
                    find_unoccupied_index_using_bitset(key, occupied);
                if (new_idx == npos()) {
                    // no more space
                    FASTLED_ASSERT(
                        false,
                        "unordered_map::rehash_inline_no_resize: invalid index");
                    return;
                }
                occupied.set(new_idx);
                if (new_idx < _size) {
                    // we have to swap the entry at new_idx with tmp
                    fl::optional<Entry> tmp2 = fl::move(_buckets[new_idx]);
                    _buckets[new_idx] = fl::move(*tmp.ptr());
                    tmp = fl::move(tmp2);
                } else {
                    // we can just move tmp to new_idx
                    _buckets[new_idx] = fl::move(*tmp.ptr());
                    tmp.reset();
                }
            }
            FASTLED_ASSERT(
                occupied.test(i),
                "unordered_map::rehash_inline_no_resize: invalid occupied");
            FASTLED_ASSERT(
                tmp.empty(), "unordered_map::rehash_inline_no_resize: invalid tmp");
        }
        // Reset tombstones count since we've cleared all deleted entries
        _tombstones = 0;
    }