diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 14:29:10 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 14:29:10 +0000 |
commit | 2aa4a82499d4becd2284cdb482213d541b8804dd (patch) | |
tree | b80bf8bf13c3766139fbacc530efd0dd9d54394c /js/src/ds/InlineTable.h | |
parent | Initial commit. (diff) | |
download | firefox-upstream.tar.xz firefox-upstream.zip |
Adding upstream version 86.0.1.upstream/86.0.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'js/src/ds/InlineTable.h')
-rw-r--r-- | js/src/ds/InlineTable.h | 645 |
1 files changed, 645 insertions, 0 deletions
diff --git a/js/src/ds/InlineTable.h b/js/src/ds/InlineTable.h new file mode 100644 index 0000000000..dc898b0c50 --- /dev/null +++ b/js/src/ds/InlineTable.h @@ -0,0 +1,645 @@ +/* -*- 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 |