src/ds/InlineTable.h

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef ds_InlineTable_h
#define ds_InlineTable_h

#include "mozilla/Maybe.h"

#include <utility>

#include "js/AllocPolicy.h"
#include "js/HashTable.h"

namespace js {

namespace detail {

// The InlineTable below needs an abstract way of testing keys for
// tombstone values, and to set a key in an entry to a tombstone.
// This is provided by the KeyPolicy generic type argument, which
// has a default implementation for pointers provided below.

// A default implementation of a KeyPolicy for some types (only pointer
// types for now).
//
// The `KeyPolicy` type parameter informs an InlineTable of how to
// check for tombstone values and to set tombstone values within
// the domain of key (entry).
//
// A `KeyPolicy` for some key type `K` must provide two static methods:
//   static bool isTombstone(const K& key);
//   static void setToTombstone(K& key);
template <typename K>
class DefaultKeyPolicy;

template <typename T>
class DefaultKeyPolicy<T*> {
  DefaultKeyPolicy() = delete;
  DefaultKeyPolicy(const T*&) = delete;

 public:
  static bool isTombstone(T* const& ptr) { return ptr == nullptr; }
  static void setToTombstone(T*& ptr) { ptr = nullptr; }
};

template <typename InlineEntry, typename Entry, typename Table,
          typename HashPolicy, typename AllocPolicy, typename KeyPolicy,
          size_t InlineEntries>
class InlineTable : private AllocPolicy {
 private:
  using TablePtr = typename Table::Ptr;
  using TableAddPtr = typename Table::AddPtr;
  using TableRange = typename Table::Range;
  using Lookup = typename HashPolicy::Lookup;

  size_t inlNext_;
  size_t inlCount_;
  InlineEntry inl_[InlineEntries];
  Table table_;

#ifdef DEBUG
  template <typename Key>
  static bool keyNonZero(const Key& key) {
    // Zero as tombstone means zero keys are invalid.
    return !!key;
  }
#endif

  InlineEntry* inlineStart() {
    MOZ_ASSERT(!usingTable());
    return inl_;
  }

  const InlineEntry* inlineStart() const {
    MOZ_ASSERT(!usingTable());
    return inl_;
  }

  InlineEntry* inlineEnd() {
    MOZ_ASSERT(!usingTable());
    return inl_ + inlNext_;
  }

  const InlineEntry* inlineEnd() const {
    MOZ_ASSERT(!usingTable());
    return inl_ + inlNext_;
  }

  bool usingTable() const { return inlNext_ > InlineEntries; }

  MOZ_MUST_USE bool switchToTable() {
    MOZ_ASSERT(inlNext_ == InlineEntries);

    table_.clear();

    InlineEntry* end = inlineEnd();
    for (InlineEntry* it = inlineStart(); it != end; ++it) {
      if (it->key && !it->moveTo(table_)) {
        return false;
      }
    }

    inlNext_ = InlineEntries + 1;
    MOZ_ASSERT(table_.count() == inlCount_);
    MOZ_ASSERT(usingTable());
    return true;
  }

  MOZ_NEVER_INLINE
  MOZ_MUST_USE bool switchAndAdd(const InlineEntry& entry) {
    if (!switchToTable()) {
      return false;
    }

    return entry.putNew(table_);
  }

 public:
  static const size_t SizeOfInlineEntries = sizeof(InlineEntry) * InlineEntries;

  explicit InlineTable(AllocPolicy a = AllocPolicy())
      : AllocPolicy(std::move(a)), inlNext_(0), inlCount_(0), table_(a) {}

  class Ptr {
    friend class InlineTable;

   protected:
    MOZ_INIT_OUTSIDE_CTOR Entry entry_;
    MOZ_INIT_OUTSIDE_CTOR TablePtr tablePtr_;
    MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlPtr_;
    MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_;

    explicit Ptr(TablePtr p)
        : entry_(p.found() ? &*p : nullptr),
          tablePtr_(p),
          isInlinePtr_(false) {}

    explicit Ptr(InlineEntry* inlineEntry)
        : entry_(inlineEntry), inlPtr_(inlineEntry), isInlinePtr_(true) {}

    void operator==(const Ptr& other);

   public:
    // Leaves Ptr uninitialized.
    Ptr() {
#ifdef DEBUG
      inlPtr_ = (InlineEntry*)0xbad;
      isInlinePtr_ = true;
#endif
    }

    // Default copy constructor works for this structure.

    bool found() const {
      return isInlinePtr_ ? bool(inlPtr_) : tablePtr_.found();
    }

    explicit operator bool() const { return found(); }

    bool operator==(const Ptr& other) const {
      MOZ_ASSERT(found() && other.found());
      if (isInlinePtr_ != other.isInlinePtr_) {
        return false;
      }
      if (isInlinePtr_) {
        return inlPtr_ == other.inlPtr_;
      }
      return tablePtr_ == other.tablePtr_;
    }

