GPL_HashTable

gpl

1998 12-05

CLASS

SYNOPSIS

class user_defined_hashtable 
    : public GPL_HashTable<node_type, compare_type>
{
    public:
    user_defined_hashtable(long a_table_size) 
         : GPL_HashTable<node_type, compare_type>(a_table_size) {}
    long HashFunction(void *element);
    long Compare(void *node, void *element);
};

user_defined_hashtable htable(table_size);

GPL_IHashTable:

class node_type : public GPL_DoubleNode { };

class user_defined_ihashtable 
    : public GPL_IHashTable<node_type, compare_type>
{
    public:
    user_defined_hashtable(long a_table_size) 
         : GPL_HashTable<node_type, compare_type>(a_table_size) {}
    long HashFunction(void *element);
    long Compare(GPL_DoubleNode *node, void *element);
};

user_defined_ihashtable ihtable(table_size);

Both GPL_HashTable and GPL_IHashTable are hash table templates. Both are hash tables implemented with a linked list at each table location to handle multiple objects with the same hash value. Nodes are inserted and found in the table based on the Compare() function and some compare_type. Note that the compare_type handed to the hash table functions does not necessarily have to be a member data of node_type. However, a compare_type should not change for a node once it has been added to a hash table.

Class GPL_HashTable is implemented with non-intrusive linked lists (see GPL_DoubleList). Class GPL_IHashTable is implemented with intrusive linked lists (see GPL_IDoubleList). For an intrusive hash table, node_type must be derived from GPL_DoubleNode.

GPL_HashTable and GPL_IHashTable are intended to be base classes for user defined hash table classes. The virtual member functions HashFunction() and Compare() are to be defined in the user defined class.

CONSTRUCTOR

user_defined_hashtable htable(long table_size)
Note that the user defined hash table must define a constructor that uses the base contructor with table_size as an argument. A table of size table_size is constructed. This means there will be table_size linked lists constructed as well, one for each hash value (0 through table_size - 1).

MEMBER FUNCTIONS

node_type *LookUp(compare_type *element)
Given element, LookUp() tries to find an entry in the hash table that matches element based on the virtual member function Compare(). If a matching node is found it is returned, otherwise NULL is returned.
node_type *Remove(compare_type *element)
Remove() is the same as LookUp() except that the matching node is removed from the hash table.
void Insert(node_type *node, compare_type *element)
Add node to the hash table. The node will be added to the linked list corresponding to the value returned by HashFunction() when handed element.
GPL_DoubleList<void> *MemberList()
Return a linked list of all members in the hash table. The GPL_DoubleList object itself is created by MemberList() and should be deleted by the calling function. Note that the type in the linked list is void so objects accessed through the list will have to be cast to the proper type. If there are no members, NULL is returned.
long GetSize()
This function returns the size of the hash table, which may be useful in the virtual member function HashFunction().
long GetCount()
Return the number of nodes currently in the hash table.
GPL_DoubleList<void> **GetArray()
Return the array of internal linked lists in a GPL_HashTable. This is intended for manually going through all members of a hash table in a situation where optimum performance is needed. Otherwise, MemberList() should be used.
GPL_IDoubleList<GPL_DoubleNode> **GetArray()
Return the array of internal linked lists in a GPL_IHashTable. This is intended for manually going through all members of a hash table in a situation where optimum performance is needed. Otherwise, MemberList() should be used.
virtual long HashFunction(compare_type *element)
Based on the argument element return an index which will determine where a node Insert()ed with element will be placed.
virtual long Compare(node_type *node, compare_type *element)
This function is used to determine if node matches element. If node matches element, zero is returned. Otherwise, Compare() should return a non-zero value.