#include <hash_table.h>

Inheritance diagram for dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >:

Public Types
typedef KeyTraits	Traits

typedef StorageTraits	Storage

Public Member Functions
	HashTable (Object key, Smi index, typename StorageTraits::ArrayHandle *data)

	HashTable (Zone *zone, typename StorageTraits::ArrayPtr data)

StorageTraits::ArrayHandle &	Release ()

	~HashTable ()

void	Initialize () const

template<typename Key >
bool	ContainsKey (const Key &key) const

template<typename Key >
intptr_t	FindKey (const Key &key) const

template<typename Key >
bool	FindKeyOrDeletedOrUnused (const Key &key, intptr_t *entry) const

void	InsertKey (intptr_t entry, const Object &key) const

bool	IsUnused (intptr_t entry) const

bool	IsOccupied (intptr_t entry) const

bool	IsDeleted (intptr_t entry) const

ObjectPtr	GetKey (intptr_t entry) const

ObjectPtr	GetPayload (intptr_t entry, intptr_t component) const

void	UpdatePayload (intptr_t entry, intptr_t component, const Object &value) const

void	DeleteEntry (intptr_t entry) const

intptr_t	NumEntries () const

intptr_t	NumUnused () const

intptr_t	NumOccupied () const

intptr_t	NumDeleted () const

Object &	KeyHandle () const

Smi &	SmiHandle () const

intptr_t	NumGrows () const

intptr_t	NumLT5Collisions () const

intptr_t	NumLT25Collisions () const

intptr_t	NumGT25Collisions () const

intptr_t	NumProbes () const

void	UpdateGrowth () const

void	UpdateCollisions (intptr_t collisions) const

void	PrintStats () const

void	UpdateWeakDeleted () const

Public Member Functions inherited from dart::ValueObject
	ValueObject ()

	~ValueObject ()

Static Public Member Functions
static intptr_t	ArrayLengthForNumOccupied (intptr_t num_occupied)

Static Public Member Functions inherited from dart::HashTableBase
static const Object &	UnusedMarker ()

static const Object &	DeletedMarker ()

Protected Member Functions
intptr_t	KeyIndex (intptr_t entry) const

intptr_t	PayloadIndex (intptr_t entry, intptr_t component) const

ObjectPtr	InternalGetKey (intptr_t entry) const

void	InternalSetKey (intptr_t entry, const Object &key) const

intptr_t	GetSmiValueAt (intptr_t index) const

void	SetSmiValueAt (intptr_t index, intptr_t value) const

void	AdjustSmiValueAt (intptr_t index, intptr_t delta) const

Protected Attributes
Object *	key_handle_

Smi *	smi_handle_

StorageTraits::ArrayHandle *	data_

StorageTraits::ArrayHandle *	released_data_

Static Protected Attributes
static constexpr intptr_t	kOccupiedEntriesIndex = 0

static constexpr intptr_t	kDeletedEntriesIndex = 1

static constexpr intptr_t	kNumGrowsIndex = 2

static constexpr intptr_t	kNumLT5LookupsIndex = 3

static constexpr intptr_t	kNumLT25LookupsIndex = 4

static constexpr intptr_t	kNumGT25LookupsIndex = 5

static constexpr intptr_t	kNumProbesIndex = 6

static constexpr intptr_t	kHeaderSize = kNumProbesIndex + 1

static constexpr intptr_t	kMetaDataIndex = kHeaderSize

static constexpr intptr_t	kFirstKeyIndex = kHeaderSize + kMetaDataSize

static constexpr intptr_t	kEntrySize = 1 + kPayloadSize

Friends
class	HashTables

template<typename Table , bool kAllCanonicalObjectsAreIncludedIntoSet>
class	CanonicalSetDeserializationCluster

template<typename Table , typename HandleType , typename PointerType , bool kAllCanonicalObjectsAreIncludedIntoSet>
class	CanonicalSetSerializationCluster

Detailed Description

template<typename KeyTraits, intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>
class dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >

Definition at line 172 of file hash_table.h.

Member Typedef Documentation

◆ Storage

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

typedef StorageTraits dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::Storage

Definition at line 175 of file hash_table.h.

◆ Traits

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

typedef KeyTraits dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::Traits

Definition at line 174 of file hash_table.h.

