ScummVM
Common::HashMap< Key, Val, HashFunc, EqualFunc > Class Template Reference

HashMap<Key,Val> maps objects of type Key to objects of type Val. More...

#include <hashmap.h>

Collaboration diagram for Common::HashMap< Key, Val, HashFunc, EqualFunc >:

Classes

class  IteratorImpl
 Simple HashMap iterator implementation. More...
 
struct  Node
 

Public Types

typedef uint size_type
 
typedef IteratorImpl< Nodeiterator
 
typedef IteratorImpl< const Nodeconst_iterator
 

Public Member Functions

 HashMap ()
 Base constructor, creates an empty hashmap. More...
 
 HashMap (const HM_t &map)
 Copy constructor, creates a full copy of the given hashmap. More...
 
 ~HashMap ()
 Destructor, frees all used memory. More...
 
HM_toperator= (const HM_t &map)
 
bool contains (const Key &key) const
 
Val & operator[] (const Key &key)
 
const Val & operator[] (const Key &key) const
 
Val & getVal (const Key &key)
 
const Val & getVal (const Key &key) const
 
const Val & getVal (const Key &key, const Val &defaultVal) const
 
void setVal (const Key &key, const Val &val)
 
void clear (bool shrinkArray=0)
 
void erase (iterator entry)
 
void erase (const Key &key)
 
size_type size () const
 
iterator begin ()
 
iterator end ()
 
const_iterator begin () const
 
const_iterator end () const
 
iterator find (const Key &key)
 
const_iterator find (const Key &key) const
 
bool empty () const
 

Private Types

enum  {
  HASHMAP_PERTURB_SHIFT = 5, HASHMAP_MIN_CAPACITY = 16, HASHMAP_LOADFACTOR_NUMERATOR = 2, HASHMAP_LOADFACTOR_DENOMINATOR = 3,
  HASHMAP_MEMORYPOOL_SIZE = HASHMAP_MIN_CAPACITY * HASHMAP_LOADFACTOR_NUMERATOR / HASHMAP_LOADFACTOR_DENOMINATOR
}
 
typedef HashMap< Key, Val, HashFunc, EqualFunc > HM_t
 

Private Member Functions

NodeallocNode (const Key &key)
 
void freeNode (Node *node)
 
void assign (const HM_t &map)
 Internal method for assigning the content of another HashMap to this one. More...
 
size_type lookup (const Key &key) const
 
size_type lookupAndCreateIfMissing (const Key &key)
 
void expandStorage (size_type newCapacity)
 

Private Attributes

ObjectPool< Node, HASHMAP_MEMORYPOOL_SIZE_nodePool
 
Val _defaultVal
 Default value, returned by the const getVal. More...
 
Node ** _storage
 hashtable of size arrsize. More...
 
size_type _mask
 Capacity of the HashMap minus one; must be a power of two of minus one. More...
 
size_type _size
 
size_type _deleted
 Number of deleted elements (_dummyNodes) More...
 
HashFunc _hash
 
EqualFunc _equal
 

Friends

template<class T >
class IteratorImpl
 

Detailed Description

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
class Common::HashMap< Key, Val, HashFunc, EqualFunc >

HashMap<Key,Val> maps objects of type Key to objects of type Val.

For each used Key type, we need an "size_type hashit(Key,size_type)" function that computes a hash for the given Key object and returns it as an an integer from 0 to hashsize-1, and also an "equality functor". that returns true if if its two arguments are to be considered equal. Also, we assume that "=" works on Val objects for assignment.

If aa is an HashMap<Key,Val>, then space is allocated each time aa[key] is referenced, for a new key. If the object is const, then an assertion is triggered instead. Hence if you are not sure whether a key is contained in the map, use contains() first to check for its presence.

Definition at line 82 of file hashmap.h.

Member Typedef Documentation

◆ const_iterator

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
typedef IteratorImpl<const Node> Common::HashMap< Key, Val, HashFunc, EqualFunc >::const_iterator

Definition at line 220 of file hashmap.h.

◆ HM_t

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
typedef HashMap<Key, Val, HashFunc, EqualFunc> Common::HashMap< Key, Val, HashFunc, EqualFunc >::HM_t
private

