dart::HashTables Class Reference

#include <hash_table.h>

Inheritance diagram for dart::HashTables:

Static Public Member Functions
template<typename Table >
static Table::Storage::ArrayPtr	New (intptr_t initial_capacity, Heap::Space space=Heap::kNew)
template<typename Table >
static Table::Storage::ArrayPtr	New (const typename Table::Storage::ArrayHandle &array)
template<typename From , typename To >
static void	Copy (const From &from, const To &to)
template<typename Table >
static void	EnsureLoadFactor (double high, const Table &table)
template<typename Table >
static ArrayPtr	ToArray (const Table &table, bool include_payload)

Static Public Attributes
static constexpr double	kMaxLoadFactor = 0.71

Detailed Description

Definition at line 570 of file hash_table.h.

Member Function Documentation

Copy()

template<typename From , typename To >

static void dart::HashTables::Copy ( const From &  from, const To &  to  )

inlinestatic

Definition at line 596 of file hash_table.h.

                                                   {
    COMPILE_ASSERT(From::kPayloadSize == To::kPayloadSize);
    to.Initialize();
    ASSERT(from.NumOccupied() < to.NumEntries());
    typename From::Iterator it(&from);
    Object& obj = Object::Handle();
    while (it.MoveNext()) {
      intptr_t from_entry = it.Current();
      obj = from.GetKey(from_entry);
      intptr_t to_entry = -1;
      const Object& key = obj;
      bool present = to.FindKeyOrDeletedOrUnused(key, &to_entry);
      ASSERT(!present);
      to.InsertKey(to_entry, obj);
      for (intptr_t i = 0; i < From::kPayloadSize; ++i) {
        obj = from.GetPayload(from_entry, i);
        to.UpdatePayload(to_entry, i, obj);
      }
    }
  }

EnsureLoadFactor()

template<typename Table >

static void dart::HashTables::EnsureLoadFactor ( double  high, const Table &  table  )

inlinestatic

Definition at line 620 of file hash_table.h.

                                                                {
    // We count deleted elements because they take up space just
    // like occupied slots in order to cause a rehashing.
    const double current = (1 + table.NumOccupied() + table.NumDeleted()) /
                           static_cast<double>(table.NumEntries());
    const bool too_many_deleted = table.NumOccupied() <= table.NumDeleted();
    if (current < high && !too_many_deleted) {
      return;
    }
 
    table.UpdateWeakDeleted();
 
    // Normally we double the size here, but if less than half are occupied
    // then it won't grow (this would imply that there were quite a lot of
    // deleted slots).  We don't want to constantly rehash if we are adding
    // and deleting entries at just under the load factor limit, so we may
    // double the size even though the number of occupied slots would not
    // necessarily justify it.  For example if the max load factor is 71% and
    // the table is 70% full we will double the size to avoid a rehash every
    // time 1% has been added and deleted.
    const intptr_t new_capacity = table.NumOccupied() * 2 + 1;
    ASSERT(table.NumOccupied() == 0 ||
           ((1.0 + table.NumOccupied()) /
            Utils::RoundUpToPowerOfTwo(new_capacity)) <= high);
    Table new_table(New<Table>(new_capacity,  // Is rounded up to power of 2.
                               table.data_->IsOld() ? Heap::kOld : Heap::kNew));
    Copy(table, new_table);
    Table::Storage::SetHandle(*table.data_, new_table.Release());
    NOT_IN_PRODUCT(table.UpdateGrowth(); table.PrintStats();)
  }

New() [1/2]

template<typename Table >

static Table::Storage::ArrayPtr dart::HashTables::New ( const typename Table::Storage::ArrayHandle &  array )

inlinestatic

Definition at line 586 of file hash_table.h.

                                                     {
    Table table(Thread::Current()->zone(), array.ptr());
    table.Initialize();
    return table.Release().ptr();
  }

New() [2/2]

template<typename Table >

static Table::Storage::ArrayPtr dart::HashTables::New ( intptr_t  initial_capacity, Heap::Space  space = Heap::kNew  )

inlinestatic

Definition at line 574 of file hash_table.h.

                                                                           {
    auto zone = Thread::Current()->zone();
    Table table(
        zone,
        Table::Storage::New(
            zone, Table::ArrayLengthForNumOccupied(initial_capacity), space));
    table.Initialize();
    return table.Release().ptr();
  }

ToArray()

template<typename Table >

static ArrayPtr dart::HashTables::ToArray ( const Table &  table, bool  include_payload  )

inlinestatic

Definition at line 653 of file hash_table.h.

                                                                    {
    const intptr_t entry_size = include_payload ? (1 + Table::kPayloadSize) : 1;
    Array& result = Array::Handle(Array::New(table.NumOccupied() * entry_size));
    typename Table::Iterator it(&table);
    Object& obj = Object::Handle();
    intptr_t result_index = 0;
    while (it.MoveNext()) {
      intptr_t entry = it.Current();
      obj = table.GetKey(entry);
      result.SetAt(result_index++, obj);
      if (include_payload) {
        for (intptr_t i = 0; i < Table::kPayloadSize; ++i) {
          obj = table.GetPayload(entry, i);
          result.SetAt(result_index++, obj);
        }
      }
    }
    return result.ptr();
  }

Member Data Documentation

kMaxLoadFactor

constexpr double dart::HashTables::kMaxLoadFactor = 0.71

staticconstexpr

Definition at line 617 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