slotmap.hpp

// FEAT3: Finite Element Analysis Toolbox, Version 3
// Copyright (C) 2010 by Stefan Turek & the FEAT group
// FEAT3 is released under the GNU General Public License version 3,
// see the file 'copyright.txt' in the top level directory for details.
 
#pragma once
 
// includes, system
#include <algorithm>
#include <optional>
#include <vector>
 
// includes, feat
#include <kernel/util/assertion.hpp>
 
namespace FEAT::Util
{
  struct SlotMapKey
  {
    SlotMapKey() : index(0), generation(0)
    {
    }
    SlotMapKey(std::uint32_t i, std::uint32_t g) : index(i), generation(g)
    {
    }
 
    std::uint32_t index;
    std::uint32_t generation;
  };
 
  template<typename V, typename Key = SlotMapKey>
  struct KeyValuePair
  {
    KeyValuePair(V& v, Key k) : value(v), key(k)
    {
    }
 
    V& value;
    Key key;
  };
 
  template<typename V, typename Key = SlotMapKey>
  struct ConstKeyValuePair
  {
    ConstKeyValuePair(const V& v, Key k) : value(v), key(k)
    {
    }
 
    const V& value;
    Key key;
  };
 
  template<typename V, typename Key = SlotMapKey>
  class SlotMap
  {
  public:
    using ValueType = V;
    using KeyType = Key;
 
    SlotMap() : freelist{0, 0}
    {
      // Create initial slot, so that freelist is always valid
      _slots.emplace_back(Slot());
    }
 
    Key insert(V&& value)
    {
      std::uint32_t idx = freelist.head;
 
      // Adjust freelist
      if(idx == freelist.tail)
      {
        // Used up the last Slot. Push a new one to keep freelist valid
        _slots.push_back(Slot());
        freelist.head = freelist.tail = (std::uint32_t)_slots.size() - 1;
      }
      else
      {
        // Move head to next element of freelist
        freelist.head = _slots[idx].index;
      }
 
      Slot& slot = _slots[idx];
 
      // Point slot to new data
      slot.index = (std::uint32_t)_data.size();
 
      // Push new data
      _data.push_back(std::move(value));
 
      // Update erase list
      // Slot for new data is _slots[idx]
      _erase.push_back(idx);
 
      return Key(idx, slot.generation);
    }
 
    Key insert(const V& value)
    {
      std::uint32_t idx = freelist.head;
 
      if(idx == freelist.tail)
      {
        // Used up the last Slot. Push a new one to keep freelist valid
        _slots.push_back(Slot());
        freelist.head = freelist.tail = (std::uint32_t)_slots.size() - 1;
      }
      else
      {
        // Move head to next element of freelist
        freelist.head = _slots[idx].index;
      }
 
      Slot& slot = _slots[idx];
 
      // Point slot to new data
      slot.index = static_cast<std::uint32_t>(_data.size());
 
      // Push new data
      _data.push_back(value);
 
      // Update erase list
      // Slot for new data is _slots[idx]
      _erase.push_back(idx);
 
      return Key(idx, slot.generation);
    }
 
    void erase(const Key& key)
    {
      if(!contains_key(key))
      {
        return;
      }
      // Retrieve Slot for key
      Slot& slot = try_get_slot(key);
 
      // Increment the slots generation
      // Previous keys are no longer valid
      slot.generation++;
 
      // Exchange positions of to-be-deleted element and last element
      // of _data and _erase for O(1) deletion later
      std::swap(_data[slot.index], _data[_data.size() - 1]);
      std::swap(_erase[slot.index], _erase[_erase.size() - 1]);
 
      // Fix Slot of moved element
      _slots[_erase[slot.index]].index = slot.index;
 
      // Actually delete elements
      _data.pop_back();
      _erase.pop_back();
 
      // Slot can now be reused. Add slot to freelist
      _slots[freelist.tail].index = key.index;
      freelist.tail = key.index;
      _slots[freelist.tail].index = freelist.tail;
    }
 
    Key replace(Key& key, V&& value)
    {
      erase(key);
      return insert(value);
    }
 
    Key replace(Key& key, V& value)
    {
      erase(key);
      return insert(value);
    }
 
    bool contains_key(const Key& key) const
    {
      return (key.index < _slots.size() && _slots[key.index].generation == key.generation);
    }
 
    const V& operator[](const Key& key) const
    {
      const Slot& slot = try_get_slot(key);
      ASSERTM(slot.index < _data.size(), "Invalid slot index.");
      return _data[slot.index];
    }
 
    V& operator[](const Key& key)
    {
      Slot& slot = try_get_slot(key);
      ASSERTM(slot.index < _data.size(), "Invalid slot index.");
      return _data[slot.index];
    }
 
    void reserve(Index capacity)
    {
      _slots.reserve(capacity + 1);
      _data.reserve(capacity);
      _slots.reserve(capacity);
    }
 
    Index capacity() const
    {
      return _data.capacity();
    }
 
    Index size() const
    {
      return _data.size();
    }
 
    V* data()
    {
      return _data.data();
    }
 
    const V* data() const
    {
      return _data.data();
    }
 
    std::size_t bytes() const
    {
      return sizeof(freelist) + _slots.size() * sizeof(Slot) + _data.size() * sizeof(V) +
             _erase.size() * sizeof(Index);
    }
 
    class SlotMapIterator
    {
    public:
      SlotMapIterator(SlotMap<V, Key>& map, Index i) : _slotmap(map), _index(i)
      {
      }
 
