rehash_inline_no_resize()

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

void fl::HashMap< Key, T, Hash, KeyEqual, INLINED_COUNT >::rehash_inline_no_resize ( )

inlineprivate

Definition at line 490 of file hash_map.h.

                                   {
        // filter out tombstones and compact
        size_t cap = _buckets.size();
        size_t pos = 0;
        // compact live elements to the left.
        for (size_t i = 0; i < cap; ++i) {
            if (is_occupied(i)) {
                if (pos != i) {
                    _buckets[pos] = _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 (size_t 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,
            //                "HashMap::rehash_inline_no_resize: invalid
            //                state");
 
            size_t idx = find_unoccupied_index_using_bitset(e.key, occupied);
            if (idx == npos) {
                // no more space
                FASTLED_ASSERT(
                    false, "HashMap::rehash_inline_no_resize: invalid index at "
                               << idx << " which is " << npos);
                return;
            }
            // if idx < pos then we are moving the entry to a new location
            FASTLED_ASSERT(!tmp,
                           "HashMap::rehash_inline_no_resize: invalid tmp");
            if (idx >= _size) {
                // directly copy it now
                _buckets[idx] = e;
                continue;
            }
            tmp = e;
            occupied.set(idx);
            _buckets[idx] = *tmp.ptr();
            while (!tmp.empty()) {
                // we have to find a place for temp.
                // find new position for tmp.
                auto key = tmp.ptr()->key;
                size_t new_idx =
                    find_unoccupied_index_using_bitset(key, occupied);
                if (new_idx == npos) {
                    // no more space
                    FASTLED_ASSERT(
                        false,
                        "HashMap::rehash_inline_no_resize: invalid index at "
                            << new_idx << " which is " << npos);
                    return;
                }
                occupied.set(new_idx);
                if (new_idx < _size) {
                    // we have to swap the entry at new_idx with tmp
                    optional<Entry> tmp2 = _buckets[new_idx];
                    _buckets[new_idx] = *tmp.ptr();
                    tmp = tmp2;
                } else {
                    // we can just move tmp to new_idx
                    _buckets[new_idx] = *tmp.ptr();
                    tmp.reset();
                }
            }
            FASTLED_ASSERT(
                occupied.test(i),
                "HashMap::rehash_inline_no_resize: invalid occupied at " << i);
            FASTLED_ASSERT(
                !tmp, "HashMap::rehash_inline_no_resize: invalid tmp at " << i);
        }
    }

Referenced by fl::HashMap< Key, T, Hash, KeyEqual >::insert().

Here is the caller graph for this function: