// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef FBL_INTRUSIVE_HASH_TABLE_H_
#define FBL_INTRUSIVE_HASH_TABLE_H_

#include <zircon/assert.h>

#include <cstddef>
#include <iterator>
#include <utility>

#include <fbl/intrusive_container_utils.h>
#include <fbl/intrusive_pointer_traits.h>
#include <fbl/intrusive_single_list.h>
#include <fbl/macros.h>

namespace fbl {

// Fwd decl of sanity checker class used by tests.
namespace tests {
namespace intrusive_containers {
class HashTableChecker;
}  // namespace intrusive_containers
}  // namespace tests

namespace internal {
inline constexpr size_t kDefaultNumBuckets = 37;
}  // namespace internal

// DefaultHashTraits defines a default implementation of traits used to
// define the hash function for a hash table.
//
// At a minimum, a class or a struct which is to be used to define the
// hash traits of a hashtable must define...
//
// GetHash : A static method which take a constant reference to an instance of
//           the container's KeyType and returns an instance of the container's
//           HashType representing the hashed value of the key.  The value must
//           be on the range from [0, Container::kNumBuckets - 1]
//
// DefaultHashTraits generates a compliant implementation of hash traits taking
// its KeyType, ObjType, HashType and NumBuckets from template parameters.
// Users of DefaultHashTraits only need to implement a static method of ObjType
// named GetHash which takes a const reference to a KeyType and returns a
// HashType.  The default implementation will automatically mod by the number of
// buckets given in the template parameters.  If the user's hash function
// already automatically guarantees that the returned hash value will be in the
// proper range, he/she should implement their own hash traits to avoid the
// extra div/mod operation.
template <typename KeyType, typename ObjType, typename HashType, HashType kNumBuckets>
struct DefaultHashTraits {
  static_assert(std::is_unsigned_v<HashType>, "HashTypes must be unsigned integers");
  static HashType GetHash(const KeyType& key) {
    return static_cast<HashType>(ObjType::GetHash(key) % kNumBuckets);
  }
};

template <typename _KeyType, typename _PtrType, typename _BucketType = SinglyLinkedList<_PtrType>,
          typename _HashType = size_t, _HashType _NumBuckets = internal::kDefaultNumBuckets,
          typename _KeyTraits = DefaultKeyedObjectTraits<
              _KeyType, typename internal::ContainerPtrTraits<_PtrType>::ValueType>,
          typename _HashTraits = DefaultHashTraits<
              _KeyType, typename internal::ContainerPtrTraits<_PtrType>::ValueType, _HashType,
              _NumBuckets>>
class __POINTER(_KeyType) HashTable {
 private:
  // Private fwd decls of the iterator implementation.
  template <typename IterTraits>
  class iterator_impl;
  struct iterator_traits;
  struct const_iterator_traits;

 public:
  // Pointer types/traits
  using PtrType = _PtrType;
  using PtrTraits = internal::ContainerPtrTraits<PtrType>;
  using ValueType = typename PtrTraits::ValueType;
  using RefType = typename PtrTraits::RefType;

  // Key types/traits
  using KeyType = _KeyType;
  using KeyTraits = _KeyTraits;

  // Hash types/traits
  using HashType = _HashType;
  using HashTraits = _HashTraits;

  // Bucket types/traits
  using BucketType = _BucketType;
  using NodeTraits = typename BucketType::NodeTraits;

  // Declarations of the standard iterator types.
  using iterator = iterator_impl<iterator_traits>;
  using const_iterator = iterator_impl<const_iterator_traits>;

  // An alias for the type of this specific HashTable<...> and its test sanity checker.
  using ContainerType =
      HashTable<_KeyType, _PtrType, _BucketType, _HashType, _NumBuckets, _KeyTraits, _HashTraits>;
  using CheckerType = ::fbl::tests::intrusive_containers::HashTableChecker;

  // The number of buckets should be a nice prime such as 37, 211, 389 unless
  // The hash function is really good. Lots of cheap hash functions have
  // hidden periods for which the mod with prime above 'mostly' fixes.
  static constexpr HashType kNumBuckets = _NumBuckets;

  // Hash tables only support constant order erase if their underlying bucket
  // type does.
  static constexpr bool SupportsConstantOrderErase = BucketType::SupportsConstantOrderErase;
  static constexpr bool SupportsConstantOrderSize = true;
  static constexpr bool IsAssociative = true;
  static constexpr bool IsSequenced = false;

