Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members   Related Pages   Examples  

hashtable Template Class Reference

Simple hash table implementation. More...

#include <hashtable.h>

Inheritance diagram for hashtable:

type_allocator List of all members.

Public Types

typedef hash_link<T> hash_object_list
 Link list of hashed objects.

typedef hash_link<T>::iterator hash_iterator
 iterator over equalivalent hash values.

typedef hash_link<T>::const_iterator const_hash_iterator
 iterator over equalivalent hash values.

typedef hash_list::iterator iterator
 iterator to hash table contents.

typedef hash_list::const_iterator const_iterator
 iterator to hash table contents.

typedef hash_list::reference reference
 Reference to hash table index.

typedef hash_list::const_reference const_reference
 Reference to hash table index.


Public Methods

 hashtable (double thr=def_threshold)
 hashtable (const hashtable& ht)
 Copy contents of hash table into current one.

hashtable& operator= (const hashtable& ht)
 Make equal hash tables. More...

 ~hashtable ()
 Invoke destroy_obj so compilers that cannot handle ~() can still use in type_allocator list.

void destroy_obj ()
 Delete all contents of the hash table. More...

void erase (iterator s)
 Remove one of entry.

void erase (iterator s, iterator e)
 Remove range of entries.

size_t getOccupancy () const
 Get current occupancy. More...

double getThreshold () const
 Get current threshold. More...

void setThreshold (double thr)
 Set threshold within allowable limits. More...

size_t nextPrimeAllocation (size_t n) const
 Determine the next prime number >= n. More...

void clear_hash_table ()
 Clear table for future reuse.

void reservePrimeSpace (size_t sz)
 Reserve enough space so that we have enough room for specified number of entries using the current threshold as the occupancy of that number of entries. More...

void reservePrimeArray (size_t sz)
 Reallocate array if specified size is below current allocated size. More...

void initialize_table (size_t sz)
 Allocate a prime number of slots. More...

iterator find_hash_link (size_t hashval)
 Find the hash table link list entry to use for the specified hash value. More...

const_iterator find_hash_link (size_t hashval) const
void reallocate_hash_table ()
 Resize the hash table to next prime number.

hash_iterator insert (const T& next, size_t hashval)
 Insert object into hash table. More...

hash_iterator insert (const T& next)
 As long as the object responds to hash, we can directly add to hash table. More...

void erase (const T& next, size_t hashval)
 Remove specified object from the hash table. More...

void erase (const T& next)
hash_iterator find (const T& next, size_t hv)
 Find the object matching specified object in the hash table. More...

hash_iterator find (const T& next)
const_hash_iterator find (const T& next, size_t hv) const
const_hash_iterator find (const T& next) const
hash_iterator begin_serial ()
 Begin the serial report of the hash table.

const_hash_iterator begin_serial () const
hash_iterator next_serial ()
 Return next entry in hash table.

const_hash_iterator next_serial () const

Protected Attributes

size_t occupancy
 How much of the table is currently occupied by entries. More...

double threshold
 If occupancy goes above this threshold, then reallocate the hash table.

Detailed Description

template<class T> template class hashtable

Simple hash table implementation.

Link lists are made ONLY of objects with the SAME absolute hash value. We then dynamically allocate a link list. When we resize the table, we only have to move the pointer as opposed to copying every object in the table.

Examples:

hashtable.cxx, and OpenGatewayBase.C.

Member Function Documentation

template<classT>
hashtable<T> & hashtable<T>::operator= ( const hashtable<T> & ht ) [inline]
 

Make equal hash tables.

All objects are copied as opposed to some ownership count. This operation might therefore be expensive.

template<classT>
void hashtable<T>::destroy_obj ( ) [inline]
 

Delete all contents of the hash table.

Override the base class because destroy(void *) does nothing. This guarantees that all hash links are deleted before we delete all of the elements.

Reimplemented from type_allocator.

template<classT>
size_t hashtable<T>::getOccupancy ( ) const [inline]
 

Get current occupancy.

Returns:
occupancy.
Examples:
hashtable.cxx.

