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, 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 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, 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; }; 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: REF _ NIL] ~ { 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: REF _ NIL] ~ { 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: REF _ NIL] ~ { 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]; }; }; Init: PROC ~ { }; Init[]; END. LExtendibleHashImpl.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 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ڑœBکBJڑœ‌œ ک Jڑ‌œ‌œlک‰Jڑœ=ک=JکK™—ڑںœ‌œ‌œ‌œ‌œ\‌œ‌œ6‌œ‌œ‌œ‌œ6‌œ‌œ;‌œ‌œکّLڑ‌œ‌œکJڑœ‌œ‌œ‌œ6‌œ‌œ‌œ کگJڑœ‌œکJڑœ'ک'Jڑœ ک Jڑœ ‌œ‌œ‌œ!ک=Jڑœ$ک$Jڑœ‌œ(کGJڑœ3ک3JڑœCکCJڑœ‌œ ک 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ڑœ<ککCJکK™—ڑںœ‌œ‌œ‌œک'Kڑœ.ک.Kڑœ$ک$KڑœکKڑœ ‌œ‌œ6‌œ‌œ‌œ‌œ6‌œ‌œ'کكKڑœ‌œ‌œک6Kڑœ8ک8Kڑœ‌œ‌œک!Lڑ‌œ‌œکJڑœ‌œ‌œ‌œ6‌œ‌œ‌œ کگJڑœ‌œکJڑœ'ک'Jڑœ ک Jڑœ ‌œ‌œ!ک=Jڑœ$ک$Jڑœ"‌œک&Jڑœ(ک(Jڑœ‌œ(کGJڑœ3ک3JڑœCکCJڑœ‌œ ک Jڑ‌œ"‌œlک‌ڑ‌œ‌کJڑ œ ‌œ‌œ‌œ‌œکCJڑ œ‌œ‌œ‌œ‌œکDJڑ‌œک—ڑ‌œ‌œ‌œ‌œک%Jڑœ!‌œک@Jڑœ‌œک'ڑ‌œ‌کJڑ‌œ‌œ‌œک&Jڑœ3ک3JڑœEکEJڑ‌œ‌œ‌œک+Jڑ‌œک—ڑ‌œ%‌œک-Jڑ‌œ‌œ‌œ ‌œ‌œ‌œکgJڑœVکVJڑœQکQJڑœ¬ک¬Jڑœ$ک$Jک—Jڑœ+‌œ‌œک:Jڑ‌œ‌œ-کNJڑœکJڑ‌œ%‌œ‌œکIڑ‌œ‌œک#Jڑ‌œ-‌œ‌œکVJک—Jڑœ<ک