Flutter Engine
The Flutter Engine
Public Types | Public Member Functions | Static Public Member Functions | Protected Member Functions | Protected Attributes | Static Protected Attributes | Friends | List of all members
dart::HashTable< KeyTraits, kPayloadSize, kMetaDataSize, StorageTraits > Class Template Reference

#include <hash_table.h>

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

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.

181 : key_handle_(key),
182 smi_handle_(index),
183 data_(data),
184 released_data_(nullptr) {}
dart::HashTable::data_
StorageTraits::ArrayHandle * data_
Definition: hash_table.h:517
dart::HashTable::released_data_
StorageTraits::ArrayHandle * released_data_
Definition: hash_table.h:518
dart::HashTable::key_handle_
Object * key_handle_
Definition: hash_table.h:514
key
int key
Definition: keyboard_key_handler_unittests.cc:114
dart::data
static int8_t data[kExtLength]
Definition: dart_api_impl_test.cc:2256

◆ 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.

188 : key_handle_(&Object::Handle(zone)),
189 smi_handle_(&Smi::Handle(zone)),
190 data_(&StorageTraits::PtrToHandle(data)),
191 released_data_(nullptr) {}
dart::Object::Handle
static Object & Handle()
Definition: object.h:407

◆ ~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.

204 {
205 // In DEBUG mode, calling 'Release' is mandatory.
206 ASSERT(data_ == nullptr);
207 if (released_data_ != nullptr) {
208 StorageTraits::ClearHandle(*released_data_);
209 }
210 }
ASSERT
#define ASSERT(E)
Definition: entrypoints_verification_test.cc:25

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.

510 {
511 SetSmiValueAt(index, (GetSmiValueAt(index) + delta));
512 }
dart::HashTable::GetSmiValueAt
intptr_t GetSmiValueAt(intptr_t index) const
Definition: hash_table.h:496
dart::HashTable::SetSmiValueAt
void SetSmiValueAt(intptr_t index, intptr_t value) const
Definition: hash_table.h:505
generate_fir_coeff.delta
int delta
Definition: generate_fir_coeff.py:92

◆ 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.

214 {
215 // Because we use quadratic (actually triangle number) probing it is
216 // important that the size is a power of two (otherwise we could fail to
217 // find an empty slot). This is described in Knuth's The Art of Computer
218 // Programming Volume 2, Chapter 6.4, exercise 20 (solution in the
219 // appendix, 2nd edition).
220 intptr_t num_entries = Utils::RoundUpToPowerOfTwo(num_occupied + 1);
221 return kFirstKeyIndex + (kEntrySize * num_entries);
222 }
dart::HashTable::kEntrySize
static constexpr intptr_t kEntrySize
Definition: hash_table.h:475
dart::HashTable::kFirstKeyIndex
static constexpr intptr_t kFirstKeyIndex
Definition: hash_table.h:474
dart::Utils::RoundUpToPowerOfTwo
static constexpr uintptr_t RoundUpToPowerOfTwo(uintptr_t x)
Definition: utils.h:135

◆ 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.

246 {
247 return FindKey(key) != -1;
248 }
dart::HashTable::FindKey
intptr_t FindKey(const Key &key) const
Definition: hash_table.h:252

◆ 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.

365 {
366 ASSERT(IsOccupied(entry));
367 for (intptr_t i = 0; i < kPayloadSize; ++i) {
368 UpdatePayload(entry, i, DeletedMarker());
369 }
370 InternalSetKey(entry, DeletedMarker());
371 AdjustSmiValueAt(kOccupiedEntriesIndex, -1);
372 AdjustSmiValueAt(kDeletedEntriesIndex, 1);
373 }
dart::HashTableBase::DeletedMarker
static const Object & DeletedMarker()
Definition: hash_table.h:104
dart::HashTable::IsOccupied
bool IsOccupied(intptr_t entry) const
Definition: hash_table.h:341
dart::HashTable::AdjustSmiValueAt
void AdjustSmiValueAt(intptr_t index, intptr_t delta) const
Definition: hash_table.h:510
dart::HashTable::kOccupiedEntriesIndex
static constexpr intptr_t kOccupiedEntriesIndex
Definition: hash_table.h:461
dart::HashTable::InternalSetKey
void InternalSetKey(intptr_t entry, const Object &key) const
Definition: hash_table.h:492
dart::HashTable::UpdatePayload
void UpdatePayload(intptr_t entry, intptr_t component, const Object &value) const
Definition: hash_table.h:357
dart::HashTable::kDeletedEntriesIndex
static constexpr intptr_t kDeletedEntriesIndex
Definition: hash_table.h:462
i
int i
Definition: fl_socket_accessible.cc:18

