#include <objects.h>

Inheritance diagram for v8::internal::HashTable< Derived, Shape, Key >:

Collaboration diagram for v8::internal::HashTable< Derived, Shape, Key >:

Public Member Functions
uint32_t	Hash (Key key)

uint32_t	HashForObject (Key key, Object *object)

int	NumberOfElements ()

int	NumberOfDeletedElements ()

int	Capacity ()

void	ElementAdded ()

void	ElementRemoved ()

void	ElementsRemoved (int n)

Object *	KeyAt (int entry)

bool	IsKey (Object *k)

void	IteratePrefix (ObjectVisitor *visitor)

void	IterateElements (ObjectVisitor *visitor)

	INLINE (static uint32_t GetProbeOffset(uint32_t n))

int	FindEntry (Key key)

int	FindEntry (Isolate *isolate, Key key)

void	Rehash (Key key)

Public Member Functions inherited from v8::internal::FixedArray
Object *	get (int index)

void	set (int index, Object *value)

bool	is_the_hole (int index)

void	set (int index, Smi *value)

void	set (int index, Object *value, WriteBarrierMode mode)

void	set_undefined (int index)

void	set_null (int index)

void	set_the_hole (int index)

Object **	GetFirstElementAddress ()

bool	ContainsOnlySmisOrHoles ()

Object **	data_start ()

void	FillWithHoles (int from, int to)

void	Shrink (int length)

void	CopyTo (int pos, FixedArray *dest, int dest_pos, int len)

Object **	RawFieldOfElementAt (int index)

void	SwapPairs (FixedArray *numbers, int i, int j)

void	SortPairs (FixedArray *numbers, uint32_t len)

Public Member Functions inherited from v8::internal::FixedArrayBase
int	length () const

void	set_length (int value)

int	synchronized_length () const

void	synchronized_set_length (int value)

Public Member Functions inherited from v8::internal::HeapObject
Map *	map () const

void	set_map (Map *value)

void	set_map_no_write_barrier (Map *value)

Map *	synchronized_map ()

MapWord	synchronized_map_word () const

void	synchronized_set_map (Map *value)

void	synchronized_set_map_no_write_barrier (Map *value)

void	synchronized_set_map_word (MapWord map_word)

MapWord	map_word () const

void	set_map_word (MapWord map_word)

Heap *	GetHeap () const

Isolate *	GetIsolate () const

Address	address ()

void	Iterate (ObjectVisitor *v)

void	IterateBody (InstanceType type, int object_size, ObjectVisitor *v)

int	Size ()

bool	MayContainRawValues ()

int	SizeFromMap (Map *map)

WriteBarrierMode	GetWriteBarrierMode (const DisallowHeapAllocation &promise)

void	HeapObjectShortPrint (OStream &os)

	STATIC_ASSERT (kMapOffset==Internals::kHeapObjectMapOffset)

Public Member Functions inherited from v8::internal::Object
bool	IsObject () const

	INLINE (bool IsFixedArrayBase() const)

	INLINE (bool IsExternal() const)

	INLINE (bool IsAccessorInfo() const)

	INLINE (bool IsStruct() const)

	INLINE (bool IsSpecObject()) const

	INLINE (bool IsSpecFunction()) const

	INLINE (bool IsTemplateInfo()) const

	INLINE (bool IsNameDictionary() const)

	INLINE (bool IsSeededNumberDictionary() const)

	INLINE (bool IsUnseededNumberDictionary() const)

	INLINE (bool IsOrderedHashSet() const)

	INLINE (bool IsOrderedHashMap() const)

bool	IsCallable () const

	INLINE (bool IsUndefined() const)

	INLINE (bool IsNull() const)

	INLINE (bool IsTheHole() const)

	INLINE (bool IsException() const)

	INLINE (bool IsUninitialized() const)

	INLINE (bool IsTrue() const)

	INLINE (bool IsFalse() const)

	INLINE (bool IsArgumentsMarker() const)

	INLINE (bool IsFiller() const)

double	Number ()

	INLINE (bool IsNaN() const)

	INLINE (bool IsMinusZero() const)

bool	ToInt32 (int32_t *value)

bool	ToUint32 (uint32_t *value)

Representation	OptimalRepresentation ()

bool	FitsRepresentation (Representation representation)

Handle< HeapType >	OptimalType (Isolate *isolate, Representation representation)

bool	HasValidElements ()

bool	HasSpecificClassOf (String *name)

bool	BooleanValue ()

Object *	GetHash ()

bool	SameValue (Object *other)

bool	SameValueZero (Object *other)

bool	ToArrayIndex (uint32_t *index)

bool	IsStringObjectWithCharacterAt (uint32_t index)

void	VerifyApiCallResultType ()

void	ShortPrint (FILE *out=stdout)

void	ShortPrint (StringStream *accumulator)

Static Public Member Functions
static MUST_USE_RESULT Handle< Derived >	New (Isolate *isolate, int at_least_space_for, MinimumCapacity capacity_option=USE_DEFAULT_MINIMUM_CAPACITY, PretenureFlag pretenure=NOT_TENURED)

