This section describes a set of routines for storing an arbitrary number of elements with a fixed access time. This implementation is designed for general-purpose use in many applications. Copies of the elements are stored in a hash table.
The elements may be of any fixed size, set at the time that the hash table is created. Each element contains a key identifying the element, along with whatever data you choose to associate with that key. For example, a key might be an x, y, z point, with an associated data value for that point.
Elements are stored in the table using long integer pseudokeys. These pseudokeys should be uniformly distributed in any range beginning at zero.
| Note: | Pseudokey 0xFFFFFFFF is reserved. Items cannot not be placed in the hash table using this pseudokey value. |
The elements themselves may contain the pseudokey as their first long integer word. Alternatively, the pseudokey may be derived from the element through a call-back function provided at the time the hash table is created.
More than one element may be stored under the same pseudokey if a compare function is provided at the time the hash table was created. Whenever the hash table query function is called with the same search key, the hash table is searched for an element whose pseudokey matches the key either in or derived from the search key. If no compare function has been provided, the found element is returned. However, if a compare function has been provided, it is called by the hash table query routine to match the search key against each element in the hash table that matches the pseudokey. When the compare function succeeds (returns a 0), the element is returned.
A similar sequence is used to either insert a unique element (if a compare function was provided) or to overwrite a previously inserted element of the same key (if a compare function was not provided).
| Note: | Only 16 elements may be stored using the same pseudokey. |
HashTable DXCreateHash() | Creates a hash table. See "Examples". See DXCreateHash. |
Element DXQueryHashElement() | Searches a hash table for an element matching a specified key. See "Examples". See DXQueryHashElement. |
Error DXInsertHashElement() | Inserts an element into a hash table. See "Examples". See DXInsertHashElement. |
Error DXDeleteHashElement() | Removes any element that matches a search key. See DXDeleteHashElement. |
Error DXInitGetNextHashElement() | Initializes the pointer to the next element for GetNextHashElement. See DXInitGetNextHashElement. |
Error DXGetNextHashElement() | Returns the next element in a hash table. See DXGetNextHashElement. |
Error DXDestroyHash() | Deletes a hash table. See DXDestroyHash. |
Optional routines provided by the caller at the time of creation of the hash table follow:
hashFunc() | Converts a search key to a long integer pseudokey. Called on insertion and query. |
cmpFunc() | Determines whether elements with the same pseudokey are unique. Called on insertion and query. |
In the following examples, underscored items are supplied by the user.
(1) No hash or compare function is provided at the time the hash table is created. Stored elements are x, y, z points, along with associated data values.
| Note: | Because no hash function is provided, the pseudokey must be stored as the first long integer word of the element. |
typedef struct
{
long pseudokey;
Point pt;
float data;
} hashelement;
HashTable hashtable; hashtable = DXCreateHash(sizeof(element), NULL, NULL);
for (i=0; i < number of points to insert; i++){
element.pseudokey = GetKey(¤t_point);
element.pt = current_point;
element.data = current_data;
DXInsertHashElement(hashtable, (Element)&element);
}
(2) If GetKey returns the same pseudokey for two different points, the second will overwrite the first because no compare function was provided to DXCreateHash().
To extract elements from the hash table:
PseudoKey pkey;
hashelement *element_ptr;
pkey = GetKey(&point_to_search_for);
element_ptr = DXQueryHashElement(hashtable, (Key)&pkey);
GetKey that returns a pseudokey given a point x, y, z:
PseudoKey GetKey(Key key)
{
Point *pt;
pt = (Point *)key;
return pt->x + 17*pt->y + 23*pt->z;
}
Alternatively, the hash function GetKey can be provided at the time the hash table is created. In that case the pseudokey does not need to be part of the element.
typedef struct
{
Point pt;
float data;
} hashelement;
HashTable hashtable;
hashelement element;
hashtable = DXCreateHash(sizeof(element), GetKey, NULL);
for (i=0; i < number_of_points_to_insert; i++){
element.pt = current_point;
element.data = current_data;
DXInsertHashElement(hashtable, (Element)&element);
where:
PseudoKey GetKey(Key key)
{
Point *pt;
pt = (Point *)key;
return pt->x + 17*pt->y + 23*pt->z;
}
To extract elements from the hash table:
hashelement *element_ptr;
element.pt = point_to_search_for;
element_ptr = DXQueryHashElement(hashtable, (Key)&element);
(3) This example uses a compare function.
typedef struct
{
Point pt;
float data;
} hashelement;
HashTable hashtable;
hashelement element;
hashtable = DXCreateHash(sizeof(element), GetKey, CompareFunc);
for (i=0; i < number of points to insert; i++){
element.pt = current_point;
element.data = current_data;
DXInsertHashElement(hashtable, (Element)&element);
}
where the compare function may be:
int CompareFunc(Key searchkey, Element element)
{
Point *p, p1, p2;
hashelement *h;
p = (Point *)searchkey;
p1 = *p;
h = (hashelement *)element;
p2 = h->pt;
if ((pl.x==p2.x)&&(p1.y==p2.y)&&(p1.z==p2.z))
return 0;
else
return 1;
}