<> <> <> <> <> <<>> < 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; <> 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] = { <> 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]}; <> DFetch: ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = { <> <> <> 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] = { <> <> 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] = { <> <> 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] = { <> <> 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] = { <> <> <> <> 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] = { < 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] = { <> <> 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] = { < 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] = { < into highest dictionary having key in dictstk,>> <> 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] = { <> <> IF NOT TryToDelete[dict, key] THEN ERROR Error[UndefinedKey]; }; AttachmentPath: PROC[dict1, dict2: Dict] RETURNS[BOOL] = { <> 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] = { <> <> 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] = { <> <> 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] = { <> 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] = { <> <> length: INT = PopInt[self]; PushDict[self, NewDict[length]]; }; ApplyKnown: PUBLIC PROC[self: State] = { <> <> key: Any = PopKey[self]; dict: Dict = PopDict[self]; PushBool[self, Known[dict, key]]; }; ApplyWhere: PUBLIC PROC[self: State] = { <> <> <> <> 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] = { <> <> key: Any = PopKey[self]; dict: Dict = PopDict[self]; Push[self, Get[dict, key]]; }; ApplyPut: PUBLIC PROC[self: State] = { <> < into dictionary>> <> <> val: Any = Pop[self]; key: Any = PopKey[self]; dict: Dict = PopDict[self]; Put[dict, key, val]; }; ApplyDef: PUBLIC PROC[self: State] = { <> < into dictionary>> <> <> val: Any = Pop[self]; key: Any = PopKey[self]; Def[self, key, val]; }; ApplyLoad: PUBLIC PROC[self: State] = { <> <> <> key: Any = PopKey[self]; Push[self, Load[self, key]]; }; ApplyStore: PUBLIC PROC[self: State] = { <> < into highest dictionary having key in dictstk,>> <> <> val: Any = Pop[self]; key: Any = PopKey[self]; Store[self, key, val]; }; ApplyDel: PUBLIC PROC[self: State] = { <> <> <> key: Any = PopKey[self]; dict: Dict = PopDict[self]; Del[dict, key]; }; ApplyBegin: PUBLIC PROC[self: State] = { <> <> dict: Dict = PopDict[self]; Begin[self, dict]; }; ApplyEnd: PUBLIC PROC[self: State] = { <> <> End[self]; }; ApplyDictForall: PUBLIC PROC[self: State] = { <> <> <> 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] = { <> <> PushDict[self, self.dictstk.first]; }; ApplyAttachDict: PUBLIC PROC[self: State] = { <> <> <> dict2: Dict = PopDict[self]; dict1: Dict = PopDict[self]; AttachDict[dict1, dict2]; }; ApplyDetachDict: PUBLIC PROC[self: State] = { <> <> <> <> dict2: Dict = PopDict[self]; dict1: Dict = PopDict[self]; DetachDict[dict1, dict2]; }; ApplyAttachedForall: PUBLIC PROC[self: State] = { <> <> <> <> 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] = { <> <> <> dict: Dict = PopDict[self]; DetachAll[dict]; }; <> <> <<};>> <<>> <> <> <> <> <> <<};>> <<>> <> <> <> <<};>> <<>> END.