Constructor & Destructor Documentation

◆ HashTable() [1/2]

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::HashTable	(	Object *	key,
		Smi *	index,
		typename StorageTraits::ArrayHandle *	data
	)

inline

Definition at line 180 of file hash_table.h.

      : key_handle_(key),
        smi_handle_(index),
        data_(data),
        released_data_(nullptr) {}

◆ HashTable() [2/2]

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::HashTable	(	Zone *	zone,
		typename StorageTraits::ArrayPtr	data
	)

inline

Definition at line 187 of file hash_table.h.

      : key_handle_(&Object::Handle(zone)),
        smi_handle_(&Smi::Handle(zone)),
        data_(&StorageTraits::PtrToHandle(data)),
        released_data_(nullptr) {}

◆ ~HashTable()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::~HashTable ( )

inline

Definition at line 204 of file hash_table.h.

               {
    // In DEBUG mode, calling 'Release' is mandatory.
    ASSERT(data_ == nullptr);
    if (released_data_ != nullptr) {
      StorageTraits::ClearHandle(*released_data_);
    }
  }

Member Function Documentation

◆ AdjustSmiValueAt()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::AdjustSmiValueAt	(	intptr_t	index,
		intptr_t	delta
	)		const

inlineprotected

Definition at line 510 of file hash_table.h.

                                                              {
    SetSmiValueAt(index, (GetSmiValueAt(index) + delta));
  }

◆ ArrayLengthForNumOccupied()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

static intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::ArrayLengthForNumOccupied ( intptr_t num_occupied )

inlinestatic

Definition at line 214 of file hash_table.h.

                                                                   {
    // Because we use quadratic (actually triangle number) probing it is
    // important that the size is a power of two (otherwise we could fail to
    // find an empty slot).  This is described in Knuth's The Art of Computer
    // Programming Volume 2, Chapter 6.4, exercise 20 (solution in the
    // appendix, 2nd edition).
    intptr_t num_entries = Utils::RoundUpToPowerOfTwo(num_occupied + 1);
    return kFirstKeyIndex + (kEntrySize * num_entries);
  }

◆ ContainsKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

template<typename Key >

bool dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::ContainsKey ( const Key & key ) const

inline

Definition at line 246 of file hash_table.h.

                                         {
    return FindKey(key) != -1;
  }

◆ DeleteEntry()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::DeleteEntry ( intptr_t entry ) const

inline

Definition at line 365 of file hash_table.h.

                                         {
    ASSERT(IsOccupied(entry));
    for (intptr_t i = 0; i < kPayloadSize; ++i) {
      UpdatePayload(entry, i, DeletedMarker());
    }
    InternalSetKey(entry, DeletedMarker());
    AdjustSmiValueAt(kOccupiedEntriesIndex, -1);
    AdjustSmiValueAt(kDeletedEntriesIndex, 1);
  }

◆ FindKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

template<typename Key >

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::FindKey ( const Key & key ) const

inline

Definition at line 252 of file hash_table.h.

                                         {
    const intptr_t num_entries = NumEntries();
    // TODO(koda): Add salt.
    NOT_IN_PRODUCT(intptr_t collisions = 0;)
    uword hash = KeyTraits::Hash(key);
    ASSERT(Utils::IsPowerOfTwo(num_entries));
    intptr_t probe = hash & (num_entries - 1);
    int probe_distance = 1;
    while (true) {
      if (IsUnused(probe)) {
        NOT_IN_PRODUCT(UpdateCollisions(collisions);)
        return -1;
      } else if (!IsDeleted(probe)) {
        *key_handle_ = GetKey(probe);
        if (KeyTraits::IsMatch(key, *key_handle_)) {
          NOT_IN_PRODUCT(UpdateCollisions(collisions);)
          return probe;
        }
        NOT_IN_PRODUCT(collisions += 1;)
      }
      // Advance probe.  See ArrayLengthForNumOccupied comment for
      // explanation of how we know this hits all slots.
      probe = (probe + probe_distance) & (num_entries - 1);
      probe_distance++;
    }
    UNREACHABLE();
    return -1;
  }

◆ FindKeyOrDeletedOrUnused()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

template<typename Key >

bool dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::FindKeyOrDeletedOrUnused	(	const Key &	key,
		intptr_t *	entry
	)		const

