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]; GetSize: PROC [x: Ref] RETURNS [INT]; Fetch: PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val]; Replace: PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL]; Store: PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL]; Insert: PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL]; Delete: PROC [x: Ref, key: Key] RETURNS [BOOL]; Erase: PROC [x: Ref]; EachPairAction: TYPE = PROC [key: Key, val: Val] RETURNS [quit: BOOL ¬ FALSE]; Pairs: PROC [x: Ref, action: EachPairAction] RETURNS [BOOL]; 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]; Copy: PROC [x: Ref] RETURNS [Ref]; EqualRope: EqualProc; HashRope: HashProc; EqualRopeCaseless: EqualProc; HashRopeCaseless: HashProc; END. ( 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. 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] returns number of key-value pairs in table 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 returns TRUE after overwriting old value for existing key-value pair if no previous value for key, returns FALSE without inserting new pair returns TRUE after inserting new pair returns FALSE after overwriting old value for existing key-value pair returns TRUE after inserted new pair if previous value existed for key, returns FALSE without changing value deletes key-value pair associated with given key returns TRUE if deletion actually occurred, FALSE if no such key deletes all key-value pairs in the table ... 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 ... 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. ... atomically copies the table. Common Hash/Equal functions ... for ROPE keys, case significant (Rope.Equal and RopeHash.FromRope with case~TRUE) ... for ROPE keys, case ignored (Rope.Equal and RopeHash.FromRope with case~FALSE) Κ •NewlineDelimiter –(cedarcode) style™codešœ ™ Kšœ ΟeœC™NKšœ ™ Kšœ#™#Kšœ™J™3Kšœ-™-K™/K™+K™*—K˜Kšœ(Οkœ žœsžœ™²K™Kšœι™ιK™KšΟnœžœž œž˜!˜Kšœžœžœ ˜Kš œ žœž œžœžœ˜=Kšœžœ˜K˜Kšœžœžœ˜Kšœžœžœ˜K˜Kš œ žœžœžœžœ˜8Kš œ žœžœ žœžœ˜4K˜š Ÿœžœžœžœžœžœ˜YKšœ2™2K™.Kšœžœ™4Kšœ<™