◆ 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.

252 {
253 const intptr_t num_entries = NumEntries();
254 // TODO(koda): Add salt.
255 NOT_IN_PRODUCT(intptr_t collisions = 0;)
256 uword hash = KeyTraits::Hash(key);
257 ASSERT(Utils::IsPowerOfTwo(num_entries));
258 intptr_t probe = hash & (num_entries - 1);
259 int probe_distance = 1;
260 while (true) {
261 if (IsUnused(probe)) {
262 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
263 return -1;
264 } else if (!IsDeleted(probe)) {
265 *key_handle_ = GetKey(probe);
266 if (KeyTraits::IsMatch(key, *key_handle_)) {
267 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
268 return probe;
269 }
270 NOT_IN_PRODUCT(collisions += 1;)
271 }
272 // Advance probe. See ArrayLengthForNumOccupied comment for
273 // explanation of how we know this hits all slots.
274 probe = (probe + probe_distance) & (num_entries - 1);
275 probe_distance++;
276 }
277 UNREACHABLE();
278 return -1;
279 }
hash
static uint32_t hash(const SkShaderBase::GradientInfo &v)
Definition: SkPDFGradientShader.cpp:33
UNREACHABLE
#define UNREACHABLE()
Definition: assert.h:248
dart::HashTable::IsUnused
bool IsUnused(intptr_t entry) const
Definition: hash_table.h:338
dart::HashTable::IsDeleted
bool IsDeleted(intptr_t entry) const
Definition: hash_table.h:344
dart::HashTable::NumEntries
intptr_t NumEntries() const
Definition: hash_table.h:374
dart::HashTable::UpdateCollisions
void UpdateCollisions(intptr_t collisions) const
Definition: hash_table.h:402
dart::HashTable::GetKey
ObjectPtr GetKey(intptr_t entry) const
Definition: hash_table.h:348
dart::Utils::IsPowerOfTwo
static constexpr bool IsPowerOfTwo(T x)
Definition: utils.h:76
dart::uword
uintptr_t uword
Definition: globals.h:501
dart::Hash
static uint32_t Hash(uint32_t key)
Definition: hashmap_test.cc:65
dart::NOT_IN_PRODUCT
NOT_IN_PRODUCT(LibraryPtr ReloadTestScript(const char *script))

◆ 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.

286 {
287 const intptr_t num_entries = NumEntries();
288 ASSERT(entry != nullptr);
289 NOT_IN_PRODUCT(intptr_t collisions = 0;)
290 uword hash = KeyTraits::Hash(key);
291 ASSERT(Utils::IsPowerOfTwo(num_entries));
292 intptr_t probe = hash & (num_entries - 1);
293 int probe_distance = 1;
294 intptr_t deleted = -1;
295 while (true) {
296 if (IsUnused(probe)) {
297 *entry = (deleted != -1) ? deleted : probe;
298 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
299 return false;
300 } else if (IsDeleted(probe)) {
301 if (deleted == -1) {
302 deleted = probe;
303 }
304 } else {
305 *key_handle_ = GetKey(probe);
306 if (KeyTraits::IsMatch(key, *key_handle_)) {
307 *entry = probe;
308 NOT_IN_PRODUCT(UpdateCollisions(collisions);)
309 return true;
310 }
311 NOT_IN_PRODUCT(collisions += 1;)
312 }
313 // Advance probe. See ArrayLengthForNumOccupied comment for
314 // explanation of how we know this hits all slots.
315 probe = (probe + probe_distance) & (num_entries - 1);
316 probe_distance++;
317 }
318 UNREACHABLE();
319 return false;
320 }

◆ 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.

348 {
349 ASSERT(IsOccupied(entry));
350 return InternalGetKey(entry);
351 }
dart::HashTable::InternalGetKey
ObjectPtr InternalGetKey(intptr_t entry) const
Definition: hash_table.h:487

◆ 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.

352 {
353 ASSERT(IsOccupied(entry));
354 return WeakSerializationReference::Unwrap(
355 StorageTraits::At(data_, PayloadIndex(entry, component)));
356 }
dart::HashTable::PayloadIndex
intptr_t PayloadIndex(intptr_t entry, intptr_t component) const
Definition: hash_table.h:482
dart::WeakSerializationReference::Unwrap
static ObjectPtr Unwrap(ObjectPtr obj)
Definition: object.h:6667

