table.h File Reference

Association table. More...

Go to the source code of this file.

Classes
struct	adt_Table_t
	Table container class. More...
Defines
#define	ADT_ERROR   (-1)
Typedefs
typedef adt_Table_t	adt_Table
	Table container class.
Functions
adt_Table *	adt_createTable (int size)
	Constructor.
void	adt_destroyTable (adt_Table *)
	Destructor.
int	adt_insertTable (adt_Table *, const char *key, int value)
	Insert (key, value) pair into table.
int	adt_lookupTable (adt_Table *, const char *key)
	Lookup table entry value associated with given key.
int	adt_updateTable (adt_Table *, const char *key, int newvalue)
	Update value for table entry.
int	adt_deleteTable (adt_Table *, const char *key)
	Delete key and its associated value from table.
int	adt_initializeTable (adt_Table *, int size)
	Alternative constructor.
void	adt_cleanupTable (adt_Table *)
	Alternative destructor.
const char *	adt_getStatsTable (adt_Table *)
	Compute table statistics.

---

Detailed Description

Association table.

Author:

John Stone and David J. Hardy

Date:

2003-2005

The adt_Table class provides an association table, a mapping of keys to values (i.e. any key has exactly one value associated with it). The keys are nil-terminated strings and the values are nonnegative integers (most likely an array index). The adt_Table supports fast searching by applying a hash function to the key.

The integer value associated with a key is intended to be an array index (i.e. nonnegative). Otherwise, the value will conflict with the ADT_ERROR (-1) return value indicating an error. The const char * strings passed in as keys are aliased by the table, so they must persist at least as long as the table does. The easiest way is to use string literals as hash keys.

Errors are generally indicated by a return value of ADT_ERROR, due either to failed memory allocation or inability to find a key in the table, depending on the function.

The hash table implementation was donated by John Stone, and the interface was subsequently modified by David Hardy.

---

Define Documentation

#define ADT_ERROR   (-1)

Return value from failed function call.

---

Typedef Documentation

typedef struct adt_Table_t adt_Table

Table container class. Members should be treated as private.

---

Function Documentation

void adt_cleanupTable (  adt_Table *   )

Alternative destructor. Use to destroy a preallocated table object (i.e. one constructed using adt_initializeTable() ).

adt_Table* adt_createTable (  int  size  )

Constructor. Creates dynamically allocated table object. Parameters: [in]  size  The starting number of table entries. Note that the table will still be dynamically resized if enough insertions are performed. A good estimate for size can avoid resizing, roughly twice the number of expected table entries. Returns: Pointer to table object or NULL if memory allocation fails.

int adt_deleteTable (  adt_Table *  , const char *  key )

Delete key and its associated value from table. Parameters: [in]  key  A nil-terminated string. Returns: The nonnegative value that had been associated with key or ADT_ERROR if key is not in the table.

void adt_destroyTable (  adt_Table *   )

Destructor. Frees dynamically allocated table space and dynamically allocated table object.

const char* adt_getStatsTable (  adt_Table *   )

Compute table statistics. Returns: A string description "# slots, # entries, and # ALOS" (ALOS = average length of search) providing diagnostics for the data structure performance.

int adt_initializeTable (  adt_Table *  , int  size )

Alternative constructor. Use to construct a preallocated table object. See adt_createTable() for a description of expected arguments.

int adt_insertTable (  adt_Table *  , const char *  key, int  value )

Insert (key, value) pair into table. Parameters: [in]  key  A nil-terminated string. [in]  value  A nonnegative integer. Make sure that the string pointed to by key persists until after the table is destroyed. The associated value is probably an array index. This routine does not update an existing value for key if key is already in the table. Instead call adt_updateTable(). Returns: The value argument on success. If key is already present in the table, then the value already associated with it is instead returned. If memory cannot be allocated for the new (key, value) pair, then ADT_ERROR is returned. Note that a memory allocation error fails gracefully (i.e. you can try freeing other memory from the heap and then re-invoke this function). An error leaves the state of the existing table intact.

int adt_lookupTable (  adt_Table *  , const char *  key )

Lookup table entry value associated with given key. Parameters: [in]  key  A nil-terminated string. Returns: The nonnegative value associated with key of ADT_ERROR if key is not in the table.

int adt_updateTable (  adt_Table *  , const char *  key, int  newvalue )

Update value for table entry. Parameters: [in]  key  A nil-terminated string. [in]  newvalue  A nonnegative integer. This changes the (key, value) association in place: Returns: The previous value that had been associated with key or ADT_ERROR if key is not in the table.

---