GeneralRefTab.Mesa
Definitions for generalized REF table abstraction, with the possibility to give the hash function and the equality function.
RefTab is a particular case of this generalized REF table abstraction, when the equality is the equality between pointers, and the hash function a well chosen XOR on the address of the key.
Copyright © 1985 by Xerox Corporation. All rights reversed.
Adapted from RefTab.Mesa by Bertrand Serlet, June 3, 1985 6:08:45 pm PDT
Last Edited by Bertrand Serlet, June 15, 1985 3:23:11 pm PDT
GeneralRefTab:
CEDAR
DEFINITIONS =
BEGIN
Ref: TYPE = REF RefTabRep;
RefTabRep: PRIVATE TYPE = MONITORED RECORD [hashProc: REF HashProc, equalProc: REF EqualProc, mod: CARDINAL, size: 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, val: Val, next: Node];
SeqIndex: TYPE = CARDINAL[0..4000);
Key: TYPE = REF;
Val: TYPE = REF;
HashProc: TYPE = PROC [key: Key] RETURNS [hashIndex: CARDINAL];
EqualProc: TYPE = PROC [key1, key2: Val] RETURNS [BOOL];
DefaultHashProc: HashProc;
DefaultEqualProc: EqualProc; -- = {RETURN [val1=val2]} The vanilla equality
Create:
PROC [hashProc: HashProc ← DefaultHashProc, equalProc: EqualProc ← DefaultEqualProc, mod: SeqIndex ← 17]
RETURNS [Ref];
creates new table with suggested hash size. The required relation between hashProc and equalProc is that 2 equal keys (equalProc returns TRUE on them) must have the same hash key.
GetSize:
PROC [x: Ref]
RETURNS [
INT];
returns number of key-value pairs in table
Fetch:
PROC [x: Ref, key: Key]
RETURNS [found:
BOOLEAN, val: Val];
looks up key in table, returns associated value (if any)
if found is TRUE, val is value associated with given key
if found is FALSE, val is NIL
Replace:
PROC [x: Ref, key: Key, val: Val]
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 [x: Ref, key: Key, val: Val]
RETURNS [
BOOLEAN];
returns TRUE after inserting new pair
returns FALSE after overwriting old value for existing key-value pair
Insert:
PROC [x: Ref, key: Key, val: Val]
RETURNS [
BOOLEAN];
returns TRUE after inserted new pair
if previous value existed for key, returns FALSE without changing value
Delete:
PROC [x: Ref, 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 [x: Ref, 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, val: Val] RETURNS [quit: BOOLEAN ← FALSE];
END.