  static_assert(kNumBuckets > 0, "Hash tables must have at least one bucket");
  static_assert(std::is_unsigned_v<HashType>, "HashTypes must be unsigned integers");

  constexpr HashTable() noexcept {
    using NodeState = internal::node_state_t<NodeTraits, RefType>;

    // Make certain that the type of pointer we are expected to manage matches
    // the type of pointer that our Node type expects to manage.  In theory, our
    // bucket has already performed this check for us, but extra sanity checks
    // are always welcome.
    static_assert(std::is_same_v<PtrType, typename NodeState::PtrType>,
                  "SinglyLinkedList's pointer type must match its Node's pointerType");

    // HashTable does not currently support direct remove-from-container (but
    // could do so if it did not track size)
    static_assert(!(NodeState::kNodeOptions & NodeOptions::AllowRemoveFromContainer),
                  "HashTable does not support nodes which allow RemoveFromContainer.");
  }

  ~HashTable() { ZX_DEBUG_ASSERT(PtrTraits::IsManaged || is_empty()); }

  // Standard begin/end, cbegin/cend iterator accessors.
  iterator begin() { return iterator(this, iterator::BEGIN); }
  const_iterator begin() const { return const_iterator(this, const_iterator::BEGIN); }
  const_iterator cbegin() const { return const_iterator(this, const_iterator::BEGIN); }

  iterator end() { return iterator(this, iterator::END); }
  const_iterator end() const { return const_iterator(this, const_iterator::END); }
  const_iterator cend() const { return const_iterator(this, const_iterator::END); }

  // make_iterator : construct an iterator out of a reference to an object.
  iterator make_iterator(ValueType& obj) {
    HashType ndx = GetHash(KeyTraits::GetKey(obj));
    return iterator(this, ndx, buckets_[ndx].make_iterator(obj));
  }
  const_iterator make_iterator(const ValueType& obj) const {
    HashType ndx = GetHash(KeyTraits::GetKey(obj));
    return const_iterator(this, ndx, buckets_[ndx].make_iterator(obj));
  }

  void insert(const PtrType& ptr) { insert(PtrType(ptr)); }
  void insert(PtrType&& ptr) {
    ZX_DEBUG_ASSERT(ptr != nullptr);
    KeyType key = KeyTraits::GetKey(*ptr);
    BucketType& bucket = GetBucket(key);

    // Duplicate keys are disallowed.  Debug assert if someone tries to to
    // insert an element with a duplicate key.  If the user thought that
    // there might be a duplicate key in the HashTable already, he/she
    // should have used insert_or_find() instead.
    ZX_DEBUG_ASSERT(FindInBucket(bucket, key).IsValid() == false);

    bucket.push_front(std::move(ptr));
    ++count_;
  }

  // insert_or_find
  //
  // Insert the element pointed to by ptr if it is not already in the
  // HashTable, or find the element that the ptr collided with instead.
  //
  // 'iter' is an optional out parameter pointer to an iterator which
  // will reference either the newly inserted item, or the item whose key
  // collided with ptr.
  //
  // insert_or_find returns true if there was no collision and the item was
  // successfully inserted, otherwise it returns false.
  //
  bool insert_or_find(const PtrType& ptr, iterator* iter = nullptr) {
    return insert_or_find(PtrType(ptr), iter);
  }

  bool insert_or_find(PtrType&& ptr, iterator* iter = nullptr) {
    ZX_DEBUG_ASSERT(ptr != nullptr);
    KeyType key = KeyTraits::GetKey(*ptr);
    HashType ndx = GetHash(key);
    auto& bucket = buckets_[ndx];
    auto bucket_iter = FindInBucket(bucket, key);

    if (bucket_iter.IsValid()) {
      if (iter)
        *iter = iterator(this, ndx, bucket_iter);
      return false;
    }

    bucket.push_front(std::move(ptr));
    ++count_;
    if (iter)
      *iter = iterator(this, ndx, bucket.begin());
    return true;
  }

  // insert_or_replace
  //
  // Find the element in the hashtable with the same key as *ptr and replace
  // it with ptr, then return the pointer to the element which was replaced.
  // If no element in the hashtable shares a key with *ptr, simply add ptr to
  // the hashtable and return nullptr.
  //
  PtrType insert_or_replace(const PtrType& ptr) { return insert_or_replace(PtrType(ptr)); }

