Repository: microsoft/terminal
File: src/inc/til/flat_set.h (C/C++)

Code before:
        }

        size_t load() const noexcept
        {
            return _load;
        }

        size_t size() const noexcept
        {
            return _load / LoadFactor;
        }

        template<typename U>
        std::pair<T&, bool> insert(U&& key)
        {
            // Putting this into the lookup path is a little pessimistic, but it
            // allows us to default-construct this hashmap with a size of 0.
            if (_load >= _capacity) [[unlikely]]
            {
                _bumpSize();
            }

            // The most common, basic and performant hash function is to multiply the value
            // by some prime number and divide by the number of slots. It's been shown
            // many times in literature that such a scheme performs the best on average.
            // As such, we perform the divide her to get the topmost bits down.
            // See flat_set_hash_integer.
            const auto hash = Trait::hash(key) >> _shift;

            for (auto i = hash;; ++i)
            {
                auto& slot = _map[i & _mask];
                if (Trait::empty(slot))
                {
                    Trait::fill(slot, std::forward<U>(key));
                    _load += LoadFactor;
                    return { slot, true };
                }
                if (Trait::equals(slot, key)) [[likely]]
                {
                    return { slot, false };
                }
            }
        }

        void clear() noexcept
        {
            Trait::clear(_map.get(), _capacity);
            _load = 0;
        }


Review comment (suggestion):
```suggestion
            // As such, we perform the divide here to get the topmost bits down.
```

Code after:
            {
                throw std::bad_array_new_length{};
            }

            const auto newShift = _shift - 1;
            const auto newCapacity = size_t{ 1 } << (digits - newShift);
            const auto newMask = newCapacity - 1;
            auto newMap = std::make_unique<T[]>(newCapacity);

            // This mirrors the insert() function, but without the lookup part.
            for (auto& oldSlot : container())
            {
                if (!oldSlot)
                {
                    continue;
                }

                const auto hash = ::std::hash<T>{}(oldSlot) >> newShift;

                for (auto i = hash;; ++i)
                {
                    auto& slot = newMap[i & newMask];
                    if (!slot)
                    {
                        slot = std::move_if_noexcept(oldSlot);
                        break;
                    }
                }
            }

            _map = std::move(newMap);
            _capacity = newCapacity;
            _shift = newShift;
            _mask = newMask;
        }

        static constexpr auto digits = std::numeric_limits<size_t>::digits;

        std::unique_ptr<T[]> _map;
        size_t _capacity = 0;
        size_t _load = 0;
        // This results in an initial capacity of 8 items, independent of the LoadFactor.
        size_t _shift = digits - LoadFactor - 1;
        size_t _mask = 0;
    };
}

#pragma warning(pop)