<> <> <> DIRECTORY Commander, CommandTool, Convert, ExtendibleHash, IO, Process, Random, Rope; ExtendibleHashTest: CEDAR PROGRAM IMPORTS Commander, CommandTool, Convert, ExtendibleHash, IO, Process, Random, Rope = BEGIN OPEN ExtendibleHash; KnownHash: TYPE = RECORD [ hash: ExtendibleHash.HashValue ]; MyPageStorage: TYPE = RECORD [ SEQUENCE noBuckets: NAT OF REF PageContents ]; PageContents: TYPE = RECORD [ ARRAY [0..1024) OF CARD ]; <> <<>> ExtendibleHashTestProc: Commander.CommandProc = { <<[cmd: Handle] RETURNS [result: REF _ NIL, msg: ROPE _ NIL]>> <> findAll: PROC = { totalEntries: INT _ 0; FOR nowList: LIST OF KnownHash _ knownHashList, nowList.rest UNTIL nowList = NIL DO lookupProc: UNSAFE PROC [entry: Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: Entry, wordsForEntriesOnPage: INT]] ~ TRUSTED { nowEntry: ExtendibleHash.Entry _ entry; wordsLeft: INT _ wordsForEntriesOnPage; WHILE wordsLeft > 0 DO nowContents: LONG POINTER TO ExtendibleHash.HashValue; IF nowEntry.entryWordSize # 2 THEN ERROR; nowContents _ LOOPHOLE[@nowEntry.entryContents]; IF nowContents.low = hash.low THEN RETURN; wordsLeft _ wordsLeft - nowEntry.entryWordSize - 1 ; nowEntry _ nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]); REPEAT FINISHED => ERROR; ENDLOOP; }; hash: ExtendibleHash.HashValue = nowList.first.hash; TRUSTED {ExtendibleHash.ReadEntry[hashTable: testHashTable, hashValue: hash, proc: lookupProc];}; ENDLOOP; FOR h: INT IN [0..noBuckets) DO lookupProc: UNSAFE PROC [entry: Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: Entry, wordsForEntriesOnPage: INT]] ~ TRUSTED { nowEntry: ExtendibleHash.Entry _ entry; wordsLeft: INT _ wordsForEntriesOnPage; WHILE wordsLeft > 0 DO nowContents: LONG POINTER TO ExtendibleHash.HashValue; IF nowEntry.entryWordSize # 2 THEN ERROR; nowContents _ LOOPHOLE[@nowEntry.entryContents]; wordsLeft _ wordsLeft - nowEntry.entryWordSize - 1 ; nowEntry _ nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]); totalEntries _ totalEntries + 1; ENDLOOP; }; hash: ExtendibleHash.HashValue ; hash.high _ 0; hash.low _ h; TRUSTED {ExtendibleHash.ReadEntry[hashTable: testHashTable, hashValue: hash, proc: lookupProc];}; ENDLOOP; IF totalEntries # numberOfActiveHashValues THEN ERROR; }; argv: CommandTool.ArgumentVector; testHashTable: ExtendibleHash.ExtendibleHashTable; noBuckets: INT; noTests: INT; numberOfActiveHashValues: INT _ 0; out: IO.STREAM; pageStorage: REF MyPageStorage; randomStream: Random.RandomStream; knownHashList: LIST OF KnownHash _ NIL; noisy: BOOL _ FALSE; offset: INT _ 0; out _ cmd.out; argv _ CommandTool.Parse[cmd: cmd ! CommandTool.Failed => {msg _ errorMsg; GO TO failed}]; IF argv.argc < 3 THEN GOTO failed; IF Rope.InlineFetch[argv[1], 0] = '- THEN { c: CHAR; IF argv[1].Length[] # 2 THEN GOTO failed; c _ argv[1].InlineFetch[1] ; SELECT c FROM 'n => noisy _ TRUE; ENDCASE; offset _ 1; }; noBuckets _ Convert.IntFromRope[argv[1+offset] ! Convert.Error => GOTO failed]; noTests _ Convert.IntFromRope[argv[2+offset] ! Convert.Error => GOTO failed]; IF noTests <= 0 THEN GOTO failed; randomStream _ Random.Create[range: 16384, seed: -1] ; pageStorage _ NEW[MyPageStorage[noBuckets + 1]]; FOR bucket: INT IN [0..noBuckets] DO pageStorage[bucket] _ NEW[PageContents]; ENDLOOP; testHashTable _ ExtendibleHash.New[storPrim: [MyReferencePage, MyReleasePage], initialState: closed]; ExtendibleHash.Open[hashTable: testHashTable, storage: pageStorage, pageSize: 1024, initialize: TRUE, initialDirectorySize: noBuckets]; FOR loopCount: INT IN (0..noTests] DO rand: INT = Random.ChooseInt[randomStream, 0, 25]; Process.CheckForAbort[]; SELECT rand FROM IN [0..2) => { -- lookup all hash values findAll[]; IF noisy THEN out.PutF["Looked up all the hash values\n"]; }; IN [2..20) => { -- make a new hash lookupProc: UNSAFE PROC [entry: Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: Entry, wordsForEntriesOnPage: INT]] RETURNS[entryToUpdate: Entry _ NIL] ~ TRUSTED { nowEntry: ExtendibleHash.Entry _ entry; wordsLeft: INT _ wordsForEntriesOnPage; WHILE wordsLeft > 0 DO nowContents: LONG POINTER TO ExtendibleHash.HashValue; IF nowEntry.entryWordSize # 2 THEN ERROR; nowContents _ LOOPHOLE[@nowEntry.entryContents]; IF nowContents.low = newHashValue.low THEN ERROR; wordsLeft _ wordsLeft - nowEntry.entryWordSize - 1 ; nowEntry _ nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]); ENDLOOP; }; modifyProc: UNSAFE PROC [entry: Entry] ~ TRUSTED { nowContents: LONG POINTER TO ExtendibleHash.HashValue; nowContents _ LOOPHOLE[@entry.entryContents]; nowContents.high _ 0; nowContents.low _ newHashValue.low; }; newHashValue: ExtendibleHash.HashValue; newHashValue.high _ 0; DO dup: BOOL _ FALSE; newHashValue.low _ Random.ChooseInt[randomStream, 0, 16383]; FOR khl: LIST OF KnownHash _ knownHashList, khl.rest UNTIL khl = NIL DO IF newHashValue.low = khl.first.low THEN {dup _ TRUE; EXIT}; ENDLOOP; IF ~dup THEN EXIT; ENDLOOP; IF noisy THEN out.PutF["New hash value of %g\n", IO.card[newHashValue.low]]; TRUSTED {ExtendibleHash.UpdateEntry[hashTable: testHashTable, hashValue: newHashValue, words: 2, findProc: lookupProc, modifyProc: modifyProc, updateType: insert];}; knownHashList _ CONS[[newHashValue], knownHashList]; numberOfActiveHashValues _ numberOfActiveHashValues + 1; }; IN [20..25) => { -- remove a hash lookupProc: UNSAFE PROC [entry: Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: Entry, wordsForEntriesOnPage: INT]] RETURNS[entryToDelete: Entry _ NIL] ~ TRUSTED { nowEntry: ExtendibleHash.Entry _ entry; wordsLeft: INT _ wordsForEntriesOnPage; WHILE wordsLeft > 0 DO nowContents: LONG POINTER TO ExtendibleHash.HashValue; IF nowEntry.entryWordSize # 2 THEN ERROR; nowContents _ LOOPHOLE[@nowEntry.entryContents]; IF nowContents.low = removeHashValue.low THEN RETURN[nowEntry]; wordsLeft _ wordsLeft - nowEntry.entryWordSize - 1 ; nowEntry _ nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]); ENDLOOP; ERROR; }; randRem: INT _ Random.ChooseInt[randomStream, 0, numberOfActiveHashValues]; prevKnownHash: LIST OF KnownHash _ NIL; removeHashValue: ExtendibleHash.HashValue; IF numberOfActiveHashValues <= 0 THEN LOOP; FOR nowList: LIST OF KnownHash _ knownHashList, nowList.rest UNTIL nowList = NIL DO randRem _ randRem - 1; IF randRem <= 0 THEN EXIT; ENDLOOP; IF prevKnownHash = NIL THEN LOOP; removeHashValue _ prevKnownHash.rest.first.hash; prevKnownHash.rest _ prevKnownHash.rest.rest; numberOfActiveHashValues _ numberOfActiveHashValues - 1; TRUSTED {ExtendibleHash.DeleteEntry[hashTable: testHashTable, hashValue: removeHashValue, proc: lookupProc];}; IF noisy THEN out.PutF["Remove hash value of %g\n", IO.card[removeHashValue.low]]; }; ENDCASE; ENDLOOP; findAll[]; out.PutF["Found all the hash values -- one final time\n"]; EXITS failed => {result _ $Failure}; }; <> <<>> MyReferencePage: ExtendibleHash.ReferencePage ~ { <> ms: REF MyPageStorage; rpc: REF PageContents; ms _ NARROW[storage]; rpc _ ms[number]; ptr _ LOOPHOLE[rpc]; }; MyReleasePage: ExtendibleHash.ReleasePage ~ { <> }; <> Init: PROC = { Commander.Register["ExtendibleHashTest", ExtendibleHashTestProc, "ExtendibleHashTest {-n} noBuckets noTests"]; }; Init[]; END. <<>>