HashTable.h

#pragma once
 
#include <Foundation/Algorithm/HashingUtils.h>
#include <Foundation/Math/Math.h>
#include <Foundation/Memory/AllocatorWrapper.h>
 
template <typename KeyType, typename ValueType, typename Hasher>
class plHashTableBase;
 
template <typename KeyType, typename ValueType, typename Hasher>
struct plHashTableBaseConstIterator
{
  using iterator_category = std::forward_iterator_tag;
  using value_type = plHashTableBaseConstIterator;
  using difference_type = std::ptrdiff_t;
  using pointer = plHashTableBaseConstIterator*;
  using reference = plHashTableBaseConstIterator&;
 
  PL_DECLARE_POD_TYPE();
 
  bool IsValid() const; // [tested]
 
  bool operator==(const plHashTableBaseConstIterator& rhs) const;
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plHashTableBaseConstIterator&);
 
  const KeyType& Key() const; // [tested]
 
  const ValueType& Value() const; // [tested]
 
  void Next(); // [tested]
 
  void operator++(); // [tested]
 
  PL_ALWAYS_INLINE plHashTableBaseConstIterator& operator*() { return *this; } // [tested]
 
protected:
  friend class plHashTableBase<KeyType, ValueType, Hasher>;
 
  explicit plHashTableBaseConstIterator(const plHashTableBase<KeyType, ValueType, Hasher>& hashTable);
  void SetToBegin();
  void SetToEnd();
 
  const plHashTableBase<KeyType, ValueType, Hasher>* m_pHashTable = nullptr;
  plUInt32 m_uiCurrentIndex = 0; // current element index that this iterator points to.
  plUInt32 m_uiCurrentCount = 0; // current number of valid elements that this iterator has found so far.
 
#if PL_ENABLED(PL_USE_CPP20_OPERATORS)
public:
  struct Pointer
  {
    std::pair<const KeyType&, const ValueType&> value;
    const std::pair<const KeyType&, const ValueType&>* operator->() const { return &value; }
  };
 
  PL_ALWAYS_INLINE Pointer operator->() const
  {
    return Pointer{.value = {Key(), Value()}};
  }
 
  // These function is used to return the values for structured bindings.
  // The number and type of type of each slot are defined in the inl file.
  template <std::size_t Index>
  std::tuple_element_t<Index, plHashTableBaseConstIterator>& get() const
  {
    if constexpr (Index == 0)
      return Key();
    if constexpr (Index == 1)
      return Value();
  }
#endif
};
 
template <typename KeyType, typename ValueType, typename Hasher>
struct plHashTableBaseIterator : public plHashTableBaseConstIterator<KeyType, ValueType, Hasher>
{
  PL_DECLARE_POD_TYPE();
 
  PL_ALWAYS_INLINE plHashTableBaseIterator(const plHashTableBaseIterator& rhs); // [tested]
 
  PL_ALWAYS_INLINE void operator=(const plHashTableBaseIterator& rhs); // [tested]
 
  // this is required to pull in the const version of this function
  using plHashTableBaseConstIterator<KeyType, ValueType, Hasher>::Value;
 
  PL_FORCE_INLINE ValueType& Value(); // [tested]
 
  PL_FORCE_INLINE ValueType& Value() const;
 
  PL_ALWAYS_INLINE plHashTableBaseIterator& operator*() { return *this; } // [tested]
 
private:
  friend class plHashTableBase<KeyType, ValueType, Hasher>;
 
  explicit plHashTableBaseIterator(const plHashTableBase<KeyType, ValueType, Hasher>& hashTable);
 
#if PL_ENABLED(PL_USE_CPP20_OPERATORS)
public:
  struct Pointer
  {
    std::pair<const KeyType&, ValueType&> value;
    const std::pair<const KeyType&, ValueType&>* operator->() const { return &value; }
  };
 
  PL_ALWAYS_INLINE Pointer operator->() const
  {
    return Pointer{.value = {plHashTableBaseConstIterator<KeyType, ValueType, Hasher>::Key(), Value()}};
  }
 