static int	ComputeCapacity (int at_least_space_for)

Static Public Member Functions inherited from v8::internal::FixedArray
static Handle< Object >	get (Handle< FixedArray > array, int index)

static Handle< FixedArray >	CopySize (Handle< FixedArray > array, int new_length, PretenureFlag pretenure=NOT_TENURED)

static MUST_USE_RESULT MaybeHandle< FixedArray >	AddKeysFromArrayLike (Handle< FixedArray > content, Handle< JSObject > array)

static MUST_USE_RESULT MaybeHandle< FixedArray >	UnionOfKeys (Handle< FixedArray > first, Handle< FixedArray > second)

static int	SizeFor (int length)

static int	OffsetOfElementAt (int index)

Static Public Member Functions inherited from v8::internal::HeapObject
static HeapObject *	FromAddress (Address address)

static Object **	RawField (HeapObject *obj, int offset)

static void	UpdateMapCodeCache (Handle< HeapObject > object, Handle< Name > name, Handle< Code > code)

Static Public Member Functions inherited from v8::internal::Object
static Handle< Object >	NewStorageFor (Isolate *isolate, Handle< Object > object, Representation representation)

static Handle< Object >	WrapForRead (Isolate *isolate, Handle< Object > object, Representation representation)

static MaybeHandle< JSReceiver >	ToObject (Isolate *isolate, Handle< Object > object)

static MaybeHandle< JSReceiver >	ToObject (Isolate *isolate, Handle< Object > object, Handle< Context > context)

static MUST_USE_RESULT MaybeHandle< Smi >	ToSmi (Isolate *isolate, Handle< Object > object)

static MUST_USE_RESULT MaybeHandle< Object >	GetProperty (LookupIterator *it)

static MUST_USE_RESULT MaybeHandle< Object >	SetProperty (Handle< Object > object, Handle< Name > key, Handle< Object > value, StrictMode strict_mode, StoreFromKeyed store_mode=MAY_BE_STORE_FROM_KEYED)

static MUST_USE_RESULT MaybeHandle< Object >	SetProperty (LookupIterator *it, Handle< Object > value, StrictMode strict_mode, StoreFromKeyed store_mode, StorePropertyMode data_store_mode=NORMAL_PROPERTY)

static MUST_USE_RESULT MaybeHandle< Object >	WriteToReadOnlyProperty (LookupIterator *it, Handle< Object > value, StrictMode strict_mode)

static Handle< Object >	SetDataProperty (LookupIterator *it, Handle< Object > value)

static MUST_USE_RESULT MaybeHandle< Object >	AddDataProperty (LookupIterator *it, Handle< Object > value, PropertyAttributes attributes, StrictMode strict_mode, StoreFromKeyed store_mode)

static MUST_USE_RESULT MaybeHandle< Object >	GetPropertyOrElement (Handle< Object > object, Handle< Name > key)

static MUST_USE_RESULT MaybeHandle< Object >	GetProperty (Isolate isolate, Handle< Object > object, const char key)

static MUST_USE_RESULT MaybeHandle< Object >	GetProperty (Handle< Object > object, Handle< Name > key)

static MUST_USE_RESULT MaybeHandle< Object >	GetPropertyWithAccessor (Handle< Object > receiver, Handle< Name > name, Handle< JSObject > holder, Handle< Object > structure)

static MUST_USE_RESULT MaybeHandle< Object >	SetPropertyWithAccessor (Handle< Object > receiver, Handle< Name > name, Handle< Object > value, Handle< JSObject > holder, Handle< Object > structure, StrictMode strict_mode)

static MUST_USE_RESULT MaybeHandle< Object >	GetPropertyWithDefinedGetter (Handle< Object > receiver, Handle< JSReceiver > getter)

static MUST_USE_RESULT MaybeHandle< Object >	SetPropertyWithDefinedSetter (Handle< Object > receiver, Handle< JSReceiver > setter, Handle< Object > value)

static MUST_USE_RESULT MaybeHandle< Object >	GetElement (Isolate *isolate, Handle< Object > object, uint32_t index)

static MUST_USE_RESULT MaybeHandle< Object >	GetElementWithReceiver (Isolate *isolate, Handle< Object > object, Handle< Object > receiver, uint32_t index)

static Handle< Smi >	GetOrCreateHash (Isolate *isolate, Handle< Object > object)

Static Public Attributes
static const int	kNumberOfElementsIndex = 0

static const int	kNumberOfDeletedElementsIndex = 1

static const int	kCapacityIndex = 2

static const int	kPrefixStartIndex = 3

static const int	kElementsStartIndex

static const int	kEntrySize = Shape::kEntrySize

static const int	kElementsStartOffset

static const int	kCapacityOffset

static const int	kNotFound = -1

static const int	kMaxCapacity

Static Public Attributes inherited from v8::internal::FixedArray
static const int	kMaxSize = 128 * MB * kPointerSize

static const int	kMaxLength = (kMaxSize - kHeaderSize) / kPointerSize

Static Public Attributes inherited from v8::internal::FixedArrayBase
static const int	kLengthOffset = HeapObject::kHeaderSize

static const int	kHeaderSize = kLengthOffset + kPointerSize

Static Public Attributes inherited from v8::internal::HeapObject
static const int	kMapOffset = Object::kHeaderSize

static const int	kHeaderSize = kMapOffset + kPointerSize

Static Public Attributes inherited from v8::internal::Object
static const int	kHeaderSize = 0

Protected Member Functions
uint32_t	FindInsertionEntry (uint32_t hash)

void	SetNumberOfElements (int nof)

void	SetNumberOfDeletedElements (int nod)

void	SetCapacity (int capacity)

Protected Member Functions inherited from v8::internal::HeapObject
void	IteratePointers (ObjectVisitor *v, int start, int end)

void	IteratePointer (ObjectVisitor *v, int offset)

void	IterateNextCodeLink (ObjectVisitor *v, int offset)

Static Protected Member Functions
static int	EntryToIndex (int entry)

static uint32_t	GetProbe (uint32_t hash, uint32_t number, uint32_t size)

static uint32_t	FirstProbe (uint32_t hash, uint32_t size)

static uint32_t	NextProbe (uint32_t last, uint32_t number, uint32_t size)

static MUST_USE_RESULT Handle< Derived >	Shrink (Handle< Derived > table, Key key)

static MUST_USE_RESULT Handle< Derived >	EnsureCapacity (Handle< Derived > table, int n, Key key, PretenureFlag pretenure=NOT_TENURED)

Static Protected Member Functions inherited from v8::internal::FixedArray
static void	NoWriteBarrierSet (FixedArray array, int index, Object value)

static void	NoIncrementalWriteBarrierSet (FixedArray array, int index, Object value)

Private Member Functions
uint32_t	EntryForProbe (Key key, Object *k, int probe, uint32_t expected)

void	Swap (uint32_t entry1, uint32_t entry2, WriteBarrierMode mode)

void	Rehash (Handle< Derived > new_table, Key key)

Friends
class	ObjectHashTable

Additional Inherited Members
Public Types inherited from v8::internal::Object
enum	StoreFromKeyed { MAY_BE_STORE_FROM_KEYED , CERTAINLY_NOT_STORE_FROM_KEYED }

enum	StorePropertyMode { NORMAL_PROPERTY , SUPER_PROPERTY }

Detailed Description

template<typename Derived, typename Shape, typename Key>
class v8::internal::HashTable< Derived, Shape, Key >

Definition at line 3190 of file objects.h.

Member Function Documentation

◆ Capacity()

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::Capacity ( )

inline

Definition at line 3220 of file objects.h.

                  {
     return Smi::cast(get(kCapacityIndex))->value();
   }

Referenced by v8::internal::MarkCompactCollector::ClearNonLiveReferences(), v8::internal::MarkCompactCollector::ClearWeakCollections(), v8::internal::V8HeapExplorer::ExtractElementReferences(), v8::internal::V8HeapExplorer::ExtractPropertyReferences(), v8::internal::FreezeDictionary(), v8::internal::JSObject::GetElementsCapacityAndUsage(), v8::internal::PatchIncrementalMarkingRecordWriteStubs(), v8::internal::MarkCompactCollector::ProcessWeakCollections(), v8::internal::JSObject::ShouldConvertToFastDoubleElements(), and v8::internal::JSObject::ShouldConvertToFastElements().

Here is the caller graph for this function:

◆ ComputeCapacity()

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::ComputeCapacity ( int at_least_space_for )

static

Definition at line 3099 of file objects-inl.h.

                                                                           {
   const int kMinCapacity = 32;
   int capacity = base::bits::RoundUpToPowerOfTwo32(at_least_space_for * 2);
   if (capacity < kMinCapacity) {
     capacity = kMinCapacity;  // Guarantee min capacity.
   }
   return capacity;
 }

References v8::base::bits::RoundUpToPowerOfTwo32().

Referenced by v8::internal::JSObject::ShouldConvertToSlowElements().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ElementAdded()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::ElementAdded ( )

inline

Definition at line 3226 of file objects.h.

3226 { SetNumberOfElements(NumberOfElements() + 1); }

v8::internal::HashTable::SetNumberOfElements

void SetNumberOfElements(int nof)

Definition: objects.h:3311

v8::internal::HashTable::NumberOfElements

int NumberOfElements()

Definition: objects.h:3210

◆ ElementRemoved()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::ElementRemoved ( )

inline

Definition at line 3230 of file objects.h.

                         {
     SetNumberOfElements(NumberOfElements() - 1);
     SetNumberOfDeletedElements(NumberOfDeletedElements() + 1);
   }

Referenced by v8::internal::MarkCompactCollector::ClearNonLiveReferences().

Here is the caller graph for this function:

◆ ElementsRemoved()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::ElementsRemoved ( int n )

inline

Definition at line 3234 of file objects.h.

                               {
     SetNumberOfElements(NumberOfElements() - n);
     SetNumberOfDeletedElements(NumberOfDeletedElements() + n);
   }

