ExtendibleHashImpl.mesa
Copyright Ó 1988, 1989 by Xerox Corporation. All rights reserved.
Bob Hagmann July 7, 1989 10:05:01 am PDT
Simple implementaion of extendible hashing.
Restrictions to fix:
1) never shrinks
2) never overflows
3) never expands
DIRECTORY
PBasics,
ExtendibleHash,
ExtendibleHashInternal;
ExtendibleHashImpl: CEDAR MONITOR LOCKS hashTable USING hashTable: REF ExtendibleHashInternal.ExtendibleHashTableRep
IMPORTS PBasics, ExtendibleHashInternal
EXPORTS ExtendibleHash
~ BEGIN
ExtendibleHashTable: TYPE = REF ExtendibleHashTableRep;
ExtendibleHashTableRep: PUBLIC TYPE = ExtendibleHashInternal.ExtendibleHashTableRep;
Exported variables
Error: PUBLIC ERROR [reason: ExtendibleHash.Reason] = CODE;
Exported procedures
New: PUBLIC PROC [ storPrim: ExtendibleHash.PageStoragePrimitives, initialState: ExtendibleHash.State[closed..suspended] ← closed] RETURNS [hashTable: ExtendibleHash.ExtendibleHashTable] ~ {
hashTable ← NEW [ExtendibleHashInternal.ExtendibleHashTableRep ← [state: [], storPrim: storPrim, objectState: initialState]];
};
Open: PUBLIC ENTRY PROC [hashTable: ExtendibleHashInternal.ExtendibleHashTable, storage: ExtendibleHash.PageStorage, pageSize: ExtendibleHash.PageSize, initialize: BOOLEANFALSE, initialDirectorySize: CARD, clientPerCallData: REF] ~ {
ENABLE UNWIND => {};
hashMaskTemp: WORD ← 1;
shiftCount: INT;
hashTable.state ← [pageSize: pageSize];
hashTable.storage ← storage;
IF initialize THEN TRUSTED {
dirSizeTemp: CARD ← initialDirectorySize;
log2DirectorySize: CARD ← 0;
pagePtr: ExtendibleHash.PagePtr;
statePtr: LONG POINTER TO ExtendibleHashInternal.StatePage ;
pagePtr ← hashTable.RefPage[ExtendibleHash.statePage, new, clientPerCallData];
statePtr ← LOOPHOLE[pagePtr];
{
where: LONG POINTERLOOPHOLE[pagePtr];
nWordsLeft: CARD32 ← pageSize/PBasics.bytesPerWord;
WHILE nWordsLeft > 0 DO
fillThisTime: CARD32MIN[nWordsLeft, 10000];
PBasics.Fill[where: where, nWords: fillThisTime, value: 0];
where ← where + fillThisTime * UNITS[PBasics.Word];
nWordsLeft ← nWordsLeft - fillThisTime;
ENDLOOP;
};
WHILE dirSizeTemp > 1 DO
dst: CARD ← dirSizeTemp/2;
IF dst*2 # dirSizeTemp THEN ERROR Error[notPowerOfTwoDirectorySize];
dirSizeTemp ← dst;
log2DirectorySize ← log2DirectorySize + 1;
ENDLOOP;
IF dirSizeTemp # 1 THEN ERROR Error[notPowerOfTwoDirectorySize];
hashTable.state.log2DirectorySize ← log2DirectorySize;
statePtr.hashState ← hashTable.state;
hashTable.dictionary ← NEW[ExtendibleHashInternal.DictionaryRep[initialDirectorySize]];
FOR index: CARD IN [0..initialDirectorySize) DO
hashPagePtr: LONG POINTER TO ExtendibleHashInternal.HashPage;
initPagePtr: ExtendibleHash.PagePtr;
hashTable.dictionary[index] ← index + 1;
initPagePtr ← hashTable.RefPage[index+1, new, clientPerCallData];
hashPagePtr ← LOOPHOLE[initPagePtr];
hashPagePtr.freeWords ← pageSize - ExtendibleHashInternal.HashPageEntriesOffset;
hashPagePtr.usedWords ← 0;
hashPagePtr.nextOverflowPage ← 0;
hashTable.RelPage[index+1, modified, clientPerCallData];
ENDLOOP;
PBasics.Move[dst: @statePtr.dictionary[0], src: LOOPHOLE[hashTable.dictionary, LONG POINTER] + UNITS[ExtendibleHashInternal.DictionaryRep[0]], nWords: initialDirectorySize*WORDS[ExtendibleHash.PageNumber]/WORDS[PBasics.Word]];
hashTable.RelPage[ExtendibleHash.statePage, modified, clientPerCallData];
}
ELSE TRUSTED {
statePtr: LONG POINTER TO ExtendibleHashInternal.StatePage ← hashTable.RefPage[ExtendibleHash.statePage, read, clientPerCallData];
directorySize: CARD ← 1;
lastIx: INT;
IF statePtr.hashState.seal#ExtendibleHashInternal.sealValue THEN ERROR Error[badSeal];
IF statePtr.hashState.pageSize#pageSize THEN ERROR Error[wrongPageSize];
hashTable.state ← statePtr.hashState;
lastIx ← statePtr.hashState.log2DirectorySize;
FOR ix: INT IN [1..lastIx) DO
directorySize ← directorySize + directorySize;
ENDLOOP;
hashTable.dictionary ← NEW[ExtendibleHashInternal.DictionaryRep[directorySize]];
PBasics.Move[src: @statePtr.dictionary[0], dst: LOOPHOLE[hashTable.dictionary, LONG POINTER] + UNITS[ExtendibleHashInternal.DictionaryRep[0]], nWords: directorySize*WORDS[ExtendibleHash.PageNumber]/WORDS[PBasics.Word]];
hashTable.RelPage[ExtendibleHash.statePage, unchanged, clientPerCallData];
};
hashTable.objectState ← open;
shiftCount ← hashTable.state.log2DirectorySize;
WHILE shiftCount > 1 DO
hashMaskTemp ← PBasics.BITOR[PBasics.BITLSHIFT[hashMaskTemp, 1], 1];
shiftCount ← shiftCount - 1;
ENDLOOP;
hashTable.hashMask.low ← hashMaskTemp;
hashTable.hashMask.high ← 0;
};
SetState: PUBLIC PROC [hashTable: ExtendibleHash.ExtendibleHashTable, state: ExtendibleHash.State[closed..suspended]] ~ {
hashTable.objectState ← state;
hashTable.storage ← NIL;
};
GetState: PUBLIC PROC [hashTable: ExtendibleHash.ExtendibleHashTable] RETURNS [state: ExtendibleHash.State, entryCount: CARD, greatestPage: ExtendibleHash.PageNumber, log2DirectorySize: CARD, storage: ExtendibleHash.PageStorage] ~ {
RETURN [state: hashTable.objectState, entryCount: hashTable.state.entryCount, greatestPage: hashTable.state.greatestPage, log2DirectorySize: hashTable.state.log2DirectorySize, storage: hashTable.storage];
};
Validate: PUBLIC PROC [hashTable: ExtendibleHash.ExtendibleHashTable, hashFunction: PROC [entry: ExtendibleHash.Entry] RETURNS [hashValue: ExtendibleHash.HashValue]] ~ {
ERROR;
};
Hash access
ReadEntry: PUBLIC ENTRY UNSAFE PROC [hashTable: ExtendibleHash.ExtendibleHashTable, hashValue: ExtendibleHash.HashValue, proc: UNSAFE PROC [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT]], clientPerCallData: REFNIL] ~ {
ENABLE UNWIND => {};
overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT] ~ {RETURN[NIL, 0]}; -- overflow not implemented
dictionaryPage: WORD;
virtualPage: ExtendibleHash.PageNumber;
pagePtr: ExtendibleHash.PagePtr;
hashPagePtr: LONG POINTER TO ExtendibleHashInternal.HashPage;
dictionaryPage ← PBasics.BITAND[hashValue.low, hashTable.hashMask.low];
virtualPage ← hashTable.dictionary[dictionaryPage];
pagePtr ← hashTable.RefPage[virtualPage, read, clientPerCallData];
hashPagePtr ← LOOPHOLE[pagePtr];
TRUSTED {proc[entry: LOOPHOLE[@hashPagePtr.entries], wordsForEntriesOnPage: hashPagePtr.usedWords, overFlowPageProc: overFlowPageProc];};
hashTable.RelPage[virtualPage, unchanged, clientPerCallData];
};
DeleteEntry: PUBLIC ENTRY UNSAFE PROC [hashTable: ExtendibleHash.ExtendibleHashTable, hashValue: ExtendibleHash.HashValue, proc: UNSAFE PROC [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT]] RETURNS [entryToDelete: ExtendibleHash.Entry], clientPerCallData: REFNIL] ~ {
ENABLE UNWIND => {};
overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT] ~ {RETURN[NIL, 0]}; -- overflow not implemented
dictionaryPage: WORD;
virtualPage: ExtendibleHash.PageNumber;
pagePtr: ExtendibleHash.PagePtr;
hashPagePtr: LONG POINTER TO ExtendibleHashInternal.HashPage;
entryToDelete: ExtendibleHash.Entry;
dictionaryPage ← PBasics.BITAND[hashValue.low, hashTable.hashMask.low];
virtualPage ← hashTable.dictionary[dictionaryPage];
pagePtr ← hashTable.RefPage[virtualPage, write, clientPerCallData];
hashPagePtr ← LOOPHOLE[pagePtr];
TRUSTED {entryToDelete ← proc[entry: LOOPHOLE[@hashPagePtr.entries], wordsForEntriesOnPage: hashPagePtr.usedWords, overFlowPageProc: overFlowPageProc];};
IF entryToDelete # NIL THEN TRUSTED {
nowEntry: ExtendibleHash.Entry ← LOOPHOLE[@hashPagePtr.entries];
wordsLeft: INT ← hashPagePtr.usedWords;
WHILE wordsLeft > 0 DO
IF nowEntry = entryToDelete THEN EXIT;
wordsLeft ← wordsLeft - nowEntry.entryWordSize - 1;
nowEntry ← nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]);
REPEAT FINISHED => ERROR Error[notAnEntry];
ENDLOOP;
hashPagePtr.usedWords ← hashPagePtr.usedWords - nowEntry.entryWordSize - 1;
hashPagePtr.freeWords ← hashPagePtr.freeWords + nowEntry.entryWordSize + 1;
PBasics.Move[src: nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]), dst: nowEntry, nWords: wordsLeft - nowEntry.entryWordSize];
{
checkEntry: ExtendibleHash.Entry ← LOOPHOLE[@hashPagePtr.entries];
checkWordsLeft: INT ← hashPagePtr.usedWords;
WHILE checkWordsLeft > 0 DO
IF checkEntry.entryWordSize > hashPagePtr.usedWords OR checkEntry.entryWordSize > hashTable.state.pageSize OR checkEntry.entryWordSize = 0 THEN ERROR;
IF (checkWordsLeft ← checkWordsLeft - checkEntry.entryWordSize - 1) < 0 THEN ERROR;
checkEntry ← checkEntry + ((checkEntry.entryWordSize + 1) * UNITS[CARD32]);
ENDLOOP;
};
hashTable.RelPage[virtualPage, modified, clientPerCallData];
}
ELSE hashTable.RelPage[virtualPage, unchanged, clientPerCallData];
};
UpdateEntry: PUBLIC ENTRY UNSAFE PROC [
hashTable: ExtendibleHash.ExtendibleHashTable,
hashValue: ExtendibleHash.HashValue,
words: ExtendibleHash.EntSize,
findProc: UNSAFE PROC [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT, overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT]] RETURNS [entryToUpdate: ExtendibleHash.Entry],
modifyProc: UNSAFE PROC [entry: ExtendibleHash.Entry],
updateType: ExtendibleHash.UpdateType ← insertOrReplace,
clientPerCallData: REFNIL] ~ {
ENABLE UNWIND => {};
overFlowPageProc: UNSAFE PROC RETURNS [entry: ExtendibleHash.Entry, wordsForEntriesOnPage: INT] ~ {RETURN[NIL, 0]}; -- overflow not implemented
dictionaryPage: WORD;
virtualPage: ExtendibleHash.PageNumber;
pagePtr: ExtendibleHash.PagePtr;
hashPagePtr: LONG POINTER TO ExtendibleHashInternal.HashPage;
entryToUpdate: ExtendibleHash.Entry;
nextEntry: ExtendibleHash.Entry ← NIL;
savedNextWordSize: CARD32 ← CARD32.LAST;
dictionaryPage ← PBasics.BITAND[hashValue.low, hashTable.hashMask.low];
virtualPage ← hashTable.dictionary[dictionaryPage];
pagePtr ← hashTable.RefPage[virtualPage, write, clientPerCallData];
hashPagePtr ← LOOPHOLE[pagePtr];
TRUSTED {entryToUpdate ← findProc[entry: LOOPHOLE[@hashPagePtr.entries], wordsForEntriesOnPage: hashPagePtr.usedWords, overFlowPageProc: overFlowPageProc];};
SELECT updateType FROM
insert => IF entryToUpdate # NIL THEN ERROR Error[wrongUpdateType];
replace => IF entryToUpdate = NIL THEN ERROR Error[wrongUpdateType];
ENDCASE;
IF entryToUpdate # NIL THEN TRUSTED {
nowEntry: ExtendibleHash.Entry ← LOOPHOLE[@hashPagePtr.entries];
wordsLeft: INT ← hashPagePtr.usedWords;
WHILE wordsLeft > 0 DO
IF nowEntry = entryToUpdate THEN EXIT;
wordsLeft ← wordsLeft - nowEntry.entryWordSize - 1;
nowEntry ← nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]);
REPEAT FINISHED => ERROR Error[notAnEntry];
ENDLOOP;
IF entryToUpdate.entryWordSize # words THEN {
IF INT[hashPagePtr.freeWords] < (INT[words] - INT[nowEntry.entryWordSize]) THEN ERROR Error[outOfRoom];
hashPagePtr.usedWords ← (hashPagePtr.usedWords + words) - entryToUpdate.entryWordSize;
hashPagePtr.freeWords ← (hashPagePtr.freeWords + nowEntry.entryWordSize) - words;
PBasics.Move[src: nowEntry + ((nowEntry.entryWordSize + 1) * UNITS[CARD32]), dst: nowEntry + ((words + 1) * UNITS[CARD32]), nWords: wordsLeft - nowEntry.entryWordSize - 1];
entryToUpdate.entryWordSize ← words;
};
nextEntry ← entryToUpdate + ((words + 1) * UNITS[CARD32]);
IF hashPagePtr.freeWords > 0 THEN savedNextWordSize ← nextEntry.entryWordSize;
modifyProc[entryToUpdate];
IF entryToUpdate.entryWordSize # words THEN ERROR Error[entrySizesWrong];
IF hashPagePtr.freeWords > 0 THEN {
IF nextEntry.entryWordSize # savedNextWordSize THEN ERROR Error[overWriteOfNextEntry];
};
hashTable.RelPage[virtualPage, modified, clientPerCallData];
}
ELSE TRUSTED {
IF hashPagePtr.freeWords + 1 < words THEN ERROR Error[outOfRoom];
entryToUpdate ← LOOPHOLE[@hashPagePtr.entries + UNITS[CARD32] * hashPagePtr.usedWords];
hashPagePtr.usedWords ← hashPagePtr.usedWords + words + 1;
hashPagePtr.freeWords ← hashPagePtr.freeWords - words - 1;
entryToUpdate.entryWordSize ← words;
nextEntry ← entryToUpdate + ((words + 1) * UNITS[CARD32]);
IF hashPagePtr.freeWords > 0 THEN savedNextWordSize ← nextEntry.entryWordSize;
modifyProc[entryToUpdate];
IF entryToUpdate.entryWordSize # words THEN ERROR Error[entrySizesWrong];
IF hashPagePtr.freeWords > 0 THEN {
IF nextEntry.entryWordSize # savedNextWordSize THEN ERROR Error[overWriteOfNextEntry];
};
hashTable.RelPage[virtualPage, unchanged, clientPerCallData];
};
};
Initialization
Init: PROC ~ {
};
Init[];
END.