inline

Definition at line 286 of file hash_table.h.

                                                                       {
    const intptr_t num_entries = NumEntries();
    ASSERT(entry != nullptr);
    NOT_IN_PRODUCT(intptr_t collisions = 0;)
    uword hash = KeyTraits::Hash(key);
    ASSERT(Utils::IsPowerOfTwo(num_entries));
    intptr_t probe = hash & (num_entries - 1);
    int probe_distance = 1;
    intptr_t deleted = -1;
    while (true) {
      if (IsUnused(probe)) {
        *entry = (deleted != -1) ? deleted : probe;
        NOT_IN_PRODUCT(UpdateCollisions(collisions);)
        return false;
      } else if (IsDeleted(probe)) {
        if (deleted == -1) {
          deleted = probe;
        }
      } else {
        *key_handle_ = GetKey(probe);
        if (KeyTraits::IsMatch(key, *key_handle_)) {
          *entry = probe;
          NOT_IN_PRODUCT(UpdateCollisions(collisions);)
          return true;
        }
        NOT_IN_PRODUCT(collisions += 1;)
      }
      // Advance probe.  See ArrayLengthForNumOccupied comment for
      // explanation of how we know this hits all slots.
      probe = (probe + probe_distance) & (num_entries - 1);
      probe_distance++;
    }
    UNREACHABLE();
    return false;
  }

◆ GetKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

ObjectPtr dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::GetKey ( intptr_t entry ) const

inline

Definition at line 348 of file hash_table.h.

                                         {
    ASSERT(IsOccupied(entry));
    return InternalGetKey(entry);
  }

◆ GetPayload()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

ObjectPtr dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::GetPayload	(	intptr_t	entry,
		intptr_t	component
	)		const

inline

Definition at line 352 of file hash_table.h.

                                                                 {
    ASSERT(IsOccupied(entry));
    return WeakSerializationReference::Unwrap(
        StorageTraits::At(data_, PayloadIndex(entry, component)));
  }

◆ GetSmiValueAt()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::GetSmiValueAt ( intptr_t index ) const

inlineprotected

Definition at line 496 of file hash_table.h.

                                               {
    ASSERT(!data_->IsNull());
    if (StorageTraits::At(data_, index)->IsHeapObject()) {
      Object::Handle(StorageTraits::At(data_, index)).Print();
    }
    ASSERT(!StorageTraits::At(data_, index)->IsHeapObject());
    return Smi::Value(Smi::RawCast(StorageTraits::At(data_, index)));
  }

◆ Initialize()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::Initialize ( ) const

inline

Definition at line 225 of file hash_table.h.

                          {
    ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
    *smi_handle_ = Smi::New(0);
    StorageTraits::SetAt(data_, kOccupiedEntriesIndex, *smi_handle_);
    StorageTraits::SetAt(data_, kDeletedEntriesIndex, *smi_handle_);
 
#if !defined(PRODUCT)
    StorageTraits::SetAt(data_, kNumGrowsIndex, *smi_handle_);
    StorageTraits::SetAt(data_, kNumLT5LookupsIndex, *smi_handle_);
    StorageTraits::SetAt(data_, kNumLT25LookupsIndex, *smi_handle_);
    StorageTraits::SetAt(data_, kNumGT25LookupsIndex, *smi_handle_);
    StorageTraits::SetAt(data_, kNumProbesIndex, *smi_handle_);
#endif  // !defined(PRODUCT)
 
    for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
      StorageTraits::SetAt(data_, i, UnusedMarker());
    }
  }

◆ InsertKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::InsertKey	(	intptr_t	entry,
		const Object &	key
	)		const

inline

Definition at line 324 of file hash_table.h.

                                                          {
    ASSERT(key.ptr() != UnusedMarker().ptr());
    ASSERT(key.ptr() != DeletedMarker().ptr());
    ASSERT(!IsOccupied(entry));
    AdjustSmiValueAt(kOccupiedEntriesIndex, 1);
    if (IsDeleted(entry)) {
      AdjustSmiValueAt(kDeletedEntriesIndex, -1);
    } else {
      ASSERT(IsUnused(entry));
    }
    InternalSetKey(entry, key);
    ASSERT(IsOccupied(entry));
  }

◆ InternalGetKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

