JaMDictImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Original version by Martin Newell, January 1979
Bill Paxton, 29-Jan-82 15:44:13
Doug Wyatt, March 18, 1985 2:46:13 pm PST
Administers JaM dictionaries. A Dictionary (Dict) is a set of <key,value> tuples, in which both key and value are Objects (Any); key is not necessarily a string.
DIRECTORY
Basics USING [LowHalf],
JaM USING [Any, Dict, DictRep, Eq, Error, Execute, Pop, PopInt, PopDict, Push, PushBool, PushDict, ROPE, RopeToAtom, State],
JaMPrimitives USING [];
JaMDictImpl: CEDAR MONITOR LOCKS x USING x: Ref
IMPORTS Basics, JaM
EXPORTS JaM, JaMPrimitives
= BEGIN OPEN JaM;
Types and constants
Ref: TYPE = REF DictImplRep;
DictImplRep: PUBLIC TYPE = MONITORED RECORD[mod, size: CARDINAL, data: Data];
Key, Val: TYPE = Any;
Node: TYPE = REF NodeRep;
NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node];
Data: TYPE = REF DataRep;
DataRep: TYPE = RECORD[nodes: SEQUENCE max: CARDINAL OF Node];
Hash:
PROC[key: Key, mod:
CARDINAL]
RETURNS[
CARDINAL] = {
bits: LONG CARDINAL;
WITH key
SELECT
FROM
x: ROPE => bits ← LOOPHOLE[RopeToAtom[x]];
x: REF INT => bits ← LOOPHOLE[REAL[x^]];
x: REF REAL => bits ← LOOPHOLE[x^];
ENDCASE => bits ← LOOPHOLE[key];
RETURN[(LOOPHOLE[Basics.LowHalf[bits], CARDINAL]/4) MOD mod];
};
Create:
PROC [mod:
CARDINAL ← 17]
RETURNS [Ref] = {
creates new table with suggested hash size
IF mod < 1 THEN mod ← 1;
IF mod > 4095 THEN mod ← 4095;
RETURN[NEW[DictImplRep ← [mod: mod, size: 0, data: NEW[DataRep[mod]]]]];
};
DSize:
PROC [x: Ref]
RETURNS [
CARDINAL] =
INLINE {
RETURN [x.size]};
returns number of key-value pairs in table
DFetch:
ENTRY
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
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
WHILE node #
NIL
DO
nkey: Key ← node.key;
IF Eq[key, node.key] THEN RETURN [TRUE, node.val];
node ← node.next;
ENDLOOP;
RETURN [FALSE, NIL];
};
DStore:
ENTRY
PROC [x: Ref, key: Key, val: Val]
RETURNS [
BOOL] = {
stores new key-value pair, overwriting previous value for given key
returns TRUE if new value, FALSE if previous value overwritten
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
WHILE node #
NIL
DO
nkey: Key ← node.key;
IF Eq[key, node.key] THEN {node.val ← val; RETURN [FALSE]};
node ← node.next;
ENDLOOP;
x.data[hash] ← NEW[NodeRep ← [key: key, val: val, next: head]];
x.size ← x.size + 1;
RETURN [TRUE];
};
DReplace:
ENTRY
PROC [x: Ref, key: Key, val: Val]
RETURNS [
BOOL] = {
looks up key, overwriting previous value iff key is found
returns TRUE if value was replaced, FALSE if not
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
WHILE node #
NIL
DO
nkey: Key ← node.key;
IF Eq[key, node.key] THEN {node.val ← val; RETURN [TRUE]};
node ← node.next;
ENDLOOP;
RETURN [FALSE];
};
DDelete:
ENTRY
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
ENABLE UNWIND => NULL;
hash: CARDINAL ← Hash[key, x.mod];
node: Node ← x.data[hash];
head: Node ← node;
lag: Node ← NIL;
WHILE node #
NIL
DO
nkey: Key ← node.key;
IF Eq[key, node.key]
THEN {
IF lag = NIL THEN x.data[hash] ← node.next ELSE lag.next ← node.next;
x.size ← x.size - 1; RETURN [TRUE]};
lag ← node;
node ← node.next;
ENDLOOP;
RETURN [FALSE];
};
DPairs:
PROC [x: Ref, action:
PROC[Key, Val]
RETURNS[
BOOL]]
RETURNS [quit:
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
node: Node ← NIL;
index: CARDINAL ← 0;
Next:
ENTRY
PROC [x: Ref, node: Node, index:
CARDINAL]
RETURNS [Node,
CARDINAL] = {
ENABLE UNWIND => NULL;
mod: CARDINAL ← x.mod;
IF node #
NIL
THEN {
node ← node.next;
IF node # NIL THEN RETURN [node, index];
index ← index + 1}
ELSE index ← 0;
WHILE index < mod
DO
node ← x.data[index];
IF node = NIL THEN {index ← index + 1; LOOP};
RETURN [node, index];
ENDLOOP;
RETURN [NIL, mod];
};
DO
[node, index] ← Next[x, node, index];
IF node = NIL THEN RETURN [FALSE];
IF action[node.key, node.val] THEN RETURN [TRUE];
ENDLOOP;
};
NewDict:
PUBLIC
PROC[length:
INT]
RETURNS[Dict] = {
IF length
IN[0..
LAST[
CARDINAL]]
THEN
RETURN[NEW[DictRep ← [impl: Create[length], attach: NIL]]]
ELSE ERROR Error[BoundsFault];
};
DictLength:
PUBLIC
PROC[dict: Dict]
RETURNS[
INT] = {
RETURN[DSize[dict.impl]];
};
TryToGet:
PUBLIC
PROC[dict: Dict, key: Any]
RETURNS[found:
BOOL, val: Any] = {
[found, val] ← DFetch[dict.impl, key];
IF found THEN RETURN;
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
adict: Dict = attach.first;
[found, val] ← TryToGet[adict, key];
IF found THEN RETURN;
ENDLOOP;
RETURN[FALSE, NIL];
};
TryToReplace:
PROC[dict: Dict, key: Any, val: Any]
RETURNS[
BOOL] = {
Enters <key,val> into dict iff key is already defined
IF DReplace[dict.impl, key, val] THEN RETURN[TRUE];
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
adict: Dict = attach.first;
IF TryToReplace[adict, key, val] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
TryToDelete:
PROC[dict: Dict, key: Any]
RETURNS[
BOOL] = {
IF DDelete[dict.impl, key] THEN RETURN[TRUE];
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
adict: Dict = attach.first;
IF TryToDelete[adict, key] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
TryToLoad:
PUBLIC
PROC[self: State, key: Any]
RETURNS[found:
BOOL, val: Any] = {
Return value looked up in highest dictionary having key in dictstk,
searching attached dictionaries if necessary
FOR stack:
LIST
OF Dict ← self.dictstk, stack.rest
UNTIL stack=
NIL
DO
dict: Dict = stack.first;
[found, val] ← TryToGet[dict, key];
IF found THEN RETURN;
ENDLOOP;
RETURN[FALSE, NIL];
};
Find:
PROC[dict: Dict, key: Any]
RETURNS[found:
BOOL, where: Dict] = {
IF DFetch[dict.impl, key].found THEN RETURN[TRUE, dict];
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
adict: Dict = attach.first;
[found, where] ← Find[adict, key];
IF found THEN RETURN;
ENDLOOP;
RETURN[FALSE, NIL];
};
Known:
PUBLIC
PROC[dict: Dict, key: Any]
RETURNS[
BOOL] = {
RETURN[TryToGet[dict, key].found];
};
Where:
PUBLIC
PROC[self: State, key: Any]
RETURNS[found:
BOOL, where: Dict] = {
FOR stack:
LIST
OF Dict ← self.dictstk, stack.rest
UNTIL stack=
NIL
DO
dict: Dict = stack.first;
[found, where] ← Find[dict, key];
IF found THEN RETURN;
ENDLOOP;
RETURN[FALSE, NIL];
};
Get:
PUBLIC
PROC[dict: Dict, key: Any]
RETURNS[Any] = {
known: BOOL; val: Any; [known, val] ← TryToGet[dict, key];
IF known THEN RETURN[val] ELSE ERROR Error[UndefinedKey];
};
Put:
PUBLIC
PROC[dict: Dict, key: Any, val: Any] = {
[] ← DStore[dict.impl, key, val];
};
Def:
PUBLIC
PROC[self: State, key: Any, val: Any] = {
Enters <key,val> into dictionary on top of dictstk,
dict: Dict = self.dictstk.first;
Put[dict, key, val];
};
Load:
PUBLIC
PROC[self: State, key: Any]
RETURNS[Any] = {
known: BOOL; val: Any; [known, val] ← TryToLoad[self, key];
IF known THEN RETURN[val] ELSE ERROR Error[UndefinedKey];
};
Store:
PUBLIC
PROC[self: State, key: Any, val: Any] = {
Enters <key,val> into highest dictionary having key in dictstk,
or into dict on top of dictstk if key not found.
FOR stack:
LIST
OF Dict ← self.dictstk, stack.rest
UNTIL stack=
NIL
DO
dict: Dict = stack.first;
IF TryToReplace[dict, key, val] THEN RETURN;
ENDLOOP;
Def[self, key, val];
};
Del:
PUBLIC
PROC[dict: Dict, key: Any] = {
Deletes object key from dictionary
Generates UndefinedKey if object not found:
IF NOT TryToDelete[dict, key] THEN ERROR Error[UndefinedKey];
};
AttachmentPath:
PROC[dict1, dict2: Dict]
RETURNS[
BOOL] = {
returns TRUE iff there is an attachment path from dict1 to dict2
IF dict1 = dict2 THEN RETURN[TRUE];
FOR attach:
LIST
OF Dict ← dict1.attach, attach.rest
UNTIL attach=
NIL
DO
adict: Dict = attach.first;
IF AttachmentPath[adict, dict2] THEN RETURN[TRUE];
ENDLOOP;
RETURN[FALSE];
};
AttachDict:
PUBLIC
PROC[dict, adict: Dict] = {
attach adict to dict
Generates AttachmentCycle
IF AttachmentPath[adict, dict] THEN ERROR Error[AttachmentCycle];
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
IF attach.first=adict THEN RETURN; -- already attached
ENDLOOP;
dict.attach ← CONS[adict, dict.attach];
};
DetachDict:
PUBLIC
PROC[dict, adict: Dict] = {
detach adict from dict
Generates NotAttached
prev: LIST OF Dict ← NIL;
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
IF attach.first=adict
THEN {
IF prev=NIL THEN dict.attach ← attach.rest
ELSE prev.rest ← attach.rest;
};
prev ← attach;
ENDLOOP;
ERROR Error[NotAttached]; -- didn't find it
};
DetachAll:
PUBLIC
PROC[dict: Dict] = {
Detaches all attached dictionaries
dict.attach ← NIL;
};
Begin:
PUBLIC
PROC[self: State, dict: Dict] = {
self.dictstk ← CONS[dict, self.dictstk];
};
End:
PUBLIC
PROC[self: State] = {
IF self.dictstk.rest=NIL THEN ERROR Error[DictionaryUnderflow]; -- don't pop .sysdict
self.dictstk ← self.dictstk.rest;
};
*** JaM INTRINSICS ***
PopKey:
PROC[self: State]
RETURNS[Any] =
INLINE {
x: Any = Pop[self];
RETURN[
WITH x
SELECT
FROM
x: ROPE => RopeToAtom[x], ENDCASE => x];
};
ApplyDict:
PUBLIC
PROC[self: State] = {
Expects opstk: (length hint)
Returns opstk: (new dictionary)
length: INT = PopInt[self];
PushDict[self, NewDict[length]];
};
ApplyKnown:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary, key)
Returns opstk: (boolean)
key: Any = PopKey[self];
dict: Dict = PopDict[self];
PushBool[self, Known[dict, key]];
};
ApplyWhere:
PUBLIC
PROC[self: State] = {
Expects opstk: (key),
dictstk: a dictionary stack
Returns opstk: (dictionary(iff key known), boolean("known"))
dictstk: unchanged
key: Any = PopKey[self];
known: BOOL; dict: Dict;
[known, dict] ← Where[self, key];
IF known THEN PushDict[self, dict];
PushBool[self, known];
};
ApplyGet:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary, key)
Returns opstk: (value looked up in dictionary)
key: Any = PopKey[self];
dict: Dict = PopDict[self];
Push[self, Get[dict, key]];
};
ApplyPut:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary, key, val)
Enters <key,val> into dictionary
Returns opstk: ()
No indication of whether an object with that key already existed.
val: Any = Pop[self];
key: Any = PopKey[self];
dict: Dict = PopDict[self];
Put[dict, key, val];
};
ApplyDef:
PUBLIC
PROC[self: State] = {
Expects opstk: (key, val), dictstk: (dictionary)
Enters <key,val> into dictionary
Returns opstk: (), dictstk: (dictionary)
No indication of whether an object with that key already existed.
val: Any = Pop[self];
key: Any = PopKey[self];
Def[self, key, val];
};
ApplyLoad:
PUBLIC
PROC[self: State] = {
Expects opstk: (key), dictstk: a dictionary stack
Returns opstk: (value looked up in highest dictionary having key in dictstk),
dictstk: unchanged
key: Any = PopKey[self];
Push[self, Load[self, key]];
};
ApplyStore:
PUBLIC
PROC[self: State] = {
Expects opstk: (key, val), dictstk: a dictionary stack
Enters <key,val> into highest dictionary having key in dictstk,
or into dict on top of dictstk
Returns opstk: (), dictstk: unchanged
val: Any = Pop[self];
key: Any = PopKey[self];
Store[self, key, val];
};
ApplyDel:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary, key)
Deletes object key from dictionary
Returns opstk: ()
key: Any = PopKey[self];
dict: Dict = PopDict[self];
Del[dict, key];
};
ApplyBegin:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary), dictstk: ()
Returns opstk: (), dictstk: (dictionary)
dict: Dict = PopDict[self];
Begin[self, dict];
};
ApplyEnd:
PUBLIC
PROC[self: State] = {
Expects dictstk: (dictionary)
Returns dictstk: ()
End[self];
};
ApplyDictForall:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary)(object)
For each tuple in dictionary put (key)(val) onto opstk and execute object
Returns opstk: ()
x: Any = Pop[self];
dict: Dict = PopDict[self];
action:
PROC[key: Any, val: Any]
RETURNS [quit:
BOOL] = {
Push[self, key];
Push[self, val];
Execute[self, x];
RETURN[FALSE];
};
[] ← DPairs[dict.impl, action];
};
ApplyCurDict:
PUBLIC
PROC[self: State] = {
Expects opstk: (), dictstk: (dictionary)
Returns opstk: (dictionary), dictstk: (dictionary)
PushDict[self, self.dictstk.first];
};
ApplyAttachDict:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary1) (dictionary2)
Returns opstk: ()
Generates AttachmentCycle
dict2: Dict = PopDict[self];
dict1: Dict = PopDict[self];
AttachDict[dict1, dict2];
};
ApplyDetachDict:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary1) (dictionary2)
detach dict2 from dict1
Returns opstk: ()
Generates NotAttached
dict2: Dict = PopDict[self];
dict1: Dict = PopDict[self];
DetachDict[dict1, dict2];
};
ApplyAttachedForall:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary1) (object)
For each dictionary2 attached to dictionary1
put dictionary2 onto opstk and execute object
Returns opstk: ()
x: Any = Pop[self];
dict: Dict = PopDict[self];
FOR attach:
LIST
OF Dict ← dict.attach, attach.rest
UNTIL attach=
NIL
DO
PushDict[self, attach.first];
Execute[self, x];
ENDLOOP;
};
ApplyDetachAll:
PUBLIC
PROC[self: State] = {
Expects opstk: (dictionary)
Detaches all attached dictionaries
Returns opstk: ()
dict: Dict = PopDict[self];
DetachAll[dict];
};
ApplyClrDictCache: PUBLIC PROC[self: State] = {
ClearCache[self.cache];
};
ApplyDictCacheStats: PUBLIC PROC[self: State] = {
cache: Cache ← self.cache;
PushInt[self, cache.clears];
PushInt[self, cache.probes];
PushInt[self, cache.hits];
};
ApplyResetDictCacheStats: PUBLIC PROC[self: State] = {
cache: Cache ← self.cache;
cache.clears ← cache.probes ← cache.hits ← 0;
};
END.