diff options
author | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
---|---|---|
committer | Matt A. Tobin <mattatobin@localhost.localdomain> | 2018-02-02 04:16:08 -0500 |
commit | 5f8de423f190bbb79a62f804151bc24824fa32d8 (patch) | |
tree | 10027f336435511475e392454359edea8e25895d /js/src/ds/InlineTable.h | |
parent | 49ee0794b5d912db1f95dce6eb52d781dc210db5 (diff) | |
download | UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.gz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.lz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.tar.xz UXP-5f8de423f190bbb79a62f804151bc24824fa32d8.zip |
Add m-esr52 at 52.6.0
Diffstat (limited to 'js/src/ds/InlineTable.h')
-rw-r--r-- | js/src/ds/InlineTable.h | 687 |
1 files changed, 687 insertions, 0 deletions
diff --git a/js/src/ds/InlineTable.h b/js/src/ds/InlineTable.h new file mode 100644 index 000000000..5b648735f --- /dev/null +++ b/js/src/ds/InlineTable.h @@ -0,0 +1,687 @@ +/* -*- 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 |