ResidualVM logo ResidualVM website - Forums - Contact us BuildBot - Doxygen - Wiki curved edge

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 >:

List of all members.

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.
 HashMap (const HM_t &map)
 Copy constructor, creates a full copy of the given hashmap.
 ~HashMap ()
 Destructor, frees all used memory.
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.
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
Node ** _storage
 hashtable of size arrsize.
size_type _mask
 Capacity of the HashMap minus one; must be a power of two of minus one.
size_type _size
size_type _deleted
 Number of deleted elements (_dummyNodes).
HashFunc _hash
EqualFunc _equal
const Val _defaultVal
 Default value, returned by the const getVal.

Friends

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

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.

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.

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.

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

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

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.

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.

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

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

Definition at line 134 of file hashmap.h.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

Definition at line 142 of file hashmap.h.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

Definition at line 157 of file hashmap.h.


Member Data Documentation

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

Default value, returned by the const getVal.

Definition at line 125 of file hashmap.h.

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 119 of file hashmap.h.

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 122 of file hashmap.h.

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 121 of file hashmap.h.

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 117 of file hashmap.h.

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.

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 118 of file hashmap.h.

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 116 of file hashmap.h.


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


Generated on Sat Jan 12 2019 05:04:11 for ResidualVM by doxygen 1.7.1
curved edge   curved edge