Hash Containers

A hash is a data structure that saves objects in such a way as to make it efficient to locate and retrieve an element. A hash consists of:

a number of storage areas, called buckets
a hashing function that determines in which bucket an element should be placed, based on the value of the element.

This chapter describes the following hash classes:

WCPtrHashDict<Key,Value>
WCPtrHashSet<Type>, WCPtrHashTable<Type>
WCValHashDict<Key,Value>
WCValHashSet<Type>, WCValHashTable<Type>

WCPtrHashDict<Key,Value> Class

Declared:

wchash.h

The WCPtrHashDict<Key,Value> class is a templated class used to store objects in a dictionary. Dictionaries store values with an associated key, which may be of any type. One example of a dictionary used in everyday life is the phone book. The phone numbers are the data values, and the customer name is the key. An example of a specialized dictionary is a vector, where the key value is the integer index.

As an element is looked up or inserted in the dictionary, the associated key is hashed. Hashing converts the key into a numeric index value that's used to locate the value. The storage area referenced by the hash value is usually called a bucket. If more than one key results in the same hash, the values associated with the keys are placed in a list stored in the bucket. The equality operator of the key's type is used to locate the key-value pairs.

In the description of each member function, the text Key is used to indicate the template parameter defining the type of the indices pointed to by the pointers stored in the dictionary. The text Value is used to indicate the template parameter defining the type of the data pointed to by the pointers stored in the dictionary.

The constructor for the WCPtrHashDict<Key,Value> class requires a hashing function, which given a reference to Key, returns an unsigned value. The returned value modulo the number of buckets determines the bucket in which the key-value pair is located. The return values of the hash function can be spread over the entire range of unsigned numbers. The hash function return value must be the same for values that are equivalent according to the equivalence operator for Key.

Pointers to the key values are stored in the dictionary. Destructors aren't called on the keys pointed to. The key values pointed to in the dictionary shouldn't be changed such that the equivalence to the old value is modified.

The WCExcept class is a base class of the WCPtrHashDict<Key,Value> class, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCPtrHashDict<Key,Value> object. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCPtrHashDict<Key,Value> class requires Key to have:

a well defined equivalence operator with constant parameters
```
    int operator ==( const Key & ) const
    
```

Public Member Functions

The following member functions are declared in the public interface:

WCPtrHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE,
               void * (*user_alloc)( size_t size ),
               void (*user_dealloc)( void *old,
                                     size_t size ) );
WCPtrHashDict( const WCPtrHashDict & );
virtual ~WCPtrHashDict();
static unsigned bitHash( void *, size_t );
unsigned buckets() const;
void clear();
void clearAndDestroy();
int contains( const Key * ) const;
unsigned entries() const;
Value * find( const Key * ) const;
Value * findKeyAndValue( const Key *,
                         Key * & ) const;
void forAll(
   void (*user_fn)( Key *, Value *, void * ) ,
   void * );
int insert( Key *, Value * );
int isEmpty() const;
Value * remove( const Key * );
void resize( unsigned );

Public Member Operators

The following member operators are declared in the public interface:

Value * & operator [ ]( const Key & );
const Value * & operator [ ]( const Key & ) const;
WCPtrHashDict & operator =( 
    const WCPtrHashDict & );
int operator ==( const WCPtrHashDict & ) const;

WCPtrHashDict<Key,Value>::WCPtrHashDict()

create a WCPtrHashDict<Key,Value> object

Synopsis:

#include <wchash.h>
public:
WCPtrHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE,
               void * (*user_alloc)( size_t ),
               void (*user_dealloc)( void *, 
                                     size_t ) );
WCPtrHashDict( const WCPtrHashDict & );

Semantics:

The public WCPtrHashDict<Key,Value> constructor creates a WCPtrHashDict<Key,Value> object:

The first form creates a WCPtrHashDict<Key,Value> object with no entries and with the number of buckets in the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash dictionary object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each key-value pair is assigned. If no hash function exists, the static member function bitHash() is available to help create one.
The second form is similar to the first, but allocator and deallocator functions are specified for use when entries are inserted and removed from the hash dictionary.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash dictionary. To determine the size of the objects that the memory management functions are required to allocate and free, the following macro may be used:
WCPtrHashDictItemSize( Key, Value )
The third form is the copy constructor for the WCPtrHashDict<Key,Value> class. The new dictionary is created with the same number of buckets, hash function, all values or pointers stored in the dictionary, and the exception trap states.
If the hash dictionary object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If there isn't enough memory to copy all of the values in the dictionary, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown, if it's enabled.

Results:

The public WCPtrHashDict<Key,Value> constructor creates the specified WCPtrHashDict<Key,Value> object.

WCPtrHashDict<Key,Value>::~WCPtrHashDict()

destroy a WCPtrHashDict<Key,Value> object

Synopsis:

#include <wchash.h>
public:
virtual ~WCPtrHashDict();

Semantics:

The public WCPtrHashDict<Key,Value> destructor is the destructor for the WCPtrHashDict<Key,Value> class. If the number of dictionary elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the dictionary elements are cleared using the clear() member function.

The objects to which the dictionary elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrHashDict<Key,Value> object goes out of scope.

Results:

This destructor destroys an WCPtrHashDict<Key,Value> object.

WCPtrHashDict<Key,Value>::bitHash()

implement a hashing function

Synopsis:

#include <wchash.h>
public:
static unsigned bitHash( void *, size_t );

Semantics:

The bitHash() public member function can be used to implement a hashing function for any type. A hashing value is generated from the value stored for the number of specified bytes pointed to by the first parameter.

Results:

The bitHash() public member function returns an unsigned value that can be used as the basis of a user-defined hash function.

WCPtrHashDict<Key,Value>::buckets()

determine the number of buckets in the object

Synopsis:

#include <wchash.h>
public:
unsigned buckets const;

Semantics:

The buckets() public member function is used to find the number of buckets contained in the WCPtrHashDict<Key,Value> object.

Results:

This function returns the number of buckets in the dictionary.

WCPtrHashDict<Key,Value>::clear()

clear the dictionary

Synopsis:

#include <wchash.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the dictionary so that it has no entries. The number of buckets remains unaffected. Objects pointed to by the dictionary elements aren't deleted. The dictionary object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

This function clears the dictionary to have no elements.

WCPtrHashDict<Key,Value>::clearAndDestroy()

clear the dictionary, destroying its elements

Synopsis:

#include <wchash.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the dictionary and delete the objects pointed to by the dictionary elements. The dictionary object isn't destroyed and re-created by this function, so the dictionary object destructor isn't invoked.

Results:

