ExtendibleHashTestProc: Commander.CommandProc = {
[cmd: Handle] RETURNS [result: REF ← NIL, msg: ROPE ← NIL]
CommandObject = [in, out, err: STREAM, commandLine, command: ROPE, ...]
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};
};