  PtrType insert_or_replace(PtrType&& ptr) {
    ZX_DEBUG_ASSERT(ptr != nullptr);
    KeyType key = KeyTraits::GetKey(*ptr);
    HashType ndx = GetHash(key);
    auto& bucket = buckets_[ndx];
    auto orig = PtrTraits::GetRaw(ptr);

    PtrType replaced = bucket.replace_if(
        [key](const ValueType& other) -> bool {
          return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
        },
        std::move(ptr));

    if (orig == PtrTraits::GetRaw(replaced)) {
      bucket.push_front(std::move(replaced));
      count_++;
      return nullptr;
    }

    return replaced;
  }

  iterator find(const KeyType& key) {
    HashType ndx = GetHash(key);
    auto& bucket = buckets_[ndx];
    auto bucket_iter = FindInBucket(bucket, key);

    return bucket_iter.IsValid() ? iterator(this, ndx, bucket_iter) : iterator(this, iterator::END);
  }

  const_iterator find(const KeyType& key) const {
    HashType ndx = GetHash(key);
    const auto& bucket = buckets_[ndx];
    auto bucket_iter = FindInBucket(bucket, key);

    return bucket_iter.IsValid() ? const_iterator(this, ndx, bucket_iter)
                                 : const_iterator(this, const_iterator::END);
  }

  PtrType erase(const KeyType& key) {
    BucketType& bucket = GetBucket(key);

    PtrType ret = internal::KeyEraseUtils<BucketType, KeyTraits>::erase(bucket, key);
    if (ret != nullptr)
      --count_;

    return ret;
  }

  PtrType erase(const iterator& iter) {
    if (!iter.IsValid())
      return PtrType(nullptr);

    return direct_erase(buckets_[iter.bucket_ndx_], *iter);
  }

  PtrType erase(ValueType& obj) { return direct_erase(GetBucket(obj), obj); }

  // clear
  //
  // Clear out the all of the hashtable buckets.  For managed pointer types,
  // this will release all references held by the hashtable to the objects
  // which were in it.
  void clear() {
    for (auto& e : buckets_)
      e.clear();
    count_ = 0;
  }

  // clear_unsafe
  //
  // Perform a clear_unsafe on all buckets and reset the internal count to
  // zero.  See comments in fbl/intrusive_single_list.h
  // Think carefully before calling this!
  void clear_unsafe() {
    static_assert(PtrTraits::IsManaged == false,
                  "clear_unsafe is not allowed for containers of managed pointers");
    static_assert(NodeTraits::NodeState::kNodeOptions & NodeOptions::AllowClearUnsafe,
                  "Container does not support clear_unsafe.  Consider adding "
                  "NodeOptions::AllowClearUnsafe to your node storage.");

    for (auto& e : buckets_)
      e.clear_unsafe();

    count_ = 0;
  }

  size_t size() const { return count_; }
  bool is_empty() const { return count_ == 0; }

  // erase_if
  //
  // Find the first member of the hash table which satisfies the predicate
  // given by 'fn' and erase it from the list, returning a referenced pointer
  // to the removed element.  Return nullptr if no member satisfies the
  // predicate.
  template <typename UnaryFn>
  PtrType erase_if(UnaryFn fn) {
    if (is_empty())
      return PtrType(nullptr);

    for (HashType i = 0; i < kNumBuckets; ++i) {
      auto& bucket = buckets_[i];
      if (!bucket.is_empty()) {
        PtrType ret = bucket.erase_if(fn);
        if (ret != nullptr) {
          --count_;
          return ret;
        }
      }
    }

    return PtrType(nullptr);
  }

  // find_if
  //
  // Find the first member of the hash table which satisfies the predicate
  // given by 'fn' and return an iterator to it.  Return end() if no member
  // satisfies the predicate.
  template <typename UnaryFn>
  const_iterator find_if(UnaryFn fn) const {
    for (auto iter = begin(); iter.IsValid(); ++iter)
      if (fn(*iter))
        return iter;

    return end();
  }

  template <typename UnaryFn>
  iterator find_if(UnaryFn fn) {
    for (auto iter = begin(); iter.IsValid(); ++iter)
      if (fn(*iter))
        return iter;

    return end();
  }

 private:
  // The traits of a non-const iterator
  struct iterator_traits {
    using RefType = typename PtrTraits::RefType;
    using RawPtrType = typename PtrTraits::RawPtrType;
    using IterType = typename BucketType::iterator;

    static IterType BucketBegin(BucketType& bucket) { return bucket.begin(); }
    static IterType BucketEnd(BucketType& bucket) { return bucket.end(); }
  };

  // The traits of a const iterator
  struct const_iterator_traits {
    using RefType = typename PtrTraits::ConstRefType;
    using RawPtrType = typename PtrTraits::ConstRawPtrType;
    using IterType = typename BucketType::const_iterator;