Definition at line 88 of file hashmap.h.

◆ iterator

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
typedef IteratorImpl<Node> Common::HashMap< Key, Val, HashFunc, EqualFunc >::iterator

Definition at line 219 of file hashmap.h.

◆ size_type

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
typedef uint Common::HashMap< Key, Val, HashFunc, EqualFunc >::size_type

Definition at line 84 of file hashmap.h.

Member Enumeration Documentation

◆ anonymous enum

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
anonymous enum
private
Enumerator
HASHMAP_PERTURB_SHIFT 
HASHMAP_MIN_CAPACITY 
HASHMAP_LOADFACTOR_NUMERATOR 
HASHMAP_LOADFACTOR_DENOMINATOR 
HASHMAP_MEMORYPOOL_SIZE 

Definition at line 97 of file hashmap.h.

Constructor & Destructor Documentation

◆ HashMap() [1/2]

template<class Key , class Val , class HashFunc , class EqualFunc >
Common::HashMap< Key, Val, HashFunc, EqualFunc >::HashMap ( )

Base constructor, creates an empty hashmap.

Definition at line 307 of file hashmap.h.

◆ HashMap() [2/2]

template<class Key , class Val , class HashFunc , class EqualFunc >
Common::HashMap< Key, Val, HashFunc, EqualFunc >::HashMap ( const HM_t map)

Copy constructor, creates a full copy of the given hashmap.

We must provide a custom copy constructor as we use pointers to heap buffers for the internal storage.

Definition at line 337 of file hashmap.h.

◆ ~HashMap()

template<class Key , class Val , class HashFunc , class EqualFunc >
Common::HashMap< Key, Val, HashFunc, EqualFunc >::~HashMap ( )

Destructor, frees all used memory.

Definition at line 351 of file hashmap.h.

Member Function Documentation

◆ allocNode()

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
Node* Common::HashMap< Key, Val, HashFunc, EqualFunc >::allocNode ( const Key &  key)
inlineprivate

Definition at line 134 of file hashmap.h.

◆ assign()

template<class Key , class Val , class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::assign ( const HM_t map)
private

Internal method for assigning the content of another HashMap to this one.

Note
We do not deallocate the previous storage here – the caller is responsible for doing that!

Definition at line 370 of file hashmap.h.

