<> <> <> <> <> <> DIRECTORY IntChainedHashTable; IntChainedHashTableImpl: CEDAR MONITOR LOCKS table USING table: Table EXPORTS IntChainedHashTable = { OPEN IntChainedHashTable; <> Stuck: PUBLIC ERROR = CODE; Create: PUBLIC PROC [invalidKey: Key, mod: SeqIndex _ 17] RETURNS [Table] = { pog: PrimeTableIndex = Pog[mod]; pmod: CARDINAL = primeTable[pog]; data: REF Seq = NEW [Seq[pmod]]; FOR i: CARDINAL IN [0..data.max) DO data[i] _ [key: invalidKey, value: NIL] ENDLOOP; RETURN [NEW [TableRec _ [ size: 0, sizeLimit: pmod*2/3, inhibitCount: 0, chain: IF pog > 0 THEN primeTable[pog-1] ELSE 1, invalidKey: invalidKey, data: data ]]]; }; GetSize: PUBLIC PROC [table: Table] RETURNS [INT] = { RETURN [table.size]; }; ComputeIndex: PROC [table: Table, key: Key] RETURNS [index: SeqIndex] = INLINE { index _ key MOD table.data.max; }; Fetch: PUBLIC ENTRY PROC [table: Table, key: Key] RETURNS [found: BOOL, value: Value] = { ENABLE UNWIND => NULL; data: REF Seq = table.data; hash: SeqIndex _ ComputeIndex[table, key]; WHILE data[hash].key # table.invalidKey DO IF key=data[hash].key THEN RETURN [TRUE, data[hash].value]; hash _ IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain); ENDLOOP; RETURN [FALSE, NIL]; }; Replace: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { ENABLE UNWIND => NULL; data: REF Seq = table.data; hash: SeqIndex _ ComputeIndex[table, key]; WHILE data[hash].key # table.invalidKey DO IF key=data[hash].key THEN {data[hash].value _ value; RETURN [TRUE]}; hash _ IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain); ENDLOOP; RETURN [FALSE]; }; Store: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { ENABLE UNWIND => NULL; IF table.size >= table.sizeLimit THEN { IF table.inhibitCount = 0 THEN ReHash[table] ELSE IF table.size+1 = table.data.max THEN ERROR Stuck}; {data: REF Seq = table.data; hash: SeqIndex _ ComputeIndex[table, key]; WHILE data[hash].key # table.invalidKey DO IF key=data[hash].key THEN {data[hash].value _ value; RETURN [FALSE]}; hash _ IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain); ENDLOOP; data[hash] _ [key: key, value: value]; table.size _ table.size + 1; RETURN [TRUE]; }}; Insert: PUBLIC ENTRY PROC [table: Table, key: Key, value: Value] RETURNS [new: BOOL] = { ENABLE UNWIND => NULL; IF table.size >= table.sizeLimit THEN { IF table.inhibitCount = 0 THEN ReHash[table] ELSE IF table.size+1 = table.data.max THEN ERROR Stuck}; new _ BasicInsert[table, key, value]; table.size _ table.size + 1; }; BasicInsert: INTERNAL PROC [table: Table, key: Key, value: Value] RETURNS [BOOL] = { data: REF Seq = table.data; hash: SeqIndex _ ComputeIndex[table, key]; WHILE data[hash].key # table.invalidKey DO IF key=data[hash].key THEN RETURN [FALSE]; hash _ IF hash < table.chain THEN (data.max - table.chain + hash) ELSE (hash - table.chain); ENDLOOP; data[hash] _ [key: key, value: value]; RETURN [TRUE]; }; Pairs: PUBLIC PROC [table: Table, action: EachPairAction] RETURNS [quit: BOOL] = { {ENABLE UNWIND => data: REF Seq = table.data; FOR index: CARDINAL IN [0 .. data.max) DO IF data[index].key # table.invalidKey AND action[data[index].key, data[index].value] THEN {quit _ TRUE; EXIT}; ENDLOOP; }; }; table.inhibitCount _ table.inhibitCount + WHILE table.inhibitCount = 0 AND table.size > table.sizeLimit DO ReHash[table] ENDLOOP; }; Erase: PUBLIC ENTRY PROC [table: Table] = { data: REF Seq = table.data; FOR i: CARDINAL IN [0..data.max) DO data[i] _ [key: table.invalidKey, value: 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: PrimeTableIndex = Pog[seek]; newMod: CARDINAL _ 0; IF primeTable[PrimeTableSize-1] > LAST[SeqIndex] THEN ERROR; newMod _ primeTable[newPTI]; IF newMod = table.data.max THEN {table.sizeLimit _ LAST[NAT]; RETURN}; table.sizeLimit _ newMod*2/3; table.chain _ primeTable[newPTI-1]; table.data _ newData _ NEW [Seq[newMod]]; FOR i: NAT IN [0 .. table.data.max) DO table.data[i] _ [key: table.invalidKey, value: NIL] ENDLOOP; table _ table; FOR i: NAT IN [0 .. oldData.max) DO IF oldData[i].key # table.invalidKey AND NOT BasicInsert[table, oldData[i].key, oldData[i].value] THEN ERROR; ENDLOOP; table _ table; }; Pog: PROC [n: CARDINAL] RETURNS [p: PrimeTableIndex] = { PrimeTableSizeMinusOne: NAT = PrimeTableSize-1; FOR p _ 0, p+1 WHILE p < PrimeTableSizeMinusOne AND primeTable[p] < n DO NULL ENDLOOP; }; PrimeTableSize: NAT = 14; PrimeTableIndex: TYPE = NAT[0 .. PrimeTableSize); primeTable: ARRAY PrimeTableIndex OF CARDINAL = [ 00002, 00005, 00011, 00023, 00053, 00113, 00251, 00509, 01019, 02039, 04079, 08179, 16369, 32749]; }.