    static IterType BucketBegin(const BucketType& bucket) { return bucket.cbegin(); }
    static IterType BucketEnd(const BucketType& bucket) { return bucket.cend(); }
  };

  // The shared implementation of the iterator
  template <class IterTraits>
  class iterator_impl {
   private:
    using IterType = typename IterTraits::IterType;

    template <typename IterCategory>
    static constexpr bool kIsBidirectional =
        std::is_base_of_v<std::bidirectional_iterator_tag, IterCategory>;

   public:
    using value_type = ValueType;
    using reference = typename IterTraits::RefType;
    using pointer = typename IterTraits::RawPtrType;
    using difference_type = std::ptrdiff_t;
    using iterator_category = typename std::iterator_traits<IterType>::iterator_category;

    iterator_impl() {}
    iterator_impl(const iterator_impl& other) {
      hash_table_ = other.hash_table_;
      bucket_ndx_ = other.bucket_ndx_;
      iter_ = other.iter_;
    }

    iterator_impl& operator=(const iterator_impl& other) {
      hash_table_ = other.hash_table_;
      bucket_ndx_ = other.bucket_ndx_;
      iter_ = other.iter_;
      return *this;
    }

    bool IsValid() const { return iter_.IsValid(); }
    bool operator==(const iterator_impl& other) const { return iter_ == other.iter_; }
    bool operator!=(const iterator_impl& other) const { return iter_ != other.iter_; }

    // Prefix
    iterator_impl& operator++() {
      if (!IsValid())
        return *this;
      ZX_DEBUG_ASSERT(hash_table_);

      // Bump the bucket iterator and go looking for a new bucket if the
      // iterator has become invalid.
      ++iter_;
      advance_if_invalid_iter();

      return *this;
    }

    template <typename _IterCategory = iterator_category,
              typename = std::enable_if_t<kIsBidirectional<_IterCategory>>>
    iterator_impl& operator--() {
      // If we have never been bound to a HashTable instance, the we had
      // better be invalid.
      if (!hash_table_) {
        ZX_DEBUG_ASSERT(!IsValid());
        return *this;
      }

      // Back up the bucket iterator.  If it is still valid, then we are done.
      --iter_;
      if (iter_.IsValid())
        return *this;

      // If the iterator is invalid after backing up, check previous
      // buckets to see if they contain any nodes.
      while (bucket_ndx_) {
        --bucket_ndx_;
        auto& bucket = GetBucket(bucket_ndx_);
        if (!bucket.is_empty()) {
          iter_ = --IterTraits::BucketEnd(bucket);
          ZX_DEBUG_ASSERT(iter_.IsValid());
          return *this;
        }
      }

      // Looks like we have backed up past the beginning.  Update the
      // bookkeeping to point at the end of the last bucket.
      bucket_ndx_ = kNumBuckets - 1;
      iter_ = IterTraits::BucketEnd(GetBucket(bucket_ndx_));

      return *this;
    }

    // Postfix
    iterator_impl operator++(int) {
      iterator_impl ret(*this);
      ++(*this);
      return ret;
    }

    template <typename _IterCategory = iterator_category,
              typename = std::enable_if_t<kIsBidirectional<_IterCategory>>>
    iterator_impl operator--(int) {
      iterator_impl ret(*this);
      --(*this);
      return ret;
    }

    typename PtrTraits::PtrType CopyPointer() const { return iter_.CopyPointer(); }
    typename IterTraits::RefType operator*() const { return iter_.operator*(); }
    typename IterTraits::RawPtrType operator->() const { return iter_.operator->(); }

   private:
    friend ContainerType;

    enum BeginTag { BEGIN };
    enum EndTag { END };

    iterator_impl(const ContainerType* hash_table, BeginTag)
        : hash_table_(hash_table), bucket_ndx_(0), iter_(IterTraits::BucketBegin(GetBucket(0))) {
      advance_if_invalid_iter();
    }

    iterator_impl(const ContainerType* hash_table, EndTag)
        : hash_table_(hash_table),
          bucket_ndx_(kNumBuckets - 1),
          iter_(IterTraits::BucketEnd(GetBucket(kNumBuckets - 1))) {}

    iterator_impl(const ContainerType* hash_table, HashType bucket_ndx, const IterType& iter)
        : hash_table_(hash_table), bucket_ndx_(bucket_ndx), iter_(iter) {}

    BucketType& GetBucket(HashType ndx) {
      return const_cast<ContainerType*>(hash_table_)->buckets_[ndx];
    }