    bool operator!=(const Ptr& other) const { return !(*this == other); }

    Entry& operator*() {
      MOZ_ASSERT(found());
      return entry_;
    }

    Entry* operator->() {
      MOZ_ASSERT(found());
      return &entry_;
    }
  };

  class AddPtr {
    friend class InlineTable;

   protected:
    MOZ_INIT_OUTSIDE_CTOR Entry entry_;
    MOZ_INIT_OUTSIDE_CTOR TableAddPtr tableAddPtr_;
    MOZ_INIT_OUTSIDE_CTOR InlineEntry* inlAddPtr_;
    MOZ_INIT_OUTSIDE_CTOR bool isInlinePtr_;
    // Indicates whether inlAddPtr is a found result or an add pointer.
    MOZ_INIT_OUTSIDE_CTOR bool inlPtrFound_;

    AddPtr(InlineEntry* ptr, bool found)
        : entry_(ptr),
          inlAddPtr_(ptr),
          isInlinePtr_(true),
          inlPtrFound_(found) {}

    explicit AddPtr(const TableAddPtr& p)
        : entry_(p.found() ? &*p : nullptr),
          tableAddPtr_(p),
          isInlinePtr_(false) {}

   public:
    AddPtr() = default;

    bool found() const {
      return isInlinePtr_ ? inlPtrFound_ : tableAddPtr_.found();
    }

    explicit operator bool() const { return found(); }

    bool operator==(const AddPtr& other) const {
      MOZ_ASSERT(found() && other.found());
      if (isInlinePtr_ != other.isInlinePtr_) {
        return false;
      }
      if (isInlinePtr_) {
        return inlAddPtr_ == other.inlAddPtr_;
      }
      return tableAddPtr_ == other.tableAddPtr_;
    }

    bool operator!=(const AddPtr& other) const { return !(*this == other); }

    Entry& operator*() {
      MOZ_ASSERT(found());
      return entry_;
    }

    Entry* operator->() {
      MOZ_ASSERT(found());
      return &entry_;
    }
  };

  size_t count() const { return usingTable() ? table_.count() : inlCount_; }

  bool empty() const { return usingTable() ? table_.empty() : !inlCount_; }

  void clear() {
    inlNext_ = 0;
    inlCount_ = 0;
  }

  MOZ_ALWAYS_INLINE
  Ptr lookup(const Lookup& l) {
    MOZ_ASSERT(keyNonZero(l));

    if (usingTable()) {
      return Ptr(table_.lookup(l));
    }

    InlineEntry* end = inlineEnd();
    for (InlineEntry* it = inlineStart(); it != end; ++it) {
      if (it->key && HashPolicy::match(it->key, l)) {
        return Ptr(it);
      }
    }

    return Ptr(nullptr);
  }

  MOZ_ALWAYS_INLINE
  AddPtr lookupForAdd(const Lookup& l) {
    MOZ_ASSERT(keyNonZero(l));

    if (usingTable()) {
      return AddPtr(table_.lookupForAdd(l));
    }

    InlineEntry* end = inlineEnd();
    for (InlineEntry* it = inlineStart(); it != end; ++it) {
      if (it->key && HashPolicy::match(it->key, l)) {
        return AddPtr(it, true);
      }
    }

    // The add pointer that's returned here may indicate the limit entry of
    // the linear space, in which case the |add| operation will initialize
    // the table if necessary and add the entry there.
    return AddPtr(inlineEnd(), false);
  }

  template <typename KeyInput, typename... Args>
  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key,
                                          Args&&... args) {
    MOZ_ASSERT(!p);
    MOZ_ASSERT(keyNonZero(key));

    if (p.isInlinePtr_) {
      InlineEntry* addPtr = p.inlAddPtr_;
      MOZ_ASSERT(addPtr == inlineEnd());

      // Switching to table mode before we add this pointer.
      if (addPtr == inlineStart() + InlineEntries) {
        if (!switchToTable()) {
          return false;
        }
        return table_.putNew(std::forward<KeyInput>(key),
                             std::forward<Args>(args)...);
      }

      MOZ_ASSERT(!p.found());
      MOZ_ASSERT(uintptr_t(inlineEnd()) == uintptr_t(p.inlAddPtr_));

      if (!this->checkSimulatedOOM()) {
        return false;
      }

      addPtr->update(std::forward<KeyInput>(key), std::forward<Args>(args)...);
      ++inlCount_;
      ++inlNext_;
      return true;
    }

    return table_.add(p.tableAddPtr_, std::forward<KeyInput>(key),
                      std::forward<Args>(args)...);
  }

