DIRECTORY HashTable, Rope, RopeHash, PrincOps USING [zXOR]; HashTableImpl: CEDAR MONITOR LOCKS table USING table: Table IMPORTS Rope, RopeHash EXPORTS HashTable = { OPEN HashTable; Munch: HashProc = TRUSTED MACHINE CODE { PrincOps.zXOR; }; Create: PUBLIC PROC [mod: SeqIndex _ 17, equal: EqualProc _ NIL, hash: HashProc _ NIL] RETURNS [Table] = { mod _ MAX[mod, minMod]; RETURN [NEW [TableRec _ [ hash: hash, equal: equal, size: 0, sizeLimit: mod, inhibitCount: 0, data: NEW [Seq[mod]] ]]]; }; minMod: SeqIndex = 2; RopeEqual: PUBLIC PROC [k1, k2: Key] RETURNS [eq: BOOL] = { r1: Rope.ROPE = NARROW[k1]; r2: Rope.ROPE = NARROW[k2]; eq _ r1.Equal[r2, TRUE]; }; RopeEqualModCase: PUBLIC PROC [k1, k2: Key] RETURNS [eq: BOOL] = { r1: Rope.ROPE = NARROW[k1]; r2: Rope.ROPE = NARROW[k2]; eq _ r1.Equal[r2, FALSE]; }; HashRope: PUBLIC PROC [k: Key] RETURNS [hash: CARDINAL] = { hash _ RopeHash.FromRope[NARROW[k], TRUE]; }; HashRopeModCase: PUBLIC PROC [k: Key] RETURNS [hash: CARDINAL] = { hash _ RopeHash.FromRope[NARROW[k], FALSE]; }; GetSize: PUBLIC PROC [table: Table] RETURNS [INT] = { RETURN [table.size]; }; ComputeIndex: PROC [table: Table, key: Key] RETURNS [index: SeqIndex] = INLINE { hash: CARDINAL _ IF table.hash=NIL THEN Munch[key] ELSE table.hash[key]; index _ hash 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 OR (table.equal#NIL AND table.equal[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 OR (table.equal#NIL AND table.equal[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 OR (table.equal#NIL AND table.equal[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 OR (table.equal#NIL AND table.equal[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 OR (table.equal#NIL AND table.equal[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]; }. $HashTableImpl.mesa 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 Spreitzer, November 18, 1985 3:32:23 pm PST Default hash Public operations Э╩ BЦ "cedar" styleШcodeЪЬЩKЪЬMЩMKЪЬ>Щ>KЩ2KЩ+ЧKШЪ╧k Ш KЪЬ Ш KЪЬШKШ KЪЬ ЭЬШKШЧЪ ЬЭЬЭЬЭЬЭЬ Ш;KЪЭЬШKЪЭЬШKЪЭЬШЧheadЪЬЩЪЬЭЬЭЬЭЬШ(KЪЬШKЪЬШЧЧЪЬЩЪ╧nЬЭЬЭЬ)ЭЬЭЬЭЬ ШkKЪЬЭЬШЪЭЬЭЬШKЪЬШKЪЬ Ш KЪЬШKЪЬШKШKЪЬЭЬШKЪЬШЧKЪЬШЧKШKШKШЪ Ю ЬЭЬЭЬЭЬЭЬШ;KЪЬ ЭЬЭЬШKЪЬ ЭЬЭЬШKЪЬЭЬШKШKШЧЪ ЮЬЭЬЭЬЭЬЭЬШBKЪЬ ЭЬЭЬШKЪЬ ЭЬЭЬШKЪЬЭЬШKШKШЧЪ ЮЬЭЬЭЬ ЭЬЭЬШ;KЪЬЭЬЭЬШ*KШKШЧЪ ЮЬЭЬЭЬ ЭЬЭЬШBKЪЬЭЬЭЬШ+KШKШЧЪ ЮЬЭЬЭЬЭЬЭЬШ5KЪЭЬШKЪЬШKШЧЪЮЬЭЬЭЬЭЬШPKЪЬЭЬЭЬЭЬЭЬЭЬШHKЪЬ ЭЬШ KШЧKШЪЮЬЭЬЭЬЭЬЭЬ ЭЬШYKЪЭЬЭЬЭЬШKЪЬ*Ш*KЪЬШЪЭЬЭЬЭШЪЭЬЭЬЭЬЭЬШDKЪЭЬЭЬЭЬШЧKШKЪЭЬШЧKЪЭЬЭЬЭЬШKЪЬШKШЧЪЮЬЭЬЭЬЭЬ(ЭЬЭЬШTKЪЭЬЭЬЭЬШKЪЬ*Ш*KЪЬШЪЭЬЭЬЭШЪЭЬЭЬЭЬЭЬШDKЪЭЬЭЬЭЬШ)ЧKШKЪЭЬШЧKЪЭЬЭЬШKЪЬШKШЧЪЮЬЭЬЭЬЭЬ(ЭЬЭЬШRKЪЭЬЭЬЭЬШKЪЬ*Ш*KЪЬШЪЭЬЭЬЭШЪЭЬЭЬЭЬЭЬШDKЪЭЬЭЬЭЬШ*ЧKШKЪЭЬШЧKЪЬЭЬ=ШSKЪЭЬ1ЭЬЭЬШaKЪЭЬЭЬШKЪЬШKШЧЪЮЬЭЬЭЬЭЬ(ЭЬЭЬШSKЪЭЬЭЬЭЬШKЪЬ*Ш*KЪЬШЪЭЬЭЬЭШЪЭЬЭЬЭЬЭЬШDKЪЭЬЭЬЭЬШЧKШKЪЭЬШЧKЪЬЭЬ=ШSKЪЭЬ1ЭЬЭЬШaKЪЭЬЭЬШKЪЬШKШЧЪЮЬЭЬЭЬЭЬЭЬЭЬШEKЪЭЬЭЬЭЬШKЪЬ*Ш*KЪЬШKЪЬЭЬШЪЭЬЭЬЭШЪ ЭЬЭЬЭЬЭЬЭЬШJKЪЭЬЭЬЭЬЭЬШ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ЪЭЬ ЭЬЭЬЭЬШ