      bool operator==(const SlotMapIterator& rhs)
      {
        // Iterators are identical if they refer to the same slotmap and point to the same indices
        return &(this->_slotmap) == &(rhs._slotmap) && this->_index == rhs._index;
      }
      bool operator!=(const SlotMapIterator& rhs)
      {
        return !(*this == rhs);
      }
 
      SlotMapIterator& operator++()
      {
        _index++;
        return *this;
      }
 
      KeyValuePair<V, Key> operator*()
      {
        // Retrieve slot for current index via erase table
        std::uint32_t slot_index = _slotmap._erase[_index];
        Slot& slot = _slotmap._slots[slot_index];
        return KeyValuePair<V, Key>(_slotmap._data[slot.index], Key(slot_index, slot.generation));
      }
 
    private:
      SlotMap<V, Key>& _slotmap;
      Index _index;
    };
 
    class ConstSlotMapIterator
    {
    public:
      ConstSlotMapIterator(const SlotMap<V, Key>& map, Index i) : _slotmap(map), _index(i)
      {
      }
 
      bool operator==(const ConstSlotMapIterator& rhs)
      {
        // Iterators are identical if they refer to the same slotmap and point to the same indices
        return &(this->_slotmap) == &(rhs._slotmap) && this->_index == rhs._index;
      }
      bool operator!=(const ConstSlotMapIterator& rhs)
      {
        return !(*this == rhs);
      }
 
      ConstSlotMapIterator& operator++()
      {
        _index++;
        return *this;
      }
 
      ConstKeyValuePair<V, Key> operator*()
      {
        // Retrieve slot for current index via erase table
        std::uint32_t slot_index = _slotmap._erase[_index];
        const Slot& slot = _slotmap._slots[slot_index];
        return ConstKeyValuePair<V, Key>(_slotmap._data[slot.index], Key(slot_index, slot.generation));
      }
 
    private:
      const SlotMap<V, Key>& _slotmap;
      Index _index;
    };
 
    SlotMapIterator begin()
    {
      return SlotMapIterator(*this, 0);
    }
 
    SlotMapIterator end()
    {
      return SlotMapIterator(*this, _data.size());
    }
 
    ConstSlotMapIterator begin() const
    {
      return ConstSlotMapIterator(*this, 0);
    }
 
    ConstSlotMapIterator end() const
    {
      return ConstSlotMapIterator(*this, _data.size());
    }
 
  private:
    struct Slot
    {
      Slot() : index(0), generation(1)
      {
      }
      Slot(std::uint32_t i, std::uint32_t g) : index(i), generation(g)
      {
      }
 
      std::uint32_t index;
      std::uint32_t generation;
    };
 
    Slot& try_get_slot(const Key& key)
    {
      ASSERTM(key.index < _slots.size(), "Invalid SlotMap key. Index exceeds number of slots.");
      Slot& slot = _slots[key.index];
      ASSERTM(key.generation == slot.generation, "Invalid SlotMap key. Generation mismatch.");
      return slot;
    }
 
    const Slot& try_get_slot(const Key& key) const
    {
      ASSERTM(key.index < _slots.size(), "Invalid SlotMap key. Index exceeds number of slots.");
      const Slot& slot = _slots[key.index];
      ASSERTM(key.generation == slot.generation, "Invalid SlotMap key. Generation mismatch.");
      return slot;
    }
 
    struct
    {
      std::uint32_t head;
      std::uint32_t tail;
    } freelist;
 
    std::vector<Slot> _slots;
    std::vector<V> _data;
    std::vector<std::uint32_t> _erase;
  };
 
  template<typename V, typename Key = SlotMapKey>
  class SecondaryMap
  {
  public:
    void insert(const Key& key, const V& value)
    {
      if(key.index >= _slots.size())
      {
        Index extend_by = 1 + key.index - _slots.size();
        _slots.insert(_slots.end(), extend_by, Slot());
      }
 
      Slot& slot = _slots[key.index];
      slot.value = std::optional<V>(value);
      slot.generation = key.generation;
    }
 
    bool contains_key(const Key& key)
    {
      return key.index < _slots.size() && _slots[key.index].generation == key.generation &&
             _slots[key.index].value.has_value();
    }
 
    const V& operator[](const Key& key) const
    {
      ASSERTM(key.index < _slots.size(), "Invalid SecondaryMap key. Index exceeds number of slots.");
      const Slot& slot = _slots[key.index];
      ASSERTM(slot.value.has_value(), "Invalid SecondaryMap key. Slot is unoccupied.");
      ASSERTM(key.generation == slot.generation, "Invalid SecondaryMap key. Generation mismatch.");
      return slot.value.value();
    }
 
    V& operator[](const Key& key)
    {
      ASSERTM(key.index < _slots.size(), "Invalid SecondaryMap key. Index exceeds number of slots.");
      Slot& slot = _slots[key.index];
      ASSERTM(slot.value.has_value(), "Invalid SecondaryMap key. Slot is unoccupied.");
      ASSERTM(key.generation == slot.generation, "Invalid SecondaryMap key. Generation mismatch.");
      return slot.value.value();
    }
 
  private:
    struct Slot
    {
      Slot() : generation(1), value(std::nullopt)
      {
      }
      explicit Slot(V&& v) : generation(1), value(std::move(v))
      {
      }
 
      std::uint32_t generation;
      std::optional<V> value;
    };
 
    std::vector<Slot> _slots;
  };
} // namespace FEAT::Util