◆ begin() [1/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::begin ( )
inline

Definition at line 255 of file hashmap.h.

◆ begin() [2/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
const_iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::begin ( ) const
inline

Definition at line 267 of file hashmap.h.

◆ clear()

template<class Key , class Val , class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::clear ( bool  shrinkArray = 0)

Definition at line 396 of file hashmap.h.

◆ contains()

template<class Key, class Val , class HashFunc , class EqualFunc >
bool Common::HashMap< Key, Val, HashFunc, EqualFunc >::contains ( const Key &  key) const

Definition at line 558 of file hashmap.h.

◆ empty()

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
bool Common::HashMap< Key, Val, HashFunc, EqualFunc >::empty ( ) const
inline

Definition at line 295 of file hashmap.h.

◆ end() [1/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::end ( )
inline

Definition at line 263 of file hashmap.h.

◆ end() [2/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
const_iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::end ( ) const
inline

Definition at line 275 of file hashmap.h.

◆ erase() [1/2]

template<class Key , class Val , class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::erase ( iterator  entry)

Definition at line 602 of file hashmap.h.

◆ erase() [2/2]

template<class Key, class Val , class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::erase ( const Key &  key)

Definition at line 619 of file hashmap.h.

◆ expandStorage()

template<class Key , class Val , class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::expandStorage ( size_type  newCapacity)
private

Definition at line 420 of file hashmap.h.

◆ find() [1/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::find ( const Key &  key)
inline

Definition at line 279 of file hashmap.h.

◆ find() [2/2]

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
const_iterator Common::HashMap< Key, Val, HashFunc, EqualFunc >::find ( const Key &  key) const
inline

Definition at line 286 of file hashmap.h.

◆ freeNode()

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::freeNode ( Node node)
inlineprivate

Definition at line 142 of file hashmap.h.

◆ getVal() [1/3]

template<class Key, class Val , class HashFunc , class EqualFunc >
Val & Common::HashMap< Key, Val, HashFunc, EqualFunc >::getVal ( const Key &  key)

Definition at line 574 of file hashmap.h.

◆ getVal() [2/3]

template<class Key, class Val , class HashFunc , class EqualFunc >
const Val & Common::HashMap< Key, Val, HashFunc, EqualFunc >::getVal ( const Key &  key) const

Definition at line 581 of file hashmap.h.

◆ getVal() [3/3]

template<class Key, class Val, class HashFunc , class EqualFunc >
const Val & Common::HashMap< Key, Val, HashFunc, EqualFunc >::getVal ( const Key &  key,
const Val &  defaultVal 
) const

Definition at line 586 of file hashmap.h.

◆ lookup()

template<class Key, class Val , class HashFunc , class EqualFunc >
HashMap< Key, Val, HashFunc, EqualFunc >::size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::lookup ( const Key &  key) const
private

Definition at line 466 of file hashmap.h.

◆ lookupAndCreateIfMissing()

template<class Key, class Val , class HashFunc , class EqualFunc >
HashMap< Key, Val, HashFunc, EqualFunc >::size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::lookupAndCreateIfMissing ( const Key &  key)
private

Definition at line 497 of file hashmap.h.

◆ operator=()

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
HM_t& Common::HashMap< Key, Val, HashFunc, EqualFunc >::operator= ( const HM_t map)
inline

Definition at line 226 of file hashmap.h.

◆ operator[]() [1/2]

template<class Key, class Val , class HashFunc , class EqualFunc >
Val & Common::HashMap< Key, Val, HashFunc, EqualFunc >::operator[] ( const Key &  key)

Definition at line 564 of file hashmap.h.

◆ operator[]() [2/2]

template<class Key, class Val , class HashFunc , class EqualFunc >
const Val & Common::HashMap< Key, Val, HashFunc, EqualFunc >::operator[] ( const Key &  key) const

Definition at line 569 of file hashmap.h.

◆ setVal()

template<class Key, class Val, class HashFunc , class EqualFunc >
void Common::HashMap< Key, Val, HashFunc, EqualFunc >::setVal ( const Key &  key,
const Val &  val 
)

Definition at line 595 of file hashmap.h.

◆ size()

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::size ( ) const
inline

Definition at line 253 of file hashmap.h.

Friends And Related Function Documentation

◆ IteratorImpl

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
template<class T >
friend class IteratorImpl
friend

Definition at line 157 of file hashmap.h.

Member Data Documentation

◆ _defaultVal

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
Val Common::HashMap< Key, Val, HashFunc, EqualFunc >::_defaultVal
private

Default value, returned by the const getVal.

Definition at line 117 of file hashmap.h.

◆ _deleted

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::_deleted
private

Number of deleted elements (_dummyNodes)

Definition at line 122 of file hashmap.h.

◆ _equal

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
EqualFunc Common::HashMap< Key, Val, HashFunc, EqualFunc >::_equal
private

Definition at line 125 of file hashmap.h.

◆ _hash

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
HashFunc Common::HashMap< Key, Val, HashFunc, EqualFunc >::_hash
private

Definition at line 124 of file hashmap.h.

◆ _mask

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::_mask
private

Capacity of the HashMap minus one; must be a power of two of minus one.

Definition at line 120 of file hashmap.h.

◆ _nodePool

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
ObjectPool<Node, HASHMAP_MEMORYPOOL_SIZE> Common::HashMap< Key, Val, HashFunc, EqualFunc >::_nodePool
private

Definition at line 113 of file hashmap.h.

◆ _size

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
size_type Common::HashMap< Key, Val, HashFunc, EqualFunc >::_size
private

Definition at line 121 of file hashmap.h.

◆ _storage

template<class Key, class Val, class HashFunc = Hash<Key>, class EqualFunc = EqualTo<Key>>
Node** Common::HashMap< Key, Val, HashFunc, EqualFunc >::_storage
private

hashtable of size arrsize.

Definition at line 119 of file hashmap.h.


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