◆ 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.

496 {
497 ASSERT(!data_->IsNull());
498 if (StorageTraits::At(data_, index)->IsHeapObject()) {
499 Object::Handle(StorageTraits::At(data_, index)).Print();
500 }
501 ASSERT(!StorageTraits::At(data_, index)->IsHeapObject());
502 return Smi::Value(Smi::RawCast(StorageTraits::At(data_, index)));
503 }
dart::Object::Print
void Print() const
Definition: object.cc:2620
dart::Object::RawCast
static ObjectPtr RawCast(ObjectPtr obj)
Definition: object.h:325
dart::Smi::Value
intptr_t Value() const
Definition: object.h:9990

◆ 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.

225 {
226 ASSERT(data_->Length() >= ArrayLengthForNumOccupied(0));
227 *smi_handle_ = Smi::New(0);
228 StorageTraits::SetAt(data_, kOccupiedEntriesIndex, *smi_handle_);
229 StorageTraits::SetAt(data_, kDeletedEntriesIndex, *smi_handle_);
230
231#if !defined(PRODUCT)
232 StorageTraits::SetAt(data_, kNumGrowsIndex, *smi_handle_);
233 StorageTraits::SetAt(data_, kNumLT5LookupsIndex, *smi_handle_);
234 StorageTraits::SetAt(data_, kNumLT25LookupsIndex, *smi_handle_);
235 StorageTraits::SetAt(data_, kNumGT25LookupsIndex, *smi_handle_);
236 StorageTraits::SetAt(data_, kNumProbesIndex, *smi_handle_);
237#endif // !defined(PRODUCT)
238
239 for (intptr_t i = kHeaderSize; i < data_->Length(); ++i) {
240 StorageTraits::SetAt(data_, i, UnusedMarker());
241 }
242 }
dart::HashTableBase::UnusedMarker
static const Object & UnusedMarker()
Definition: hash_table.h:103
dart::HashTable::ArrayLengthForNumOccupied
static intptr_t ArrayLengthForNumOccupied(intptr_t num_occupied)
Definition: hash_table.h:214
dart::HashTable::kNumGT25LookupsIndex
static constexpr intptr_t kNumGT25LookupsIndex
Definition: hash_table.h:469
dart::HashTable::kNumLT25LookupsIndex
static constexpr intptr_t kNumLT25LookupsIndex
Definition: hash_table.h:468
dart::HashTable::kHeaderSize
static constexpr intptr_t kHeaderSize
Definition: hash_table.h:471
dart::HashTable::kNumGrowsIndex
static constexpr intptr_t kNumGrowsIndex
Definition: hash_table.h:466
dart::HashTable::kNumLT5LookupsIndex
static constexpr intptr_t kNumLT5LookupsIndex
Definition: hash_table.h:467
dart::HashTable::kNumProbesIndex
static constexpr intptr_t kNumProbesIndex
Definition: hash_table.h:470
dart::Smi::New
static SmiPtr New(intptr_t value)
Definition: object.h:10006

◆ 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.

324 {
325 ASSERT(key.ptr() != UnusedMarker().ptr());
326 ASSERT(key.ptr() != DeletedMarker().ptr());
327 ASSERT(!IsOccupied(entry));
328 AdjustSmiValueAt(kOccupiedEntriesIndex, 1);
329 if (IsDeleted(entry)) {
330 AdjustSmiValueAt(kDeletedEntriesIndex, -1);
331 } else {
332 ASSERT(IsUnused(entry));
333 }
334 InternalSetKey(entry, key);
335 ASSERT(IsOccupied(entry));
336 }

◆ 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.

487 {
488 return WeakSerializationReference::Unwrap(
489 StorageTraits::At(data_, KeyIndex(entry)));
490 }
dart::HashTable::KeyIndex
intptr_t KeyIndex(intptr_t entry) const
Definition: hash_table.h:477

◆ 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.

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

◆ 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.

344 {
345 return InternalGetKey(entry) == DeletedMarker().ptr();
346 }
dart::Object::ptr
ObjectPtr ptr() const
Definition: object.h:332

◆ 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.

341 {
342 return !IsUnused(entry) && !IsDeleted(entry);
343 }

◆ 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.

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

◆ 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.

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

◆ 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.

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

◆ 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.

393 {
394 return GetSmiValueAt(kNumGT25LookupsIndex);
395 }

◆ 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.

390 {
391 return GetSmiValueAt(kNumLT25LookupsIndex);
392 }

