#include <hash_map.h>

Inheritance diagram for dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >:

Classes
class	Iterator

Public Member Functions
	BaseDirectChainedHashMap (Allocator *allocator, intptr_t initial_size=kInitialSize)

	BaseDirectChainedHashMap (const BaseDirectChainedHashMap &other)

intptr_t	Length () const

	~BaseDirectChainedHashMap ()

void	Insert (typename KeyValueTrait::Pair kv)

bool	Remove (typename KeyValueTrait::Key key)

void	Update (typename KeyValueTrait::Pair kv)

KeyValueTrait::Value	LookupValue (typename KeyValueTrait::Key key) const

KeyValueTrait::Pair *	Lookup (typename KeyValueTrait::Key key) const

bool	HasKey (typename KeyValueTrait::Key key) const

intptr_t	Size () const

bool	IsEmpty () const

void	Clear ()

Iterator	GetIterator () const

Public Member Functions inherited from B
	B ()

void	setValues (int v) override

bool	checkValues (int v) override

Public Member Functions inherited from A
	A ()

virtual	~A ()

void *	operator new (size_t size)

void	operator delete (void *p)

Protected Member Functions
void	Resize (intptr_t new_size)

Protected Attributes
Allocator *const	allocator_

uint32_t *	hash_table_ = nullptr

KeyValueTrait::Pair *	pairs_ = nullptr

uint32_t	hash_table_size_ = 0

uint32_t	pairs_size_ = 0

uint32_t	next_pair_index_ = 0

uint32_t	deleted_count_ = 0

Static Protected Attributes
static constexpr intptr_t	kInitialSize = 16

static constexpr uint32_t	kEmpty = kMaxUint32

static constexpr uint32_t	kDeleted = kMaxUint32 - 1

static constexpr uint32_t	kMaxPairs = kMaxUint32 - 2

Additional Inherited Members
Static Public Member Functions inherited from A
static A *	Create (SkRandom *r)

static void	SetAllocator (size_t preallocSize, size_t minAllocSize)

static void	ResetAllocator ()

static void	ValidatePool ()

Detailed Description

template<typename KeyValueTrait, typename B, typename Allocator = Zone>
class dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >

Definition at line 17 of file hash_map.h.

Constructor & Destructor Documentation

◆ BaseDirectChainedHashMap() [1/2]

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::BaseDirectChainedHashMap	(	Allocator *	allocator,
		intptr_t	initial_size = `kInitialSize`
	)

inlineexplicit

Definition at line 19 of file hash_map.h.

      : allocator_(allocator) {
    Resize(initial_size);
  }

◆ BaseDirectChainedHashMap() [2/2]

template<typename KeyValueTrait , typename B , typename Allocator >

dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::BaseDirectChainedHashMap ( const BaseDirectChainedHashMap< KeyValueTrait, B, Allocator > & other )

Definition at line 111 of file hash_map.h.

    : B(),
      allocator_(other.allocator_),
      hash_table_(
          other.allocator_->template Alloc<uint32_t>(other.hash_table_size_)),
      pairs_(other.allocator_->template Alloc<typename KeyValueTrait::Pair>(
          other.pairs_size_)),
      hash_table_size_(other.hash_table_size_),
      pairs_size_(other.pairs_size_),
      next_pair_index_(other.next_pair_index_),
      deleted_count_(other.deleted_count_) {
  memmove(hash_table_, other.hash_table_, hash_table_size_ * sizeof(uint32_t));
  memmove(pairs_, other.pairs_,
          pairs_size_ * sizeof(typename KeyValueTrait::Pair));
}

◆ ~BaseDirectChainedHashMap()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::~BaseDirectChainedHashMap ( )

inline

Definition at line 29 of file hash_map.h.

                              {
    allocator_->template Free<uint32_t>(hash_table_, hash_table_size_);
    allocator_->template Free<typename KeyValueTrait::Pair>(pairs_,
                                                            pairs_size_);
  }

Member Function Documentation

◆ Clear()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

void dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Clear ( )

inline

Definition at line 59 of file hash_map.h.

               {
    for (uint32_t i = 0; i < hash_table_size_; i++) {
      hash_table_[i] = kEmpty;
    }
    for (uint32_t i = 0; i < next_pair_index_; i++) {
      pairs_[i] = typename KeyValueTrait::Pair();
    }
    next_pair_index_ = 0;
    deleted_count_ = 0;
  }

◆ GetIterator()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

Iterator dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::GetIterator ( ) const

inline

Definition at line 87 of file hash_map.h.

87{ return Iterator(*this); }

◆ HasKey()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

bool dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::HasKey ( typename KeyValueTrait::Key key ) const

inline

Definition at line 52 of file hash_map.h.

                                                   {
    return Lookup(key) != nullptr;
  }