ObjectPtr dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::InternalGetKey ( intptr_t entry ) const

inlineprotected

Definition at line 487 of file hash_table.h.

                                                 {
    return WeakSerializationReference::Unwrap(
        StorageTraits::At(data_, KeyIndex(entry)));
  }

◆ InternalSetKey()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::InternalSetKey	(	intptr_t	entry,
		const Object &	key
	)		const

inlineprotected

Definition at line 492 of file hash_table.h.

                                                               {
    StorageTraits::SetAt(data_, KeyIndex(entry), key);
  }

◆ IsDeleted()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

bool dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::IsDeleted ( intptr_t entry ) const

inline

Definition at line 344 of file hash_table.h.

                                       {
    return InternalGetKey(entry) == DeletedMarker().ptr();
  }

◆ IsOccupied()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

bool dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::IsOccupied ( intptr_t entry ) const

inline

Definition at line 341 of file hash_table.h.

                                        {
    return !IsUnused(entry) && !IsDeleted(entry);
  }

◆ IsUnused()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

bool dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::IsUnused ( intptr_t entry ) const

inline

Definition at line 338 of file hash_table.h.

                                      {
    return InternalGetKey(entry) == UnusedMarker().ptr();
  }

◆ KeyHandle()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

Object & dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::KeyHandle ( ) const

inline

Definition at line 382 of file hash_table.h.

382{ return *key_handle_; }

◆ KeyIndex()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::KeyIndex ( intptr_t entry ) const

inlineprotected

Definition at line 477 of file hash_table.h.

                                          {
    ASSERT(0 <= entry && entry < NumEntries());
    return kFirstKeyIndex + (kEntrySize * entry);
  }

◆ NumDeleted()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumDeleted ( ) const

inline

Definition at line 381 of file hash_table.h.

381{ return GetSmiValueAt(kDeletedEntriesIndex); }

◆ NumEntries()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumEntries ( ) const

inline

Definition at line 374 of file hash_table.h.

                              {
    return (data_->Length() - kFirstKeyIndex) / kEntrySize;
  }

◆ NumGrows()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumGrows ( ) const

inline

Definition at line 386 of file hash_table.h.

386{ return GetSmiValueAt(kNumGrowsIndex); }

◆ NumGT25Collisions()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumGT25Collisions ( ) const

inline

Definition at line 393 of file hash_table.h.

                                     {
    return GetSmiValueAt(kNumGT25LookupsIndex);
  }

◆ NumLT25Collisions()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumLT25Collisions ( ) const

inline

Definition at line 390 of file hash_table.h.

                                     {
    return GetSmiValueAt(kNumLT25LookupsIndex);
  }

◆ NumLT5Collisions()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumLT5Collisions ( ) const

inline

Definition at line 387 of file hash_table.h.

                                    {
    return GetSmiValueAt(kNumLT5LookupsIndex);
  }

◆ NumOccupied()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumOccupied ( ) const

inline

Definition at line 380 of file hash_table.h.

380{ return GetSmiValueAt(kOccupiedEntriesIndex); }

◆ NumProbes()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumProbes ( ) const

inline

Definition at line 396 of file hash_table.h.

396{ return GetSmiValueAt(kNumProbesIndex); }

◆ NumUnused()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::NumUnused ( ) const

inline

Definition at line 377 of file hash_table.h.

                             {
    return NumEntries() - NumOccupied() - NumDeleted();
  }

◆ PayloadIndex()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::PayloadIndex	(	intptr_t	entry,
		intptr_t	component
	)		const

inlineprotected

Definition at line 482 of file hash_table.h.

                                                                  {
    ASSERT(0 <= component && component < kPayloadSize);
    return KeyIndex(entry) + 1 + component;
  }

◆ PrintStats()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::PrintStats ( ) const

inline

Definition at line 417 of file hash_table.h.

                          {
    if (!KeyTraits::ReportStats()) {
      return;
    }
    const intptr_t num5 = NumLT5Collisions();
    const intptr_t num25 = NumLT25Collisions();
    const intptr_t num_more = NumGT25Collisions();
    // clang-format off
    OS::PrintErr("Stats for %s table :\n"
              " Size of table = %" Pd ",Number of Occupied entries = %" Pd "\n"
              " Number of Grows = %" Pd "\n"
              " Number of lookups with < 5 collisions = %" Pd "\n"
              " Number of lookups with < 25 collisions = %" Pd "\n"
              " Number of lookups with > 25 collisions = %" Pd "\n"
              " Average number of probes = %g\n",
              KeyTraits::Name(),
              NumEntries(), NumOccupied(), NumGrows(),
              num5, num25, num_more,
              static_cast<double>(NumProbes()) / (num5 + num25 + num_more));
    // clang-format on
  }

