order_index.hpp

Go to the documentation of this file.

#pragma once
 
 
#include <cstddef>
#include <cstdint>
#include <vector>
 
namespace itch::book {
 
class OrderIndex {
   public:
    static constexpr std::uint32_t NPOS = 0xFFFFFFFFU;
 
    OrderIndex() { rehash(INITIAL_CAPACITY); }
 
    [[nodiscard]] auto size() const noexcept -> std::size_t { return m_count; }
 
    [[nodiscard]] auto empty() const noexcept -> bool { return m_count == 0; }
 
    [[nodiscard]] auto find(std::uint64_t key) const noexcept -> std::uint32_t {
        std::size_t slot = hash(key) & m_mask;
        while (m_slots[slot].used) {
            if (m_slots[slot].key == key) {
                return m_slots[slot].value;
            }
            slot = (slot + 1) & m_mask;
        }
        return NPOS;
    }
 
    [[nodiscard]] auto contains(std::uint64_t key) const noexcept -> bool {
        return find(key) != NPOS;
    }
 
    auto insert(std::uint64_t key, std::uint32_t value) -> void {
        if ((m_count + 1) * LOAD_FACTOR_DEN >= m_slots.size() * LOAD_FACTOR_NUM) {
            rehash(m_slots.size() * 2);
        }
        std::size_t slot = hash(key) & m_mask;
        while (m_slots[slot].used) {
            if (m_slots[slot].key == key) {
                m_slots[slot].value = value;
                return;
            }
            slot = (slot + 1) & m_mask;
        }
        m_slots[slot] = Slot {key, value, true};
        ++m_count;
    }
 
    auto erase(std::uint64_t key) -> void {
        std::size_t slot = hash(key) & m_mask;
        while (m_slots[slot].used) {
            if (m_slots[slot].key == key) {
                remove_at(slot);
                return;
            }
            slot = (slot + 1) & m_mask;
        }
    }
 
    auto clear() -> void {
        for (auto& slot : m_slots) {
            slot.used = false;
        }
        m_count = 0;
    }
 
   private:
    struct Slot {
        std::uint64_t key {0};
        std::uint32_t value {0};
        bool          used {false};
    };
 
    static constexpr std::size_t INITIAL_CAPACITY = 1024;
    static constexpr std::size_t LOAD_FACTOR_NUM  = 7;  // Grow past 70% load.
    static constexpr std::size_t LOAD_FACTOR_DEN  = 10;
 
    [[nodiscard]] static auto hash(std::uint64_t key) noexcept -> std::size_t {
        key ^= key >> 33;
        key *= 0xFF51AFD7ED558CCDULL;
        key ^= key >> 33;
        key *= 0xC4CEB9FE1A85EC53ULL;
        key ^= key >> 33;
        return static_cast<std::size_t>(key);
    }
 
    auto remove_at(std::size_t hole) -> void {
        m_slots[hole].used = false;
        --m_count;
        std::size_t next = (hole + 1) & m_mask;
        while (m_slots[next].used) {
            const std::size_t home = hash(m_slots[next].key) & m_mask;
            // Move the entry into the hole if its home position is not within the
            // cyclic interval (hole, next], i.e. the hole sits between its home
            // and its current slot.
            const bool movable =
                (hole <= next) ? (home <= hole || home > next) : (home <= hole && home > next);
            if (movable) {
                m_slots[hole]      = m_slots[next];
                m_slots[next].used = false;
                hole               = next;
            }
            next = (next + 1) & m_mask;
        }
    }
 
    auto rehash(std::size_t new_capacity) -> void {
        std::vector<Slot> old = std::move(m_slots);
        m_slots.assign(new_capacity, Slot {});
        m_mask  = new_capacity - 1;
        m_count = 0;
        for (const auto& slot : old) {
            if (slot.used) {
                insert(slot.key, slot.value);
            }
        }
    }
 
    std::vector<Slot> m_slots;
    std::size_t       m_count {0};
    std::size_t       m_mask {0};
};
 
}  // namespace itch::book