This function clears the dictionary by deleting the objects pointed to by the dictionary elements.

WCPtrHashDict<Key,Value>::contains()

determine whether or not the dictionary contains a given element

Synopsis:

#include <wchash.h>
public:
int contains( const Key * ) const;

Semantics:

The contains() public member function returns non-zero if an element with the specified key is stored in the dictionary, or zero if there is no equivalent element. Note that equivalence is based on the equivalence operator of the Key type.

Results:

This function returns a non-zero value if the Key is found in the dictionary.

WCPtrHashDict<Key,Value>::entries()

count the entries in the dictionary

Synopsis:

#include <wchash.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the dictionary.

Results:

This function returns the number of elements in the dictionary.

WCPtrHashDict<Key,Value>::find()

find an element in the dictionary

Synopsis:

#include <wchash.h>
public:
Value * find( const Key * ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the dictionary. If an equivalent element is found, a pointer to the element Value is returned. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCPtrHashDict<Key,Value>::findKeyAndValue()

find an element in the dictionary

Synopsis:

#include <wchash.h>
public:
Value * findKeyAndValue( const Key *,
                         Key &, Value & ) const;

Semantics:

The findKeyAndValue() public member function is used to find an element in the dictionary with an key equivalent to the first parameter. If an equivalent element is found, a pointer to the element Value is returned. The reference to a Key passed as the second parameter is assigned the found element's key. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCPtrHashDict<Key,Value>::forAll()

invoke a function for each element in the dictionary

Synopsis:

#include <wchash.h>
public:
void forAll(
      void (*user_fn)( Key *, Value *, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every key-value pair in the dictionary. The user function has the prototype:

void user_func( Key * key, Value * value, void * data );

As the elements are visited, the user function is invoked with the Key and Value components of the element passed as the first two parameters. The second parameter of the forAll() function is passed as the third parameter to the user function. This value can be used to pass any appropriate data from the main code to the user function.

Results:

The elements in the dictionary are all visited, and the user function is invoked for each one.

WCPtrHashDict<Key,Value>::insert()

insert an element into the dictionary

Synopsis:

#include <wchash.h>
public:
int insert( Key *, Value * );

Semantics:

The insert() public member function inserts a key and value into the dictionary, using the hash function on the key to determine in which bucket it should be stored. If allocation of the node to store the key-value pair fails, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

At some point, the number of buckets initially selected may be too small for the number of elements inserted. The resizing of the dictionary can be controlled by the insertion mechanism by using WCPtrHashDict as a base class, and providing an insert member function to do a resize when appropriate. This insert could then call WCPtrHashDict::insert to insert the element.

Copy constructors and assignment operators aren't inherited in your class, but you can provide the following inline definitions (assuming that the class inherited from WCPtrHashDict is named MyHashDict):

inline MyHashDict(
   const MyHashDict &orig ) : WCPtrHashDict( orig ) {};
inline MyHashDict &operator=( const MyHashDict &orig ) {
    return( WCPtrHashDict::operator=( orig ) );
}

Results:

The insert() public member function inserts a key and value into the dictionary. If the insertion is successful, a non-zero value is returned. Zero is returned if the insertion fails.

WCPtrHashDict<Key,Value>::isEmpty()

detemine whether or not the dictionary is empty

Synopsis:

#include <wchash.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the dictionary is empty.

Results:

This function returns zero if the dictionary contains at least one entry, non-zero if it's empty.

WCPtrHashDict<Key,Value>::operator [ ]()

index into the dictionary

Synopsis:

#include <wchash.h>
public:
Value * & operator[ ]( const Key & );
Value * const & operator[ ]( const Key * ) const;

Semantics:

The operator [ ]() public member function is the dictionary index operator. It's available in two forms.

The first form returns a reference to the object stored in the dictionary with the given Key. If no equivalent element is found, then a new key-value pair is created with the specified Key value, and initialized with the default constructor. The returned reference can then be assigned to, so that insertions can be made with the operator.
If an allocation error occurs while inserting a new key-value pair, then the out_of_memory exception is thrown, if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.
The second form of this function returns a constant reference to the object stored in the dictionary with the given Key is returned. If no equivalent element is found, then the index_range exception is thrown, if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.

Results:

The first form of the operator [ ]() public member function returns a reference to the element at the given key value. If the key doesn't exist, a reference to a created element is returned. The result of the operator may be assigned to.
The second form returns a constant reference to the element at the given key value. The result of the operator may not be assigned to.

WCPtrHashDict<Key,Value>::operator =()

assign one dictionary to another

Synopsis:

#include <wchash.h>
public:
WCPtrHashDict & operator =( 
    const WCPtrHashDict & );

Semantics:

The operator =() public member function is the assignment operator for the WCPtrHashDict<Key,Value> class. The left hand side dictionary is first cleared, using the clear() member function, and then the right hand side dictionary is copied. The hash function, exception trap states, and all of the dictionary elements are copied.

If an allocation failure occurs when creating the buckets, the table is created with zero buckets, and the out_of_memory exception is thrown, if it's enabled. If there isn't enough memory to copy all of the values or pointers in the dictionary, then only some are copied, and the out_of_memory exception is thrown, if it's enabled. The number of entries correctly reflects the number copied.

Results:

The operator =() public member function assigns the left hand side dictionary to be a copy of the right hand side.

WCPtrHashDict<Key,Value>::operator ==()

determine whether or not two dictionaries are equivalent

Synopsis:

#include <wchash.h>
public:
int operator ==( const WCPtrHashDict & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCPtrHashDict<Key,Value> class. Two dictionary objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side and right hand side dictionaries are the same object. A FALSE (zero) value is returned otherwise.

WCPtrHashDict<Key,Value>::remove()

remove an element from the dictionary

Synopsis:

#include <wchash.h>
public:
Value * remove( const Key * );

Semantics:

The remove() public member function is used to remove the specified element from the dictionary. If an equivalent element is found, the pointer value is returned. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element is removed from the dictionary if it's found.

WCPtrHashDict<Key,Value>::resize()

change the number of buckets in the dictionary

Synopsis:

#include <wchash.h>
public:
void resize( unsigned );

Semantics:

The resize() public member function is used to change the number of buckets contained in the dictionary.

If the new number is larger than the previous dictionary size, then the hash function is used on all of the stored elements to determine in which bucket they should be stored. Entries aren't destroyed or created in the process of being moved. If there isn't enough memory to resize the dictionary, the out_of_memory exception is thrown, if it's enabled, and the dictionary contains the number of buckets it contained before the resize.

If the new number is zero, then the zero_buckets exception is thrown, if it's enabled, and no resize is performed. The dictionary is guaranteed to contain the same number of entries after the resize.

Results:

The dictionary is resized to contain the new number of buckets.

`WCPtrHashSet<Type>`, `WCPtrHashTable<Type>` Classes

Declared:

wchash.h

The WCPtrHashSet<Type> and WCPtrHashTable<Type> classes are templated classes used to store objects in a hash. A hash saves objects in such a way as to make it efficient to locate and retrieve an element. As an element is looked up or inserted into the hash, the value of the element is hashed. Hashing results in a numeric index that is used to locate the value. The storage area referenced by the hash value is usually called a bucket. If more than one element results in the same hash, the value associated with the hash is placed in a list stored in the bucket. A hash table allows more than one copy of an element that is equivalent, while the hash set allows only one copy. The equality operator of the element's type is used to locate the value.

In the description of each member function, the text Type is used to indicate the template parameter defining the type of the data pointed to by the pointers stored in the hash.

The constructors for the WCPtrHashTable<Type> and WCPtrHashSet<Type> classes require a hashing function that, given a reference to Type, returns an unsigned value. The returned value modulo the number of buckets determines the bucket in which the element is located. The return values of the hash function can be spread over the entire range of unsigned numbers. The hash function return value must be the same for values that are equivalent according to the equivalence operator for Type.

Pointers to the elements are stored in the hash. Destructors aren't called on the elements pointed to. The data values pointed to in the hash shouldn't be changed such that the equivalence to the old value is modified.

The WCExcept class is a base class of the WCPtrHashTable<Type> and WCPtrHashSet<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by these objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCPtrHashTable<Type> and WCPtrHashSet<Type> classes require Type to have:

a well defined equivalence operator with constant parameters
```
    int operator ==( const Type & ) const
    
```

Public Member Functions

The following member functions are declared in the public interface:

WCPtrHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE,
              void * (*user_alloc)( size_t size ),
              void (*user_dealloc)( void *old,
                                    size_t size ) );
WCPtrHashSet( const WCPtrHashSet & );
virtual ~WCPtrHashSet();

WCPtrHashTable( unsigned (*hash_fn)( const Type & ),
                unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashTable( unsigned (*hash_fn)( const Type & ),
                unsigned = WC_DEFAULT_HASH_SIZE,
                void * (*user_alloc)( size_t size ),
                void (*user_dealloc)( void *old,
                                      size_t size ) );
WCPtrHashTable( const WCPtrHashTable & );
virtual ~WCPtrHashTable();

static unsigned bitHash( void *, size_t );
unsigned buckets() const;
void clear();
void clearAndDestroy();
int contains( const Type * ) const;
unsigned entries() const;
Type * find( const Type * ) const;
void forAll( void (*user_fn)( Type *, void * ),
                        void * );
int insert( Type * );
int isEmpty() const;
Type * remove( const Type * );
void resize( unsigned );

The following public member functions are available for the WCPtrHashTable<Type> class only:

unsigned occurrencesOf( const Type * ) const;
unsigned removeAll( const Type * );

Public Member Operators

The following member operators are declared in the public interface:

WCPtrHashSet & operator =( const WCPtrHashSet & );
int operator ==( const WCPtrHashSet & ) const;
WCPtrHashTable & operator =( const WCPtrHashTable & );
int operator ==( const WCPtrHashTable & ) const;

WCPtrHashSet<Key,Value>::WCPtrHashSet()

create a WCPtrHashSet object

Synopsis:

#include <wchash.h>
public:
WCPtrHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE,
              void * (*user_alloc)( size_t ),
              void (*user_dealloc)( void *, 
                                    size_t ) );
WCPtrHashSet( const WCPtrHashSet & );

Semantics:

The WCPtrHashSet<Type> constructor creates a WCPtrHashSet object:

The first form creates a WCPtrHashSet object with no entries, and with the number of buckets in the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each value is assigned. If no hash function exists, the static member function bitHash() is available to help create one.
The second form of the constructor is similar to the first, but specifies the allocation and deallocation functions for use when entries are inserted and removed from the hash.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash. To determine the size of the objects that the memory management functions are required to allocate and free, use the WCPtrHashSetItemSize( Type ) macro.
The third form is the copy constructor for the WCPtrHashSet class. The new hash is created with the same number of buckets, hash function, all values or pointers stored in the hash, and the exception trap states.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the hash is created with zero buckets. If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown, if it's enabled.

Results:

This constructor creates a WCPtrHashSet object.

WCPtrHashSet<Type>::~WCPtrHashSet()

destroy a WCPtrHashSet object

Synopsis:

#include <wchash.h>
public:
virtual ~WCPtrHashSet();

Semantics:

This function is the destructor for the WCPtrHashSet class. If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the hash elements are cleared using the clear() member function. The objects to which the hash elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to the WCPtrHashSet<Type> destructor is inserted implicitly by the compiler at the point where the WCPtrHashSet object goes out of scope.

Results:

The WCPtrHashSet object is destroyed.

WCPtrHashTable<Type>::WCPtrHashTable()

create a WCPtrHashTable object

Synopsis:

#include <wchash.h>
public:
WCPtrHashTable( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE );
WCPtrHashTable( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCPtrHashTable( const WCPtrHashTable & );

Semantics:

The WCPtrHashTable<Type> constructor creates a WCPtrHashTable object:

The first form creates a WCPtrHashTable object with no entries and with the number of buckets specified by the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each value is assigned. If no hash function exists, the static member function bitHash() is available to help create one.
The second form of the constructor is similar to the first, but specifies the allocator and deallocator functions that are used when entries are inserted and removed from the hash.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash. To determine the size of the objects that the memory management functions are required to allocate and free, you can use the WCPtrHashTableItemSize( Type ) macro.
The third form is the copy constructor for the WCPtrHashTable class. The new hash is created with the same number of buckets, hash function, all values or pointers stored in the hash, and the exception trap states.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the hash is created with zero buckets. If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown, if it's enabled.

Results:

The WCPtrHashTable<Type> constructor creates a WCPtrHashTable object.

WCPtrHashTable<Type>::~WCPtrHashTable()

destroy a WCPtrHashTable object

Synopsis:

#include <wchash.h>
public:
virtual ~WCPtrHashTable();

Semantics:

This function is the destructor for the WCPtrHashTable class. If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the hash elements are cleared using the clear() member function. The objects to which the hash elements point aren't deleted unless the clearAndDestroy() member function is explicitly called before the destructor is called.

The call to this destructor is inserted implicitly by the compiler at the point where the WCPtrHashTable object goes out of scope.

Results:

This destructor destroys a WCPtrHashTable object.

WCPtrHashTable<Type>::bitHash(), WCPtrHashSet<Type>::bitHash()

implement a hashing function

Synopsis:

#include <wchash.h>
public:
static unsigned bitHash( void *, size_t );

Semantics:

Results:

The bitHash() public member function returns an unsigned value that can be used as the basis of a user-defined hash function.

WCPtrHashTable<Type>::buckets(), WCPtrHashSet<Type>::buckets()

count the buckets in the hash table

Synopsis:

#include <wchash.h>
public:
unsigned buckets const;

Semantics:

The buckets() public member function is used to find the number of buckets contained in the hash object.

Results:

This function returns the number of buckets in the hash.

WCPtrHashTable<Type>::clear(), WCPtrHashSet<Type>::clear()

clear the hash object

Synopsis:

#include <wchash.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the hash so that it has no entries. The number of buckets remains unaffected. Objects pointed to by the hash elements aren't deleted. The hash object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

This function clears the hash to have no elements.

WCPtrHashTable<Type>::clearAndDestroy(), WCPtrHashSet<Type>::clearAndDestroy()

clear the hash, by deleting the objects in it

Synopsis:

#include <wchash.h>
public:
void clearAndDestroy();

Semantics:

The clearAndDestroy() public member function is used to clear the hash and delete the objects pointed to by the hash elements. The hash object isn't destroyed and re-created by this function, so the hash object destructor isn't invoked.

Results:

The clearAndDestroy() public member function clears the hash by deleting the objects pointed to by the hash elements.

WCPtrHashTable<Type>::contains(), WCPtrHashSet<Type>::contains()

determine whether or not the hash contains a given element

Synopsis:

#include <wchash.h>
public:
int contains( const Type * ) const;

Semantics:

The contains() public member function returns non-zero if the element is stored in the hash, or zero if there's no equivalent element. Note that equivalence is based on the equivalence operator of the element type.

Results:

The contains() public member function returns a non-zero value if the element is found in the hash.

WCPtrHashTable<Type>::entries(), WCPtrHashSet<Type>::entries()

count the elements in the hash

Synopsis:

#include <wchash.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the hash.

Results:

The entries() public member function returns the number of elements in the hash.

WCPtrHashTable<Type>::find(), WCPtrHashSet<Type>::find()

find an element in the hash

Synopsis:

#include <wchash.h>
public:
Type * find( const Type * ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the hash. If an equivalent element is found, a pointer to the element is returned. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the element type.

Results:

The element equivalent to the passed key is located in the hash.

WCPtrHashTable<Type>::forAll(), WCPtrHashSet<Type>::forAll()

invoke a function for each element in the hash table

Synopsis:

#include <wchash.h>
public:
void forAll(
        void (*user_fn)( Type *, void * ),
        void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every value in the hash. The user function has the prototype

void user_func( Type * value, void * data );

As the elements are visited, the user function is invoked with the element passed as the first parameter. The second parameter of the forAll function is passed as the second parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the hash are all visited, and the the user function is invoked for each one.

WCPtrHashTable<Type>::insert(), WCPtrHashSet<Type>::insert()

insert a value into the hash

Synopsis:

#include <wchash.h>
public:
int insert( Type * );

Semantics:

The insert() public member function inserts a value into the hash, using the hash function to determine in which bucket it should be stored.

If allocation of the node to store the value fails, then the out_of_memory exception is thrown, if it's enabled. If the exception isn't enabled, the insertion isn't completed.

With a WCPtrHashSet, there must be only one equivalent element in the set. If an element equivalent to the inserted element is already in the hash set, the hash set remains unchanged, and the not_unique exception is thrown, if it's enabled. If the exception isn't enabled, the insertion isn't completed.

At some point, the number of buckets initially selected may be too small for the number of elements inserted. The resize of the hash can be controlled by the insertion mechanism by using WCPtrHashSet (or WCPtrHashTable) as a base class, and providing an insert-member function to do a resize when appropriate. This function could then call WCPtrHashSet::insert() (or WCPtrHashTable::insert()) to insert the element.

inline MyHashTable( const MyHashTable &orig )
     : WCPtrHashTable( orig ) {};
inline MyHashTable &operator=( const MyHashTable &orig )
{
    return( WCPtrHashTable::operator=( orig ) );
}

Results:

The insert() public member function inserts a value into the hash. If the insertion is successful, a non-zero is returned. A zero is returned if the insertion fails.

WCPtrHashTable<Type>::isEmpty(), WCPtrHashSet<Type>::isEmpty()

determine if the hash is empty

Synopsis:

#include <wchash.h>
public:
int isEmpty() const;

If an allocation failure occurs when creating the buckets, the table is created with zero buckets, and the out_of_memory exception is thrown, if it's enabled. If there isn't enough memory to copy all of the values or pointers in the hash, then only some are copied, and the out_of_memory exception is thrown, if it's enabled. The number of entries correctly reflects the number copied.

Results:

The operator =() public member function assigns a copy of the right hand side hash to the left hand side.

WCPtrHashTable<Type>::operator ==(), WCPtrHashSet<Type>::operator ==()

determine whether or not two elements are equivalent

Synopsis:

#include <wchash.h>
public:
int operator ==( const WCPtrHashSet & ) const;
int operator ==( const WCPtrHashTable & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCPtrHashTable<Type> and WCPtrHashSet<Type> classes. Two hash objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left-hand-side and right-hand-side hashes are the same object. A FALSE (zero) value is returned otherwise.

WCPtrHashTable<Type>::remove(), WCPtrHashSet<Type>::remove()

remove an element from the hash

Synopsis:

#include <wchash.h>
public:
Type * remove( const Type * );

Semantics:

The remove() public member function is used to remove the specified element from the hash. If an equivalent element is found, the pointer value is returned. Zero is returned if the element isn't found.

If the hash is a table and there's more than one element equivalent to the specified element, then the first equivalent element added to the table is removed.

Note that equivalence is based on the equivalence operator of the element type.

Results:

The element is removed from the hash if it's found.

WCPtrHashTable<Type>::removeAll()

remove all occurrences of a given element from the hash

Synopsis:

#include <wchash.h>
public:
unsigned removeAll( const Type * );

Semantics:

The removeAll() public member function is used to remove all elements equivalent to the specified element from the hash. Zero is returned if no equivalent elements are found. Note that equivalence is based on the equivalence operator of the element type.

Results:

All equivalent elements are removed from the hash.

WCPtrHashTable<Type>::resize(), WCPtrHashSet<Type>::resize()

change the number of buckets in the hash

Synopsis:

#include <wchash.h>
public:
void resize( unsigned );

Semantics:

The resize() public member function is used to change the number of buckets contained in the hash.

If the new number is larger than the previous hash size, then the hash function is used on all of the stored elements to determine in which bucket they should be stored. Entries aren't destroyed or created in the process of being moved. If there isn't enough memory to resize the hash, the out_of_memory exception is thrown, if it's enabled, and the hash contains the number of buckets it contained before the resize.

If the new number is zero, then the zero_buckets exception is thrown, if it's enabled, and no resize is performed. The hash is guaranteed to contain the same number of entries after the resize.

Results:

The hash is resized to the new number of buckets.

WCValHashDict<Key,Value> Class

Declared:

wchash.h

The WCValHashDict<Key,Value> class is a templated class used to store objects in a dictionary. Dictionaries store values with an associated key, which may be of any type. One example of a dictionary used in everyday life is the phone book. The phone numbers are the data values, and the customer name is the key. An example of a specialized dictionary is a vector, where the key value is the integer index.

As an element is looked up or inserted into the dictionary, the associated key is hashed. Hashing converts the key into a numeric index value that is used to locate the value. The storage area referenced by the hash value is usually called a bucket. If more than one key results in the same hash, the values associated with the keys are placed in a list stored in the bucket. The equality operator of the key's type is used to locate the key-value pairs.

In the description of each member function, the text Key is used to indicate the template parameter defining the type of the indices used to store data in the dictionary. The text Value is used to indicate the template parameter defining the type of the data stored in the dictionary.

The constructor for the WCValHashDict<Key,Value> class requires a hashing function, which given a reference to Key, returns an unsigned value. The returned value modulo the number of buckets determines the bucket in which the key-value pair is located. The return values of the hash function can be spread over the entire range of unsigned numbers. The hash function return value must be the same for values that are equivalent according to the equivalence operator for Key.

Values are copied into the dictionary, which could be undesirable if the stored objects are complicated and copying is expensive. Value dictionaries shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the dictionary, or if the destructor for a derived class must be called.

The WCExcept class is a base class of the WCValHashDict class, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCValHashDict<Key,Value> object. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCValHashDict<Key,Value> class requires Key to have:

a default constructor
```
    Key::Key()
    
```
a well defined copy constructor
```
    Key::Key( const Key & )
    
```

a well defined assignment operator

    Key & operator =( const Key & )

a well defined equivalence operator with constant parameters
```
    int operator ==( const Key & ) const
    
```

The WCValHashDict<Key,Value> class requires Value to have:

a default constructor
```
    Value::Value()
    
```
A well defined copy constructor
```
    Value::Value( const Value & )
    
```

a well defined assignment operator

    Value & operator =( const Value & )

Public Member Functions

The following member functions are declared in the public interface:

WCValHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE,
               void * (*user_alloc)( size_t size ),
               void (*user_dealloc)( void *old, size_t size ) );
WCValHashDict( const WCValHashDict & );
virtual ~WCValHashDict();
static unsigned bitHash( void *, size_t );
unsigned buckets() const;
void clear();
int contains( const Key & ) const;
unsigned entries() const;
int find( const Key &, Value & ) const;
int findKeyAndValue( const Key &,
                     Key &, Value & ) const;
void forAll( void (*user_fn)( Key, Value, void * ),
             void * );
int insert( const Key &, const Value & );
int isEmpty() const;
int remove( const Key & );
void resize( unsigned );

Public Member Operators

The following member operators are declared in the public interface:

        Value & operator [ ]( const Key & );
const   Value & operator [ ]( const Key & ) const;
WCValHashDict & operator =( const WCValHashDict & );
int              operator ==( const WCValHashDict & ) const;

WCValHashDict<Key,Value>::WCValHashDict()

create a WCValHashDict object

Synopsis:

#include <wchash.h>
public:
WCValHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashDict( unsigned (*hash_fn)( const Key & ),
               unsigned = WC_DEFAULT_HASH_SIZE,
               void * (*user_alloc)( size_t ),
               void (*user_dealloc)( void *, 
                                     size_t ) );
WCValHashDict( const WCValHashDict & );

Semantics:

The public WCValHashDict<Key,Value> constructor creates a WCValHashDict<Key,Value> object:

The first form creates a WCValHashDict<Key,Value> object with no entries and with the number of buckets specified by the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash dictionary object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each key-value pair is assigned. If no hash function exists, the static member function bitHash() is available to help create one.
The second form of the constructor is similar to the first, but allocator and deallocator functions are specified for use when entries are inserted and removed from the hash dictionary.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash dictionary. To determine the size of the objects that the memory management functions are required to allocate and free, you can use the WCValHashDictItemSize( Key, Value ) macro.
The third form is the copy constructor for the WCValHashDict<Key,Value> class. The new dictionary is created with the same number of buckets, hash function, all values or pointers stored in the dictionary, and the exception trap states.
If the hash dictionary object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If there isn't enough memory to copy all of the values in the dictionary, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown, if it's enabled.

Results:

The public WCValHashDict<Key,Value> constructor creates a WCValHashDict<Key,Value> object.

WCValHashDict<Key,Value>::~WCValHashDict()

destroy a WCValHashDict object

Synopsis:

#include <wchash.h>
public:
virtual ~WCValHashDict();

Semantics:

This function is the destructor for the WCValHashDict<Key,Value> class. If the number of dictionary elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the dictionary elements are cleared using the clear() member function. The call to this destructor is inserted implicitly by the compiler at the point where the WCValHashDict<Key,Value> object goes out of scope.

Results:

The public WCValHashDict<Key,Value> destructor destroys an WCValHashDict<Key,Value> object.

WCValHashDict<Key,Value>::bitHash()

implement a hashing function for any type

Synopsis:

#include <wchash.h>
public:
static unsigned bitHash( void *, size_t );

Semantics:

unsigned my_hash_fn( const int & key ) {
    return( WCValHashDict<int,String>::bitHash( &key, 
              sizeof( int ) );
}
WCValHashDict<int,String> data_object( &my_hash_fn );

Results:

The bitHash() public member function returns an unsigned value that can be used as the basis of a user-defined hash function.

WCValHashDict<Key,Value>::buckets()

count the buckets in a WCValHashDict object

Synopsis:

#include <wchash.h>
public:
unsigned buckets const;

Semantics:

The buckets() public member function is used to find the number of buckets contained in the WCValHashDict<Key,Value> object.

Results:

This function returns the number of buckets in the dictionary.

WCValHashDict<Key,Value>::clear()

clear the dictionary of all entries

Synopsis:

#include <wchash.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the dictionary so that it has no entries. The number of buckets remains unaffected. Elements stored in the dictionary are destroyed using the destructors of Key and of Value. The dictionary object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

The clear() public member function clears the dictionary to have no elements.

WCValHashDict<Key,Value>::contains()

determine whther or not a given key is stored in the dictionary

Synopsis:

#include <wchash.h>
public:
int contains( const Key & ) const;

Semantics:

Results:

This function returns a non-zero value if the Key is found in the dictionary.

WCValHashDict<Key,Value>::entries()

count the entries in the dictionary

Synopsis:

#include <wchash.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the dictionary.

Results:

This function returns the number of elements in the dictionary.

WCValHashDict<Key,Value>::find()

find an element in the dictionary

Synopsis:

#include <wchash.h>
public:
int find( const Key &, Value & ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the dictionary. If an equivalent element is found, a non-zero value is returned. The reference to a Value passed as the second argument is assigned the found element's Value. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCValHashDict<Key,Value>::findKeyAndValue()

find an element in the dictionary

Synopsis:

#include <wchash.h>
public:
int findKeyAndValue( const Key &,
                     Key &, Value & ) const;

Semantics:

The findKeyAndValue() public member function is used to find an element in the dictionary with an key equivalent to the first parameter. If an equivalent element is found, a non-zero value is returned. The reference to a Key passed as the second parameter is assigned the found element's key. The reference to a Value passed as the third argument is assigned the found element's Value. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the Key type.

Results:

The element equivalent to the passed key is located in the dictionary.

WCValHashDict<Key,Value>::forAll()

invoke a user-supplied function for each entry in the dictionary

Synopsis:

#include <wchash.h>
public:
void forAll(
      void (*user_fn)( Key, Value, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every key-value pair in the dictionary. The user function has the prototype

void user_func( Key key, Value value, void * data );

As the elements are visited, the user function is invoked with the Key and Value components of the element passed as the first two parameters. The second parameter of the forAll function is passed as the third parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the dictionary are all visited, and the user function is invoked for each one.

WCValHashDict<Key,Value>::insert()

insert a key and a value into the dictionary

Synopsis:

#include <wchash.h>
public:
int insert( const Key &, const Value & );

Semantics:

The insert() public member function inserts a key and value into the dictionary, using the hash function on the key to determine in which bucket it should be stored.

If allocation of the node to store the key-value pair fails, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, the insertion isn't completed.

At some point, the number of buckets initially selected may be too small for the number of elements inserted. The resize of the dictionary can be controlled by the insertion mechanism by using WCValHashDict as a base class, and providing an insert-member function to do a resize when appropriate. This function could then call WCValHashDict::insert to insert the element.

Copy constructors and assignment operators aren't inherited in your class, but you can provide the following inline definitions (assuming that the class inherited from WCValHashDict is named MyHashDict):

inline MyHashDict( const MyHashDict &orig ) : 
                   WCValHashDict( orig ) {};
inline MyHashDict &operator=( const MyHashDict &orig ) 
{
    return( WCValHashDict::operator=( orig ) );
}

Results:

The insert() public member function inserts a key and value into the dictionary. If the insertion is successful, a non-zero value is returned. A zero is returned if the insertion fails.

WCValHashDict<Key,Value>::isEmpty()

determine whether or not the dictionary is empty

Synopsis:

#include <wchash.h>
public:
int isEmpty() const;

Semantics:

The isEmpty() public member function is used to determine if the dictionary is empty.

Results:

This function returns zero if the dictionary contains at least one entry, non-zero if it's empty.

WCValHashDict<Key,Value>::operator [ ]()

index into the dictionary

Synopsis:

#include <wchash.h>
public:
Value & operator[ ]( const Key & );
const Value & operator[ ]( const Key & ) const;

Semantics:

operator [ ]() is the dictionary index operator. It's available in two forms:

The first form returns a reference to the object stored in the dictionary with the given Key. If no equivalent element is found, then a new key-value pair is created with the specified Key value, and is initialized with the default constructor. The returned reference can then be assigned to, so insertions can be made with this operator.
For example,
```
    WCValHashDict<int,String> data_object( &my_hash_fn );
    data_object[ 5 ] = "Hello";
    
```
If an allocation error occurs while inserting a new key-value pair, then the out_of_memory exception is thrown if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.
The second form of the operator [ ]() returns a constant reference to the object stored in the dictionary with the given Key. If no equivalent element is found, then the index_range exception is thrown, if it's enabled. If the exception isn't enabled, then a reference to address zero is returned. This results in a run-time error on systems that trap references to address zero.

Results:

The first form of the operator [ ]() public member function returns a reference to the element at the given key value. If the key doesn't exist, a reference to a created element is returned. You can assign values to the result of the operator.
The second form returns a constant reference to the element at the given key value. You can't assign values to the result of this operator.

WCValHashDict<Key,Value>::operator =()

assign the value of one dictionary to another

Synopsis:

#include <wchash.h>
public:
WCValHashDict & operator =( 
    const WCValHashDict & );

`WCValHashSet<Type>` and `WCValHashTable<Type>` Classes

Declared:

wchash.h

WCValHashTable<Type> and WCValHashSet<Type> classes are templated classes used to store objects in a hash. A hash saves objects in such a way as to make it efficient to locate and retrieve an element. As an element is looked up or inserted into the hash, the value of the element is hashed. Hashing results in a numeric index which is used to locate the value. The storage area referenced by the hash value is usually called a bucket. If more than one element results in the same hash, the value associated with the hash is placed in a list stored in the bucket. A hash table allows more than one copy of an element that is equivalent, while the hash set allows only one copy. The equality operator of the element's type is used to locate the value.

In the description of each member function, the text Type is used to indicate the template parameter defining the type of the data to be stored in the hash.

The constructors for the WCValHashTable<Type> and WCValHashSet<Type> classes require a hashing function that, given a reference to Type, returns an unsigned value. The returned value modulo the number of buckets determines the bucket in which the element is located. The return values of the hash function can be spread over the entire range of unsigned numbers. The hash function return value must be the same for values that are equivalent according to the equivalence operator for Type.

Values are copied into the hash, which could be undesirable if the stored objects are complicated and copying is expensive. Value hashes shouldn't be used to store objects of a base class if any derived types of different sizes would be stored in the hash, or if the destructor for a derived class must be called.

The WCExcept class is a base class of the WCValHashTable<Type> and WCValHashSet<Type> classes, and provides the exceptions() member function. This member function controls the exceptions that can be thrown by the WCValHashTable<Type> and WCValHashSet<Type> objects. No exceptions are enabled unless they're set by the exceptions() member function.

Requirements of Type

The WCValHashTable<Type> and WCValHashSet<Type> classes require Type to have:

a default constructor
```
    Type::Type()
    
```
a well defined copy constructor
```
    Type::Type( const Type & )
    
```

a well defined assignment operator

    Type & operator =( const Type & )

a well defined equivalence operator with constant parameters
```
    int operator ==( const Type & ) const
    
```

Public Member Functions

The following member functions are declared in the public interface:

WCValHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashSet( unsigned (*hash_fn)( const Type & ),
              unsigned = WC_DEFAULT_HASH_SIZE,
              void * (*user_alloc)( size_t size ),
              void (*user_dealloc)( void *old, 
                                    size_t size ) );
WCValHashSet( const WCValHashSet & );
virtual ~WCValHashSet();

WCValHashTable( unsigned (*hash_fn)( const Type & ),
                unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashTable( unsigned (*hash_fn)( const Type & ),
                unsigned = WC_DEFAULT_HASH_SIZE,
                void * (*user_alloc)( size_t size ),
                void (*user_dealloc)( void *old, 
                                      size_t size ) );
WCValHashTable( const WCValHashTable & );
virtual ~WCValHashTable();

static unsigned bitHash( void *, size_t );
unsigned buckets() const;
void clear();
int contains( const Type & ) const;
unsigned entries() const;
int find( const Type &, Type & ) const;
void forAll( void (*user_fn)( Type, void * ),
                        void * );
int insert( const Type & );
int isEmpty() const;
int remove( const Type & );
void resize( unsigned );

The following public member functions are available for the WCValHashTable class only:

unsigned occurrencesOf( const Type & ) const;
unsigned removeAll( const Type & );

Public Member Operators

The following member operators are declared in the public interface:

WCValHashSet & operator =( const WCValHashSet & );
int operator ==( const WCValHashSet & ) const;
WCValHashTable & operator =( const WCValHashTable & );
int operator ==( const WCValHashTable & ) const;

WCValHashSet<Type>::WCValHashSet()

create a WCValHashSet object

Synopsis:

#include <wchash.h>
public:
WCValHashSet( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashSet( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCValHashSet( const WCValHashSet & );

Semantics:

The WCValHashSet<Type> constructor creates a WCValHashSet object:

The first form creates a WCValHashSet object with no entries and with the number of buckets specified by the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each value is assigned. If no hash function exists, the static member function bitHash is available to help create one.
The second form of the constructor is similar to the first, but allocator and deallocator functions are specified for use when entries are inserted and removed from the hash.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash. To determine the size of the objects that the memory management functions are required to allocate and free, you can use the WCValHashSetItemSize( Type ) macro.
The third form of this function is the copy constructor for the WCValHashSet class. The new hash is created with the same number of buckets, hash function, all values or pointers stored in the hash, and the exception trap states.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the hash is created with zero buckets. If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown, if it's enabled.

Results:

The WCValHashSet<Type> constructor creates a WCValHashSet object.

WCValHashSet<Type>::~WCValHashSet()

destroy a WCValHashSet object

Synopsis:

#include <wchash.h>
public:
virtual ~WCValHashSet();

Semantics:

This function is the destructor for the WCValHashSet class. If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the hash elements are cleared using the clear() member function. The call to the WCValHashSet<Type> destructor is inserted implicitly by the compiler at the point where the WCValHashSet object goes out of scope.

Results:

The WCValHashSet object is destroyed.

WCValHashTable<Type>::WCValHashTable()

create a WCValHashTable object

Synopsis:

#include <wchash.h>
public:
WCValHashTable( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE );
WCValHashTable( 
    unsigned (*hash_fn)( const Type & ),
    unsigned = WC_DEFAULT_HASH_SIZE,
    void * (*user_alloc)( size_t ),
    void (*user_dealloc)( void *, size_t ) );
WCValHashTable( const WCValHashTable & );

Semantics:

The WCValHashTable<Type> constructor creates a WCValHashTable object:

The first form creates a WCValHashTable object with no entries and with the number of buckets specified by the second optional parameter, which defaults to the constant WC_DEFAULT_HASH_SIZE (currently defined as 101). The number of buckets specified must be greater than zero, and is forced to be at least one.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the table is created with zero buckets. If the out_of_memory exception is enabled, then attempting to insert into a hash table with zero buckets throws an out_of_memory error.
The hash function hash_fn is used to determine to which bucket each value is assigned. If no hash function exists, the static member function bitHash is available to help create one.
The second form of this constructor is similar to the first, but allocator and deallocator functions are specified for use when entries are inserted and removed from the hash.
The allocation function must return a zero if it can't perform the allocation. The deallocation function is passed the size as well as the pointer to the data. Your allocation system may take advantage of the characteristic that the allocation function is always called with the same size value for any particular instantiation of a hash. To determine the size of the objects that the memory management functions are required to allocate and free, you can use the WCValHashTableItemSize( Type ) macro.
The third form of this function is the copy constructor for the WCValHashTable class. The new hash is created with the same number of buckets, hash function, all values or pointers stored in the hash, and the exception trap states.
If the hash object can be created, but an allocation failure occurs when creating the buckets, the hash is created with zero buckets. If there isn't enough memory to copy all of the values, then only some are copied, and the number of entries correctly reflects the number copied. If all of the elements can't be copied, then the out_of_memory exception is thrown if it's enabled.

Results:

The WCValHashTable<Type> constructor creates a WCValHashTable object.

WCValHashTable<Type>::~WCValHashTable()

destroy a WCValHashTable object

Synopsis:

#include <wchash.h>
public:
virtual ~WCValHashTable();

Semantics:

This function is the destructor for the WCValHashTable class. If the number of elements isn't zero and the not_empty exception is enabled, the exception is thrown. Otherwise, the hash elements are cleared using the clear() member function.

The call to this destructor is inserted implicitly by the compiler at the point where the WCValHashTable object goes out of scope.

Results:

The WCValHashTable object is destroyed.

WCValHashTable<Type>::bitHash(), WCValHashSet<Type>::bitHash()

implement a hashing function

Synopsis:

#include <wchash.h>
public:
static unsigned bitHash( void *, size_t );

Semantics:

unsigned my_hash_fn( const int & elem ) {
    return( WCValHashSet<int,String>::bitHash(&elem,
                                              sizeof(int));
}
WCValHashSet<int> data_object( &my_hash_fn );

Results:

The bitHash() public member function returns an unsigned value that can be used as the basis of a user-defined hash function.

WCValHashTable<Type>::buckets(), WCValHashSet<Type>::buckets()

count the buckets in the hash object

Synopsis:

#include <wchash.h>
public:
unsigned buckets const;

Semantics:

The buckets() public member function is used to find the number of buckets contained in the hash object.

Results:

This function returns the number of buckets in the hash.

WCValHashTable<Type>::clear(), WCValHashSet<Type>::clear()

clear the hash object so that it has no entries

Synopsis:

#include <wchash.h>
public:
void clear();

Semantics:

The clear() public member function is used to clear the hash so that it has no entries. The number of buckets remains unaffected. Elements stored in the hash are destroyed using the destructors of Type. The hash object isn't destroyed and re-created by this function, so the object destructor isn't invoked.

Results:

The clear() public member function clears the hash to have no elements.

WCValHashTable<Type>::contains(), WCValHashSet<Type>::contains()

find an element in the hash object

Synopsis:

#include <wchash.h>
public:
int contains( const Type & ) const;

Semantics:

Results:

The contains() public member function returns a non-zero value if the element is found in the hash.

WCValHashTable<Type>::entries(), WCValHashSet<Type>::entries()

count the entries in the hash object

Synopsis:

#include <wchash.h>
public:
unsigned entries() const;

Semantics:

The entries() public member function is used to return the current number of elements stored in the hash.

Results:

This function returns the number of elements in the hash.

WCValHashTable<Type>::find(), WCValHashSet<Type>::find()

find an element in the hash object

Synopsis:

#include <wchash.h>
public:
int find( const Type &, Type & ) const;

Semantics:

The find() public member function is used to find an element with an equivalent key in the hash. If an equivalent element is found, a non-zero value is returned. The reference to the element passed as the second argument is assigned the found element's value. Zero is returned if the element isn't found. Note that equivalence is based on the equivalence operator of the element type.

Results:

The element equivalent to the passed key is located in the hash.

WCValHashTable<Type>::forAll(), WCValHashSet<Type>::forAll()

invoke a user-supplied function for each element in the hash object

Synopsis:

#include <wchash.h>
public:
void forAll(
      void (*user_fn)( Type, void * ),
      void * );

Semantics:

The forAll() public member function causes the user-supplied function to be invoked for every value in the hash. The user function has the prototype:

    void user_func( Type & value, void * data );

As the elements are visited, the user function is invoked with the element passed as the first parameter. The second parameter of the forAll() function is passed as the second parameter to the user function. This value can be used to pass any appropriate data from the main program to the user function.

Results:

The elements in the hash are all visited, and the user function is invoked for each one.

WCValHashTable<Type>::insert(), WCValHashSet<Type>::insert()

insert a value into the hash object

Synopsis:

#include <wchash.h>
public:
int insert( const Type & );

Semantics:

The insert() public member function inserts a value into the hash, using the hash function to determine in which bucket it should be stored. If allocation of the node to store the value fails, then the out_of_memory exception is thrown, if it's enabled. If the exception isn't enabled, the insertion isn't completed.

With a WCValHashSet, there must be only one equivalent element in the set. If an element equivalent to the inserted element is already in the hash set, the hash set remains unchanged, and the not_unique exception is thrown, if it's enabled. If the exception isn't enabled, the insertion isn't completed.

At some point, the number of buckets initially selected may be too small for the number of elements inserted. The resize of the hash can be controlled by the insertion mechanism by using WCValHashSet (or WCValHashTable ) as a base class, and providing an insert-member function to do a resize when appropriate. This insertion function could then call WCValHashSet::insert (or WCValHashTable::insert ) to insert the element.

Note that copy constructors and assignment operators aren't inherited in your class, but you can provide the following inline definitions (assuming that the class inherited from WCValHashTable is named MyHashTable):

inline MyHashTable( const MyHashTable &orig )
     : WCValHashTable( orig ) {};
inline MyHashTable &operator=( const MyHashTable &orig ) 
{
    return( WCValHashTable::operator=( orig ) );
}

Results:

The insert() public member function inserts a value into the hash. If the insertion is successful, a non-zero is returned. A zero is returned if the insertion fails.

WCValHashTable<Type>::isEmpty(), WCValHashSet<Type>::isEmpty()

determine whether or not the hash object is empty

Synopsis:

#include <wchash.h>
public:
int isEmpty() const;

If an allocation failure occurs when creating the buckets, the table is created with zero buckets, and the out_of_memory exception is thrown, if it's enabled. If there isn't enough memory to copy all of the values or pointers in the hash, then only some are be copied, and the out_of_memory exception is thrown, if it's enabled. The number of entries correctly reflects the number copied.

Results:

The operator =() public member function assigns the left hand side hash to be a copy of the right hand side.

WCValHashTable<Type>::operator ==(), WCValHashSet<Type>::operator ==()

determine whether or not two hash objects are equivalent

Synopsis:

#include <wchash.h>
public:
int operator ==( const WCValHashSet & ) const;
int operator ==( const WCValHashTable & ) const;

Semantics:

The operator ==() public member function is the equivalence operator for the WCValHashTable<Type> and WCValHashSet<Type> classes. Two hash objects are equivalent if they're the same object and share the same address.

Results:

A TRUE (non-zero) value is returned if the left hand side and right hand side hashes are the same object. A FALSE (zero) value is returned otherwise.

WCValHashTable<Type>::remove(), WCValHashSet<Type>::remove()

remove an element from the hash table

Synopsis:

#include <wchash.h>
public:
int remove( const Type & );

Semantics:

The remove() public member function is used to remove the specified element from the hash. If an equivalent element is found, a non-zero value is returned. Zero is returned if the element isn't found. If the hash is a table and there's more than one element equivalent to the specified element, then the first equivalent element added to the table is removed.

Note that equivalence is based on the equivalence operator of the element type.

Results:

The element is removed from the hash if it's found.

WCValHashTable<Type>::removeAll()

remove all occurrences of an element from the hash object

Synopsis:

#include <wchash.h>
public:
unsigned removeAll( const Type & );

Semantics:

Results:

All equivalent elements are removed from the hash.

WCValHashTable<Type>::resize(), WCValHashSet<Type>::resize()

change the number of buckets in the hash object

Synopsis:

#include <wchash.h>
public:
void resize( unsigned );

Semantics:

The resize() public member function is used to change the number of buckets contained in the hash.

If the new number is zero, then the zero_buckets exception is thrown, if it's enabled, and no resize is performed. The hash is guaranteed to contain the same number of entries after the resize.

Results:

The hash is resized to the new number of buckets.

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

Synopsis:

Semantics:

Results:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics:

Results:

See also:

Synopsis:

Semantics: