blob: 0172986d1f8638f922d0a7dada9a43d6a667de1f [file] [log] [blame]
// Copyright 2018 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#ifndef V8_OBJECTS_ORDERED_HASH_TABLE_H_
#define V8_OBJECTS_ORDERED_HASH_TABLE_H_
#include "src/base/export-template.h"
#include "src/common/globals.h"
#include "src/objects/fixed-array.h"
#include "src/objects/internal-index.h"
#include "src/objects/js-objects.h"
#include "src/objects/smi.h"
#include "src/roots/roots.h"
// Has to be the last include (doesn't have include guards):
#include "src/objects/object-macros.h"
namespace v8 {
namespace internal {
// OrderedHashTable is a HashTable with Object keys that preserves
// insertion order. There are Map and Set interfaces (OrderedHashMap
// and OrderedHashTable, below). It is meant to be used by JSMap/JSSet.
//
// Only Object keys are supported, with Object::SameValueZero() used as the
// equality operator and Object::GetHash() for the hash function.
//
// Based on the "Deterministic Hash Table" as described by Jason Orendorff at
// https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
// Originally attributed to Tyler Close.
//
// Memory layout:
// [0] : Prefix
// [kPrefixSize]: element count
// [kPrefixSize + 1]: deleted element count
// [kPrefixSize + 2]: bucket count
// [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfBuckets() - 1)]: "hash table",
// where each item is an offset into the
// data table (see below) where the first
// item in this bucket is stored.
// [kPrefixSize + 3 + NumberOfBuckets()..length]: "data table", an
// array of length Capacity() * kEntrySize,
// where the first entrysize items are
// handled by the derived class and the
// item at kChainOffset is another entry
// into the data table indicating the next
// entry in this hash bucket.
//
// When we transition the table to a new version we obsolete it and reuse parts
// of the memory to store information how to transition an iterator to the new
// table:
//
// Memory layout for obsolete table:
// [0] : Prefix
// [kPrefixSize + 0]: Next newer table
// [kPrefixSize + 1]: deleted element count or kClearedTableSentinel if
// the table was cleared
// [kPrefixSize + 2]: bucket count
// [kPrefixSize + 3..(kPrefixSize + 3 + NumberOfDeletedElements() - 1)]:
// The indexes of the removed holes. This part is only
// usable for non-cleared tables, as clearing removes the
// deleted elements count.
// [kPrefixSize + 3 + NumberOfDeletedElements()..length]: Not used
template <class Derived, int entrysize>
class OrderedHashTable : public FixedArray {
public:
// Returns an OrderedHashTable (possibly |table|) with enough space
// to add at least one new element.
static MaybeHandle<Derived> EnsureGrowable(Isolate* isolate,
Handle<Derived> table);
// Returns an OrderedHashTable (possibly |table|) that's shrunken
// if possible.
static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
// Returns a new empty OrderedHashTable and records the clearing so that
// existing iterators can be updated.
static Handle<Derived> Clear(Isolate* isolate, Handle<Derived> table);
// Returns true if the OrderedHashTable contains the key
static bool HasKey(Isolate* isolate, Derived table, Object key);
// Returns whether a potential key |k| returned by KeyAt is a real
// key (meaning that it is not a hole).
static inline bool IsKey(ReadOnlyRoots roots, Object k);
// Returns a true value if the OrderedHashTable contains the key and
// the key has been deleted. This does not shrink the table.
static bool Delete(Isolate* isolate, Derived table, Object key);
InternalIndex FindEntry(Isolate* isolate, Object key);
Object SlowReverseLookup(Isolate* isolate, Object value);
int NumberOfElements() const {
return Smi::ToInt(get(NumberOfElementsIndex()));
}
int NumberOfDeletedElements() const {
return Smi::ToInt(get(NumberOfDeletedElementsIndex()));
}
// Returns the number of contiguous entries in the data table, starting at 0,
// that either are real entries or have been deleted.
int UsedCapacity() const {
return NumberOfElements() + NumberOfDeletedElements();
}
int NumberOfBuckets() const {
return Smi::ToInt(get(NumberOfBucketsIndex()));
}
InternalIndex::Range IterateEntries() {
return InternalIndex::Range(UsedCapacity());
}
// use IsKey to check if this is a deleted entry.
Object KeyAt(InternalIndex entry) {
DCHECK_LT(entry.as_int(), this->UsedCapacity());
return get(EntryToIndex(entry));
}
// Similar to KeyAt, but indicates whether the given entry is valid
// (not deleted one)
bool ToKey(ReadOnlyRoots roots, InternalIndex entry, Object* out_key);
bool IsObsolete() { return !get(NextTableIndex()).IsSmi(); }
// The next newer table. This is only valid if the table is obsolete.
Derived NextTable() { return Derived::cast(get(NextTableIndex())); }
// When the table is obsolete we store the indexes of the removed holes.
int RemovedIndexAt(int index) {
return Smi::ToInt(get(RemovedHolesIndex() + index));
}
// The extra +1 is for linking the bucket chains together.
static const int kEntrySize = entrysize + 1;
static const int kEntrySizeWithoutChain = entrysize;
static const int kChainOffset = entrysize;
static const int kNotFound = -1;
// The minimum capacity. Note that despite this value, 0 is also a permitted
// capacity, indicating a table without any storage for elements.
static const int kInitialCapacity = 4;
static constexpr int PrefixIndex() { return 0; }
static constexpr int NumberOfElementsIndex() { return Derived::kPrefixSize; }
// The next table is stored at the same index as the nof elements.
static constexpr int NextTableIndex() { return NumberOfElementsIndex(); }
static constexpr int NumberOfDeletedElementsIndex() {
return NumberOfElementsIndex() + 1;
}
static constexpr int NumberOfBucketsIndex() {
return NumberOfDeletedElementsIndex() + 1;
}
static constexpr int HashTableStartIndex() {
return NumberOfBucketsIndex() + 1;
}
static constexpr int RemovedHolesIndex() { return HashTableStartIndex(); }
static constexpr int NumberOfElementsOffset() {
return FixedArray::OffsetOfElementAt(NumberOfElementsIndex());
}
static constexpr int NextTableOffset() {
return FixedArray::OffsetOfElementAt(NextTableIndex());
}
static constexpr int NumberOfDeletedElementsOffset() {
return FixedArray::OffsetOfElementAt(NumberOfDeletedElementsIndex());
}
static constexpr int NumberOfBucketsOffset() {
return FixedArray::OffsetOfElementAt(NumberOfBucketsIndex());
}
static constexpr int HashTableStartOffset() {
return FixedArray::OffsetOfElementAt(HashTableStartIndex());
}
static const int kLoadFactor = 2;
// NumberOfDeletedElements is set to kClearedTableSentinel when
// the table is cleared, which allows iterator transitions to
// optimize that case.
static const int kClearedTableSentinel = -1;
static constexpr int MaxCapacity() {
return (FixedArray::kMaxLength - HashTableStartIndex()) /
(1 + (kEntrySize * kLoadFactor));
}
protected:
// Returns an OrderedHashTable with a capacity of at least |capacity|.
static MaybeHandle<Derived> Allocate(
Isolate* isolate, int capacity,
AllocationType allocation = AllocationType::kYoung);
static MaybeHandle<Derived> AllocateEmpty(Isolate* isolate,
AllocationType allocation,
RootIndex root_ndex);
static MaybeHandle<Derived> Rehash(Isolate* isolate, Handle<Derived> table);
static MaybeHandle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
int new_capacity);
int HashToEntryRaw(int hash) {
int bucket = HashToBucket(hash);
Object entry = this->get(HashTableStartIndex() + bucket);
int entry_int = Smi::ToInt(entry);
DCHECK(entry_int == kNotFound || entry_int >= 0);
return entry_int;
}
int NextChainEntryRaw(int entry) {
DCHECK_LT(entry, this->UsedCapacity());
Object next_entry = get(EntryToIndexRaw(entry) + kChainOffset);
int next_entry_int = Smi::ToInt(next_entry);
DCHECK(next_entry_int == kNotFound || next_entry_int >= 0);
return next_entry_int;
}
// Returns an index into |this| for the given entry.
int EntryToIndexRaw(int entry) {
return HashTableStartIndex() + NumberOfBuckets() + (entry * kEntrySize);
}
int EntryToIndex(InternalIndex entry) {
return EntryToIndexRaw(entry.as_int());
}
int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
void SetNumberOfBuckets(int num) {
set(NumberOfBucketsIndex(), Smi::FromInt(num));
}
void SetNumberOfElements(int num) {
set(NumberOfElementsIndex(), Smi::FromInt(num));
}
void SetNumberOfDeletedElements(int num) {
set(NumberOfDeletedElementsIndex(), Smi::FromInt(num));
}
// Returns the number elements that can fit into the allocated buffer.
int Capacity() { return NumberOfBuckets() * kLoadFactor; }
void SetNextTable(Derived next_table) { set(NextTableIndex(), next_table); }
void SetRemovedIndexAt(int index, int removed_index) {
return set(RemovedHolesIndex() + index, Smi::FromInt(removed_index));
}
OBJECT_CONSTRUCTORS(OrderedHashTable, FixedArray);
private:
friend class OrderedNameDictionaryHandler;
};
class V8_EXPORT_PRIVATE OrderedHashSet
: public OrderedHashTable<OrderedHashSet, 1> {
using Base = OrderedHashTable<OrderedHashSet, 1>;
public:
DECL_CAST(OrderedHashSet)
static MaybeHandle<OrderedHashSet> Add(Isolate* isolate,
Handle<OrderedHashSet> table,
Handle<Object> value);
static Handle<FixedArray> ConvertToKeysArray(Isolate* isolate,
Handle<OrderedHashSet> table,
GetKeysConversion convert);
static MaybeHandle<OrderedHashSet> Rehash(Isolate* isolate,
Handle<OrderedHashSet> table,
int new_capacity);
static MaybeHandle<OrderedHashSet> Rehash(Isolate* isolate,
Handle<OrderedHashSet> table);
static MaybeHandle<OrderedHashSet> Allocate(
Isolate* isolate, int capacity,
AllocationType allocation = AllocationType::kYoung);
static MaybeHandle<OrderedHashSet> AllocateEmpty(
Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);
static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static inline bool Is(Handle<HeapObject> table);
static const int kPrefixSize = 0;
OBJECT_CONSTRUCTORS(OrderedHashSet, OrderedHashTable<OrderedHashSet, 1>);
};
class V8_EXPORT_PRIVATE OrderedHashMap
: public OrderedHashTable<OrderedHashMap, 2> {
using Base = OrderedHashTable<OrderedHashMap, 2>;
public:
DECL_CAST(OrderedHashMap)
// Returns a value if the OrderedHashMap contains the key, otherwise
// returns undefined.
static MaybeHandle<OrderedHashMap> Add(Isolate* isolate,
Handle<OrderedHashMap> table,
Handle<Object> key,
Handle<Object> value);
static MaybeHandle<OrderedHashMap> Allocate(
Isolate* isolate, int capacity,
AllocationType allocation = AllocationType::kYoung);
static MaybeHandle<OrderedHashMap> AllocateEmpty(
Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);
static MaybeHandle<OrderedHashMap> Rehash(Isolate* isolate,
Handle<OrderedHashMap> table,
int new_capacity);
static MaybeHandle<OrderedHashMap> Rehash(Isolate* isolate,
Handle<OrderedHashMap> table);
Object ValueAt(InternalIndex entry);
// This takes and returns raw Address values containing tagged Object
// pointers because it is called via ExternalReference.
static Address GetHash(Isolate* isolate, Address raw_key);
static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static inline bool Is(Handle<HeapObject> table);
static const int kValueOffset = 1;
static const int kPrefixSize = 0;
OBJECT_CONSTRUCTORS(OrderedHashMap, OrderedHashTable<OrderedHashMap, 2>);
};
// This is similar to the OrderedHashTable, except for the memory
// layout where we use byte instead of Smi. The max capacity of this
// is only 254, we transition to an OrderedHashTable beyond that
// limit.
//
// Each bucket and chain value is a byte long. The padding exists so
// that the DataTable entries start aligned. A bucket or chain value
// of 255 is used to denote an unknown entry.
//
// The prefix size is calculated as the kPrefixSize * kTaggedSize.
//
// Memory layout: [ Prefix ] [ Header ] [ Padding ] [ DataTable ] [ HashTable ]
// [ Chains ]
//
// The index are represented as bytes, on a 64 bit machine with
// kEntrySize = 1, capacity = 4 and entries = 2:
//
// [ 0 ] : Prefix
//
// Note: For the sake of brevity, the following start with index 0
// but, they actually start from kPrefixSize * kTaggedSize to
// account for the the prefix.
//
// [ Header ] :
// [0] : Number of elements
// [1] : Number of deleted elements
// [2] : Number of buckets
//
// [ Padding ] :
// [3 .. 7] : Padding
//
// [ DataTable ] :
// [8 .. 15] : Entry 1
// [16 .. 23] : Entry 2
// [24 .. 31] : empty
// [32 .. 39] : empty
//
// [ HashTable ] :
// [40] : First chain-link for bucket 1
// [41] : empty
//
// [ Chains ] :
// [42] : Next chain link for bucket 1
// [43] : empty
// [44] : empty
// [45] : empty
//
template <class Derived>
class SmallOrderedHashTable : public HeapObject {
public:
// Offset points to a relative location in the table
using Offset = int;
// ByteIndex points to a index in the table that needs to be
// converted to an Offset.
using ByteIndex = int;
void Initialize(Isolate* isolate, int capacity);
static Handle<Derived> Allocate(
Isolate* isolate, int capacity,
AllocationType allocation = AllocationType::kYoung);
// Returns a true if the OrderedHashTable contains the key
bool HasKey(Isolate* isolate, Handle<Object> key);
// Returns a true value if the table contains the key and
// the key has been deleted. This does not shrink the table.
static bool Delete(Isolate* isolate, Derived table, Object key);
// Returns an SmallOrderedHashTable (possibly |table|) with enough
// space to add at least one new element. Returns empty handle if
// we've already reached MaxCapacity.
static MaybeHandle<Derived> Grow(Isolate* isolate, Handle<Derived> table);
InternalIndex FindEntry(Isolate* isolate, Object key);
static Handle<Derived> Shrink(Isolate* isolate, Handle<Derived> table);
// Iterates only fields in the DataTable.
class BodyDescriptor;
// Returns total size in bytes required for a table of given
// capacity.
static int SizeFor(int capacity) {
DCHECK_GE(capacity, kMinCapacity);
DCHECK_LE(capacity, kMaxCapacity);
int data_table_size = DataTableSizeFor(capacity);
int hash_table_size = capacity / kLoadFactor;
int chain_table_size = capacity;
int total_size = DataTableStartOffset() + data_table_size +
hash_table_size + chain_table_size;
return RoundUp(total_size, kTaggedSize);
}
// Returns the number elements that can fit into the allocated table.
int Capacity() const {
int capacity = NumberOfBuckets() * kLoadFactor;
DCHECK_GE(capacity, kMinCapacity);
DCHECK_LE(capacity, kMaxCapacity);
return capacity;
}
// Returns the number elements that are present in the table.
int NumberOfElements() const {
int nof_elements = getByte(NumberOfElementsOffset(), 0);
DCHECK_LE(nof_elements, Capacity());
return nof_elements;
}
int NumberOfDeletedElements() const {
int nof_deleted_elements = getByte(NumberOfDeletedElementsOffset(), 0);
DCHECK_LE(nof_deleted_elements, Capacity());
return nof_deleted_elements;
}
int NumberOfBuckets() const { return getByte(NumberOfBucketsOffset(), 0); }
V8_INLINE Object KeyAt(InternalIndex entry) const;
InternalIndex::Range IterateEntries() {
return InternalIndex::Range(UsedCapacity());
}
DECL_VERIFIER(SmallOrderedHashTable)
static const int kMinCapacity = 4;
static const byte kNotFound = 0xFF;
// We use the value 255 to indicate kNotFound for chain and bucket
// values, which means that this value can't be used a valid
// index.
static const int kMaxCapacity = 254;
STATIC_ASSERT(kMaxCapacity < kNotFound);
// The load factor is used to derive the number of buckets from
// capacity during Allocation. We also depend on this to calaculate
// the capacity from number of buckets after allocation. If we
// decide to change kLoadFactor to something other than 2, capacity
// should be stored as another field of this object.
static const int kLoadFactor = 2;
// Our growth strategy involves doubling the capacity until we reach
// kMaxCapacity, but since the kMaxCapacity is always less than 256,
// we will never fully utilize this table. We special case for 256,
// by changing the new capacity to be kMaxCapacity in
// SmallOrderedHashTable::Grow.
static const int kGrowthHack = 256;
protected:
static Handle<Derived> Rehash(Isolate* isolate, Handle<Derived> table,
int new_capacity);
void SetDataEntry(int entry, int relative_index, Object value);
// TODO(gsathya): Calculate all the various possible values for this
// at compile time since capacity can only be 4 different values.
Offset GetBucketsStartOffset() const {
int capacity = Capacity();
int data_table_size = DataTableSizeFor(capacity);
return DataTableStartOffset() + data_table_size;
}
Address GetHashTableStartAddress(int capacity) const {
return field_address(DataTableStartOffset() + DataTableSizeFor(capacity));
}
void SetFirstEntry(int bucket, byte value) {
DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
setByte(GetBucketsStartOffset(), bucket, value);
}
int GetFirstEntry(int bucket) const {
DCHECK_LE(static_cast<unsigned>(bucket), NumberOfBuckets());
return getByte(GetBucketsStartOffset(), bucket);
}
// TODO(gsathya): Calculate all the various possible values for this
// at compile time since capacity can only be 4 different values.
Offset GetChainTableOffset() const {
int nof_buckets = NumberOfBuckets();
int capacity = nof_buckets * kLoadFactor;
DCHECK_EQ(Capacity(), capacity);
int data_table_size = DataTableSizeFor(capacity);
int hash_table_size = nof_buckets;
return DataTableStartOffset() + data_table_size + hash_table_size;
}
void SetNextEntry(int entry, int next_entry) {
DCHECK_LT(static_cast<unsigned>(entry), Capacity());
DCHECK_GE(static_cast<unsigned>(next_entry), 0);
DCHECK(next_entry <= Capacity() || next_entry == kNotFound);
setByte(GetChainTableOffset(), entry, next_entry);
}
int GetNextEntry(int entry) const {
DCHECK_LT(entry, Capacity());
return getByte(GetChainTableOffset(), entry);
}
V8_INLINE Object GetDataEntry(int entry, int relative_index);
int HashToBucket(int hash) const { return hash & (NumberOfBuckets() - 1); }
int HashToFirstEntry(int hash) const {
int bucket = HashToBucket(hash);
int entry = GetFirstEntry(bucket);
DCHECK(entry < Capacity() || entry == kNotFound);
return entry;
}
void SetNumberOfBuckets(int num) { setByte(NumberOfBucketsOffset(), 0, num); }
void SetNumberOfElements(int num) {
DCHECK_LE(static_cast<unsigned>(num), Capacity());
setByte(NumberOfElementsOffset(), 0, num);
}
void SetNumberOfDeletedElements(int num) {
DCHECK_LE(static_cast<unsigned>(num), Capacity());
setByte(NumberOfDeletedElementsOffset(), 0, num);
}
static constexpr Offset PrefixOffset() { return kHeaderSize; }
static constexpr Offset NumberOfElementsOffset() {
return PrefixOffset() + (Derived::kPrefixSize * kTaggedSize);
}
static constexpr Offset NumberOfDeletedElementsOffset() {
return NumberOfElementsOffset() + kOneByteSize;
}
static constexpr Offset NumberOfBucketsOffset() {
return NumberOfDeletedElementsOffset() + kOneByteSize;
}
static constexpr Offset PaddingOffset() {
return NumberOfBucketsOffset() + kOneByteSize;
}
static constexpr size_t PaddingSize() {
return RoundUp<kTaggedSize>(PaddingOffset()) - PaddingOffset();
}
static constexpr Offset DataTableStartOffset() {
return PaddingOffset() + PaddingSize();
}
static constexpr int DataTableSizeFor(int capacity) {
return capacity * Derived::kEntrySize * kTaggedSize;
}
// This is used for accessing the non |DataTable| part of the
// structure.
byte getByte(Offset offset, ByteIndex index) const {
DCHECK(offset < DataTableStartOffset() ||
offset >= GetBucketsStartOffset());
return ReadField<byte>(offset + (index * kOneByteSize));
}
void setByte(Offset offset, ByteIndex index, byte value) {
DCHECK(offset < DataTableStartOffset() ||
offset >= GetBucketsStartOffset());
WriteField<byte>(offset + (index * kOneByteSize), value);
}
Offset GetDataEntryOffset(int entry, int relative_index) const {
DCHECK_LT(entry, Capacity());
int offset_in_datatable = entry * Derived::kEntrySize * kTaggedSize;
int offset_in_entry = relative_index * kTaggedSize;
return DataTableStartOffset() + offset_in_datatable + offset_in_entry;
}
int UsedCapacity() const {
int used = NumberOfElements() + NumberOfDeletedElements();
DCHECK_LE(used, Capacity());
return used;
}
private:
friend class OrderedHashMapHandler;
friend class OrderedHashSetHandler;
friend class OrderedNameDictionaryHandler;
friend class CodeStubAssembler;
OBJECT_CONSTRUCTORS(SmallOrderedHashTable, HeapObject);
};
class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
public:
DECL_CAST(SmallOrderedHashSet)
DECL_PRINTER(SmallOrderedHashSet)
EXPORT_DECL_VERIFIER(SmallOrderedHashSet)
static const int kKeyIndex = 0;
static const int kEntrySize = 1;
static const int kPrefixSize = 0;
// Adds |value| to |table|, if the capacity isn't enough, a new
// table is created. The original |table| is returned if there is
// capacity to store |value| otherwise the new table is returned.
V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashSet> Add(
Isolate* isolate, Handle<SmallOrderedHashSet> table, Handle<Object> key);
V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
SmallOrderedHashSet table, Object key);
V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
static inline bool Is(Handle<HeapObject> table);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static Handle<SmallOrderedHashSet> Rehash(Isolate* isolate,
Handle<SmallOrderedHashSet> table,
int new_capacity);
OBJECT_CONSTRUCTORS(SmallOrderedHashSet,
SmallOrderedHashTable<SmallOrderedHashSet>);
};
STATIC_ASSERT(kSmallOrderedHashSetMinCapacity ==
SmallOrderedHashSet::kMinCapacity);
class SmallOrderedHashMap : public SmallOrderedHashTable<SmallOrderedHashMap> {
public:
DECL_CAST(SmallOrderedHashMap)
DECL_PRINTER(SmallOrderedHashMap)
EXPORT_DECL_VERIFIER(SmallOrderedHashMap)
static const int kKeyIndex = 0;
static const int kValueIndex = 1;
static const int kEntrySize = 2;
static const int kPrefixSize = 0;
// Adds |value| to |table|, if the capacity isn't enough, a new
// table is created. The original |table| is returned if there is
// capacity to store |value| otherwise the new table is returned.
V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedHashMap> Add(
Isolate* isolate, Handle<SmallOrderedHashMap> table, Handle<Object> key,
Handle<Object> value);
V8_EXPORT_PRIVATE static bool Delete(Isolate* isolate,
SmallOrderedHashMap table, Object key);
V8_EXPORT_PRIVATE bool HasKey(Isolate* isolate, Handle<Object> key);
static inline bool Is(Handle<HeapObject> table);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static Handle<SmallOrderedHashMap> Rehash(Isolate* isolate,
Handle<SmallOrderedHashMap> table,
int new_capacity);
OBJECT_CONSTRUCTORS(SmallOrderedHashMap,
SmallOrderedHashTable<SmallOrderedHashMap>);
};
STATIC_ASSERT(kSmallOrderedHashMapMinCapacity ==
SmallOrderedHashMap::kMinCapacity);
// TODO(gsathya): Rename this to OrderedHashTable, after we rename
// OrderedHashTable to LargeOrderedHashTable. Also set up a
// OrderedHashSetBase class as a base class for the two tables and use
// that instead of a HeapObject here.
template <class SmallTable, class LargeTable>
class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) OrderedHashTableHandler {
public:
using Entry = int;
static MaybeHandle<HeapObject> Allocate(Isolate* isolate, int capacity);
static bool Delete(Isolate* isolate, Handle<HeapObject> table,
Handle<Object> key);
static bool HasKey(Isolate* isolate, Handle<HeapObject> table,
Handle<Object> key);
// TODO(gsathya): Move this to OrderedHashTable
static const int OrderedHashTableMinSize =
SmallOrderedHashTable<SmallTable>::kGrowthHack << 1;
};
extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap>;
class V8_EXPORT_PRIVATE OrderedHashMapHandler
: public OrderedHashTableHandler<SmallOrderedHashMap, OrderedHashMap> {
public:
static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
Handle<Object> key, Handle<Object> value);
static MaybeHandle<OrderedHashMap> AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedHashMap> table);
};
extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet>;
class V8_EXPORT_PRIVATE OrderedHashSetHandler
: public OrderedHashTableHandler<SmallOrderedHashSet, OrderedHashSet> {
public:
static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
Handle<Object> key);
static MaybeHandle<OrderedHashSet> AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedHashSet> table);
};
class V8_EXPORT_PRIVATE OrderedNameDictionary
: public OrderedHashTable<OrderedNameDictionary, 3> {
using Base = OrderedHashTable<OrderedNameDictionary, 3>;
public:
DECL_CAST(OrderedNameDictionary)
static MaybeHandle<OrderedNameDictionary> Add(
Isolate* isolate, Handle<OrderedNameDictionary> table, Handle<Name> key,
Handle<Object> value, PropertyDetails details);
void SetEntry(InternalIndex entry, Object key, Object value,
PropertyDetails details);
InternalIndex FindEntry(Isolate* isolate, Object key);
int NumberOfEnumerableProperties();
Object SlowReverseLookup(Isolate* isolate, Object value);
static Handle<OrderedNameDictionary> DeleteEntry(
Isolate* isolate, Handle<OrderedNameDictionary> table,
InternalIndex entry);
static MaybeHandle<OrderedNameDictionary> Allocate(
Isolate* isolate, int capacity,
AllocationType allocation = AllocationType::kYoung);
static MaybeHandle<OrderedNameDictionary> AllocateEmpty(
Isolate* isolate, AllocationType allocation = AllocationType::kReadOnly);
static MaybeHandle<OrderedNameDictionary> Rehash(
Isolate* isolate, Handle<OrderedNameDictionary> table, int new_capacity);
// Returns the value for entry.
inline Object ValueAt(InternalIndex entry);
// Like KeyAt, but casts to Name
inline Name NameAt(InternalIndex entry);
// Set the value for entry.
inline void ValueAtPut(InternalIndex entry, Object value);
// Returns the property details for the property at entry.
inline PropertyDetails DetailsAt(InternalIndex entry);
// Set the details for entry.
inline void DetailsAtPut(InternalIndex entry, PropertyDetails value);
inline void SetHash(int hash);
inline int Hash();
static HeapObject GetEmpty(ReadOnlyRoots ro_roots);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static inline bool Is(Handle<HeapObject> table);
static const int kValueOffset = 1;
static const int kPropertyDetailsOffset = 2;
static const int kPrefixSize = 1;
static const bool kIsOrderedDictionaryType = true;
OBJECT_CONSTRUCTORS(OrderedNameDictionary,
OrderedHashTable<OrderedNameDictionary, 3>);
};
extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
OrderedHashTableHandler<SmallOrderedNameDictionary, OrderedNameDictionary>;
class V8_EXPORT_PRIVATE OrderedNameDictionaryHandler
: public OrderedHashTableHandler<SmallOrderedNameDictionary,
OrderedNameDictionary> {
public:
static MaybeHandle<HeapObject> Add(Isolate* isolate, Handle<HeapObject> table,
Handle<Name> key, Handle<Object> value,
PropertyDetails details);
static Handle<HeapObject> Shrink(Isolate* isolate, Handle<HeapObject> table);
static Handle<HeapObject> DeleteEntry(Isolate* isolate,
Handle<HeapObject> table,
InternalIndex entry);
static InternalIndex FindEntry(Isolate* isolate, HeapObject table, Name key);
static void SetEntry(HeapObject table, InternalIndex entry, Object key,
Object value, PropertyDetails details);
// Returns the value for entry.
static Object ValueAt(HeapObject table, InternalIndex entry);
// Set the value for entry.
static void ValueAtPut(HeapObject table, InternalIndex entry, Object value);
// Returns the property details for the property at entry.
static PropertyDetails DetailsAt(HeapObject table, InternalIndex entry);
// Set the details for entry.
static void DetailsAtPut(HeapObject table, InternalIndex entry,
PropertyDetails value);
static Name KeyAt(HeapObject table, InternalIndex entry);
static void SetHash(HeapObject table, int hash);
static int Hash(HeapObject table);
static int NumberOfElements(HeapObject table);
static int Capacity(HeapObject table);
protected:
static MaybeHandle<OrderedNameDictionary> AdjustRepresentation(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table);
};
class SmallOrderedNameDictionary
: public SmallOrderedHashTable<SmallOrderedNameDictionary> {
public:
DECL_CAST(SmallOrderedNameDictionary)
DECL_PRINTER(SmallOrderedNameDictionary)
DECL_VERIFIER(SmallOrderedNameDictionary)
// Returns the value for entry.
inline Object ValueAt(InternalIndex entry);
static Handle<SmallOrderedNameDictionary> Rehash(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
int new_capacity);
V8_EXPORT_PRIVATE static Handle<SmallOrderedNameDictionary> DeleteEntry(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
InternalIndex entry);
// Set the value for entry.
inline void ValueAtPut(InternalIndex entry, Object value);
// Returns the property details for the property at entry.
inline PropertyDetails DetailsAt(InternalIndex entry);
// Set the details for entry.
inline void DetailsAtPut(InternalIndex entry, PropertyDetails value);
inline void SetHash(int hash);
inline int Hash();
static const int kKeyIndex = 0;
static const int kValueIndex = 1;
static const int kPropertyDetailsIndex = 2;
static const int kEntrySize = 3;
static const int kPrefixSize = 1;
// Adds |value| to |table|, if the capacity isn't enough, a new
// table is created. The original |table| is returned if there is
// capacity to store |value| otherwise the new table is returned.
V8_EXPORT_PRIVATE static MaybeHandle<SmallOrderedNameDictionary> Add(
Isolate* isolate, Handle<SmallOrderedNameDictionary> table,
Handle<Name> key, Handle<Object> value, PropertyDetails details);
V8_EXPORT_PRIVATE void SetEntry(InternalIndex entry, Object key, Object value,
PropertyDetails details);
static inline Handle<Map> GetMap(ReadOnlyRoots roots);
static inline bool Is(Handle<HeapObject> table);
OBJECT_CONSTRUCTORS(SmallOrderedNameDictionary,
SmallOrderedHashTable<SmallOrderedNameDictionary>);
};
} // namespace internal
} // namespace v8
#include "src/objects/object-macros-undef.h"
#endif // V8_OBJECTS_ORDERED_HASH_TABLE_H_