ReHashTable.Mesa
Copyright © 1985 by Xerox Corporation. All rights reversed.
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
Last Edited by Mike Spreitzer, November 6, 1985 12:19:06 pm PST
Definitions for hashed REF table abstraction. Hash and Equality functions are given. Each table is monitored.
RefTab is a particular case of this interface, when defaults are used. Particular Hash and Equality functions are provided to produce behavior equivalent to SymTab.
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 (Pairs) is going on.
ReHashTable: CEDAR DEFINITIONS = BEGIN
Table: TYPE = REF TableRec;
TableRec: PRIVATE TYPE = MONITORED RECORD [
hash: HashProc,
equal: EqualProc,
size, sizeLimit, inhibitCount: INT,
data: REF Seq
];
Seq: TYPE = PRIVATE RECORD [nodes: SEQUENCE max: SeqIndex OF Node];
Node: TYPE = PRIVATE REF NodeRep;
NodeRep: TYPE = PRIVATE RECORD [key: Key, value: Value, next: Node];
SeqIndex: TYPE = NAT;
Key: TYPE = REF;
Value: TYPE = REF;
HashProc: TYPE = PROC [Key] RETURNS [CARDINAL];
EqualProc: TYPE = PROC [Key, Key] RETURNS [BOOL];
Create: PROC [mod: SeqIndex ← 17, equal: EqualProc ← NIL, hash: HashProc ← NIL] RETURNS [Table];
creates new table, whose length is mod. The required relation between hashProc and equalProc is that 2 equal keys (equalProc returns TRUE on them) must have the same hash key. equal defaults to pointer equality, and hash defaults to a magic Xor on key adress.
RopeEqual, RopeEqualModCase: EqualProc;
Some EqualProcs that clients may find commonly useful.
HashRope, HashRopeModCase: HashProc;
Some HashProcs that clients may find commonly useful.
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
Delete: PROC [table: Table, key: Key] RETURNS [BOOLEAN];
deletes key-value pair associated with given key
returns TRUE if deletion actually occurred, FALSE if no such key
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: BOOLEANFALSE];
Erase: PROC [table: Table];
deletes all key-value pairs in given table
END.