Referenced by v8::internal::MarkCompactCollector::AfterMarking(), and v8::internal::MarkCompactCollector::ProcessMapCaches().

Here is the caller graph for this function:

◆ EnsureCapacity()

template<typename Derived , typename Shape , typename Key >

Handle< Derived > v8::internal::HashTable< Derived, Shape, Key >::EnsureCapacity	(	Handle< Derived >	table,
		int	n,
		Key	key,
		PretenureFlag	pretenure = `NOT_TENURED`
	)

staticprotected

Definition at line 13928 of file objects.cc.

                              {
   Isolate* isolate = table->GetIsolate();
   int capacity = table->Capacity();
   int nof = table->NumberOfElements() + n;
   int nod = table->NumberOfDeletedElements();
   // Return if:
   //   50% is still free after adding n elements and
   //   at most 50% of the free elements are deleted elements.
   if (nod <= (capacity - nof) >> 1) {
     int needed_free = nof >> 1;
     if (nof + needed_free <= capacity) return table;
   }
  
   const int kMinCapacityForPretenure = 256;
   bool should_pretenure = pretenure == TENURED ||
       ((capacity > kMinCapacityForPretenure) &&
           !isolate->heap()->InNewSpace(*table));
   Handle<Derived> new_table = HashTable::New(
       isolate,
       nof * 2,
       USE_DEFAULT_MINIMUM_CAPACITY,
       should_pretenure ? TENURED : NOT_TENURED);
  
   table->Rehash(new_table, key);
   return new_table;
 }

References v8::internal::Isolate::heap(), v8::internal::Heap::InNewSpace(), v8::internal::HashTable< Derived, Shape, Key >::New(), v8::internal::NOT_TENURED, v8::internal::TENURED, and v8::internal::USE_DEFAULT_MINIMUM_CAPACITY.

Here is the call graph for this function:

◆ EntryForProbe()

template<typename Derived , typename Shape , typename Key >

uint32_t v8::internal::HashTable< Derived, Shape, Key >::EntryForProbe	(	Key	key,
		Object *	k,
		int	probe,
		uint32_t	expected
	)

private

Definition at line 13859 of file objects.cc.

                        {
   uint32_t hash = HashTable::HashForObject(key, k);
   uint32_t capacity = Capacity();
   uint32_t entry = FirstProbe(hash, capacity);
   for (int i = 1; i < probe; i++) {
     if (entry == expected) return expected;
     entry = NextProbe(entry, i, capacity);
   }
   return entry;
 }

References v8::internal::HashTable< Derived, Shape, Key >::HashForObject().

Here is the call graph for this function:

◆ EntryToIndex()

template<typename Derived , typename Shape , typename Key >

static int v8::internal::HashTable< Derived, Shape, Key >::EntryToIndex ( int entry )

inlinestaticprotected

Definition at line 3306 of file objects.h.

                                             {
     return (entry * kEntrySize) + kElementsStartIndex;
   }

Referenced by v8::internal::MarkCompactCollector::ClearNonLiveReferences().

Here is the caller graph for this function:

◆ FindEntry() [1/2]

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::FindEntry	(	Isolate *	isolate,
		Key	key
	)

Definition at line 3117 of file objects-inl.h.

                                                                        {
   uint32_t capacity = Capacity();
   uint32_t entry = FirstProbe(HashTable::Hash(key), capacity);
   uint32_t count = 1;
   // EnsureCapacity will guarantee the hash table is never full.
   while (true) {
     Object* element = KeyAt(entry);
     // Empty entry. Uses raw unchecked accessors because it is called by the
     // string table during bootstrapping.
     if (element == isolate->heap()->raw_unchecked_undefined_value()) break;
     if (element != isolate->heap()->raw_unchecked_the_hole_value() &&
         Shape::IsMatch(key, element)) return entry;
     entry = NextProbe(entry, count++, capacity);
   }
   return kNotFound;
 }

References v8::internal::HashTable< Derived, Shape, Key >::Hash(), v8::internal::Isolate::heap(), and v8::internal::DescriptorArray::kNotFound.

Here is the call graph for this function:

◆ FindEntry() [2/2]

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::FindEntry ( Key key )

inline

Definition at line 3110 of file objects-inl.h.

                                                      {
   return FindEntry(GetIsolate(), key);
 }

References v8::internal::HeapObject::GetIsolate().

Referenced by v8::internal::CopyDictionaryToDoubleElements(), v8::internal::CopyDictionaryToObjectElements(), v8::internal::PropertyICCompiler::FindPreMonomorphic(), v8::internal::JSObject::GetAccessor(), and v8::internal::UpdateGetterSetterInDictionary().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ FindInsertionEntry()

template<typename Derived , typename Shape , typename Key >

uint32_t v8::internal::HashTable< Derived, Shape, Key >::FindInsertionEntry ( uint32_t hash )

protected

Definition at line 13993 of file objects.cc.

                                                                          {
   uint32_t capacity = Capacity();
   uint32_t entry = FirstProbe(hash, capacity);
   uint32_t count = 1;
   // EnsureCapacity will guarantee the hash table is never full.
   while (true) {
     Object* element = KeyAt(entry);
     if (element->IsUndefined() || element->IsTheHole()) break;
     entry = NextProbe(entry, count++, capacity);
   }
   return entry;
 }