◆ Insert()

template<typename KeyValueTrait , typename B , typename Allocator >

void dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Insert ( typename KeyValueTrait::Pair kv )

Definition at line 230 of file hash_map.h.

                                   {
  // TODO(dartbug.com/38018):
  // ASSERT(Lookup(KeyValueTrait::KeyOf(kv)) == nullptr);
  ASSERT(next_pair_index_ < pairs_size_);
  uword hash = KeyValueTrait::Hash(KeyValueTrait::KeyOf(kv));
  uint32_t mask = hash_table_size_ - 1;
  uint32_t hash_index = hash & mask;
  uint32_t start = hash_index;
  intptr_t probes = 0;
  for (;;) {
    uint32_t pair_index = hash_table_[hash_index];
    if ((pair_index == kEmpty) || (pair_index == kDeleted)) {
      hash_table_[hash_index] = next_pair_index_;
      pairs_[next_pair_index_] = kv;
      next_pair_index_++;
      break;
    }
    RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
    ASSERT(pair_index < pairs_size_);
    hash_index = (hash_index + 1) & mask;
    // Hashtable must contain at least one empty marker.
    ASSERT(hash_index != start);
  }
 
  if (next_pair_index_ == pairs_size_) {
    Resize(Size() << 1);
  }
}

◆ IsEmpty()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

bool dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::IsEmpty ( ) const

inline

Definition at line 57 of file hash_map.h.

57{ return Size() == 0; }

◆ Length()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

intptr_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Length ( ) const

inline

Definition at line 27 of file hash_map.h.

27{ return next_pair_index_ - deleted_count_; }

◆ Lookup()

template<typename KeyValueTrait , typename B , typename Allocator >

KeyValueTrait::Pair * dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Lookup ( typename KeyValueTrait::Key key ) const

Definition at line 130 of file hash_map.h.

                                         {
  uword hash = KeyValueTrait::Hash(key);
  uint32_t mask = hash_table_size_ - 1;
  uint32_t hash_index = hash & mask;
  uint32_t start = hash_index;
  intptr_t probes = 0;
  for (;;) {
    uint32_t pair_index = hash_table_[hash_index];
    if (pair_index == kEmpty) {
      return nullptr;
    }
    if (pair_index != kDeleted) {
      ASSERT(pair_index < pairs_size_);
      RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
      if (KeyValueTrait::IsKeyEqual(pairs_[pair_index], key)) {
        return &pairs_[pair_index];
      }
    }
    hash_index = (hash_index + 1) & mask;
    // Hashtable must contain at least one empty marker.
    ASSERT(hash_index != start);
  }
  UNREACHABLE();
  return nullptr;
}

◆ LookupValue()

template<typename KeyValueTrait , typename B , typename Allocator >

KeyValueTrait::Value dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::LookupValue ( typename KeyValueTrait::Key key ) const

Definition at line 159 of file hash_map.h.

                                         {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
  typename KeyValueTrait::Pair* pair = Lookup(key);
  return (pair == nullptr) ? kNoValue : KeyValueTrait::ValueOf(*pair);
}

◆ Remove()

template<typename KeyValueTrait , typename B , typename Allocator >

bool dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Remove ( typename KeyValueTrait::Key key )

Definition at line 275 of file hash_map.h.

                                   {
  uword hash = KeyValueTrait::Hash(key);
  uint32_t mask = hash_table_size_ - 1;
  uint32_t hash_index = hash & mask;
  uint32_t start = hash_index;
  intptr_t probes = 0;
  for (;;) {
    uint32_t pair_index = hash_table_[hash_index];
    if (pair_index == kEmpty) {
      return false;
    }
    if (pair_index != kDeleted) {
      ASSERT(pair_index < pairs_size_);
      RELEASE_ASSERT(++probes < FLAG_hash_map_probes_limit);
      if (KeyValueTrait::IsKeyEqual(pairs_[pair_index], key)) {
        hash_table_[hash_index] = kDeleted;
        pairs_[pair_index] = typename KeyValueTrait::Pair();
        deleted_count_++;
        return true;
      }
    }
    hash_index = (hash_index + 1) & mask;
    // Hashtable must contain at least one empty marker.
    ASSERT(hash_index != start);
  }
  UNREACHABLE();
  return false;
}

◆ Resize()

template<typename KeyValueTrait , typename B , typename Allocator >

void dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Resize ( intptr_t new_size )

protected