template<classT>
double hashtable<T>::getThreshold ( ) const [inline]
 

Get current threshold.

Returns:
threshold.

template<classT>
void hashtable<T>::setThreshold ( double thr ) [inline]
 

Set threshold within allowable limits.

Parameters:
thr   threshold to set.

template<classT>
size_t hashtable<T>::nextPrimeAllocation ( size_t n ) const [inline]
 

Determine the next prime number >= n.

If n itself is a prime number, return the number itself. Uses nextAllocation to determine the start of the next prime number search.

See also:
nextAllocation().
Parameters:
n   allocation is next prime number greater than this value.
Returns:
first prime number greater than n.

template<classT>
void hashtable<T>::reservePrimeSpace ( size_t sz ) [inline]
 

Reserve enough space so that we have enough room for specified number of entries using the current threshold as the occupancy of that number of entries.

Parameters:
sz   requested array size.

template<classT>
void hashtable<T>::reservePrimeArray ( size_t sz ) [inline]
 

Reallocate array if specified size is below current allocated size.

Parameters:
sz   requested array size.

template<classT>
void hashtable<T>::initialize_table ( size_t sz ) [inline]
 

Allocate a prime number of slots.

If the table is too small, resize the table to next prime number. Initialize the table with 0 pointer values. to specified size.

Parameters:
sz   requested initial size of the hash table.

template<classT>
iterator hashtable<T>::find_hash_link ( size_t hashval ) [inline]
 

Find the hash table link list entry to use for the specified hash value.

Parameters:
hashval   hash table value to find.
Returns:
iterator to entry to use.

template<classT>
const_iterator hashtable<T>::find_hash_link ( size_t hashval ) const [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<classT>
hash_iterator hashtable<T>::insert ( const T & next,
size_t hashval ) [inline]
 

Insert object into hash table.

We use hash value of the object mod the current hash table size as the start index. Look for the first hash list that matches the hash value OR the first 0 pointer. If we match hash value, then add object to end of link list. If we find a 0 pointer, create new hash link list and bump up the occupancy count by 1. If the occupancy exceeds threshold percentage, reallocate hash table to next prime number of put each link list into proper place on table.

Parameters:
next   object to insert into table.
hashval   externally computed hash value.
Returns:
iterator to link list that holds the inserted object. p == 0 indicates a real bug because the table is full but wasn't resized.
Examples:
hashtable.cxx.

template<classT>
hash_iterator hashtable<T>::insert ( const T & next ) [inline]
 

As long as the object responds to hash, we can directly add to hash table.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Reimplemented from type_allocator.

template<classT>
void hashtable<T>::erase ( const T & next,
size_t hashval ) [inline]
 

Remove specified object from the hash table.

Parameters:
next   object to remove from hash table.
hashval   externally computed hash value.

template<classT>
void hashtable<T>::erase ( const T & next ) [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<classT>
hash_iterator hashtable<T>::find ( const T & next,
size_t hv ) [inline]
 

Find the object matching specified object in the hash table.

Return the iterator to the found hash entry.

Parameters:
next   object to find.
hv   externally calculated hash value.
Returns:
iterator to entry. If 0, entry not found.
Examples:
hashtable.cxx.

template<classT>
hash_iterator hashtable<T>::find ( const T & next ) [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Reimplemented from type_allocator.

template<classT>
const_hash_iterator hashtable<T>::find ( const T & next,
size_t hv ) const [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<classT>
const_hash_iterator hashtable<T>::find ( const T & next ) const [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Reimplemented from type_allocator.

template<classT>
const_hash_iterator hashtable<T>::begin_serial ( ) const [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

template<classT>
const_hash_iterator hashtable<T>::next_serial ( ) const [inline]
 

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Member Data Documentation

template<classT>
size_t hashtable<T>::occupancy [protected]
 

How much of the table is currently occupied by entries.

Objects with the same hash value are not counted.

The documentation for this class was generated from the following file:
Generated at Wed Mar 2 11:17:47 2005 for Result Library by doxygen1.2.0 written by Dimitri van Heesch, © 1997-2000