HashTable.Mesa
Copyright © 1985, 1986 by Xerox Corporation. All rights reversed.
Adapted from HashTable.mesa by Satterthwaite, March 21, 1986 3:37:16 pm PST
Last Edited by Satterthwaite, May 13, 1986 11:42:02 am PDT
Definitions for hashed table abstraction, parameterized with respect to entry (node) and key type. Hash and Equality functions are given. 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 1.0 and no enumeration (ForEach) is going on.
DIRECTORY
ParticularTable: TYPE USING [Node, Key];
HashTable: CEDAR DEFINITIONS = {
Value: TYPE = ParticularTable.Node;
Key: TYPE = ParticularTable.Key;
OpsRec: TYPE = RECORD[
GetKey: PROC[v: Value] RETURNS[Key],
HashFromKey: PROC[k: Key] RETURNS[CARDINAL],
EqualKeys: PROC[k1, k2: Key] RETURNS[BOOL]];
The required relation between HashFromKey and EqualKeys is that 2 equal keys (EqualKeys returns TRUE on them) must have the same hash key.
Table: TYPE = REF TableRec;
TableRec: PRIVATE TYPE = MONITORED RECORD[
ops: OpsRec,
size, sizeLimit, inhibitCount: INT,
data: REF Seq];
Seq: PRIVATE TYPE = RECORD[nodes: SEQUENCE max: SeqIndex OF NodeList];
SeqIndex: PRIVATE TYPE = NAT;
NodeList: PRIVATE TYPE = LIST OF Value;
Create: PROC[ops: OpsRec, mod: SeqIndex�] RETURNS[Table];
creates new table, whose length is mod.
GetSize: PROC[table: Table] RETURNS[INT];
returns number of key-value pairs in table
Fetch: PROC[table: Table, key: Key] RETURNS[found: BOOL, value: Value];
looks up key in table, returns associated value (if any)
if found is TRUE, value is value with given key
if found is FALSE, value is NIL
Replace: PROC[table: Table, key: Key, value: Value] RETURNS[BOOL];
returns TRUE after overwriting old value
if no previous value for key, returns FALSE without inserting new pair
Store: PROC[table: Table, key: Key, value: Value] RETURNS[BOOL];
returns TRUE after inserting new value
returns FALSE after overwriting old value for existing key-value pair
Insert: PROC[table: Table, key: Key, value: Value] RETURNS[BOOL];
returns TRUE after inserted new value
if previous value existed for key, returns FALSE without changing value
Delete: PROC[table: Table, key: Key] RETURNS[BOOL];
deletes value associated with given key
returns TRUE if deletion actually occurred, FALSE if no such key
ForEach: PROC[table: Table, action: EachValueAction] RETURNS[BOOL];
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
EachValueAction: TYPE = PROC[value: Value] RETURNS[quit: BOOL ← FALSE];
Erase: PROC[table: Table];
deletes all key-value pairs in given table
}.