DIRECTORY IntHashTable, Basics; IntHashTableImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Basics EXPORTS IntHashTable = { OPEN IntHashTable; Create: PUBLIC PROC [mod: SeqIndex ¬ 17] RETURNS [Table] = { mod ¬ MAX[mod, minMod]; RETURN [NEW [TableRec ¬ [ size: 0, sizeLimit: mod, inhibitCount: 0, data: NEW [Seq[mod]] ]]]; }; minMod: SeqIndex = 2; GetSize: PUBLIC PROC [table: Table] RETURNS [INT] = { RETURN [table.size]; }; Nicefy: PROC [key: INT32] RETURNS [CARD16] = TRUSTED INLINE { RETURN[ Basics.LowHalf[LOOPHOLE[key]] + Basics.HighHalf[LOOPHOLE[key]] ]; }; ComputeIndex: PROC [table: Table, key: Key] RETURNS [index: SeqIndex] = INLINE { index ¬ Nicefy[key] MOD table.data.max; }; Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, value: Value] = { ENABLE UNWIND => NULL; hash: SeqIndex ¬ ComputeIndex[table, key]; node: Node ¬ table.data[hash]; WHILE node # NIL DO IF key=node.key THEN RETURN [TRUE, node.value]; node ¬ node.next; ENDLOOP; RETURN [FALSE, NIL]; }; Replace: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex ¬ ComputeIndex[table, key]; node: Node ¬ table.data[hash]; WHILE node # NIL DO IF key=node.key THEN {node.value ¬ value; RETURN [TRUE]}; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Store: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex ¬ ComputeIndex[table, key]; node: Node ¬ table.data[hash]; WHILE node # NIL DO IF key=node.key THEN {node.value ¬ value; RETURN [FALSE]}; node ¬ node.next; ENDLOOP; table.data[hash] ¬ NEW[NodeRep ¬ [key: key, value: value, next: table.data[hash]]]; IF (table.size ¬ table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN ReHash[table]; RETURN [TRUE]; }; Insert: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex ¬ ComputeIndex[table, key]; node: Node ¬ table.data[hash]; WHILE node # NIL DO IF key=node.key THEN RETURN [FALSE]; node ¬ node.next; ENDLOOP; table.data[hash] ¬ NEW[NodeRep ¬ [key: key, value: value, next: table.data[hash]]]; IF (table.size ¬ table.size + 1) > table.sizeLimit AND table.inhibitCount = 0 THEN ReHash[table]; RETURN [TRUE]; }; Delete: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex ¬ ComputeIndex[table, key]; node: Node ¬ table.data[hash]; lag: Node ¬ NIL; WHILE node # NIL DO IF key=node.key THEN { IF lag = NIL THEN table.data[hash] ¬ node.next ELSE lag.next ¬ node.next; table.size ¬ table.size - 1; RETURN [TRUE]; }; lag ¬ node; node ¬ node.next; ENDLOOP; RETURN [FALSE]; }; Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = { node: Node ¬ NIL; DInhibit[table, +1]; {ENABLE UNWIND => DInhibit[table, -1]; index: CARDINAL ¬ table.data.max; DO [node, index] ¬ GetNext[table, node, index]; IF node = NIL THEN {quit ¬ FALSE; EXIT}; IF action[node.key, node.value] THEN {quit ¬ TRUE; EXIT}; ENDLOOP; }; DInhibit[table, -1]; }; DInhibit: ENTRY PROC [table: Table, D: INT] = { table.inhibitCount ¬ table.inhibitCount + D; WHILE table.inhibitCount = 0 AND table.size > table.sizeLimit DO ReHash[table] ENDLOOP; }; GetNext: ENTRY PROC [table: Table, node: Node, index: CARDINAL] RETURNS [Node, CARDINAL] = { ENABLE UNWIND => NULL; IF node # NIL THEN { node ¬ node.next; IF node # NIL THEN RETURN [node, index]; }; WHILE index > 0 DO index ¬ index - 1; node ¬ table.data[index]; IF node # NIL THEN RETURN [node, index]; ENDLOOP; RETURN [NIL, 0]; }; Erase: PUBLIC ENTRY PROC [table: Table] = { FOR i: CARDINAL IN [0..table.data.max) DO table.data[i] ¬ NIL ENDLOOP; table.size ¬ 0; }; ReHash: INTERNAL PROC [table: Table] = { oldData: REF Seq = table.data; newData: REF Seq; seek: CARDINAL = table.data.max * 2; newPTI, newMod: CARDINAL ¬ 0; IF primeTable[PrimeTableSize-1] > LAST[SeqIndex] THEN ERROR; FOR newPTI ¬ 0, newPTI+1 WHILE newPTI+1 < PrimeTableSize AND primeTable[newPTI] < seek DO NULL ENDLOOP; newMod ¬ primeTable[newPTI]; IF newMod = table.data.max THEN {table.sizeLimit ¬ LAST[INT]; RETURN}; table.sizeLimit ¬ newMod; table.data ¬ newData ¬ NEW [Seq[newMod]]; FOR i: NAT IN [0 .. oldData.max) DO next: Node ¬ NIL; FOR cur: Node ¬ oldData[i], next WHILE cur # NIL DO hash: SeqIndex ¬ ComputeIndex[table, cur.key]; next ¬ cur.next; cur.next ¬ newData[hash]; newData[hash] ¬ cur; ENDLOOP; IF next # NIL THEN ERROR; ENDLOOP; table ¬ table; }; PrimeTableSize: NAT = 14; primeTable: ARRAY [0 .. PrimeTableSize) OF CARDINAL = [ 00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, 32749]; }.  IntHashTableImpl.mesa Copyright Σ 1992 by Xerox Corporation. All rights reserved. Adapted from RefTabImpl.mesa by Bertrand Serlet, July 24, 1985 4:29:40 pm PDT Last Edited by Bertrand Serlet, August 12, 1985 7:06:47 pm PDT Last Edited by Widom, July 25, 1985 4:46:10 pm PDT Adapted from HashTableImpl.mesa by Mike Spreitzer, May 7, 1986 4:29:35 pm PDT Spreitzer, May 7, 1986 4:32:49 pm PDT Russ Atkinson (RRA) January 16, 1987 6:31:36 pm PST Ported by Bob Krivacic, December 4, 1989 10:37:18 am PST Public operations Κ₯–(cedarcode) style•NewlineDelimiter ˜codešœ™Kšœ Οeœ1™™>K™2K™MK™%K™3K™8—K˜šΟk œ˜K˜—š Οnœžœžœžœžœ ˜>Kšžœ˜Kšžœ˜Kšžœ˜—headšœ™šŸœžœžœžœ ˜=Kšœžœ˜šžœžœ˜Kšœ˜Kšœ˜K˜Kšœžœ ˜Kšœ˜—Kšœ˜—K˜K˜K˜š Ÿœžœžœžœžœ˜5Kšžœ˜Kšœ˜K˜—š Ÿœžœžœžœžœžœ˜=Kšžœžœžœ ˜IK˜K˜—šŸ œžœžœžœ˜PKšœžœ˜'K˜—K˜š Ÿœžœžœžœžœ žœ˜YKšžœžœžœ˜K˜*K˜šžœžœž˜Kšžœžœžœžœ˜/K˜Kšžœ˜—Kšžœžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ(žœžœ˜TKšžœžœžœ˜K˜*K˜šžœžœž˜Kšžœžœžœžœ˜9K˜Kšžœ˜—Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ(žœžœ˜RKšžœžœžœ˜K˜*K˜šžœžœž˜Kšžœžœžœžœ˜:K˜Kšžœ˜—Kšœžœ=˜SKšžœ1žœžœ˜aKšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœ(žœžœ˜SKšžœžœžœ˜K˜*K˜šžœžœž˜Kšžœžœžœžœ˜$K˜Kšžœ˜—Kšœžœ=˜SKšžœ1žœžœ˜aKšžœžœ˜Kšœ˜K˜—š Ÿœžœžœžœžœžœ˜EKšžœžœžœ˜K˜*K˜Kšœ žœ˜šžœžœž˜šžœžœ˜Kšžœžœžœžœ˜IK˜Kšžœžœ˜Kšœ˜—K˜ K˜Kšžœ˜—Kšžœžœ˜Kšœ˜K˜—š Ÿœžœžœ(žœžœ˜RKšœ žœ˜šΟgœ˜Kšœžœžœ œ˜&Kšœžœ˜!šž˜K˜,Kš žœžœžœ žœžœ˜(Kšžœžœ žœžœ˜9Kšžœ˜—K˜—Kš œ˜Kšœ˜K˜—š ΠgnŸœžœžœ œžœ˜/Kšœ* œ˜,Kšžœžœžœžœ˜WKšœ˜K˜—š Ÿœžœžœ#žœžœžœ˜\Kšžœžœžœ˜šžœžœžœ˜K˜Kšžœžœžœžœ˜(K˜—šžœ ž˜K˜K˜Kšžœžœžœžœ˜(Kšžœ˜—Kšžœžœ˜K˜K˜—šŸœžœžœžœ˜+Kš žœžœžœžœžœžœ˜FK˜Kšœ˜—K˜šŸœžœžœ˜(Kšœ žœ˜Kšœ žœ˜Kšœžœ˜$Kšœžœ˜Kšžœ žœ žœžœ˜