Clarisse 5.0 SP8 SDK  5.0.5.8.0
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Classes | Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | Friends | List of all members
CoreHashTableDense< T, U > Class Template Reference

Classes

class  Iterator
 

Public Member Functions

 CoreHashTableDense (const unsigned int &hash_size=CoreHashTableDense::HASH_TABLE_DEFAULT_SIZE)
 
 CoreHashTableDense (const CoreHashTableDense &hash)
 
void add (const T &key, const U &item)
 
void set (const T &key, const U &item)
 
U & operator[] (const T &key)
 
const U & operator[] (const T &key) const
 
U & get_value (const T &key) const
 
void remove (const T &key)
 
void remove_all ()
 
const unsigned int & get_count () const
 
CoreArray< T > get_keys () const
 
CoreArray< U > get_values () const
 
U * is_key_exists (const T &key) const
 
void copy_from (const CoreHashTableDense &hash)
 
CoreHashTableDense< T, U > & operator= (const CoreHashTableDense &hash)
 
void refit ()
 
size_t get_memory_size () const
 
CoreHashTableIterator< T, U, true > begin (void) const
 
CoreHashTableIterator< T, U,
false > 
begin (void)
 
CoreHashTableIterator< T, U, true > end (void) const
 
CoreHashTableIterator< T, U,
false > 
end (void)
 

Static Public Attributes

static const unsigned int HASH_TABLE_UNASSIGNED_KEY = 0xFFFFFFFF
 
static const unsigned int HASH_TABLE_DIRTY_KEY_TO_REMOVE = 0xFFFFFFFE
 
static const unsigned int HASH_TABLE_DEFAULT_SIZE = 16
 
static const float HASH_TABLE_DEFAULT_THRESHOLD = 0.8
 

Protected Member Functions

unsigned int hash_1 (const unsigned int &key) const
 
unsigned int hash_2 (const unsigned int &key) const
 
unsigned int rehash (const unsigned int &previous_index, const unsigned int &key) const
 
CoreHashTableDenseNode< T, U > * get_node (const T &key, unsigned int &hash_key, const bool &write) const
 
CoreHashTableDenseNode< T, U > * get_node_from_key (const T &key, const unsigned int &hash_key, const bool &write) const
 
void resize (const int &size)
 
void repopulate_table () const
 

Protected Attributes

CoreHashTableDenseNode< T, U > * m_table
 
unsigned int m_table_count
 
unsigned int m_key_count
 
unsigned int m_dirty_key_count
 
unsigned int m_previous_table_count
 
unsigned int m_start_table_count
 
unsigned int m_resize_upper_limit
 
unsigned int m_resize_lower_limit
 

Friends

class CoreHashTable< T, U >
 
class CoreHashTableIterator< T, U, false >
 
class CoreHashTableIterator< T, U, true >
 

Detailed Description

template<class T, class U>
class CoreHashTableDense< T, U >

Legacy comment: Access efficient template collection of Key/Value objects couples when the number of element is dense The implementation relies on an internal array hosting key and values. The array is automatically resized when the number of items increases. Collisions are handled by rehashing until it finds a new empty slot. In other words removing elements invalidates a typical slot which is flagged as dirty. Due to our collision strategy, a "dirty" slot can then be only reused if the newly added item shares the exact same key as its previous owner. If a lot of removing is performed, it is advised to call the CoreHashTableDense::refit method as performance can be degraded. This method will reallocate the hash table and free up all dirty slots and free up unused memory.

New: To add support for structs or classes as key (e.g. CoreHashTableDense<Foo, int>) you need to implement the core_get_hash function for that type. Here is an exemple:

``` struct Foo { unsigned int a; unsigned int b; inline bool operator == (const Foo& other) const { return a == other.a && b == other.b; } };

inline unsigned int core_get_hash(const Foo& value) { return CoreHash::combine(value.a, value.b); }

// now you can declare and use the following: CoreHashTable<Foo, int> table; ```

You can see CoreHash monostate to check available hash helpers. Use the ones dealing with Core32BitHashKey only (CoreHashTableDense uses unsigned int keys) Here is an example with a slightly more complicated key structure:

``` struct Foo { CoreString str; SomeClass *pointer; double d;

// implementation ommited for the example's sake inline bool operator == (const Foo& other) const; };

inline unsigned int core_get_hash(const Foo& value) { return CoreHash::combine( CoreHash::generate_jenkins(value.str.get_data(), value.str.get_count()), CoreHash::get_hash(value.pointer), CoreHash::get_hash(value.d) }; } ```

Note
In the past, the implementation of the CoreHashTableDense was always using the implementation of CoreHash::generate_jenkins, no matter what the type was. This was not really performant since it was hashing byte by byte, even if the type was a pointer or numeric type that could be used almost as is.

Another problem with that is that if the structure contained some allocated data (for instance if it contained a CoreString) it couldn't work: what was hashed was the value of the CoreString's m_data member instead of the actual string's data. So once a value was added, you couldn't access it anymore using a temporary key.

So if you need to hash a complex structure that only contains pod data and want to do a quick test, you can use the old implementation:

``` inline unsigned int core_get_hash(const BigStruct& value) { return CoreHash::generate_jenkins(&value, sizeof(BigStruct)); } ```

For anything else it's highly recommanded to prefer the new hash functions.

See Also
CoreHash

Member Function Documentation

template<class T , class U >
CoreHashTableIterator< T, U, true > CoreHashTableDense< T, U >::begin ( void  ) const
inline

Get a const iterator on the first node of the table.

template<class T , class U >
CoreHashTableIterator< T, U, false > CoreHashTableDense< T, U >::begin ( void  )
inline

Get an iterator on the first node of the table.

template<class T , class U >
CoreHashTableIterator< T, U, true > CoreHashTableDense< T, U >::end ( void  ) const
inline

Get a const iterator on the node past the last one of the table.

template<class T , class U >
CoreHashTableIterator< T, U, false > CoreHashTableDense< T, U >::end ( void  )
inline

Get an iterator on the node past the last one of the table.