[an error occurred while processing this directive]

Table Module Implementation Specifications

Client Specifications

Implementation Data Model

Except for caching, the Table implementation is a standard hash table with separate chaining. In brief, a Table is a reference to a structure that contains an array of linked lists. Each node in a linked list contains a key and a data field for a table entry, and a reference to the next node in the list.

A key parameter is specified for the isKey(), add(), dataFor(), and remove() functions. For each of these functions, a hash value is computed for the key. The hash value is used to select one of the linked lists. Then a standard linked list operation is done with the selected list.

Caching is used to reduce the overhead that results from separating the check for presence of a key in isKey() from the add(), dataFor(), and remove() functions. Caching is accomplished by storing the key for the most recent call to isKey(), along with a reference to the list node that contains the key. A reference to the preceding node is also saved to facilitate the remove() function. This reference is null for the first entry in a hash list. Finally, the hash value for the key is saved to handle the remove() case where the entry to be removed is at the front of its list. When an isKey() search is unsuccessful, a null value is stored as the cache key. All data access functions use a call to isKey() to set up the cache variables.

For the add(), dataFor(), and remove() functions, the parameter key is first compared with the cached key. If they are the same then the cached information is used to do the required operation. Otherwise, a normal hash table operation is attempted. The function isKey() is always called after checking the cached key in order to ensure that preconditions are met. This call also puts the right values into the cache variables so that these functions do not need to do a search.

Private Importing Information

The source code file for this module must include Table.h. If the data type is a non-standard type declared in a header file then that header file must be included prior to the include for Table.h

Private Data Type Implementations

The following data types are declared in Table.C.

HashList - A HashList is a pointer to a HashListNode.
HashListNode - A HashListNode is a typedeffed struct with the following members:
- char * key - the key for a table entry
- Data data - the data for a table entry
- HashList next - a reference to the next list entry
HashTableStructure - A HashTableStructure is a typedeffed struct with the following members:
- HashList hashLists[256] - the array of hash lists
- char * cacheKey - the most recent key parameter for isKey()
- int cacheHashVal - the hash value for cacheKey
- HashList cachePointer - a reference to the list node whose key is cacheKey
- HashList cacheTrailer - a reference to the list node preceding cachePointer

Public Data Type Implementations

The following data type is declared in Table.h.

Table - Table is typedeffed as a pointer to a HashTableStructure.

Private Function Specifications

The following functions are declared static in Table.C.

static void freeList(HashList l)
freeList(l) frees the nodes in l.

Private Function Algorithms

freeList
Specification

parameter: HashList l

if l is not null
    recursively free all but the first node of l
    free(l)

Public Function Algorithms

newTable
Client Specification

malloc a TableStructure
set all of the hash lists of the TableStructure to null
return the pointer to the TableStructure

freeTable
Client Specification

parameter: Table tbl

clear tbl
free tbl

isKey
Client Specification

parameter: Table tbl
parameter: char * k

if k is equal to tbl->cacheKey
    return true
compute the hash value for k
search for k in the hash list indexed by the hash value
if k is found
    set tbl->cacheKey to k
    set tbl->cacheHashVal to the hash value
    set tbl->cachePointer to point to the list node containing k
    set tbl->cacheTrailer to point to the preceding node or null if there
	    is no preceding node
else
    set tbl->cacheKey to null
return cacheKey != null

dataFor
Client Specification

parameter: Table tbl
parameter: char * k

if tbl->cacheKey is null or tbl->cacheKey is not the same as k
    check if k is a key in tbl (call isKey())
if tbl->cacheKey is null
    terminate the program with a precondition violation error message
return tbl->cachePointer->data

add
Client Specification

parameter: Table tbl
parameter: char * k
parameter: Data dat

if tbl->cacheKey is null or tbl->cacheKey is not the same as k
    check if k is a key in tbl (call isKey())
if tbl->cacheKey is not null
    terminate the program with a precondition violation error message
malloc a new HashListNode that contains key k and data dat
insert the new HashListNode at the beginning of tbl->hashList[cacheHashVal]

remove
Client Specification

parameter: Table tbl
parameter: char * k

if tbl->cacheKey is null or tbl->cacheKey is not the same as k
    check if k is a key in tbl (call isKey())
if tbl->cacheKey is null
    terminate the program with a precondition violation error message
if tbl->cacheTrailer is null
    remove the first list node in tbl->hashLists[tbl->cashHashVal]
else
    remove the list node that is linked to tbl->cacheTrailer
set cacheKey to null

clear
Client Specification

parameter: Table tbl

for each index i for tbl->hashLists
    free nodes in tbl->hashLists[i] (call freeList())
    set tbl->hashLists[i] to null

iteratorFor
Client Specification See TableIterator Module Implementation Specifications

[an error occurred while processing this directive]