RefTab.mesa
Copyright Ó 1985, 1986, 1987, 1991 by Xerox Corporation. All rights reserved.
Paxton - August 19, 1982 9:24 am
Teitelman - August 31, 1982 2:20 pm
Rovner - May 13, 1983 10:39 am
Russ Atkinson (RRA) February 5, 1985 2:01:00 pm PST
Bertrand Serlet, July 24, 1985 4:20:46 pm PDT
Mike Spreitzer, October 23, 1985 5:41:07 pm PDT
Doug Wyatt, January 15, 1987 4:14:21 pm PST
Carl Hauser, June 21, 1988 10:28:18 pm PDT
A RefTab is hash table which associates REF keys with REF values. The client may supply Equality and Hash functions; the defaults are suitable for canonicalized keys like ATOMs.
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.
RefTab: CEDAR DEFINITIONS = BEGIN
Ref: TYPE = REF RefTabRep;
RefTabRep: TYPE = MONITORED RECORD [impl: REF RefTabImplRep];
RefTabImplRep: TYPE;
Key: TYPE = REF;
Val: TYPE = REF;
EqualProc: TYPE = PROC [key1, key2: Key] RETURNS [BOOL];
HashProc: TYPE = PROC [key: Key] RETURNS [CARDINAL];
Create: PROC [mod: NAT ¬ 17, equal: EqualProc ¬ NIL, hash: HashProc ¬ NIL] RETURNS [Ref];
creates new table with suggested initial hash size
equal defaults to key1=key2 (pointer equality)
hash defaults to BITXOR[HighHalf[key], LowHalf[key]]
the following must hold: equal[k1, k2] => hash[k1]=hash[k2]
GetSize: PROC [x: Ref] RETURNS [INT];
returns number of key-value pairs in table
Fetch: PROC [x: Ref, key: Key] RETURNS [found: BOOL, 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 [BOOL];
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 [BOOL];
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 [BOOL];
returns TRUE after inserted new pair
if previous value existed for key, returns FALSE without changing value
Delete: PROC [x: Ref, key: Key] RETURNS [BOOL];
deletes key-value pair associated with given key
returns TRUE if deletion actually occurred, FALSE if no such key
Erase: PROC [x: Ref];
deletes all key-value pairs in the table
EachPairAction: TYPE = PROC [key: Key, val: Val] RETURNS [quit: BOOL ¬ FALSE];
Pairs: PROC [x: Ref, action: EachPairAction] 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
UpdateOperation: TYPE = {none, store, delete};
UpdateAction: TYPE = PROC [found: BOOL, val: Val]
RETURNS [op: UpdateOperation ¬ none, new: Val ¬ NIL];
Update: PROC [x: Ref, key: Key, action: UpdateAction];
... atomically performs an update action; looks up key and calls action, which returns the desired operation. If op=none, the table is not changed; if op=store, the new value is stored; if op=delete, key is removed from the table.
Copy: PROC [x: Ref] RETURNS [Ref];
... atomically copies the table.
Common Hash/Equal functions
EqualRope: EqualProc;
HashRope: HashProc;
... for ROPE keys, case significant (Rope.Equal and RopeHash.FromRope with case~TRUE)
EqualRopeCaseless: EqualProc;
HashRopeCaseless: HashProc;
... for ROPE keys, case ignored (Rope.Equal and RopeHash.FromRope with case~FALSE)
END.