CrystalSpace

Public API Reference

csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > Class Template Reference
[Containers]

A generic hash table class, which grows dynamically and whose buckets are unsorted arrays. More...

#include <csutil/hash.h>

Inheritance diagram for csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >:

List of all members.

Classes

class  ConstGlobalIterator
 An const iterator class for the csHash class. More...
class  ConstIterator
 An const iterator class for the csHash class. More...
class  GlobalIterator
 An iterator class for the csHash class. More...
class  Iterator
 An iterator class for the csHash class. More...

Public Member Functions

bool Contains (const K &key) const
 Returns whether at least one element matches the given key.
 csHash (const csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > &o)
 Copy constructor.
 csHash (size_t size=23, size_t grow_rate=5, size_t max_size=20000)
 Construct a hash table with an array of the given size, which for optimisation reasons should be a prime number.
bool Delete (const K &key, const T &value)
 Delete all the elements matching the given key and value.
bool DeleteAll (const K &key)
 Delete all the elements matching the given key.
void DeleteAll ()
 Delete all the elements.
void DeleteElement (ConstGlobalIterator &iterator)
 Delete the element pointed by the iterator.
void DeleteElement (GlobalIterator &iterator)
 Delete the element pointed by the iterator.
void Empty ()
 Delete all the elements. (Idiomatic alias for DeleteAll().).
T & Get (const K &key, T &fallback)
 Get the first element matching the given key, or fallback if there is none.
const T & Get (const K &key, const T &fallback) const
 Get the first element matching the given key, or fallback if there is none.
template<typename H , typename M >
csArray< T, H, M > GetAll (const K &key) const
 Get all the elements with the given key, or empty if there are none.
csArray< T > GetAll (const K &key) const
 Get all the elements with the given key, or empty if there are none.
csArray< T > GetAll () const
 Get all the elements, or empty if there are none.
T * GetElementPointer (const K &key)
 Get a pointer to the first element matching the given key, or 0 if there is none.
const T * GetElementPointer (const K &key) const
 Get a pointer to the first element matching the given key, or 0 if there is none.
ConstGlobalIterator GetIterator () const
 Return a const iterator for the hash, to iterate over all elements.
ConstIterator GetIterator (const K &key) const
 Return a const iterator for the hash, to iterate only over the elements with the given key.
GlobalIterator GetIterator ()
 Return an iterator for the hash, to iterate over all elements.
Iterator GetIterator (const K &key)
 Return an iterator for the hash, to iterate only over the elements with the given key.
T & GetOrCreate (const K &key, const T &defaultValue=T())
 Get the first element matching the given key, or, if there is none, insert default and return a reference to the new entry.
size_t GetSize () const
 Get the number of elements in the hash.
bool In (const K &key) const
 Returns whether at least one element matches the given key.
bool IsEmpty () const
 Return true if the hash is empty.
T * operator[] (const K &key)
 h["key"] shorthand notation for h.GetElementPointer ("key")
T & Put (const K &key, const T &value)
 Add an element to the hash table.
T & PutUnique (const K &key, const T &value)
 Add an element to the hash table, overwriting if the key already exists.

Detailed Description

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
class csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >

A generic hash table class, which grows dynamically and whose buckets are unsorted arrays.

The hash value of a key is computed using csHashComputer<>, two keys are compared using csComparator<>. You need to provide appropriate specializations of those templates if you want use non-integral types (other than const char* and csString for which appropriate specializations are already provided) or special hash algorithms.

Definition at line 128 of file hash.h.


Constructor & Destructor Documentation

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::csHash ( size_t  size = 23,
size_t  grow_rate = 5,
size_t  max_size = 20000 
) [inline]

Construct a hash table with an array of the given size, which for optimisation reasons should be a prime number.

grow_rate is the rate at which the hash table grows: size doubles once there are size/grow_rate collisions. It will not grow after it reaches max_size.

Here are a few primes: 7, 11, 19, 29, 59, 79, 101, 127, 151, 199, 251, 307, 401, 503, 809, 1009, 1499, 2003, 3001, 5003, 12263, 25247, 36923, 50119, 70951, 90313, 104707.

For a bigger list go to http://www.utm.edu/research/primes/

Definition at line 203 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::csHash ( const csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler > &  o  )  [inline]

Copy constructor.

Definition at line 210 of file hash.h.


Member Function Documentation

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Contains ( const K &  key  )  const [inline]

Returns whether at least one element matches the given key.

Definition at line 311 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Delete ( const K &  key,
const T &  value 
) [inline]

Delete all the elements matching the given key and value.

Reimplemented in csHashReversible< T, K >.

