DIRECTORY GeneralRefTab, PrincOps USING [zXOR]; GeneralRefTabImpl: CEDAR MONITOR LOCKS x USING x: Ref EXPORTS GeneralRefTab = { OPEN GeneralRefTab; Munch: PRIVATE HashProc = TRUSTED MACHINE CODE { PrincOps.zXOR; }; DefaultHashProc: PUBLIC HashProc = {RETURN[Munch[key]]}; DefaultEqualProc: PUBLIC EqualProc = {RETURN [key1=key2]}; -- The vanilla equality Create: PUBLIC PROC [hashProc: HashProc _ DefaultHashProc, equalProc: EqualProc _ DefaultEqualProc, mod: SeqIndex _ 17] RETURNS [Ref] = { index: CARDINAL _ 0; data: REF Seq _ NIL; IF mod < 7 THEN mod _ 7; data _ NEW[Seq[mod]]; RETURN[NEW[RefTabRep _ [hashProc: NEW[HashProc _ hashProc], equalProc: NEW[EqualProc _ equalProc], mod: mod, size: 0, data: data]]]; }; GetSize: PUBLIC PROC [x: Ref] RETURNS [INT] = { RETURN [x.size]; }; Fetch: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [found: BOOL, val: Val] = { ENABLE UNWIND => NULL; hash: CARDINAL _ x.hashProc[key] MOD x.mod; node: Node _ x.data[hash]; WHILE node # NIL DO IF x.equalProc[key, node.key] THEN RETURN [TRUE, node.val]; node _ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; Replace: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: CARDINAL _ x.hashProc[key] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; WHILE node # NIL DO IF x.equalProc[key, node.key] THEN {node.val _ val; RETURN [TRUE]}; node _ node.next; ENDLOOP; RETURN [FALSE]; }; Store: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: CARDINAL _ x.hashProc[key] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; WHILE node # NIL DO IF x.equalProc[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]; }; Insert: PUBLIC ENTRY PROC [x: Ref, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: CARDINAL _ x.hashProc[key] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; WHILE node # NIL DO IF x.equalProc[key, node.key] THEN RETURN [FALSE]; node _ node.next; ENDLOOP; x.data[hash] _ NEW[NodeRep _ [key: key, val: val, next: head]]; x.size _ x.size + 1; RETURN [TRUE]; }; Delete: PUBLIC ENTRY PROC [x: Ref, key: Key] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: CARDINAL _ x.hashProc[key] MOD x.mod; node: Node _ x.data[hash]; head: Node _ node; lag: Node _ NIL; WHILE node # NIL DO IF x.equalProc[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]; }; Pairs: PUBLIC PROC [x: Ref, action: EachPairAction] RETURNS [quit: BOOL] = { node: Node _ NIL; index: CARDINAL _ 0; DO [node, index] _ GetNext[x, node, index]; IF node = NIL THEN RETURN [FALSE]; IF action[node.key, node.val] THEN RETURN [TRUE]; ENDLOOP; }; GetNext: 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]; }; }. VGeneralRefTabImpl.Mesa Implementation for generalized REF table abstraction, with the possibility to give the hash function and the equality function. Adapted from RefTabImpl.Mesa by Bertrand Serlet, June 3, 1985 6:08:45 pm PDT Last Edited by Bertrand Serlet, June 15, 1985 2:44:10 pm PDT Default hash and equality Public operations ΚΘ˜codešœ™Kšœ€™€KšœL™LKšœ<™<—K˜šΟk ˜ Kšœ˜Kšœ œ˜K˜—š œœœœœ˜5Kšœœ˜-K˜K™K˜š œœ œœœ˜0Kšœ˜Kšœ˜—K˜KšΟbœœ œ˜8K˜KšžœœœΟc˜RK™Kšœ™K˜šΟnœœœeœ ˜ŠKšœœ˜Kšœœœ˜Kšœ œ ˜Kšœœ ˜Kšœœœ"œ:˜„Kšœ˜K˜—š  œœœ œœ˜/Kšœ ˜Kšœ˜K˜—š  œœœœœ œ˜OKšœœœ˜Kšœœœ˜+K˜šœœ˜Kšœœœœ ˜;K˜Kšœ˜—Kšœœœ˜Kšœ˜K˜—š  œœ œœœ˜JKšœœœ˜Kšœœœ˜+K˜K˜šœœ˜Kšœœœœ˜CK˜Kšœ˜—Kšœœ˜Kšœ˜K˜—š  œœœœœœ˜HKšœœœ˜Kšœœœ˜+K˜K˜šœœ˜Kšœœœœ˜DK˜Kšœ˜—Kšœœ-˜?K˜Kšœœ˜Kšœ˜K˜—š  œœœœœœ˜IKšœœœ˜Kšœœœ˜+K˜K˜šœœ˜Kšœœœœ˜2K˜Kšœ˜—Kšœœ-˜?K˜Kšœœ˜Kšœ˜K˜—š  œœœœœœ˜?Kšœœœ˜Kšœœœ˜+K˜K˜Kšœ œ˜šœœ˜šœœ˜$Kšœœœœ˜EK˜Kšœœ˜—K˜ K˜Kšœ˜—Kšœœ˜Kšœ˜K˜—š  œœœ!œœ˜LKšœ œ˜Kšœœ˜š˜K˜(Kš œœœœœ˜"Kšœœœœ˜1Kšœ˜—Kšœ˜K˜—š  œœœœœœ˜VKšœœœ˜Kšœœ ˜šœœœ˜K˜Kšœœœœ˜(K˜Kšœ ˜—šœ ˜K˜Kšœœœœ˜-Kšœ˜Kšœ˜—Kšœœ˜K˜K˜—Kšœ˜K˜K˜K˜——…— ήό