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] = { 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] = { 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] = { 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; }; 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] = { val: Any = Pop[self]; key: Any = PopKey[self]; dict: Dict = PopDict[self]; Put[dict, key, val]; }; ApplyDef: PUBLIC PROC[self: State] = { 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] = { 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. ςJaMDictImpl.mesa Copyright c 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 tuples, in which both key and value are Objects (Any); key is not necessarily a string. Types and constants creates new table with suggested hash size 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 stores new key-value pair, overwriting previous value for given key returns TRUE if new value, FALSE if previous value overwritten looks up key, overwriting previous value iff key is found returns TRUE if value was replaced, FALSE if not deletes key-value pair associated with given key returns TRUE if deletion actually occurred, FALSE if no such key 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 Enters into dict iff key is already defined Return value looked up in highest dictionary having key in dictstk, searching attached dictionaries if necessary Enters into dictionary on top of dictstk, Enters into highest dictionary having key in dictstk, or into dict on top of dictstk if key not found. Deletes object key from dictionary Generates UndefinedKey if object not found: returns TRUE iff there is an attachment path from dict1 to dict2 attach adict to dict Generates AttachmentCycle detach adict from dict Generates NotAttached Detaches all attached dictionaries *** JaM INTRINSICS *** Expects opstk: (length hint) Returns opstk: (new dictionary) Expects opstk: (dictionary, key) Returns opstk: (boolean) Expects opstk: (key), dictstk: a dictionary stack Returns opstk: (dictionary(iff key known), boolean("known")) dictstk: unchanged Expects opstk: (dictionary, key) Returns opstk: (value looked up in dictionary) Expects opstk: (dictionary, key, val) Enters into dictionary Returns opstk: () No indication of whether an object with that key already existed. Expects opstk: (key, val), dictstk: (dictionary) Enters into dictionary Returns opstk: (), dictstk: (dictionary) No indication of whether an object with that key already existed. Expects opstk: (key), dictstk: a dictionary stack Returns opstk: (value looked up in highest dictionary having key in dictstk), dictstk: unchanged Expects opstk: (key, val), dictstk: a dictionary stack Enters into highest dictionary having key in dictstk, or into dict on top of dictstk Returns opstk: (), dictstk: unchanged Expects opstk: (dictionary, key) Deletes object key from dictionary Returns opstk: () Expects opstk: (dictionary), dictstk: () Returns opstk: (), dictstk: (dictionary) Expects dictstk: (dictionary) Returns dictstk: () Expects opstk: (dictionary)(object) For each tuple in dictionary put (key)(val) onto opstk and execute object Returns opstk: () Expects opstk: (), dictstk: (dictionary) Returns opstk: (dictionary), dictstk: (dictionary) Expects opstk: (dictionary1) (dictionary2) Returns opstk: () Generates AttachmentCycle Expects opstk: (dictionary1) (dictionary2) detach dict2 from dict1 Returns opstk: () Generates NotAttached Expects opstk: (dictionary1) (object) For each dictionary2 attached to dictionary1 put dictionary2 onto opstk and execute object Returns opstk: () Expects opstk: (dictionary) Detaches all attached dictionaries Returns opstk: () 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; }; Κύ˜codešœ™Kšœ Οmœ1™K˜š Οnœžœžœžœžœ˜9Kšœžœžœ˜šžœžœž˜Kšœžœ žœ˜*Kš œžœžœ žœžœ˜(Kšœžœžœ žœ˜#Kšžœ žœ˜ —Kšžœžœžœžœ˜=K˜—K˜š œžœžœžœ ˜3Kšœ*™*Kšžœ žœ ˜Kšžœ žœ ˜Kšžœžœ)žœ˜HK˜K˜—š  œžœ žœžœžœžœ ˜CKšœ*™*K˜—š  œžœžœžœ žœ˜IKšœ8™8Kšœ8™8Kšœ™Kšžœžœžœ˜Kšœžœ˜"K˜šžœžœž˜K˜Kšžœžœžœžœ ˜2K˜Kšžœ˜—Kšžœžœžœ˜K˜K˜—š  œžœžœžœžœ˜BKšœC™CKšœ>™>Kšžœžœžœ˜Kšœžœ˜"K˜K˜šžœžœž˜K˜Kšžœžœžœžœ˜;K˜Kšžœ˜—Kšœžœ-˜?K˜Kšžœžœ˜K˜K˜—š  œžœžœžœžœ˜DKšœ9™9Kšœ0™0Kšžœžœžœ˜Kšœžœ˜"K˜K˜šžœžœž˜K˜Kšžœžœžœžœ˜:K˜Kšžœ˜—Kšžœžœ˜K˜K˜—š  œžœžœžœžœ˜9Kšœ0™0Kšœ@™@Kšžœžœžœ˜Kšœžœ˜"K˜K˜Kšœ žœ˜šžœžœž˜K˜šžœžœ˜Kšžœžœžœžœ˜EKšœžœžœ˜$—K˜ K˜Kšžœ˜—Kšžœžœ˜K˜K˜—š œžœžœ žœžœžœžœ˜TKšœ?™?Kšœ@™@KšœF™FKšœ(™(Kšœ žœ˜Kšœžœ˜š  œžœžœžœžœžœ˜SKšžœžœžœ˜Kšœžœ ˜šžœžœžœ˜K˜Kšžœžœžœžœ˜(K˜Kšžœ ˜—šžœ ž˜K˜Kšžœžœžœžœ˜-Kšžœ˜Kšžœ˜—Kšžœžœ˜K˜—šž˜K˜%Kš žœžœžœžœžœ˜"Kšžœžœžœžœ˜1Kšžœ˜—K˜K˜—K˜š  œžœžœ žœžœ ˜3š žœžœžœžœž˜$Kšžœžœ*žœ˜:—Kšžœžœ˜K˜K˜—š   œžœžœ žœžœ˜4Kšžœ˜K˜K˜—š  œžœžœžœžœ˜NK˜&Kšžœžœžœ˜š žœ žœžœ!žœžœž˜GK˜K˜$Kšžœžœžœ˜Kšžœ˜—Kšžœžœžœ˜K˜—K˜š  œžœ!žœžœ˜DKšœ5™5Kšžœžœžœžœ˜3š žœ žœžœ!žœžœž˜GK˜Kšžœžœžœžœ˜3Kšžœ˜—Kšžœžœ˜K˜K˜—š  œžœžœžœ˜9Kšžœžœžœžœ˜-š žœ žœžœ!žœžœž˜GK˜Kšžœžœžœžœ˜-Kšžœ˜—Kšžœžœ˜K˜K˜—š   œžœžœžœžœ˜PKšœC™CKšœ,™,š žœžœžœ!žœžœž˜EK˜K˜#Kšžœžœžœ˜Kšžœ˜—Kšžœžœžœ˜K˜K˜—š œžœžœžœ˜FKšžœžœžœžœ˜8š žœ žœžœ!žœžœž˜GK˜Kšœ"˜"Kšžœžœžœ˜Kšžœ˜—Kšžœžœžœ˜K˜—K˜š  œžœžœžœžœ˜:Kšžœ˜"K˜K˜—š  œžœžœžœžœ˜Oš žœžœžœ!žœžœž˜EK˜K˜!Kšžœžœžœ˜Kšžœ˜—Kšžœžœžœ˜K˜K˜—š œžœžœžœ ˜7Kšœžœ/˜:Kš žœžœžœžœžœ˜9K˜K˜—š œžœžœ$˜4K˜!K˜K˜—š œžœžœ%˜5Kšœ3™3K˜ K˜K˜K˜—š œžœžœžœ ˜9Kšœžœ0˜;Kš žœžœžœžœžœ˜9K˜K˜—š œžœžœ%˜7Kšœ?™?Kšœ0™0š žœžœžœ!žœžœž˜EK˜Kšžœžœžœ˜,Kšžœ˜—K˜K˜K˜—š œžœžœ˜*Kšœ"™"Kšœ+™+Kšžœžœžœžœ˜=K˜K˜—š œžœžœžœ˜:Kšœ@™@Kšžœžœžœžœ˜#š žœ žœžœ"žœžœž˜HK˜Kšžœžœžœžœ˜2Kšžœ˜—Kšžœžœ˜K˜K˜—š  œžœžœ˜.Kšœ™Kšœ™Kšžœžœžœ˜Aš žœ žœžœ!žœžœž˜GKšžœžœžœΟc˜6Kšžœ˜—Kšœžœ˜'K˜K˜—š  œžœžœ˜.Kšœ™Kšœ™Kšœžœžœžœ˜š žœ žœžœ!žœžœž˜Gšžœžœ˜Kšžœžœžœ˜*Kšžœ˜K˜—K˜Kšžœ˜—Kšžœ‘˜+K˜K˜—š  œžœžœ˜&Kšœ"™"Kšœžœ˜K˜K˜—š œžœžœ˜/Kšœžœ˜(K˜K˜—š œžœžœ˜!Kš žœžœžœžœ‘˜UK˜!K˜K˜—Kšœ™K˜š œžœžœžœ˜1Kšœ˜šžœžœžœž˜Kšœžœžœ˜(—K˜—K˜š  œžœžœ˜'Kšœ™Kšœ™Kšœžœ˜K˜ K˜K˜—š  œžœžœ˜(Kšœ ™ Kšœ™Kšœ˜K˜K˜!K˜K˜—š  œžœžœ˜(Kšœ™Kšœ™Kšœ<™