◆ FirstProbe()

template<typename Derived , typename Shape , typename Key >

static uint32_t v8::internal::HashTable< Derived, Shape, Key >::FirstProbe	(	uint32_t	hash,
		uint32_t	size
	)

inlinestaticprotected

Definition at line 3337 of file objects.h.

                                                                   {
     return hash & (size - 1);
   }

References size.

◆ GetProbe()

template<typename Derived , typename Shape , typename Key >

static uint32_t v8::internal::HashTable< Derived, Shape, Key >::GetProbe	(	uint32_t	hash,
		uint32_t	number,
		uint32_t	size
	)

inlinestaticprotected

Definition at line 3332 of file objects.h.

                                                                           {
     DCHECK(base::bits::IsPowerOfTwo32(size));
     return (hash + GetProbeOffset(number)) & (size - 1);
   }

References DCHECK, v8::base::bits::IsPowerOfTwo32(), and size.

Here is the call graph for this function:

◆ Hash()

template<typename Derived , typename Shape , typename Key >

uint32_t v8::internal::HashTable< Derived, Shape, Key >::Hash ( Key key )

inline

Definition at line 3193 of file objects.h.

                                 {
     if (Shape::UsesSeed) {
       return Shape::SeededHash(key, GetHeap()->HashSeed());
     } else {
       return Shape::Hash(key);
     }
   }

References v8::internal::Hash().

Referenced by v8::internal::HashTable< Derived, Shape, Key >::FindEntry().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ HashForObject()

template<typename Derived , typename Shape , typename Key >

uint32_t v8::internal::HashTable< Derived, Shape, Key >::HashForObject	(	Key	key,
		Object *	object
	)

inline

Definition at line 3201 of file objects.h.

                                                          {
     if (Shape::UsesSeed) {
       return Shape::SeededHashForObject(key, GetHeap()->HashSeed(), object);
     } else {
       return Shape::HashForObject(key, object);
     }
   }

Referenced by v8::internal::HashTable< Derived, Shape, Key >::EntryForProbe(), and v8::internal::HashTable< Derived, Shape, Key >::Rehash().

Here is the caller graph for this function:

◆ INLINE()

template<typename Derived , typename Shape , typename Key >

v8::internal::HashTable< Derived, Shape, Key >::INLINE ( static uint32_t GetProbeOffsetuint32_t n )

inline

Definition at line 3266 of file objects.h.

                                                      {
     return (n + n * n) >> 1;
   }

◆ IsKey()

template<typename Derived , typename Shape , typename Key >

bool v8::internal::HashTable< Derived, Shape, Key >::IsKey ( Object * k )

inline

Definition at line 3255 of file objects.h.

                         {
     return !k->IsTheHole() && !k->IsUndefined();
   }

Referenced by v8::internal::MarkCompactCollector::ClearNonLiveReferences(), v8::internal::Dictionary< Derived, Shape, Key >::CopyValuesTo(), v8::internal::V8HeapExplorer::ExtractElementReferences(), v8::internal::V8HeapExplorer::ExtractPropertyReferences(), v8::internal::FreezeDictionary(), v8::internal::PatchIncrementalMarkingRecordWriteStubs(), and v8::internal::Dictionary< Derived, Shape, Key >::SlowReverseLookup().

Here is the caller graph for this function:

◆ IterateElements()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::IterateElements ( ObjectVisitor * visitor )

Definition at line 13748 of file objects.cc.

                                                                      {
   IteratePointers(v,
                   kElementsStartOffset,
                   kHeaderSize + length() * kPointerSize);
 }

References v8::internal::HeapObject::IteratePointers(), v8::internal::FixedArrayBase::kHeaderSize, v8::internal::kPointerSize, and v8::internal::FixedArrayBase::length().

Referenced by v8::internal::MarkCompactCollector::AfterMarking().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ IteratePrefix()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::IteratePrefix ( ObjectVisitor * visitor )

Definition at line 13742 of file objects.cc.

                                                                    {
   IteratePointers(v, 0, kElementsStartOffset);
 }

References v8::internal::HeapObject::IteratePointers().

Referenced by v8::internal::MarkCompactCollector::MarkStringTable().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ KeyAt()

template<typename Derived , typename Shape , typename Key >

Object* v8::internal::HashTable< Derived, Shape, Key >::KeyAt ( int entry )

inline

Definition at line 3251 of file objects.h.

3251 { return get(EntryToIndex(entry)); }

v8::internal::HashTable::EntryToIndex

static int EntryToIndex(int entry)

Definition: objects.h:3306

Referenced by v8::internal::MarkCompactCollector::ClearWeakCollections(), v8::internal::Dictionary< Derived, Shape, Key >::CopyValuesTo(), v8::internal::V8HeapExplorer::ExtractElementReferences(), v8::internal::V8HeapExplorer::ExtractPropertyReferences(), v8::internal::FreezeDictionary(), v8::internal::PatchIncrementalMarkingRecordWriteStubs(), v8::internal::MarkCompactCollector::ProcessWeakCollections(), and v8::internal::JSObject::ShouldConvertToFastDoubleElements().