◆ Release()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

StorageTraits::ArrayHandle & dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::Release ( )

inline

Definition at line 195 of file hash_table.h.

                                               {
    ASSERT(data_ != nullptr);
    ASSERT(released_data_ == nullptr);
    // Ensure that no methods are called after 'Release'.
    released_data_ = data_;
    data_ = nullptr;
    return *released_data_;
  }

◆ SetSmiValueAt()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::SetSmiValueAt	(	intptr_t	index,
		intptr_t	value
	)		const

inlineprotected

Definition at line 505 of file hash_table.h.

                                                           {
    *smi_handle_ = Smi::New(value);
    StorageTraits::SetAt(data_, index, *smi_handle_);
  }

◆ SmiHandle()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

Smi & dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::SmiHandle ( ) const

inline

Definition at line 383 of file hash_table.h.

383{ return *smi_handle_; }

◆ UpdateCollisions()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::UpdateCollisions ( intptr_t collisions ) const

inline

Definition at line 402 of file hash_table.h.

                                                   {
    if (KeyTraits::ReportStats()) {
      if (Storage::IsImmutable(*data_)) {
        return;
      }
      AdjustSmiValueAt(kNumProbesIndex, collisions + 1);
      if (collisions < 5) {
        AdjustSmiValueAt(kNumLT5LookupsIndex, 1);
      } else if (collisions < 25) {
        AdjustSmiValueAt(kNumLT25LookupsIndex, 1);
      } else {
        AdjustSmiValueAt(kNumGT25LookupsIndex, 1);
      }
    }
  }

◆ UpdateGrowth()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::UpdateGrowth ( ) const

inline

Definition at line 397 of file hash_table.h.

                            {
    if (KeyTraits::ReportStats()) {
      AdjustSmiValueAt(kNumGrowsIndex, 1);
    }
  }

◆ UpdatePayload()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::UpdatePayload	(	intptr_t	entry,
		intptr_t	component,
		const Object &	value
	)		const

inline

Definition at line 357 of file hash_table.h.

                                                {
    ASSERT(IsOccupied(entry));
    ASSERT(0 <= component && component < kPayloadSize);
    StorageTraits::SetAt(data_, PayloadIndex(entry, component), value);
  }

◆ UpdateWeakDeleted()

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

void dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::UpdateWeakDeleted ( ) const

inline

Definition at line 440 of file hash_table.h.

                                 {
    if (StorageTraits::ArrayCid != kWeakArrayCid) return;
 
    // As entries are deleted by GC, NumOccupied and NumDeleted become stale.
    // Re-count before growing/rehashing to prevent table growth when the
    // number of live entries is not increasing.
    intptr_t num_occupied = 0;
    intptr_t num_deleted = 0;
    for (intptr_t i = 0, n = NumEntries(); i < n; i++) {
      if (IsDeleted(i)) {
        num_deleted++;
      }
      if (IsOccupied(i)) {
        num_occupied++;
      }
    }
    SetSmiValueAt(kOccupiedEntriesIndex, num_occupied);
    SetSmiValueAt(kDeletedEntriesIndex, num_deleted);
  }

Friends And Related Symbol Documentation

◆ CanonicalSetDeserializationCluster

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

template<typename Table , bool kAllCanonicalObjectsAreIncludedIntoSet>

friend class CanonicalSetDeserializationCluster

friend

Definition at line 522 of file hash_table.h.

◆ CanonicalSetSerializationCluster

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

template<typename Table , typename HandleType , typename PointerType , bool kAllCanonicalObjectsAreIncludedIntoSet>

friend class CanonicalSetSerializationCluster

friend

Definition at line 527 of file hash_table.h.

◆ HashTables

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

friend class HashTables

friend

Definition at line 520 of file hash_table.h.

Member Data Documentation

◆ data_

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

StorageTraits::ArrayHandle* dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::data_

