[Indigo]<Yggdrasil>ExtendibleHash>ExtendibleHashImpl.mesa!16

ExtendibleHashImpl.mesa

Bob Hagmann July 6, 1989 10:30:04 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: BOOLEAN ← FALSE, initialDirectorySize: CARD] ~ {

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];

statePtr ← LOOPHOLE[pagePtr];

{

where: LONG POINTER ← LOOPHOLE[pagePtr];

nWordsLeft: CARD32 ← pageSize/PBasics.bytesPerWord;

WHILE nWordsLeft > 0 DO

fillThisTime: CARD32 ← MIN[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];

hashPagePtr ← LOOPHOLE[initPagePtr];

hashPagePtr.freeWords ← pageSize - ExtendibleHashInternal.HashPageEntriesOffset;

hashPagePtr.usedWords ← 0;

hashPagePtr.nextOverflowPage ← 0;

hashTable.RelPage[index+1, modified];

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];

}

ELSE TRUSTED {

statePtr: LONG POINTER TO ExtendibleHashInternal.StatePage ← hashTable.RefPage[ExtendibleHash.statePage, read];

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];

};

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]]] ~ {

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];

hashPagePtr ← LOOPHOLE[pagePtr];

TRUSTED {proc[entry: LOOPHOLE[@hashPagePtr.entries], wordsForEntriesOnPage: hashPagePtr.usedWords, overFlowPageProc: overFlowPageProc];};

hashTable.RelPage[virtualPage];

};

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]] ~ {

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];

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];

}

ELSE hashTable.RelPage[virtualPage, unchanged];

};

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] ~ {

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];

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];

}

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];

};

Initialization

Init: PROC ~ {

};

Init[];

END.