  void remove(Ptr& p) {
    MOZ_ASSERT(p);
    if (p.isInlinePtr_) {
      MOZ_ASSERT(inlCount_ > 0);
      MOZ_ASSERT(!KeyPolicy::isTombstone(p.inlPtr_->key));
      KeyPolicy::setToTombstone(p.inlPtr_->key);
      --inlCount_;
      return;
    }
    MOZ_ASSERT(usingTable());
    table_.remove(p.tablePtr_);
  }

  void remove(const Lookup& l) {
    if (Ptr p = lookup(l)) {
      remove(p);
    }
  }

  class Range {
    friend class InlineTable;

   protected:
    mozilla::Maybe<TableRange> tableRange_;  // `Nothing` if `isInline_==true`
    InlineEntry* cur_;
    InlineEntry* end_;
    bool isInline_;

    explicit Range(TableRange r)
        : tableRange_(mozilla::Some(r)),
          cur_(nullptr),
          end_(nullptr),
          isInline_(false) {
      MOZ_ASSERT(!isInlineRange());
    }

    Range(const InlineEntry* begin, const InlineEntry* end)
        : tableRange_(mozilla::Nothing()),
          cur_(const_cast<InlineEntry*>(begin)),
          end_(const_cast<InlineEntry*>(end)),
          isInline_(true) {
      advancePastNulls(cur_);
      MOZ_ASSERT(isInlineRange());
    }

    bool assertInlineRangeInvariants() const {
      MOZ_ASSERT(uintptr_t(cur_) <= uintptr_t(end_));
      MOZ_ASSERT_IF(cur_ != end_, !KeyPolicy::isTombstone(cur_->key));
      return true;
    }

    bool isInlineRange() const {
      MOZ_ASSERT_IF(isInline_, assertInlineRangeInvariants());
      return isInline_;
    }

    void advancePastNulls(InlineEntry* begin) {
      InlineEntry* newCur = begin;
      while (newCur < end_ && KeyPolicy::isTombstone(newCur->key)) {
        ++newCur;
      }
      MOZ_ASSERT(uintptr_t(newCur) <= uintptr_t(end_));
      cur_ = newCur;
    }

    void bumpCurPtr() {
      MOZ_ASSERT(isInlineRange());
      advancePastNulls(cur_ + 1);
    }

   public:
    bool empty() const {
      return isInlineRange() ? cur_ == end_ : tableRange_->empty();
    }

    Entry front() {
      MOZ_ASSERT(!empty());
      if (isInlineRange()) {
        return Entry(cur_);
      }
      return Entry(&tableRange_->front());
    }

    void popFront() {
      MOZ_ASSERT(!empty());
      if (isInlineRange()) {
        bumpCurPtr();
      } else {
        tableRange_->popFront();
      }
    }
  };

  Range all() const {
    return usingTable() ? Range(table_.all())
                        : Range(inlineStart(), inlineEnd());
  }
};

}  // namespace detail

// A map with InlineEntries number of entries kept inline in an array.
//
// The Key type must be zeroable as zeros are used as tombstone keys.
// The Value type must have a default constructor.
//
// The API is very much like HashMap's.
template <typename Key, typename Value, size_t InlineEntries,
          typename HashPolicy = DefaultHasher<Key>,
          typename AllocPolicy = TempAllocPolicy,
          typename KeyPolicy = detail::DefaultKeyPolicy<Key>>
class InlineMap {
  using Map = HashMap<Key, Value, HashPolicy, AllocPolicy>;

  struct InlineEntry {
    Key key;
    Value value;

    template <typename KeyInput, typename ValueInput>
    void update(KeyInput&& key, ValueInput&& value) {
      this->key = std::forward<KeyInput>(key);
      this->value = std::forward<ValueInput>(value);
    }

    MOZ_MUST_USE bool moveTo(Map& map) {
      return map.putNew(std::move(key), std::move(value));
    }
  };

  class Entry {
    using MapEntry = typename Map::Entry;

    MapEntry* mapEntry_;
    InlineEntry* inlineEntry_;

   public:
    Entry() = default;

    explicit Entry(MapEntry* mapEntry)
        : mapEntry_(mapEntry), inlineEntry_(nullptr) {}

    explicit Entry(InlineEntry* inlineEntry)
        : mapEntry_(nullptr), inlineEntry_(inlineEntry) {}

    const Key& key() const {
      MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
      if (mapEntry_) {
        return mapEntry_->key();
      }
      return inlineEntry_->key;
    }

    Value& value() {
      MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
      if (mapEntry_) {
        return mapEntry_->value();
      }
      return inlineEntry_->value;
    }
  };

  using Impl = detail::InlineTable<InlineEntry, Entry, Map, HashPolicy,
                                   AllocPolicy, KeyPolicy, InlineEntries>;