Definition at line 473 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteAll ( const K &  key  )  [inline]

Delete all the elements matching the given key.

Reimplemented in csHashReversible< T, K >.

Definition at line 453 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteAll (  )  [inline]

Delete all the elements.

Reimplemented in csHashReversible< T, K >.

Definition at line 442 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteElement ( ConstGlobalIterator iterator  )  [inline]

Delete the element pointed by the iterator.

This is safe for this iterator, not for the others.

Definition at line 887 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::DeleteElement ( GlobalIterator iterator  )  [inline]

Delete the element pointed by the iterator.

This is safe for this iterator, not for the others.

Definition at line 877 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
void csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Empty (  )  [inline]

Delete all the elements. (Idiomatic alias for DeleteAll().).

Definition at line 450 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Get ( const K &  key,
T &  fallback 
) [inline]

Get the first element matching the given key, or fallback if there is none.

Definition at line 403 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
const T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Get ( const K &  key,
const T &  fallback 
) const [inline]

Get the first element matching the given key, or fallback if there is none.

Definition at line 383 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
template<typename H , typename M >
csArray<T, H, M> csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetAll ( const K &  key  )  const [inline]

Get all the elements with the given key, or empty if there are none.

Definition at line 264 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
csArray<T> csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetAll ( const K &  key  )  const [inline]

Get all the elements with the given key, or empty if there are none.

Definition at line 256 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
csArray<T> csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetAll (  )  const [inline]

Get all the elements, or empty if there are none.

Definition at line 241 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetElementPointer ( const K &  key  )  [inline]

Get a pointer to the first element matching the given key, or 0 if there is none.

Definition at line 355 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
const T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetElementPointer ( const K &  key  )  const [inline]

Get a pointer to the first element matching the given key, or 0 if there is none.

Definition at line 335 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
ConstGlobalIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetIterator (  )  const [inline]

Return a const iterator for the hash, to iterate over all elements.

Warning:
Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 932 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
ConstIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetIterator ( const K &  key  )  const [inline]

Return a const iterator for the hash, to iterate only over the elements with the given key.

Warning:
Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 922 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
GlobalIterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetIterator (  )  [inline]

Return an iterator for the hash, to iterate over all elements.

Warning:
Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Reimplemented in CS::Container::WeakKeyedHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >, and CS::Container::WeakKeyedHash< csRef< CachedCursor >, csWeakRef< iImage > >.

Definition at line 911 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
Iterator csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetIterator ( const K &  key  )  [inline]

Return an iterator for the hash, to iterate only over the elements with the given key.

Warning:
Modifying the hash (except with DeleteElement()) while you have open iterators will result in undefined behaviour.

Definition at line 901 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetOrCreate ( const K &  key,
const T &  defaultValue = T() 
) [inline]

Get the first element matching the given key, or, if there is none, insert default and return a reference to the new entry.

Definition at line 423 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
size_t csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::GetSize (  )  const [inline]

Get the number of elements in the hash.

Definition at line 494 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::In ( const K &  key  )  const [inline]

Returns whether at least one element matches the given key.

Remarks:
This is rigidly equivalent to Contains(key), but may be considered more idiomatic by some.

Definition at line 328 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
bool csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::IsEmpty (  )  const [inline]

Return true if the hash is empty.

Remarks:
Rigidly equivalent to return GetSize() == 0, but more idiomatic.

Definition at line 504 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T* csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::operator[] ( const K &  key  )  [inline]

h["key"] shorthand notation for h.GetElementPointer ("key")

Definition at line 374 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::Put ( const K &  key,
const T &  value 
) [inline]

Add an element to the hash table.

Remarks:
If key is already present, does NOT replace the existing value, but merely adds value as an additional value of key. To retrieve all values for a given key, use GetAll(). If you instead want to replace an existing value for key, use PutUnique().

Reimplemented in csHashReversible< T, K >, CS::Container::WeakKeyedHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >, and CS::Container::WeakKeyedHash< csRef< CachedCursor >, csWeakRef< iImage > >.

Definition at line 222 of file hash.h.

template<class T, class K = unsigned int, class ArrayMemoryAlloc = CS::Memory::AllocatorMalloc, class ArrayElementHandler = csArrayElementHandler< CS::Container::HashElement<T, K> >>
T& csHash< T, K, ArrayMemoryAlloc, ArrayElementHandler >::PutUnique ( const K &  key,
const T &  value 
) [inline]

Add an element to the hash table, overwriting if the key already exists.

Reimplemented in csHashReversible< T, K >.

Definition at line 281 of file hash.h.


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

Generated for Crystal Space 2.0 by doxygen 1.6.1