DIRECTORY IntToIntTab; IntToIntTabImpl: CEDAR MONITOR LOCKS table USING table: Table EXPORTS IntToIntTab = BEGIN OPEN IntToIntTab; Impl: TYPE ~ REF IntToIntTabImplRep; IntToIntTabImplRep: PUBLIC TYPE = RECORD [ size, sizeLimit, inhibitCount: INT, data: REF Seq ]; SeqIndex: TYPE = NAT; Seq: TYPE = RECORD [nodes: SEQUENCE max: SeqIndex OF Node]; Node: TYPE = REF NodeRep; NodeRep: TYPE = RECORD [key: Key, val: Val, next: Node]; minMod: SeqIndex = 2; Create: PUBLIC PROC [mod: SeqIndex ¬ 17] RETURNS [Table] = { seqLen: SeqIndex ~ MAX[mod, minMod]; impl: Impl ~ NEW [IntToIntTabImplRep ¬ [ size: 0, sizeLimit: seqLen, inhibitCount: 0, data: NEW [Seq[seqLen]] ]]; RETURN [NEW [IntToIntTabRep ¬ [impl: impl]]]; }; GetSize: PUBLIC ENTRY PROC [table: Table] RETURNS [INT] = { impl: Impl ~ table.impl; RETURN [impl.size]; }; Nicefy: PROC [key: INT32] RETURNS [CARD32] = INLINE { RETURN [ LOOPHOLE[key] ] }; ComputeIndex: PROC [impl: Impl, key: Key] RETURNS [index: SeqIndex] = INLINE { index ¬ Nicefy[key] MOD impl.data.max; }; Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, val: Val] = { impl: Impl ~ table.impl; hash: SeqIndex ¬ ComputeIndex[impl, key]; node: Node ¬ impl.data[hash]; WHILE node # NIL DO IF key=node.key THEN RETURN [TRUE, node.val]; node ¬ node.next; ENDLOOP; RETURN [FALSE, -1]; }; Replace: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = { impl: Impl ~ table.impl; hash: SeqIndex ¬ ComputeIndex[impl, key]; node: Node ¬ impl.data[hash]; WHILE node # NIL DO IF key=node.key THEN {node.val ¬ val; RETURN [TRUE]}; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Store: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = { impl: Impl ~ table.impl; hash: SeqIndex ¬ ComputeIndex[impl, key]; node: Node ¬ impl.data[hash]; WHILE node # NIL DO IF key=node.key THEN {node.val ¬ val; RETURN [FALSE]}; node ¬ node.next; ENDLOOP; impl.data[hash] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[hash]]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; RETURN [TRUE]; }; Insert: PUBLIC ENTRY PROC [table: Table, key: Key, val: Val] RETURNS [BOOL] = { ENABLE UNWIND => NULL; impl: Impl ~ table.impl; hash: SeqIndex ¬ ComputeIndex[impl, key]; node: Node ¬ impl.data[hash]; WHILE node # NIL DO IF key=node.key THEN RETURN [FALSE]; node ¬ node.next; ENDLOOP; impl.data[hash] ¬ NEW[NodeRep ¬ [key: key, val: val, next: impl.data[hash]]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; RETURN [TRUE]; }; Delete: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [BOOL] = { impl: Impl ~ table.impl; hash: SeqIndex ¬ ComputeIndex[impl, key]; node: Node ¬ impl.data[hash]; lag: Node ¬ NIL; WHILE node # NIL DO IF key=node.key THEN { IF lag = NIL THEN impl.data[hash] ¬ node.next ELSE lag.next ¬ node.next; impl.size ¬ impl.size - 1; RETURN [TRUE]; }; lag ¬ node; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Erase: PUBLIC ENTRY PROC [table: Table] = { impl: Impl ~ table.impl; FOR i: SeqIndex IN [0..impl.data.max) DO impl.data[i] ¬ NIL ENDLOOP; impl.size ¬ 0; }; Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = { Inhibit: ENTRY PROC [table: Table] ~ { impl: Impl ~ table.impl; impl.inhibitCount ¬ impl.inhibitCount + 1; }; Release: ENTRY PROC [table: Table] ~ { impl: Impl ~ table.impl; impl.inhibitCount ¬ impl.inhibitCount - 1; IF impl.inhibitCount#0 THEN RETURN; WHILE impl.size > impl.sizeLimit DO ReHash[impl] ENDLOOP; }; Enumerate: PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL ¬ FALSE] ~ { node: Node ¬ NIL; index: CARDINAL ¬ 0; DO [node, index] ¬ GetNext[table, node, index]; IF node = NIL THEN EXIT; IF action[node.key, node.val] THEN RETURN [TRUE]; ENDLOOP; }; Inhibit[table]; quit ¬ Enumerate[table, action ! UNWIND => Release[table]]; Release[table]; }; GetNext: ENTRY PROC [table: Table, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = { impl: Impl ~ table.impl; IF node = NIL THEN index ¬ impl.data.max ELSE { node ¬ node.next; IF node # NIL THEN RETURN [node, index]; }; WHILE index > 0 DO index ¬ index - 1; node ¬ impl.data[index]; IF node # NIL THEN RETURN [node, index]; ENDLOOP; RETURN [NIL, 0]; }; Update: PUBLIC ENTRY PROC [table: Table, key: Key, action: UpdateAction] = { ENABLE UNWIND => NULL; --necessary: calls client procedure IF action # NIL THEN { impl: Impl ~ table.impl; index: SeqIndex ¬ ComputeIndex[impl, key]; head: Node ¬ impl.data[index]; node: Node ¬ head; lag: Node ¬ NIL; op: UpdateOperation ¬ none; val: Val; WHILE node # NIL DO next: Node ¬ node.next; IF key=node.key THEN { [op, val] ¬ action[TRUE, node.val]; SELECT op FROM delete => IF lag = NIL THEN impl.data[index] ¬ next ELSE lag.next ¬ next; store => node.val ¬ val; ENDCASE; RETURN; }; lag ¬ node; node ¬ next; ENDLOOP; [op, val] ¬ action[FALSE, -1]; SELECT op FROM store => { impl.data[index] ¬ NEW[NodeRep ¬ [key: key, val: val, next: head]]; IF (impl.size ¬ impl.size + 1) > impl.sizeLimit AND impl.inhibitCount = 0 THEN ReHash[impl]; }; ENDCASE; }; }; Copy: PUBLIC ENTRY PROC [table: Table] RETURNS [Table] = { impl: Impl = table.impl; oldData: REF Seq = impl.data; max: CARDINAL = oldData.max; newImpl: Impl = NEW[IntToIntTabImplRep ¬ impl­]; newData: REF Seq = NEW[Seq[max]]; -- note, all buckets initially NIL newImpl.data ¬ newData; FOR i: NAT IN [0..max) DO oldChain: Node ¬ oldData[i]; IF oldChain # NIL THEN { newTail: Node ¬ NIL; WHILE oldChain # NIL DO new: Node ¬ NEW[NodeRep ¬ [key: oldChain.key, val: oldChain.val, next: NIL]]; IF newTail = NIL THEN newData[i] ¬ new ELSE newTail.next ¬ new; newTail ¬ new; oldChain ¬ oldChain.next; ENDLOOP; }; ENDLOOP; RETURN [NEW[IntToIntTabRep ¬ [impl: newImpl]]]; }; ReHash: INTERNAL PROC [impl: Impl] = { oldData: REF Seq = impl.data; newData: REF Seq; seek: CARDINAL = impl.data.max * 2; newPTI: CARDINAL ¬ 0; newMod: CARDINAL ¬ highPrime; IF seek >= highPrime THEN newPTI ¬ primeTableSize-1 ELSE DO newMod ¬ primeTable[newPTI]; IF newMod >= seek THEN EXIT; newPTI ¬ newPTI+1; ENDLOOP; IF newMod = impl.data.max THEN {impl.sizeLimit ¬ LAST[INT]; RETURN}; impl.sizeLimit ¬ newMod; impl.data ¬ newData ¬ NEW[Seq[newMod]]; FOR i: SeqIndex IN [0 .. oldData.max) DO next: Node ¬ NIL; FOR cur: Node ¬ oldData[i], next WHILE cur # NIL DO hash: SeqIndex ¬ ComputeIndex[impl, cur.key]; next ¬ cur.next; cur.next ¬ newData[hash]; newData[hash] ¬ cur; ENDLOOP; IF next # NIL THEN ERROR; ENDLOOP; }; primeTableSize: NAT = 14; highPrime: CARDINAL[0..LAST[SeqIndex]] = 32749; primeTable: ARRAY [0 .. primeTableSize) OF CARDINAL = [ 00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, highPrime]; END.  IntToIntTabImpl.mesa Copyright Σ 1987, 1988, 1990, 1991 by Xerox Corporation. All rights reserved. Adapted from similar package by Christian Jacobi, May 13, 1987 10:43:20 am PDT Christian Jacobi, July 19, 1990 12:43 pm PDT ENABLE UNWIND => NULL; --for 32 bit machine CARD32 is good operand for MOD operation ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; ENABLE UNWIND => NULL; Κ —–(cedarcode) style•NewlineDelimiter ™codešœ™Kšœ ΟeœC™NKšœN™NKšœ,™,—K˜šΟk œ˜ Kšœ ˜ K˜—š Οnœžœžœžœžœ ˜=Kšžœ˜—šžœ˜Kšžœ ˜—˜Kšœžœžœ˜$šœžœžœžœ˜*Kšœžœ˜#Kšœžœ˜ Kšœ˜—K˜Kšœ žœžœ˜Kš œžœžœ žœžœ˜;K˜Kšœžœžœ ˜Kšœ žœžœ"˜8K˜K˜K˜—šŸœžœžœžœ ˜=Kšœžœ˜$šœ žœ˜(Kšœ,˜,Kšœžœ˜Kšœ˜—Kšžœžœ"˜-Kšœ˜K˜—š Ÿœžœžœžœžœžœ˜;Kšžœžœžœ™Kšœ˜Kšžœ ˜Kšœ˜K˜—š Ÿœžœžœžœžœžœ˜5Jšœ=™=Kšžœžœ˜K˜K˜—šŸ œžœžœžœ˜NKšœžœ˜&K˜K˜—š Ÿœžœžœžœžœ žœ˜UKšžœžœžœ™Kšœ˜Kšœ)˜)Kšœ˜šžœžœž˜Kšžœžœžœžœ ˜-K˜Kšžœ˜—Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ$žœžœ˜PKšžœžœžœ™Kšœ˜Kšœ)˜)Kšœ˜šžœžœž˜Kšžœžœžœžœ˜5K˜Kšžœ˜—Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ$žœžœ˜NKšžœžœžœ™Kšœ˜Kšœ)˜)Kšœ˜šžœžœž˜Kšžœžœžœžœ˜6K˜Kšžœ˜—Kšœžœ8˜MKšžœ.žœžœ˜\Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ$žœžœ˜OKšžœžœžœ˜Kšœ˜Kšœ)˜)Kšœ˜šžœžœž˜Kšžœžœžœžœ˜$K˜Kšžœ˜—Kšœžœ8˜MKšžœ.žœžœ˜\Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœžœžœ˜EKšžœžœžœ™Kšœ˜Kšœ)˜)Kšœ˜Kšœ žœ˜šžœžœž˜šžœžœ˜Kšžœžœžœžœ˜HKšœ˜Kšžœžœ˜Kšœ˜—K˜ K˜Kšžœ˜—Kšžœžœ˜Kšœ˜K˜—šŸœžœžœžœ˜+Kšžœžœžœ™Kšœ˜Kš žœ žœžœžœžœ˜DKšœ˜Kšœ˜K˜—š Ÿœžœžœ(žœžœ˜RšŸœžœžœ˜&Kšžœžœžœ™Kšœ˜Kšœ*˜*K˜—šŸœžœžœ˜&Kšžœžœžœ™Kšœ˜Kšœ*˜*Kšžœžœžœ˜#Kšžœžœžœ˜9K˜—š Ÿ œžœ(žœžœžœ˜WKšœ žœ˜Kšœžœ˜šž˜Kšœ,˜,Kšžœžœžœžœ˜Kšžœžœžœžœ˜1Kšžœ˜—K˜—Kšœ˜Kšœ!žœ˜;Kšœ˜Kšœ˜K˜—š Ÿœžœžœ#žœžœžœ˜\Kšžœžœžœ™Kšœ˜šžœž˜ Kšžœ˜šžœ˜K˜Kšžœžœžœžœ˜(K˜——šžœ ž˜Kšœ˜Kšœ˜Kšžœžœžœžœ˜(Kšžœ˜—Kšžœžœ˜K˜K˜—šŸœžœžœžœ3˜LKšžœžœžœΟc#˜:šžœ žœžœ˜Kšœ˜Kšœ*˜*Kšœ˜Kšœ˜Kšœ žœ˜Kšœ˜Kšœ ˜ šžœžœž˜Kšœ˜šžœžœ˜Kšœžœ ˜#šžœž˜Kš œ žœžœžœžœ˜IKšœ˜Kšžœ˜—Kšžœ˜K˜—K˜ Kšœ ˜ Kšžœ˜—Kšœžœ˜šžœž˜šœ ˜ Kšœžœ-˜Cšžœ.žœž˜NKšœ ˜ —Kšœ˜—Kšžœ˜—K˜—K˜K˜—š Ÿœžœžœžœžœ ˜:Kšžœžœžœ™Kšœ˜Kšœ žœ˜Kšœžœ˜Kšœžœ˜0Kšœ žœžœ  "˜EKšœ˜šžœžœžœ ž˜Kšœ˜šžœ žœžœ˜Kšœžœ˜šžœ žœž˜Kšœ žœ8žœ˜MKšžœ žœžœžœ˜?Kšœ˜Kšœ˜Kšžœ˜—K˜—Kšžœ˜—Kšžœžœ$˜/K˜K™—šŸœžœžœ˜&Kšœ žœ˜Kšœ žœ˜Kšœžœ˜#Kšœžœ˜Kšœžœ ˜šžœ˜Kšžœ˜šžœž˜Kšœ˜Kšžœžœžœ˜Kšœ˜Kšžœ˜——Kš žœžœžœžœžœ˜DKšœ˜Kšœžœ˜'šžœ žœž˜(Kšœ žœ˜šžœžœžœž˜3Kšœ-˜-K˜K˜K˜Kšžœ˜—Kšžœžœžœžœ˜Kšžœ˜—K˜—˜Kšœžœ˜Kšœ žœžœ˜/šœ žœžœžœ˜7Kšœs˜s——Kšžœ˜K˜˜K˜——…—V'ω