Here is the caller graph for this function:

◆ New()

template<typename Derived , typename Shape , typename Key >

template Handle< NameDictionary > v8::internal::HashTable< Derived, Shape, Key >::New	(	Isolate *	isolate,
		int	at_least_space_for,
		MinimumCapacity	capacity_option = `USE_DEFAULT_MINIMUM_CAPACITY`,
		PretenureFlag	pretenure = `NOT_TENURED`
	)

static

Definition at line 13756 of file objects.cc.

                              {
   DCHECK(0 <= at_least_space_for);
   DCHECK(!capacity_option || base::bits::IsPowerOfTwo32(at_least_space_for));
   int capacity = (capacity_option == USE_CUSTOM_MINIMUM_CAPACITY)
                      ? at_least_space_for
                      : ComputeCapacity(at_least_space_for);
   if (capacity > HashTable::kMaxCapacity) {
     v8::internal::Heap::FatalProcessOutOfMemory("invalid table size", true);
   }
  
   Factory* factory = isolate->factory();
   int length = EntryToIndex(capacity);
   Handle<FixedArray> array = factory->NewFixedArray(length, pretenure);
   array->set_map_no_write_barrier(*factory->hash_table_map());
   Handle<Derived> table = Handle<Derived>::cast(array);
  
   table->SetNumberOfElements(0);
   table->SetNumberOfDeletedElements(0);
   table->SetCapacity(capacity);
   return table;
 }

References v8::internal::Handle< T >::cast(), DCHECK, v8::internal::Isolate::factory(), v8::internal::Heap::FatalProcessOutOfMemory(), v8::base::bits::IsPowerOfTwo32(), v8::internal::HashTable< Derived, Shape, Key >::kMaxCapacity, v8::internal::FixedArrayBase::length(), and v8::internal::USE_CUSTOM_MINIMUM_CAPACITY.

Referenced by v8::internal::HashTable< Derived, Shape, Key >::EnsureCapacity(), and v8::internal::HashTable< Derived, Shape, Key >::Shrink().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ NextProbe()

template<typename Derived , typename Shape , typename Key >

static uint32_t v8::internal::HashTable< Derived, Shape, Key >::NextProbe	(	uint32_t	last,
		uint32_t	number,
		uint32_t	size
	)

inlinestaticprotected

Definition at line 3341 of file objects.h.

                                                      {
     return (last + number) & (size - 1);
   }

References size.

◆ NumberOfDeletedElements()

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::NumberOfDeletedElements ( )

inline

Definition at line 3215 of file objects.h.

                                 {
     return Smi::cast(get(kNumberOfDeletedElementsIndex))->value();
   }

◆ NumberOfElements()

template<typename Derived , typename Shape , typename Key >

int v8::internal::HashTable< Derived, Shape, Key >::NumberOfElements ( )

inline

Definition at line 3210 of file objects.h.

                          {
     return Smi::cast(get(kNumberOfElementsIndex))->value();
   }

Referenced by v8::internal::JSObject::GetElementsCapacityAndUsage(), and v8::internal::MarkCompactCollector::ProcessMapCaches().

Here is the caller graph for this function:

◆ Rehash() [1/2]

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::Rehash	(	Handle< Derived >	new_table,
		Key	key
	)

private

Definition at line 13824 of file objects.cc.

              {
   DCHECK(NumberOfElements() < new_table->Capacity());
  
   DisallowHeapAllocation no_gc;
   WriteBarrierMode mode = new_table->GetWriteBarrierMode(no_gc);
  
   // Copy prefix to new array.
   for (int i = kPrefixStartIndex;
        i < kPrefixStartIndex + Shape::kPrefixSize;
        i++) {
     new_table->set(i, get(i), mode);
   }
  
   // Rehash the elements.
   int capacity = Capacity();
   for (int i = 0; i < capacity; i++) {
     uint32_t from_index = EntryToIndex(i);
     Object* k = get(from_index);
     if (IsKey(k)) {
       uint32_t hash = HashTable::HashForObject(key, k);
       uint32_t insertion_index =
           EntryToIndex(new_table->FindInsertionEntry(hash));
       for (int j = 0; j < Shape::kEntrySize; j++) {
         new_table->set(insertion_index + j, get(from_index + j), mode);
       }
     }
   }
   new_table->SetNumberOfElements(NumberOfElements());
   new_table->SetNumberOfDeletedElements(0);
 }

References DCHECK, v8::internal::FixedArray::get(), v8::internal::HashTable< Derived, Shape, Key >::HashForObject(), and mode().

Here is the call graph for this function:

◆ Rehash() [2/2]

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::Rehash ( Key key )

