VLib/TVHash [ Modules ]
NAME
TVHash -- a hash table data structure.
DESCRIPTION
IDEAS
One point should be noted in regard of the implementation intruduced here. It is the fact that two types for a key-object are defined and used in different situations. Let's see an example.
We have a string repository that maps the atom (an integral id) to the string. It supports two operations:
* introducing a new string with an atom to identify it and
* converting the atom to the string.
Note that no string look up operation is supported.
Now we have a string and we need an atom that represents it in the repository or insert it as a new string if it was not present so far. A hash table is an ideal structure to fullfill the task.
The string is hashed to obtain an address to addressing space. An atom is then retrieved or stored on the obtained address. It is all right so far. But what when the table is filled up and needs to grow? The entries need to be re-hashed to the new address space. However the atom only is stored in the hash table. That is why an idea of two types and hash functions is introduced.
As a result input and internal (or outer and inner) key-object types and hash functions are introduced. Together with an user's data pointer passed to hash function it provides a solution to the instanced problem.
The inner type would be defined as the atom's type whereas the outer type would be a char pointer. According to it the outer hash function is defined to compute a hash value from the string while the inner may be defined as a composition of the outer hash function and a string-repository function to map the atom to the string.
The hash table implemented here is intended to store just two data cells:
* key cell - TVHT_IKey_M * and data cell - TVHT_Data_M.
Memory management of keys and data objects is left out of the module's scope.
Collisions are solved with linked list.
HISTORY
- Documented on 2008-08-11.
common.thash/TVHT_Data [ Types ]
NAME
TVHT_Data_M (name template) -- data type to store to the hash table
PURPOSE
TVHT_Data_M macro is used to type structure fields and variables to store user's data inserted into the hash table and functions to return it.
Every time an entry is inserted in a hash table, a cell for TVHT_Data_M value is alocated within the linked list.
EXAMPLE
147 * #define TVHT_Data_M vnat
common.thash/TVHT_IKey_M [ Types ]
NAME
TVHT_IKey_M (name template) -- data type to store the key in the hash table
PURPOSE
TVHT_IKey_M macro is used to type structure fields and variables to store a user's key (or reference to it) in the hash table and functions to return it.
Every time an entry is inserted in a hash table, a cell for TVHT_IKey_M value is alocated within the linked list.
EXAMPLE
101 * #define TVHT_IKey_M vnat
common.thash/TVHT_OKey_M [ Types ]
NAME
TVHT_OKey_M (name template) -- data type to handle a key object that is hashed
PURPOSE
TVHT_OKey_M macro is used to type variables to store a reference to user's key object. It is not stored anywhere and thus nor returned by any function.
NOTES
Inner and outer keys are distinguished to allow implementation of object-to-atom repositories. The user having a string pointer (for instance) in her hand does not know its representaional atom number nor whether the string has been inserted. So she tries to lookup it through the pointer (outer key) possibly yielding the atom (associated value). If the string was not in the repository, she inserts it there and hooks the atom in the hash table as the inner key.
EXAMPLE
128 * #define TVHT_OKey_M char *
thash/v_ht_insert [ Functions ]
NAME
v_ht_insert_M (name template) -- insert an entry associated with the inner key.
SYNOPSIS
296 * TVHT_Data_M *data_ptr = v_ht_insert(ht, string_atom) 297 * (or if the table is used as a set (not a map); void variant) 298 * v_ht_insert(ht, string_atom)
FUNCTION
The function prepends an entry to the linked list of items associated with the inner key. It does not care whether the key has been introduced before. No space is alocated for the object values referenced by the key nor by data. However the key and data itself are stored.
INPUTS
ht - the hash table ikey - inner key as expected by the f_hash_int function
RESULT
data_ptr - pointer to the space to that data ought to be stored.
thash/v_ht_lookup2 [ Functions ]
NAME
v_ht_lookup2_M (name template) -- get data last inserted with the outer
key.
SYNOPSIS
270 * TVHT_Data_M data = v_ht_lookup2(ht, string_ptr, NULL)
FUNCTION
The function looks the linked list at the hashed address up for the outer key. It returns the first found data associated with the key if any or not_found value otherwise.
INPUTS
ht - the hash table okey - outer key as expected by the f_hash_inp function not_found - data value that ought to be returned if the key is not
present
RESULT
data - associated data or not_found value
thash/v_ht_lookup_start_inp [ Functions ]
NAME
v_ht_lookup_start_inp_M (name template) -- start browsing of items
associated with the outer key.
SYNOPSIS
350 * list = v_ht_lookup_start_inp(ht, string_ptr)
FUNCTION
The function chooses the linked list from the address space table using the hash function. It does not care whether there is any entry.
INPUTS
ht - the hash table ikey - outer key as expected by the f_hash_inp function
RESULT
list - references internal linked lists repository if the key is
present or is equal to V_HT_NULL otherwise.
SEE ALSO
thash/v_ht_lookup_start_int [ Functions ]
NAME
v_ht_lookup_start_int_M (name template) -- start browsing of items
associated with the inner key.
SYNOPSIS
326 * list = v_ht_lookup_start_int(ht, string_atom)
FUNCTION
The function chooses the linked list from the address space table using the hash function. It does not care whether there is any entry.
INPUTS
ht - the hash table ikey - inner key as expected by the f_hash_int function
RESULT
list - references internal linked lists repository if the key is
present or is equal to V_HT_NULL otherwise.
SEE ALSO
TVHash/vnat [ Types ]
NAME
vnat -- natural number
PURPOSE
The vnat number type is intended to hold a size of any single object that may appear in the program. It ought to be an unsigned integer type, possibly of an architecture independent size. Its range grows with the problem scale. However 32 bit could be usualy enought.
SOURCE
69 #define vnat uint32_t