◆ 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.

387 {
388 return GetSmiValueAt(kNumLT5LookupsIndex);
389 }

◆ 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.

377 {
378 return NumEntries() - NumOccupied() - NumDeleted();
379 }
dart::HashTable::NumDeleted
intptr_t NumDeleted() const
Definition: hash_table.h:381
dart::HashTable::NumOccupied
intptr_t NumOccupied() const
Definition: hash_table.h:380

◆ 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.

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

◆ 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.

417 {
418 if (!KeyTraits::ReportStats()) {
419 return;
420 }
421 const intptr_t num5 = NumLT5Collisions();
422 const intptr_t num25 = NumLT25Collisions();
423 const intptr_t num_more = NumGT25Collisions();
424 // clang-format off
425 OS::PrintErr("Stats for %s table :\n"
426 " Size of table = %" Pd ",Number of Occupied entries = %" Pd "\n"
427 " Number of Grows = %" Pd "\n"
428 " Number of lookups with < 5 collisions = %" Pd "\n"
429 " Number of lookups with < 25 collisions = %" Pd "\n"
430 " Number of lookups with > 25 collisions = %" Pd "\n"
431 " Average number of probes = %g\n",
432 KeyTraits::Name(),
433 NumEntries(), NumOccupied(), NumGrows(),
434 num5, num25, num_more,
435 static_cast<double>(NumProbes()) / (num5 + num25 + num_more));
436 // clang-format on
437 }
dart::HashTable::NumLT5Collisions
intptr_t NumLT5Collisions() const
Definition: hash_table.h:387
dart::HashTable::NumLT25Collisions
intptr_t NumLT25Collisions() const
Definition: hash_table.h:390
dart::HashTable::NumGrows
intptr_t NumGrows() const
Definition: hash_table.h:386
dart::HashTable::NumGT25Collisions
intptr_t NumGT25Collisions() const
Definition: hash_table.h:393
dart::HashTable::NumProbes
intptr_t NumProbes() const
Definition: hash_table.h:396
dart::OS::PrintErr
static void static void PrintErr(const char *format,...) PRINTF_ATTRIBUTE(1
DM::Name
ImplicitString Name
Definition: DMSrcSink.h:38
Pd
#define Pd
Definition: globals.h:408

◆ 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.

195 {
196 ASSERT(data_ != nullptr);
197 ASSERT(released_data_ == nullptr);
198 // Ensure that no methods are called after 'Release'.
199 released_data_ = data_;
200 data_ = nullptr;
201 return *released_data_;
202 }

◆ 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.

505 {
506 *smi_handle_ = Smi::New(value);
507 StorageTraits::SetAt(data_, index, *smi_handle_);
508 }
value
uint8_t value
Definition: fl_standard_message_codec.cc:36

◆ 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.

402 {
403 if (KeyTraits::ReportStats()) {
404 if (Storage::IsImmutable(*data_)) {
405 return;
406 }
407 AdjustSmiValueAt(kNumProbesIndex, collisions + 1);
408 if (collisions < 5) {
409 AdjustSmiValueAt(kNumLT5LookupsIndex, 1);
410 } else if (collisions < 25) {
411 AdjustSmiValueAt(kNumLT25LookupsIndex, 1);
412 } else {
413 AdjustSmiValueAt(kNumGT25LookupsIndex, 1);
414 }
415 }
416 }

◆ 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.

397 {
398 if (KeyTraits::ReportStats()) {
399 AdjustSmiValueAt(kNumGrowsIndex, 1);
400 }
401 }

◆ 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.

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

◆ 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.

440 {
441 if (StorageTraits::ArrayCid != kWeakArrayCid) return;
442
443 // As entries are deleted by GC, NumOccupied and NumDeleted become stale.
444 // Re-count before growing/rehashing to prevent table growth when the
445 // number of live entries is not increasing.
446 intptr_t num_occupied = 0;
447 intptr_t num_deleted = 0;
448 for (intptr_t i = 0, n = NumEntries(); i < n; i++) {
449 if (IsDeleted(i)) {
450 num_deleted++;
451 }
452 if (IsOccupied(i)) {
453 num_occupied++;
454 }
455 }
456 SetSmiValueAt(kOccupiedEntriesIndex, num_occupied);
457 SetSmiValueAt(kDeletedEntriesIndex, num_deleted);
458 }

Friends And Related Function 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:
Generated on Sun Jun 23 2024 21:59:11 for Flutter Engine by doxygen 1.9.4