  // These functions are used to return the values for structured bindings.
  // The number and type of type of each slot are defined in the inl file.
  template <std::size_t Index>
  std::tuple_element_t<Index, plHashTableBaseIterator>& get()
  {
    if constexpr (Index == 0)
      return plHashTableBaseConstIterator<KeyType, ValueType, Hasher>::Key();
    if constexpr (Index == 1)
      return Value();
  }
 
  template <std::size_t Index>
  std::tuple_element_t<Index, plHashTableBaseIterator>& get() const
  {
    if constexpr (Index == 0)
      return plHashTableBaseConstIterator<KeyType, ValueType, Hasher>::Key();
    if constexpr (Index == 1)
      return Value();
  }
#endif
};
 
 
template <typename KeyType, typename ValueType, typename Hasher>
class plHashTableBase
{
public:
  using Iterator = plHashTableBaseIterator<KeyType, ValueType, Hasher>;
  using ConstIterator = plHashTableBaseConstIterator<KeyType, ValueType, Hasher>;
 
protected:
  explicit plHashTableBase(plAllocator* pAllocator); // [tested]
 
  plHashTableBase(const plHashTableBase<KeyType, ValueType, Hasher>& rhs, plAllocator* pAllocator); // [tested]
 
  plHashTableBase(plHashTableBase<KeyType, ValueType, Hasher>&& rhs, plAllocator* pAllocator); // [tested]
 
  ~plHashTableBase(); // [tested]
 
  void operator=(const plHashTableBase<KeyType, ValueType, Hasher>& rhs); // [tested]
 
  void operator=(plHashTableBase<KeyType, ValueType, Hasher>&& rhs); // [tested]
 
public:
  bool operator==(const plHashTableBase<KeyType, ValueType, Hasher>& rhs) const; // [tested]
  PL_ADD_DEFAULT_OPERATOR_NOTEQUAL(const plHashTableBase<KeyType, ValueType, Hasher>&);
 
  void Reserve(plUInt32 uiCapacity); // [tested]
 
  void Compact(); // [tested]
 
  plUInt32 GetCount() const; // [tested]
 
  bool IsEmpty() const; // [tested]
 
  void Clear(); // [tested]
 
  template <typename CompatibleKeyType, typename CompatibleValueType>
  bool Insert(CompatibleKeyType&& key, CompatibleValueType&& value, ValueType* out_pOldValue = nullptr); // [tested]
 
  template <typename CompatibleKeyType>
  bool Remove(const CompatibleKeyType& key, ValueType* out_pOldValue = nullptr); // [tested]
 
  Iterator Remove(const Iterator& pos); // [tested]
 
  void Remove(const ConstIterator& pos) = delete;
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, ValueType& out_value) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, const ValueType*& out_pValue) const; // [tested]
 
  template <typename CompatibleKeyType>
  bool TryGetValue(const CompatibleKeyType& key, ValueType*& out_pValue) const; // [tested]
 
  template <typename CompatibleKeyType>
  ConstIterator Find(const CompatibleKeyType& key) const;
 
  template <typename CompatibleKeyType>
  Iterator Find(const CompatibleKeyType& key);
 
  template <typename CompatibleKeyType>
  const ValueType* GetValue(const CompatibleKeyType& key) const; // [tested]
 
  template <typename CompatibleKeyType>
  ValueType* GetValue(const CompatibleKeyType& key); // [tested]
 
  ValueType& operator[](const KeyType& key); // [tested]
 
  ValueType& FindOrAdd(const KeyType& key, bool* out_pExisted = nullptr); // [tested]
 
  template <typename CompatibleKeyType>
  bool Contains(const CompatibleKeyType& key) const; // [tested]
 
  Iterator GetIterator(); // [tested]
 
  Iterator GetEndIterator(); // [tested]
 
  ConstIterator GetIterator() const; // [tested]
 
  ConstIterator GetEndIterator() const; // [tested]
 
  plAllocator* GetAllocator() const;
 
  plUInt64 GetHeapMemoryUsage() const; // [tested]
 
  void Swap(plHashTableBase<KeyType, ValueType, Hasher>& other); // [tested]
 