protected

Definition at line 517 of file hash_table.h.

◆ kDeletedEntriesIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kDeletedEntriesIndex = 1

staticconstexprprotected

Definition at line 462 of file hash_table.h.

◆ kEntrySize

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kEntrySize = 1 + kPayloadSize

staticconstexprprotected

Definition at line 475 of file hash_table.h.

◆ key_handle_

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

Object* dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::key_handle_

protected

Definition at line 514 of file hash_table.h.

◆ kFirstKeyIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kFirstKeyIndex = kHeaderSize + kMetaDataSize

staticconstexprprotected

Definition at line 474 of file hash_table.h.

◆ kHeaderSize

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kHeaderSize = kNumProbesIndex + 1

staticconstexprprotected

Definition at line 471 of file hash_table.h.

◆ kMetaDataIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kMetaDataIndex = kHeaderSize

staticconstexprprotected

Definition at line 473 of file hash_table.h.

◆ kNumGrowsIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kNumGrowsIndex = 2

staticconstexprprotected

Definition at line 466 of file hash_table.h.

◆ kNumGT25LookupsIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kNumGT25LookupsIndex = 5

staticconstexprprotected

Definition at line 469 of file hash_table.h.

◆ kNumLT25LookupsIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kNumLT25LookupsIndex = 4

staticconstexprprotected

Definition at line 468 of file hash_table.h.

◆ kNumLT5LookupsIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kNumLT5LookupsIndex = 3

staticconstexprprotected

Definition at line 467 of file hash_table.h.

◆ kNumProbesIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kNumProbesIndex = 6

staticconstexprprotected

Definition at line 470 of file hash_table.h.

◆ kOccupiedEntriesIndex

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

constexpr intptr_t dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::kOccupiedEntriesIndex = 0

staticconstexprprotected

Definition at line 461 of file hash_table.h.

◆ released_data_

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

StorageTraits::ArrayHandle* dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::released_data_

protected

Definition at line 518 of file hash_table.h.

◆ smi_handle_

template<typename KeyTraits , intptr_t kPayloadSize, intptr_t kMetaDataSize, typename StorageTraits = ArrayStorageTraits>

Smi* dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits >::smi_handle_

protected

Definition at line 515 of file hash_table.h.

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

third_party/dart-lang/sdk/runtime/vm/hash_table.h

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

◆ Storage

◆ Traits

Constructor & Destructor Documentation

◆ HashTable() [1/2]

◆ HashTable() [2/2]

◆ ~HashTable()

Member Function Documentation

◆ AdjustSmiValueAt()

◆ ArrayLengthForNumOccupied()

◆ ContainsKey()

◆ DeleteEntry()

◆ FindKey()

◆ FindKeyOrDeletedOrUnused()

◆ GetKey()

◆ GetPayload()

◆ GetSmiValueAt()

◆ Initialize()

◆ InsertKey()

◆ InternalGetKey()

◆ InternalSetKey()

◆ IsDeleted()

◆ IsOccupied()

◆ IsUnused()

◆ KeyHandle()

◆ KeyIndex()

◆ NumDeleted()

◆ NumEntries()

◆ NumGrows()

◆ NumGT25Collisions()

◆ NumLT25Collisions()

◆ NumLT5Collisions()

◆ NumOccupied()

◆ NumProbes()

◆ NumUnused()

◆ PayloadIndex()

◆ PrintStats()

◆ Release()

◆ SetSmiValueAt()

◆ SmiHandle()

◆ UpdateCollisions()

◆ UpdateGrowth()

◆ UpdatePayload()

◆ UpdateWeakDeleted()

Friends And Related Symbol Documentation

◆ CanonicalSetDeserializationCluster

◆ CanonicalSetSerializationCluster

◆ HashTables

Member Data Documentation

◆ data_

◆ kDeletedEntriesIndex

◆ kEntrySize

◆ key_handle_

◆ kFirstKeyIndex

◆ kHeaderSize

◆ kMetaDataIndex

◆ kNumGrowsIndex

◆ kNumGT25LookupsIndex

◆ kNumLT25LookupsIndex

◆ kNumLT5LookupsIndex

◆ kNumProbesIndex

◆ kOccupiedEntriesIndex

◆ released_data_

◆ smi_handle_