CACAO
Data Structures | Public Types | Public Member Functions | Static Public Attributes | Private Member Functions | Static Private Member Functions | Private Attributes
HashTable< _Entry, _Allocator > Struct Template Reference

Data Structures

class  EntryRef
 
class  Iterator
 

Public Types

typedef _Entry Entry
 
typedef _Allocator Allocator
 

Public Member Functions

 HashTable ()
 
 HashTable (size_t initial_capacity, size_t load_factor=DEFAULT_LOAD_FACTOR)
 
 ~HashTable ()
 
template<typename T >
EntryRef find (const T &t)
 
template<typename T >
Entry & insert (const T &t)
 
template<typename T >
Entry & insert (EntryRef ref, const T &t)
 
template<typename T >
Entry & update (const T &t)
 
template<typename T >
Entry & update (EntryRef ref, const T &t)
 
template<typename Key , typename Val >
Entry & insert (const Key &k, const Val &v)
 Utility function for hashtables that store key value pairs. More...
 
template<typename Key , typename Val >
Entry & insert (EntryRef ref, const Key &k, const Val &v)
 Utility function for hashtables that store key value pairs. More...
 
template<typename Key , typename Val >
Entry & update (const Key &k, const Val &v)
 Utility function for hashtables that store key value pairs. More...
 
template<typename Key , typename Val >
Entry & update (EntryRef ref, const Key &k, const Val &v)
 Utility function for hashtables that store key value pairs. More...
 
void remove (EntryRef ref)
 
template<typename T >
void remove (const T &t)
 
void clear ()
 
void reserve (size_t n)
 
void set_load_factor (size_t load_factor)
 
Iterator begin ()
 
Iterator end ()
 
size_t size ()
 
bool empty ()
 

Static Public Attributes

static const size_t DEFAULT_INITIAL_CAPACITY = 256
 
static const size_t DEFAULT_LOAD_FACTOR = 85
 

Private Member Functions

 HashTable (const HashTable &)
 
HashTable & operator= (const HashTable &)
 
bool has_empty_entries ()
 
void grow_table (size_t new_capacity)
 Increase capacity, re-allocate table and copy over all old entries. More...
 
void allocate_table ()
 
void destroy (Entry *es, size_t sz)
 
void update_threshold ()
 

Static Private Member Functions

static Entry * next_occupied (Entry *current, Entry *end)
 

Private Attributes

Entry * entries
 
size_t capacity
 
size_t count
 
size_t deleted
 
size_t threshold
 
size_t load_factor
 
Allocator allocator
 

Detailed Description

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
struct HashTable< _Entry, _Allocator >

Definition at line 112 of file hashtable.hpp.

Member Typedef Documentation

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
typedef _Allocator HashTable< _Entry, _Allocator >::Allocator

Definition at line 114 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
typedef _Entry HashTable< _Entry, _Allocator >::Entry

Definition at line 113 of file hashtable.hpp.

Constructor & Destructor Documentation

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
HashTable< _Entry, _Allocator >::HashTable ( )
inline

Definition at line 124 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
HashTable< _Entry, _Allocator >::HashTable ( size_t  initial_capacity,
size_t  load_factor = DEFAULT_LOAD_FACTOR 
)
inline

Definition at line 131 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
HashTable< _Entry, _Allocator >::~HashTable ( )
inline

Definition at line 141 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
HashTable< _Entry, _Allocator >::HashTable ( const HashTable< _Entry, _Allocator > &  )
private

Member Function Documentation

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::allocate_table ( )
inlineprivate

Definition at line 516 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
Iterator HashTable< _Entry, _Allocator >::begin ( )
inline

Definition at line 442 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::clear ( )
inline

Definition at line 407 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::destroy ( Entry *  es,
size_t  sz 
)
inlineprivate

Definition at line 530 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
bool HashTable< _Entry, _Allocator >::empty ( )
inline

Definition at line 458 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
Iterator HashTable< _Entry, _Allocator >::end ( )
inline

Definition at line 453 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
EntryRef HashTable< _Entry, _Allocator >::find ( const T &  t)
inline

Definition at line 215 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::grow_table ( size_t  new_capacity)
inlineprivate

Increase capacity, re-allocate table and copy over all old entries.

Definition at line 470 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
bool HashTable< _Entry, _Allocator >::has_empty_entries ( )
inlineprivate

Definition at line 463 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
Entry& HashTable< _Entry, _Allocator >::insert ( const T &  t)
inline

Definition at line 273 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
Entry& HashTable< _Entry, _Allocator >::insert ( EntryRef  ref,
const T &  t 
)
inline

Definition at line 291 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename Key , typename Val >
Entry& HashTable< _Entry, _Allocator >::insert ( const Key &  k,
const Val &  v 
)
inline

Utility function for hashtables that store key value pairs.

Definition at line 346 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename Key , typename Val >
Entry& HashTable< _Entry, _Allocator >::insert ( EntryRef  ref,
const Key &  k,
const Val &  v 
)
inline

Utility function for hashtables that store key value pairs.

Definition at line 354 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
static Entry* HashTable< _Entry, _Allocator >::next_occupied ( Entry *  current,
Entry *  end 
)
inlinestaticprivate

Definition at line 542 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
HashTable& HashTable< _Entry, _Allocator >::operator= ( const HashTable< _Entry, _Allocator > &  )
private
template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::remove ( EntryRef  ref)
inline

Definition at line 383 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
void HashTable< _Entry, _Allocator >::remove ( const T &  t)
inline

Definition at line 400 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::reserve ( size_t  n)
inline

Definition at line 419 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::set_load_factor ( size_t  load_factor)
inline

Definition at line 431 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::size ( )
inline

Definition at line 457 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
Entry& HashTable< _Entry, _Allocator >::update ( const T &  t)
inline

Definition at line 310 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename T >
Entry& HashTable< _Entry, _Allocator >::update ( EntryRef  ref,
const T &  t 
)
inline

Definition at line 327 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename Key , typename Val >
Entry& HashTable< _Entry, _Allocator >::update ( const Key &  k,
const Val &  v 
)
inline

Utility function for hashtables that store key value pairs.

Definition at line 362 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
template<typename Key , typename Val >
Entry& HashTable< _Entry, _Allocator >::update ( EntryRef  ref,
const Key &  k,
const Val &  v 
)
inline

Utility function for hashtables that store key value pairs.

Definition at line 370 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
void HashTable< _Entry, _Allocator >::update_threshold ( )
inlineprivate

Definition at line 538 of file hashtable.hpp.

Field Documentation

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
Allocator HashTable< _Entry, _Allocator >::allocator
private

Definition at line 559 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::capacity
private

Definition at line 553 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::count
private

Definition at line 554 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
const size_t HashTable< _Entry, _Allocator >::DEFAULT_INITIAL_CAPACITY = 256
static

Definition at line 116 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
const size_t HashTable< _Entry, _Allocator >::DEFAULT_LOAD_FACTOR = 85
static

Definition at line 117 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::deleted
private

Definition at line 555 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
Entry* HashTable< _Entry, _Allocator >::entries
private

Definition at line 552 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::load_factor
private

Definition at line 558 of file hashtable.hpp.

template<typename _Entry, typename _Allocator = MemoryAllocator<_Entry>>
size_t HashTable< _Entry, _Allocator >::threshold
private

Definition at line 556 of file hashtable.hpp.

The documentation for this struct was generated from the following file:
Generated on Fri Aug 4 2017 03:02:00 for CACAO by   doxygen 1.8.5