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š
œ;˜;Lšœœ
˜š
œ
˜
Kšœœ
œœ
˜(Kšœœ!˜3šœ˜Kšœœœ˜.Kš
œ;˜;Kšœœ˜3Kš
œ'˜'Kšœ
˜—K˜—šœ˜Lšœœ˜Lšœœ
œ#˜DLš
œ˜Lš
œ*˜*Lšœ
˜—Lšœœ
œ#˜@Lš
œ6˜6Lš
œ%˜%Lšœœ=˜Wšœœ
œ˜/Jšœ
œ
œ!˜=Lš
œ$˜$Lš
œ(˜(Lš
œ.˜.Jš
œ$˜$Lš
œP˜PLš
œ˜Lš
œ!˜!Lš
œ%˜%Lšœ
˜—Lš
œ0œœ
œœHœœ˜β
Lš
œ6˜6Lš
œ
˜
—šœ
œ˜Lšœ
œ
œ
œV˜oLšœœ˜Lšœœ
˜Lšœ:œ
œ˜VLšœ&œ
œ˜HLš
œ%˜%Lš
œ.˜.šœœ
œ
˜Lš
œ.˜.Lšœ
˜—Lšœœ6˜PLšœ0œœœAœœ˜Ϋ
Lš
œ,˜,Lš
œ˜—Lš
œ˜Lš
œ/˜/šœ˜Lšœœ		œ˜DLš
œ˜Lšœ
˜—Jš
œ&˜&Jš
œ˜J˜K™—šŸœœ
œd˜yLš
œ˜Lšœœ
˜J˜K™—šŸœœ
œ1œ+œ>œ*˜θ
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š
œ<˜<Lšœ
œ˜Jšœœ
œ
œ6œœ
œ ˜
Jšœœ
˜Jš
œ'˜'Jš
œ ˜ Jšœ
œ
œ!˜=Jš
œ$˜$Jšœ"œ
˜&Jš
œ(˜(Jšœœ(˜GJš
œ3˜3Jš
œ0˜0Jšœœ
˜ 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š
œ)˜)J˜
—šœ
œ
œ˜Jšœ#œ
œ˜AJšœœ?˜WJš
œ:˜:Jš
œ:˜:Jš
œ$˜$Jšœ+œ
œ˜:Jšœœ-˜NJš
œ˜Jšœ%œ
œ˜Išœœ˜#Jšœ-œ
œ˜VJ˜—Jš
œ*˜*J˜—J˜—K˜—™šŸœœ˜K˜—K˜K˜—Kšœ
˜—…—-²9·