Definition at line 13895 of file objects.cc.

                                                    {
   DisallowHeapAllocation no_gc;
   WriteBarrierMode mode = GetWriteBarrierMode(no_gc);
   uint32_t capacity = Capacity();
   bool done = false;
   for (int probe = 1; !done; probe++) {
     // All elements at entries given by one of the first _probe_ probes
     // are placed correctly. Other elements might need to be moved.
     done = true;
     for (uint32_t current = 0; current < capacity; current++) {
       Object* current_key = get(EntryToIndex(current));
       if (IsKey(current_key)) {
         uint32_t target = EntryForProbe(key, current_key, probe, current);
         if (current == target) continue;
         Object* target_key = get(EntryToIndex(target));
         if (!IsKey(target_key) ||
             EntryForProbe(key, target_key, probe, target) != target) {
           // Put the current element into the correct position.
           Swap(current, target, mode);
           // The other element will be processed on the next iteration.
           current--;
         } else {
           // The place for the current element is occupied. Leave the element
           // for the next probe.
           done = false;
         }
       }
     }
   }
 }

References v8::internal::FixedArray::get(), v8::internal::HeapObject::GetWriteBarrierMode(), and mode().

Referenced by v8::internal::MarkCompactCollector::EvacuateNewSpaceAndCandidates().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ SetCapacity()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::SetCapacity ( int capacity )

inlineprotected

Definition at line 3321 of file objects.h.

                                  {
     // To scale a computed hash code to fit within the hash table, we
     // use bit-wise AND with a mask, so the capacity must be positive
     // and non-zero.
     DCHECK(capacity > 0);
     DCHECK(capacity <= kMaxCapacity);
     set(kCapacityIndex, Smi::FromInt(capacity));
   }

References DCHECK, and v8::internal::Smi::FromInt().

Here is the call graph for this function:

◆ SetNumberOfDeletedElements()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::SetNumberOfDeletedElements ( int nod )

inlineprotected

Definition at line 3316 of file objects.h.

                                            {
     set(kNumberOfDeletedElementsIndex, Smi::FromInt(nod));
   }

References v8::internal::Smi::FromInt().

Here is the call graph for this function:

◆ SetNumberOfElements()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::SetNumberOfElements ( int nof )

inlineprotected

Definition at line 3311 of file objects.h.

                                     {
     set(kNumberOfElementsIndex, Smi::FromInt(nof));
   }

References v8::internal::Smi::FromInt().

Here is the call graph for this function:

◆ Shrink()

template<typename Derived , typename Shape , typename Key >

template Handle< SeededNumberDictionary > v8::internal::HashTable< Derived, Shape, Key >::Shrink	(	Handle< Derived >	table,
		Key	key
	)

staticprotected

Definition at line 13961 of file objects.cc.

                                                                 {
   int capacity = table->Capacity();
   int nof = table->NumberOfElements();
  
   // Shrink to fit the number of elements if only a quarter of the
   // capacity is filled with elements.
   if (nof > (capacity >> 2)) return table;
   // Allocate a new dictionary with room for at least the current
   // number of elements. The allocation method will make sure that
   // there is extra room in the dictionary for additions. Don't go
   // lower than room for 16 elements.
   int at_least_room_for = nof;
   if (at_least_room_for < 16) return table;
  
   Isolate* isolate = table->GetIsolate();
   const int kMinCapacityForPretenure = 256;
   bool pretenure =
       (at_least_room_for > kMinCapacityForPretenure) &&
       !isolate->heap()->InNewSpace(*table);
   Handle<Derived> new_table = HashTable::New(
       isolate,
       at_least_room_for,
       USE_DEFAULT_MINIMUM_CAPACITY,
       pretenure ? TENURED : NOT_TENURED);
  
   table->Rehash(new_table, key);
   return new_table;
 }

References v8::internal::Isolate::heap(), v8::internal::Heap::InNewSpace(), v8::internal::HashTable< Derived, Shape, Key >::New(), v8::internal::NOT_TENURED, v8::internal::TENURED, and v8::internal::USE_DEFAULT_MINIMUM_CAPACITY.

Here is the call graph for this function:

◆ Swap()

template<typename Derived , typename Shape , typename Key >

void v8::internal::HashTable< Derived, Shape, Key >::Swap	(	uint32_t	entry1,
		uint32_t	entry2,
		WriteBarrierMode	mode
	)

private

Definition at line 13876 of file objects.cc.

                                                                  {
   int index1 = EntryToIndex(entry1);
   int index2 = EntryToIndex(entry2);
   Object* temp[Shape::kEntrySize];
   for (int j = 0; j < Shape::kEntrySize; j++) {
     temp[j] = get(index1 + j);
   }
   for (int j = 0; j < Shape::kEntrySize; j++) {
     set(index1 + j, get(index2 + j), mode);
   }
   for (int j = 0; j < Shape::kEntrySize; j++) {
     set(index2 + j, temp[j], mode);
   }
 }

References v8::internal::FixedArray::get(), mode(), and v8::internal::FixedArray::set().

Here is the call graph for this function:

Friends And Related Function Documentation

◆ ObjectHashTable

template<typename Derived , typename Shape , typename Key >

friend class ObjectHashTable

friend

Definition at line 3299 of file objects.h.

Member Data Documentation

