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; Error: PUBLIC ERROR [reason: ExtendibleHash.Reason] = CODE; 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; }; 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]; }; }; Init: PROC ~ { }; Init[]; END. LExtendibleHashImpl.mesa Copyright Σ 1988, 1989 by Xerox Corporation. All rights reserved. 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 Exported variables Exported procedures Hash access Initialization Κ Ή˜code•Mark outsideHeaderšœ™KšœB™BKšœ(™(—K™K™+™K™K™K™—K™šΟk ˜ K˜Kšœ˜Kšœ˜—K˜KšΡblnœœœ œ=˜tKšœ ˜'Kšœ˜šœ˜Kšœœœ˜7Icode2šœœœ1˜T—headšœ™KšΟnœœœ#œ˜;—šœ™šŸœœœtœ4˜ΏJšœ œn˜}J˜K™—šŸœœœœœœœ˜ΤLšœœ˜Lšœœ˜Lšœ œ˜Lšœ'˜'Lšœ˜šœ œœ˜Lšœ œ˜)Lšœœ˜Lšœ ˜ Lšœ  œœ#˜œ*˜θLšœΖ˜ΜJ˜K™—š Ÿœœœ?œœ+˜©Jšœ˜J˜K™——šœ ™ K™šŸ œœœœœ\œœ7œœœœ6œ˜«Lšœœ˜Jšœœœœ6œœœΟc˜Jšœœ˜Jšœ'˜'Jšœ ˜ Jšœ  œœ!˜=Jšœœ(˜GJšœ3˜3Jšœ/˜/Jšœœ ˜ Jšœœl˜‰Jšœ˜J˜K™—šŸ œœœœœ\œœ6œœœœ6œœ+˜ΪLšœœ˜Jšœœœœ6œœœ ˜Jšœœ˜Jšœ'˜'Jšœ ˜ Jšœ œœœ!˜=Jšœ$˜$Jšœœ(˜GJšœ3˜3Jšœ0˜0Jšœœ ˜ Jšœœl˜™šœœœœ˜%Jšœ!œ˜@Jšœ œ˜'šœ˜Jšœœœ˜&Jšœ3˜3Jšœ6œœ˜EJšœœœ˜+Jšœ˜—JšœK˜KJšœK˜KJšœ=œœ?˜ˆ˜Jšœ#œ˜BJšœœ˜,šœ˜Lš œ2œ5œœœ˜–JšœFœœ˜SJšœ<œœ˜KJšœ˜—J˜—Jšœ)˜)J˜—Jšœœ+˜0J˜K™—šŸ œœ œœ˜'Kšœ.˜.Kšœ$˜$Kšœ˜Kšœ œœ6œœœœ6œœ'˜ίKšœ œœ˜6Kšœ<˜