IntHashTableThreaded.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
Adapted from HashTable.mesa by Mike Spreitzer, February 5, 1986 4:24:22 pm PST
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, May 7, 1986 4:00:14 pm PDT
Definitions for hashed table abstraction. The keys are INTs, and the values are REF ANYs. The hash bucket links are threaded through the values. 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 (Pairs) is going on.
IntHashTableThreaded: CEDAR DEFINITIONS = BEGIN
Table: TYPE = REF TableRec;
TableRec: PRIVATE TYPE = MONITORED RECORD [
class: Class,
size, sizeLimit, inhibitCount: INT,
data: REF Seq
];
Seq: TYPE = PRIVATE RECORD [nodes: SEQUENCE max: SeqIndex OF Value];
SeqIndex: TYPE = NAT;
Key: TYPE = INT;
Value: TYPE = REF;
Class: TYPE = RECORD [
GetKey: PROC [Value] RETURNS [Key],
SetLink: PROC [from, to: Value],
GetLink: PROC [from: Value] RETURNS [to: Value]
];
Create: PROC [mod: SeqIndex ← 17, class: Class] 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: 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: BOOLEAN ← FALSE];
Erase: PROC [table: Table];
deletes all key-value pairs in given table
END.