private:
  friend struct plHashTableBaseConstIterator<KeyType, ValueType, Hasher>;
  friend struct plHashTableBaseIterator<KeyType, ValueType, Hasher>;
 
  struct Entry
  {
    KeyType key;
    ValueType value;
  };
 
  Entry* m_pEntries = nullptr;
  plUInt32* m_pEntryFlags = nullptr;
 
  plUInt32 m_uiCount = 0;
  plUInt32 m_uiCapacity = 0;
 
  plAllocator* m_pAllocator = nullptr;
 
  enum
  {
    FREE_ENTRY = 0,
    VALID_ENTRY = 1,
    DELETED_ENTRY = 2,
    FLAGS_MASK = 3,
    CAPACITY_ALIGNMENT = 32
  };
 
  void SetCapacity(plUInt32 uiCapacity);
 
  void RemoveInternal(plUInt32 uiIndex);
 
  template <typename CompatibleKeyType>
  plUInt32 FindEntry(const CompatibleKeyType& key) const;
 
  template <typename CompatibleKeyType>
  plUInt32 FindEntry(plUInt32 uiHash, const CompatibleKeyType& key) const;
 
  plUInt32 GetFlagsCapacity() const;
  plUInt32 GetFlags(plUInt32* pFlags, plUInt32 uiEntryIndex) const;
  void SetFlags(plUInt32 uiEntryIndex, plUInt32 uiFlags);
 
  bool IsFreeEntry(plUInt32 uiEntryIndex) const;
  bool IsValidEntry(plUInt32 uiEntryIndex) const;
  bool IsDeletedEntry(plUInt32 uiEntryIndex) const;
 
  void MarkEntryAsFree(plUInt32 uiEntryIndex);
  void MarkEntryAsValid(plUInt32 uiEntryIndex);
  void MarkEntryAsDeleted(plUInt32 uiEntryIndex);
};
 
template <typename KeyType, typename ValueType, typename Hasher = plHashHelper<KeyType>, typename AllocatorWrapper = plDefaultAllocatorWrapper>
class plHashTable : public plHashTableBase<KeyType, ValueType, Hasher>
{
public:
  plHashTable();
  explicit plHashTable(plAllocator* pAllocator);
 
  plHashTable(const plHashTable<KeyType, ValueType, Hasher, AllocatorWrapper>& other);
  plHashTable(const plHashTableBase<KeyType, ValueType, Hasher>& other);
 
  plHashTable(plHashTable<KeyType, ValueType, Hasher, AllocatorWrapper>&& other);
  plHashTable(plHashTableBase<KeyType, ValueType, Hasher>&& other);
 
 
  void operator=(const plHashTable<KeyType, ValueType, Hasher, AllocatorWrapper>& rhs);
  void operator=(const plHashTableBase<KeyType, ValueType, Hasher>& rhs);
 
  void operator=(plHashTable<KeyType, ValueType, Hasher, AllocatorWrapper>&& rhs);
  void operator=(plHashTableBase<KeyType, ValueType, Hasher>&& rhs);
};
 
// begin() /end() for range-based for-loop support
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::Iterator begin(plHashTableBase<KeyType, ValueType, Hasher>& ref_container)
{
  return ref_container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::ConstIterator begin(const plHashTableBase<KeyType, ValueType, Hasher>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::ConstIterator cbegin(const plHashTableBase<KeyType, ValueType, Hasher>& container)
{
  return container.GetIterator();
}
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::Iterator end(plHashTableBase<KeyType, ValueType, Hasher>& ref_container)
{
  return ref_container.GetEndIterator();
}
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::ConstIterator end(const plHashTableBase<KeyType, ValueType, Hasher>& container)
{
  return container.GetEndIterator();
}
 
template <typename KeyType, typename ValueType, typename Hasher>
typename plHashTableBase<KeyType, ValueType, Hasher>::ConstIterator cend(const plHashTableBase<KeyType, ValueType, Hasher>& container)
{
  return container.GetEndIterator();
}
 
#include <Foundation/Containers/Implementation/HashTable_inl.h>