<> <> <> <> DIRECTORY HashTable: TYPE USING [ Key, Value, Table, OpsRec, EachValueAction, TableRec, Seq, SeqIndex, NodeList]; HashTableImpl: CEDAR MONITOR LOCKS table USING table: Table EXPORTS HashTable = { Key: TYPE = HashTable.Key; Value: TYPE = HashTable.Value; Table: TYPE = HashTable.Table; NodeList: TYPE = HashTable.NodeList; SeqIndex: TYPE = HashTable.SeqIndex; <> Create: PUBLIC PROC[ops: HashTable.OpsRec, mod: SeqIndex_71] RETURNS[Table] = { mod _ MAX[mod, minMod]; RETURN[NEW [HashTable.TableRec _ [ ops: ops, size: 0, sizeLimit: mod, inhibitCount: 0, data: NEW [HashTable.Seq[mod]] ]]] }; minMod: SeqIndex = 2; GetSize: PUBLIC PROC[table: Table] RETURNS[INT] = { RETURN[table.size]}; ComputeIndex: PROC[table: Table, key: Key] RETURNS[SeqIndex] = INLINE { RETURN[table.ops.HashFromKey[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]; FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN RETURN[TRUE, node.first]; ENDLOOP; RETURN [FALSE, NIL]}; Replace: PUBLIC ENTRY PROC[table: Table, key: Key, value: Value] RETURNS[BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex = ComputeIndex[table, key]; FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN { node.first _ value; RETURN[TRUE]}; ENDLOOP; RETURN[FALSE]}; Store: PUBLIC ENTRY PROC[table: Table, key: Key, value: Value] RETURNS[BOOL] = { ENABLE UNWIND => NULL; hash: SeqIndex = ComputeIndex[table, key]; FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN { node.first _ value; RETURN [FALSE]}; ENDLOOP; table.data[hash] _ CONS[first: value, rest: 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]; FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN RETURN[FALSE]; ENDLOOP; table.data[hash] _ CONS[first: value, rest: 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]; lag: NodeList _ NIL; FOR node: NodeList _ table.data[hash], node.rest WHILE node # NIL DO IF table.ops.EqualKeys[key, table.ops.GetKey[node.first]] THEN { IF lag = NIL THEN table.data[hash] _ node.rest ELSE lag.rest _ node.rest; table.size _ table.size - 1; RETURN[TRUE]}; lag _ node; ENDLOOP; RETURN[FALSE]}; ForEach: PUBLIC PROC[table: Table, action: HashTable.EachValueAction] RETURNS[quit: BOOL] = { {ENABLE UNWIND => head: NodeList _ NIL; index: CARDINAL _ table.data.max; DO [head, index] _ GetNext[table, head, index]; IF head = NIL THEN {quit _ FALSE; EXIT}; IF action[head.first] THEN {quit _ TRUE; EXIT}; ENDLOOP; }; table.inhibitCount _ table.inhibitCount + WHILE table.inhibitCount = 0 AND table.size > table.sizeLimit DO ReHash[table] ENDLOOP}; GetNext: ENTRY PROC[table: Table, head: NodeList, index: CARDINAL] RETURNS[NodeList, CARDINAL] = { ENABLE UNWIND => NULL; IF head # NIL THEN { head _ head.rest; IF head # NIL THEN RETURN[head, index]}; WHILE index > 0 DO index _ index - 1; head _ table.data[index]; IF head # NIL THEN RETURN[head, index]; ENDLOOP; RETURN[NIL, 0]}; Erase: PUBLIC ENTRY PROC[table: Table] = { FOR i: SeqIndex IN [0..table.data.max) DO table.data[i] _ NIL ENDLOOP; table.size _ 0}; ReHash: INTERNAL PROC[table: Table] = { oldData: REF HashTable.Seq = table.data; newData: REF HashTable.Seq; seek: CARDINAL = table.data.max * 2; newPTI, newMod: CARDINAL _ 0; IF primeTable[PrimeTableSize-1] > SeqIndex.LAST 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 _ INT.LAST; RETURN}; table.sizeLimit _ newMod; table.data _ newData _ NEW [HashTable.Seq[newMod]]; FOR i: NAT IN [0 .. oldData.max) DO next: NodeList _ NIL; FOR cur: NodeList _ oldData[i], next WHILE cur # NIL DO hash: SeqIndex = ComputeIndex[table, table.ops.GetKey[cur.first]]; next _ cur.rest; cur.rest _ 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]; }.