Definition at line 184 of file hash_map.h.

                       {
  ASSERT(new_size >= Size());
 
  uint32_t old_hash_table_size = hash_table_size_;
  // 75% load factor + at least one kEmpty slot
  hash_table_size_ = Utils::RoundUpToPowerOfTwo(new_size * 4 / 3 + 1);
  hash_table_ = allocator_->template Realloc<uint32_t>(
      hash_table_, old_hash_table_size, hash_table_size_);
  for (uint32_t i = 0; i < hash_table_size_; i++) {
    hash_table_[i] = kEmpty;
  }
 
  typename KeyValueTrait::Pair* old_pairs = pairs_;
  uint32_t old_pairs_size = pairs_size_;
  uint32_t old_next_pair_index = next_pair_index_;
  uint32_t old_deleted_count = deleted_count_;
  next_pair_index_ = 0;
  deleted_count_ = 0;
  pairs_size_ = new_size;
  pairs_ =
      allocator_->template Alloc<typename KeyValueTrait::Pair>(pairs_size_);
  for (uint32_t i = 0; i < pairs_size_; i++) {
    pairs_[i] = typename KeyValueTrait::Pair();
  }
 
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
  uint32_t used = 0;
  uint32_t deleted = 0;
  for (uint32_t i = 0; i < old_next_pair_index; i++) {
    if (KeyValueTrait::ValueOf(old_pairs[i]) == kNoValue) {
      deleted++;
    } else {
      Insert(old_pairs[i]);
      used++;
    }
  }
  ASSERT_EQUAL(deleted, old_deleted_count);
  ASSERT_EQUAL(used, old_next_pair_index - old_deleted_count);
  ASSERT_EQUAL(used, next_pair_index_);
  allocator_->template Free<typename KeyValueTrait::Pair>(old_pairs,
                                                          old_pairs_size);
}

◆ Size()

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

intptr_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Size ( ) const

inline

Definition at line 56 of file hash_map.h.

56{ return next_pair_index_ - deleted_count_; }

◆ Update()

template<typename KeyValueTrait , typename B , typename Allocator >

void dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::Update ( typename KeyValueTrait::Pair kv )

Definition at line 261 of file hash_map.h.

                                   {
  const typename KeyValueTrait::Value kNoValue =
      KeyValueTrait::ValueOf(typename KeyValueTrait::Pair());
 
  ASSERT(KeyValueTrait::ValueOf(kv) != kNoValue);
  if (auto const old_kv = Lookup(KeyValueTrait::KeyOf(kv))) {
    *old_kv = kv;
  } else {
    Insert(kv);
  }
}

Member Data Documentation

◆ allocator_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

Allocator* const dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::allocator_

protected

Definition at line 94 of file hash_map.h.

◆ deleted_count_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::deleted_count_ = 0

protected

Definition at line 100 of file hash_map.h.

◆ hash_table_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

uint32_t* dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::hash_table_ = nullptr

protected

Definition at line 95 of file hash_map.h.

◆ hash_table_size_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::hash_table_size_ = 0

protected

Definition at line 97 of file hash_map.h.

◆ kDeleted

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

constexpr uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::kDeleted = kMaxUint32 - 1

staticconstexprprotected

Definition at line 103 of file hash_map.h.

◆ kEmpty

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

constexpr uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::kEmpty = kMaxUint32

staticconstexprprotected

Definition at line 102 of file hash_map.h.

◆ kInitialSize

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

constexpr intptr_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::kInitialSize = 16

staticconstexprprotected

Definition at line 90 of file hash_map.h.

◆ kMaxPairs

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

constexpr uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::kMaxPairs = kMaxUint32 - 2

staticconstexprprotected

Definition at line 104 of file hash_map.h.

◆ next_pair_index_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::next_pair_index_ = 0

protected

Definition at line 99 of file hash_map.h.

◆ pairs_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

KeyValueTrait::Pair* dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::pairs_ = nullptr

protected

Definition at line 96 of file hash_map.h.

◆ pairs_size_

template<typename KeyValueTrait , typename B , typename Allocator = Zone>

uint32_t dart::BaseDirectChainedHashMap< KeyValueTrait, B, Allocator >::pairs_size_ = 0

protected

Definition at line 98 of file hash_map.h.

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

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

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Static Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ BaseDirectChainedHashMap() [1/2]

◆ BaseDirectChainedHashMap() [2/2]

◆ ~BaseDirectChainedHashMap()

Member Function Documentation

◆ Clear()

◆ GetIterator()

◆ HasKey()

◆ Insert()

◆ IsEmpty()

◆ Length()

◆ Lookup()

◆ LookupValue()

◆ Remove()

◆ Resize()

◆ Size()

◆ Update()

Member Data Documentation

◆ allocator_

◆ deleted_count_

◆ hash_table_

◆ hash_table_size_

◆ kDeleted

◆ kEmpty

◆ kInitialSize

◆ kMaxPairs

◆ next_pair_index_

◆ pairs_

◆ pairs_size_