[Cyan]<CedarChest6.1>IntChainedHashTable>IntChainedHashTable.mesa!1

IntChainedHashTable.Mesa

Adapted from RefTab.mesa by Bertrand Serlet, July 24, 1985 4:20:46 pm PDT

Adapted from HashTable.mesa by Mike Spreitzer, October 23, 1985 5:41:07 pm PDT

Last Edited by Bertrand Serlet, July 29, 1985 11:42:28 am PDT

Last Edited by Widom, July 25, 1985 4:36:47 pm PDT

Adapted from HashTable.mesa by Mike Spreitzer, May 7, 1986 4:26:04 pm PDT

Last Edited by Mike Spreitzer, August 19, 1986 7:10:33 pm PDT

Definitions for a chained hash table abstraction. The keys are INTs and the values are REF ANYs. Each table is monitored.

These tables will grow in size (up to a limit), so as to keep the density (i.e., (# elements in table) / (# hash table buckets)) from growing too large. When these tables grow, they pick as new modulus a prime number at least twice as large as the old modulus. These tables will try to grow when the density exceeds 2/3 and no enumeration (Pairs) is going on.

IntChainedHashTable: CEDAR DEFINITIONS = BEGIN

Table: TYPE = REF TableRec;

TableRec: PRIVATE TYPE = MONITORED RECORD [

size, sizeLimit, inhibitCount, chain: NAT,

invalidKey: Key,

data: REF Seq

];

Seq: TYPE = PRIVATE RECORD [nodes: SEQUENCE max: SeqIndex OF NodeRep];

NodeRep: TYPE = PRIVATE RECORD [key: Key, value: Value];

SeqIndex: TYPE = NAT;

Key: TYPE = INT;

Value: TYPE = REF ANY;

Create: PROC [invalidKey: Key, mod: SeqIndex ← 17] RETURNS [Table];

creates new table, whose length is mod.

You must provide it with one Key which will never occur in your data.

GetSize: PROC [table: Table] RETURNS [INT];

returns number of key-value pairs in table

Fetch: PROC [table: Table, key: Key] RETURNS [found: BOOLEAN, value: Value];

looks up key in table, returns associated value (if any)

if found is TRUE, value is value associated with given key

if found is FALSE, value is NIL

Replace: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN];

returns TRUE after overwriting old value for existing key-value pair

if no previous value for key, returns FALSE without inserting new pair

Store: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN];

returns TRUE after inserting new pair

returns FALSE after overwriting old value for existing key-value pair

Insert: PROC [table: Table, key: Key, value: Value] RETURNS [BOOLEAN];

returns TRUE after inserted new pair

if previous value existed for key, returns FALSE without changing value

Pairs: PROC [table: Table, action: EachPairAction] RETURNS [BOOLEAN];

enumerates pairs currently in symbol table in unspecified order

pairs inserted/deleted during enumeration may or may not be seen

applies action to each pair until action returns TRUE or no more pairs

returns TRUE if some action returns TRUE

EachPairAction: TYPE = PROC [key: Key, value: Value] RETURNS [quit: BOOLEAN ← FALSE];

Erase: PROC [table: Table];

deletes all key-value pairs in given table

Stuck: ERROR;

Raised from Store & Insert if table full and an enumeration is going on.

END.