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 SymTabRep; SymTabRep: 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[SymTabRep _ [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 _ [tab: Create[length], attach: NIL]]] ELSE ERROR Error[BoundsFault]; }; DictLength: PUBLIC PROC[dict: Dict] RETURNS[INT] = { RETURN[DSize[dict.tab]]; }; TryToGet: PUBLIC PROC[dict: Dict, key: Any] RETURNS[found: BOOL, val: Any] = { [found, val] _ DFetch[dict.tab, 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.tab, 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.tab, 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.tab, 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.tab, 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.tab, 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. nJaMDictImpl.mesa Administers JaM dictionaries A Dictionary is a set of tuples, in which both key and value are Objects (key is not necessarily a string) Present implementation: Dictionary is allocated as a contiguous vector of tuples Hash coding is used to access tuples Dictionary stack is cached with single level cache. Last edited by: Original version by Martin Newell, January 1979 Bill Paxton, 29-Jan-82 15:44:13 Doug Wyatt, November 21, 1983 1:08 pm 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; }; Ê5˜Jšœ™J™šœ™JšœH™HJšœ-™-Jšœ™JšœH™HJšœ$™$Jšœ3™3—J™™Jšœ/™/Jšœ™Jšœ%™%—J˜šÏk ˜ Jšœœ ˜JšœœZœ˜|Jšœœ˜J˜—Jš œ œœœœ˜/Jšœ ˜Jšœ˜Jšœœœ˜J˜Jšœ™J˜Jšœœœ ˜Jš œ œœ œœ œ˜KJšœ œ˜Jšœœœ ˜Jšœ œœ"˜8Jšœœœ ˜Jš œ œœœœœ˜>J˜š Ïnœœœœœ˜9Jšœœœ˜šœœ˜Jšœœ œ˜*Jš œœœ œœ˜(Jšœœœ œ˜#Jšœ œ˜ —Jšœœœœ˜=J˜—J˜šžœœœœ ˜3Jšœ*™*Jšœ œ ˜Jšœ œ ˜Jšœœ'œ˜FJ˜J˜—š žœœ œœœœ ˜CJšœ*™*J˜—š žœœœœ œ˜IJšœ8™8Jšœ8™8Jšœ™Jšœœœ˜Jšœœ˜"J˜šœœ˜J˜Jšœœœœ ˜2J˜Jšœ˜—Jšœœœ˜J˜J˜—š žœœœœœ˜BJšœC™CJšœ>™>Jšœœœ˜Jšœœ˜"J˜J˜šœœ˜J˜Jšœœœœ˜;J˜Jšœ˜—Jšœœ-˜?J˜Jšœœ˜J˜J˜—š žœœœœœ˜DJšœ9™9Jšœ0™0Jšœœœ˜Jšœœ˜"J˜J˜šœœ˜J˜Jšœœœœ˜:J˜Jšœ˜—Jšœœ˜J˜J˜—š žœœœœœ˜9Jšœ0™0Jšœ@™@Jšœœœ˜Jšœœ˜"J˜J˜Jšœ œ˜šœœ˜J˜šœœ˜Jšœœœœ˜EJšœœœ˜$—J˜ J˜Jšœ˜—Jšœœ˜J˜J˜—šžœœœ œœœœ˜TJšœ?™?Jšœ@™@JšœF™FJšœ(™(Jšœ œ˜Jšœœ˜š žœœœœœœ˜SJšœœœ˜Jšœœ ˜šœœœ˜J˜Jšœœœœ˜(J˜Jšœ ˜—šœ ˜J˜Jšœœœœ˜-Jšœ˜Jšœ˜—Jšœœ˜J˜—š˜J˜%Jš œœœœœ˜"Jšœœœœ˜1Jšœ˜—J˜J˜—J˜š žœœœ œœ ˜3š œœœœ˜$Jšœœ)œ˜9—Jšœœ˜J˜J˜—š ž œœœ œœ˜4Jšœ˜J˜J˜—š žœœœœœ˜NJ˜%Jšœœœ˜š œ œœ!œœ˜GJ˜J˜$Jšœœœ˜Jšœ˜—Jšœœœ˜J˜—J˜šž œœ!œœ˜DJšœ5™5Jšœœœœ˜2š œ œœ!œœ˜GJ˜Jšœœœœ˜3Jšœ˜—Jšœœ˜J˜J˜—šž œœœœ˜9Jšœœœœ˜,š œ œœ!œœ˜GJ˜Jšœœœœ˜-Jšœ˜—Jšœœ˜J˜J˜—š ž œœœœœ˜PJšœC™CJšœ,™,š œœœ!œœ˜EJ˜J˜#Jšœœœ˜Jšœ˜—Jšœœœ˜J˜J˜—šžœœœœ˜FJšœœœœ˜7š œ œœ!œœ˜GJ˜Jšœ"˜"Jšœœœ˜Jšœ˜—Jšœœœ˜J˜—J˜š žœœœœœ˜:Jšœ˜"J˜J˜—š žœœœœœ˜Oš œœœ!œœ˜EJ˜J˜!Jšœœœ˜Jšœ˜—Jšœœœ˜J˜J˜—šžœœœœ ˜7Jšœœ/˜:Jš œœœœœ˜9J˜J˜—šžœœœ$˜4J˜ J˜J˜—šžœœœ%˜5Jšœ3™3J˜ J˜J˜J˜—šžœœœœ ˜9Jšœœ0˜;Jš œœœœœ˜9J˜J˜—šžœœœ%˜7Jšœ?™?Jšœ0™0š œœœ!œœ˜EJ˜Jšœœœ˜,Jšœ˜—J˜J˜J˜—šžœœœ˜*Jšœ"™"Jšœ+™+Jšœœœœ˜=J˜J˜—šžœœœœ˜:Jšœ@™@Jšœœœœ˜#š œ œœ"œœ˜HJ˜Jšœœœœ˜2Jšœ˜—Jšœœ˜J˜J˜—šž œœœ˜.Jšœ™Jšœ™Jšœœœ˜Aš œ œœ!œœ˜GJšœœœÏc˜6Jšœ˜—Jšœœ˜'J˜J˜—šž œœœ˜.Jšœ™Jšœ™Jšœœœœ˜š œ œœ!œœ˜Gšœœ˜Jšœœœ˜*Jšœ˜J˜—J˜Jšœ˜—JšœŸ˜+J˜J˜—šž œœœ˜&Jšœ"™"Jšœœ˜J˜J˜—šžœœœ˜/Jšœœ˜(J˜J˜—šžœœœ˜!Jš œœœœŸ˜UJ˜!J˜J˜—Jšœ™J˜šžœœœœ˜1Jšœ˜šœœœ˜Jšœœœ˜(—J˜—J˜šž œœœ˜'Jšœ™Jšœ™Jšœœ˜J˜ J˜J˜—šž œœœ˜(Jšœ ™ Jšœ™Jšœ˜J˜J˜!J˜J˜—šž œœœ˜(Jšœ™Jšœ™Jšœ<™