687 lines
17 KiB
C++
687 lines
17 KiB
C++
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
|
|
* 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
|