src/ds/InlineTable.h

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * 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/Move.h"

#include "jsalloc.h"

#include "js/HashTable.h"

namespace js {

namespace detail {

template <typename InlineEntry,
          typename Entry,
          typename Table,
          typename HashPolicy,
          typename AllocPolicy,
          size_t InlineEntries>
class InlineTable
{
  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);

        if (table_.initialized()) {
            table_.clear();
        } else {
            if (!table_.init(count()))
                return false;
            MOZ_ASSERT(table_.initialized());
        }

        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())
      : inlNext_(0),
        inlCount_(0),
        table_(a)
    { }

    class Ptr
    {
        friend class InlineTable;

      protected:
        Entry        entry_;
        TablePtr     tablePtr_;
        InlineEntry* inlPtr_;
        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:
        Entry        entry_;
        TableAddPtr  tableAddPtr_;
        InlineEntry* inlAddPtr_;
        bool         isInlinePtr_;
        // Indicates whether inlAddPtr is a found result or an add pointer.
        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() {}

        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(mozilla::Forward<KeyInput>(key),
                                     mozilla::Forward<Args>(args)...);
            }

            MOZ_ASSERT(!p.found());
            MOZ_ASSERT(uintptr_t(inlineEnd()) == uintptr_t(p.inlAddPtr_));
            addPtr->update(mozilla::Forward<KeyInput>(key),
                           mozilla::Forward<Args>(args)...);
            ++inlCount_;
            ++inlNext_;
            return true;
        }

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

    void remove(Ptr& p) {
        MOZ_ASSERT(p);
        if (p.isInlinePtr_) {
            MOZ_ASSERT(inlCount_ > 0);
            MOZ_ASSERT(p.inlPtr_->key != nullptr);
            p.inlPtr_->key = nullptr;
            --inlCount_;
            return;
        }
        MOZ_ASSERT(table_.initialized() && usingTable());
        table_.remove(p.tablePtr_);
    }

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

    class Range
    {
        friend class InlineTable;

      protected:
        TableRange   tableRange_;
        InlineEntry* cur_;
        InlineEntry* end_;
        bool         isInline_;

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

        Range(const InlineEntry* begin, const InlineEntry* end)
          : 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_, cur_->key != nullptr);
            return true;
        }

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

        void advancePastNulls(InlineEntry* begin) {
            InlineEntry* newCur = begin;
            while (newCur < end_ && nullptr == 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>
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 = mozilla::Forward<KeyInput>(key);
            this->value = mozilla::Forward<ValueInput>(value);
        }

        MOZ_MUST_USE bool moveTo(Map& map) {
            return map.putNew(mozilla::Move(key), mozilla::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,
                                     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_(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, mozilla::Forward<KeyInput>(key), mozilla::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() = mozilla::Forward<ValueInput>(value);
            return true;
        }
        return add(p, mozilla::Forward<KeyInput>(key), mozilla::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>
class InlineSet
{
    using Set = HashSet<T, HashPolicy, AllocPolicy>;

    struct InlineEntry
    {
        T key;

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

        MOZ_MUST_USE bool moveTo(Set& set) {
            return set.putNew(mozilla::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,
                                     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_(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, mozilla::Forward<TInput>(key));
    }

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

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

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

} // namespace js

#endif // ds_InlineTable_h