  Impl impl_;

 public:
  using Table = Map;
  using Ptr = typename Impl::Ptr;
  using AddPtr = typename Impl::AddPtr;
  using Range = typename Impl::Range;
  using Lookup = typename HashPolicy::Lookup;

  static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;

  explicit InlineMap(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {}

  size_t count() const { return impl_.count(); }

  bool empty() const { return impl_.empty(); }

  void clear() { impl_.clear(); }

  Range all() const { return impl_.all(); }

  MOZ_ALWAYS_INLINE
  Ptr lookup(const Lookup& l) { return impl_.lookup(l); }

  MOZ_ALWAYS_INLINE
  bool has(const Lookup& l) const {
    return const_cast<InlineMap*>(this)->lookup(l).found();
  }

  MOZ_ALWAYS_INLINE
  AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); }

  template <typename KeyInput, typename ValueInput>
  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key,
                                          ValueInput&& value) {
    return impl_.add(p, std::forward<KeyInput>(key),
                     std::forward<ValueInput>(value));
  }

  template <typename KeyInput, typename ValueInput>
  MOZ_MUST_USE bool put(KeyInput&& key, ValueInput&& value) {
    AddPtr p = lookupForAdd(key);
    if (p) {
      p->value() = std::forward<ValueInput>(value);
      return true;
    }
    return add(p, std::forward<KeyInput>(key), std::forward<ValueInput>(value));
  }

  void remove(Ptr& p) { impl_.remove(p); }

  void remove(const Lookup& l) { impl_.remove(l); }
};

// A set with InlineEntries number of entries kept inline in an array.
//
// The T type must be zeroable as zeros are used as tombstone keys.
// The T type must have a default constructor.
//
// The API is very much like HashMap's.
template <typename T, size_t InlineEntries,
          typename HashPolicy = DefaultHasher<T>,
          typename AllocPolicy = TempAllocPolicy,
          typename KeyPolicy = detail::DefaultKeyPolicy<T>>
class InlineSet {
  using Set = HashSet<T, HashPolicy, AllocPolicy>;

  struct InlineEntry {
    T key;

    template <typename TInput>
    void update(TInput&& key) {
      this->key = std::forward<TInput>(key);
    }

    MOZ_MUST_USE bool moveTo(Set& set) { return set.putNew(std::move(key)); }
  };

  class Entry {
    using SetEntry = typename Set::Entry;

    SetEntry* setEntry_;
    InlineEntry* inlineEntry_;

   public:
    Entry() = default;

    explicit Entry(const SetEntry* setEntry)
        : setEntry_(const_cast<SetEntry*>(setEntry)), inlineEntry_(nullptr) {}

    explicit Entry(InlineEntry* inlineEntry)
        : setEntry_(nullptr), inlineEntry_(inlineEntry) {}

    operator T() const {
      MOZ_ASSERT(!!setEntry_ != !!inlineEntry_);
      if (setEntry_) {
        return *setEntry_;
      }
      return inlineEntry_->key;
    }
  };

  using Impl = detail::InlineTable<InlineEntry, Entry, Set, HashPolicy,
                                   AllocPolicy, KeyPolicy, InlineEntries>;

  Impl impl_;

 public:
  using Table = Set;
  using Ptr = typename Impl::Ptr;
  using AddPtr = typename Impl::AddPtr;
  using Range = typename Impl::Range;
  using Lookup = typename HashPolicy::Lookup;

  static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;

  explicit InlineSet(AllocPolicy a = AllocPolicy()) : impl_(std::move(a)) {}

  size_t count() const { return impl_.count(); }

  bool empty() const { return impl_.empty(); }

  void clear() { impl_.clear(); }

  Range all() const { return impl_.all(); }

  MOZ_ALWAYS_INLINE
  Ptr lookup(const Lookup& l) { return impl_.lookup(l); }

  MOZ_ALWAYS_INLINE
  bool has(const Lookup& l) const {
    return const_cast<InlineSet*>(this)->lookup(l).found();
  }

  MOZ_ALWAYS_INLINE
  AddPtr lookupForAdd(const Lookup& l) { return impl_.lookupForAdd(l); }

  template <typename TInput>
  MOZ_ALWAYS_INLINE MOZ_MUST_USE bool add(AddPtr& p, TInput&& key) {
    return impl_.add(p, std::forward<TInput>(key));
  }

  template <typename TInput>
  MOZ_MUST_USE bool put(TInput&& key) {
    AddPtr p = lookupForAdd(key);
    return p ? true : add(p, std::forward<TInput>(key));
  }

  void remove(Ptr& p) { impl_.remove(p); }

  void remove(const Lookup& l) { impl_.remove(l); }
};

}  // namespace js

#endif  // ds_InlineTable_h