◆ kCapacityIndex

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kCapacityIndex = 2

static

Definition at line 3272 of file objects.h.

◆ kCapacityOffset

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kCapacityOffset

static

Initial value:

=

kHeaderSize + kCapacityIndex * kPointerSize

Definition at line 3279 of file objects.h.

◆ kElementsStartIndex

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kElementsStartIndex

static

Initial value:

=

kPrefixStartIndex + Shape::kPrefixSize

Definition at line 3274 of file objects.h.

◆ kElementsStartOffset

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kElementsStartOffset

static

Initial value:

=

kHeaderSize + kElementsStartIndex * kPointerSize

Definition at line 3277 of file objects.h.

◆ kEntrySize

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kEntrySize = Shape::kEntrySize

static

Definition at line 3276 of file objects.h.

Referenced by v8::internal::JSObject::ShouldConvertToFastElements(), and v8::internal::JSObject::ShouldConvertToSlowElements().

◆ kMaxCapacity

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kMaxCapacity

static

Initial value:

=

(FixedArray::kMaxLength - kElementsStartOffset) / kEntrySize

v8::internal::FixedArray::kMaxLength

static const int kMaxLength

Definition: objects.h:2469

Definition at line 3288 of file objects.h.

Referenced by v8::internal::HashTable< Derived, Shape, Key >::New().

◆ kNotFound

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kNotFound = -1

static

Definition at line 3283 of file objects.h.

Referenced by v8::internal::Dictionary< Derived, Shape, Key >::Add(), v8::internal::Dictionary< Derived, Shape, Key >::AtPut(), v8::internal::CopyDictionaryToDoubleElements(), v8::internal::CopyDictionaryToObjectElements(), v8::internal::DictionaryElementsAccessor::DeleteCommon(), v8::internal::JSObject::DeleteNormalizedProperty(), v8::internal::JSGlobalObject::EnsurePropertyCell(), v8::internal::JSObject::GetAccessor(), v8::internal::DictionaryElementsAccessor::GetAccessorPairImpl(), v8::internal::DictionaryElementsAccessor::GetAttributesImpl(), v8::internal::DictionaryElementsAccessor::GetImpl(), v8::internal::TypeFeedbackOracle::GetInfo(), v8::internal::DictionaryElementsAccessor::HasElementImpl(), v8::internal::PropertyHandlerCompiler::NonexistentFrontendHeader(), v8::internal::RUNTIME_FUNCTION(), v8::internal::JSObject::SetDictionaryElement(), v8::internal::JSObject::SetElementWithCallbackSetterInPrototypes(), v8::internal::TypeFeedbackOracle::SetInfo(), v8::internal::JSObject::SetNormalizedProperty(), and v8::internal::UpdateGetterSetterInDictionary().

◆ kNumberOfDeletedElementsIndex

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kNumberOfDeletedElementsIndex = 1

static

Definition at line 3271 of file objects.h.

◆ kNumberOfElementsIndex

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kNumberOfElementsIndex = 0

static

Definition at line 3270 of file objects.h.

◆ kPrefixStartIndex

template<typename Derived , typename Shape , typename Key >

const int v8::internal::HashTable< Derived, Shape, Key >::kPrefixStartIndex = 3

static

Definition at line 3273 of file objects.h.

The documentation for this class was generated from the following files:

/mnt/V8SourceCode/src/objects.h
/mnt/V8SourceCode/src/objects-inl.h
/mnt/V8SourceCode/src/objects.cc

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Private Member Functions

Friends

Additional Inherited Members

Detailed Description

template<typename Derived, typename Shape, typename Key> class v8::internal::HashTable< Derived, Shape, Key >

Member Function Documentation

◆ Capacity()

◆ ComputeCapacity()

◆ ElementAdded()

◆ ElementRemoved()

◆ ElementsRemoved()

◆ EnsureCapacity()

◆ EntryForProbe()

◆ EntryToIndex()

◆ FindEntry() [1/2]

◆ FindEntry() [2/2]

◆ FindInsertionEntry()

◆ FirstProbe()

◆ GetProbe()

◆ Hash()

◆ HashForObject()

◆ INLINE()

◆ IsKey()

◆ IterateElements()

◆ IteratePrefix()

◆ KeyAt()

◆ New()

◆ NextProbe()

◆ NumberOfDeletedElements()

◆ NumberOfElements()

◆ Rehash() [1/2]

◆ Rehash() [2/2]

◆ SetCapacity()

◆ SetNumberOfDeletedElements()

◆ SetNumberOfElements()

◆ Shrink()

◆ Swap()

Friends And Related Function Documentation

◆ ObjectHashTable

Member Data Documentation

◆ kCapacityIndex

◆ kCapacityOffset

◆ kElementsStartIndex

◆ kElementsStartOffset

◆ kEntrySize

◆ kMaxCapacity

◆ kNotFound

◆ kNumberOfDeletedElementsIndex

◆ kNumberOfElementsIndex

◆ kPrefixStartIndex

template<typename Derived, typename Shape, typename Key>
class v8::internal::HashTable< Derived, Shape, Key >