    void advance_if_invalid_iter() {
      // If the iterator has run off the end of it's current bucket, then
      // check to see if there are nodes in any of the remaining buckets.
      if (!iter_.IsValid()) {
        while (bucket_ndx_ < (kNumBuckets - 1)) {
          ++bucket_ndx_;
          auto& bucket = GetBucket(bucket_ndx_);

          if (!bucket.is_empty()) {
            iter_ = IterTraits::BucketBegin(bucket);
            ZX_DEBUG_ASSERT(iter_.IsValid());
            break;
          } else if (bucket_ndx_ == (kNumBuckets - 1)) {
            iter_ = IterTraits::BucketEnd(bucket);
          }
        }
      }
    }

    const ContainerType* hash_table_ = nullptr;
    HashType bucket_ndx_ = 0;
    IterType iter_;
  };

  PtrType direct_erase(BucketType& bucket, ValueType& obj) {
    PtrType ret = internal::DirectEraseUtils<BucketType>::erase(bucket, obj);

    if (ret != nullptr)
      --count_;

    return ret;
  }

  static typename BucketType::iterator FindInBucket(BucketType& bucket, const KeyType& key) {
    return bucket.find_if([key](const ValueType& other) -> bool {
      return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
    });
  }

  static typename BucketType::const_iterator FindInBucket(const BucketType& bucket,
                                                          const KeyType& key) {
    return bucket.find_if([key](const ValueType& other) -> bool {
      return KeyTraits::EqualTo(key, KeyTraits::GetKey(other));
    });
  }

  // The test framework's 'checker' class is our friend.
  friend CheckerType;

  // Iterators need to access our bucket array in order to iterate.
  friend iterator;
  friend const_iterator;

  // Hash tables may not currently be copied, assigned or moved.
  DISALLOW_COPY_ASSIGN_AND_MOVE(HashTable);

  BucketType& GetBucket(const KeyType& key) { return buckets_[GetHash(key)]; }
  BucketType& GetBucket(const ValueType& obj) { return GetBucket(KeyTraits::GetKey(obj)); }

  static HashType GetHash(const KeyType& obj) {
    HashType ret = HashTraits::GetHash(obj);
    ZX_DEBUG_ASSERT((ret >= 0) && (ret < kNumBuckets));
    return ret;
  }

  size_t count_ = 0UL;
  BucketType buckets_[kNumBuckets];
};

// TaggedHashTable<> is intended for use with ContainableBaseClasses<>.
//
// For an easy way to allow instances of your class to live in multiple
// intrusive containers at once, simply derive from
// ContainableBaseClasses<YourContainables<PtrType, TagType>...> and then use
// this template instead of HashTable<> as the container, passing the same tag
// type you used earlier as the third parameter.
//
// See comments on ContainableBaseClasses<> in fbl/intrusive_container_utils.h
// for more details.
//
template <typename KeyType, typename PtrType, typename TagType,
          typename BucketType = TaggedSinglyLinkedList<PtrType, TagType>,
          typename HashType = size_t, HashType NumBuckets = internal::kDefaultNumBuckets,
          typename KeyTraits = DefaultKeyedObjectTraits<
              KeyType, typename internal::ContainerPtrTraits<PtrType>::ValueType>,
          typename HashTraits =
              DefaultHashTraits<KeyType, typename internal::ContainerPtrTraits<PtrType>::ValueType,
                                HashType, NumBuckets>>
using TaggedHashTable =
    HashTable<KeyType, PtrType, BucketType, HashType, NumBuckets, KeyTraits, HashTraits>;

// Explicit declaration of constexpr storage.
#define HASH_TABLE_PROP(_type, _name)                                                   \
  template <typename KeyType, typename PtrType, typename BucketType, typename HashType, \
            HashType NumBuckets, typename KeyTraits, typename HashTraits>               \
  constexpr _type                                                                       \
      HashTable<KeyType, PtrType, BucketType, HashType, NumBuckets, KeyTraits, HashTraits>::_name

HASH_TABLE_PROP(HashType, kNumBuckets);
HASH_TABLE_PROP(bool, SupportsConstantOrderErase);
HASH_TABLE_PROP(bool, SupportsConstantOrderSize);
HASH_TABLE_PROP(bool, IsAssociative);
HASH_TABLE_PROP(bool, IsSequenced);

#undef HASH_TABLE_PROP

}  // namespace fbl

#endif  // FBL_INTRUSIVE_HASH_TABLE_H_