<> <> <> DIRECTORY ExtendibleHash; ExtendibleHashInternal: CEDAR DEFINITIONS = BEGIN <> <> HashState: TYPE = MACHINE DEPENDENT RECORD [ <> seal (0): CARD _ sealValue, pageSize (1*WORDS[INT]): ExtendibleHash.PageSize _ TRASH, -- in words <> greatestPage (2*WORDS[INT]): ExtendibleHash.PageNumber _ ExtendibleHash.statePage, -- greatest page that has ever been part of the hash firstFreePage (3*WORDS[INT]): ExtendibleHash.PageNumber _ nilPage, -- head of list of free pages entryCount (4*WORDS[INT]): CARD _ 0, -- number of entries in the hash log2DirectorySize(5*WORDS[INT]): CARD _ 0 -- number of bits in the directory of the hash ]; sealValue: CARDINAL = 01066B; StatePage: TYPE = MACHINE DEPENDENT RECORD [ hashState (0): HashState, -- room for the HashState and some spare spare (6*WORDS[INT]): ARRAY [6*WORDS[INT]..31*WORDS[INT]) OF WORD, -- room for the HashState and some spare nextPage (31*WORDS[INT]): CARD, -- next page in the chain dictionary (32*WORDS[INT]): ARRAY [0..32) OF WORD ]; <> HashPageEntriesOffset: INT = 3; HashPage: TYPE = MACHINE DEPENDENT RECORD [ freeWords (0): CARD, <> usedWords (1*WORDS[INT]): CARD, <> nextOverflowPage (2*WORDS[INT]): ExtendibleHash.PageNumber, <> entries (HashPageEntriesOffset*WORDS[INT]): ARRAY [0..0) OF WORD -- really an array of ExtendibleHash.EntryRep ]; nilPage: ExtendibleHash.PageNumber = ExtendibleHash.statePage; -- The "nil" PageNumber is the same as statePage. This is ok because the PageNumber of the statePage is never stored anywhere. freePageMarker: CARD = LAST[CARD]; -- value of freeWords which marks page as being in free list <> <> ExtendibleHashTable: TYPE = REF ExtendibleHashTableRep; ExtendibleHashTableRep: TYPE = MONITORED RECORD [ <> state: HashState, <> storPrim: ExtendibleHash.PageStoragePrimitives, <> objectState: ExtendibleHash.State _ closed, storage: ExtendibleHash.PageStorage _ NIL, <> hashMask: ExtendibleHash.HashValue _ [0, 0], -- mask to extract the proper number of low order bits from the 64 bit hash version: LONG CARDINAL _ 0, -- number of updates to this hash since it was opened dictionary: Dictionary, lockCount: INTEGER _ 0, -- + reader count, or -1 for (single) writer unlocked: CONDITION -- notified when the lock is released <> ]; Dictionary: TYPE = REF DictionaryRep; DictionaryRep: TYPE = RECORD [ SEQUENCE nSlots: NAT OF ExtendibleHash.PageNumber ]; <> RefPage: PROC [hashTable: ExtendibleHashTable, number: ExtendibleHash.PageNumber, type: ExtendibleHash.ReferenceType _ read] RETURNS [ptr: ExtendibleHash.PagePtr] = TRUSTED INLINE { RETURN [hashTable.storPrim.referencePage[storage: hashTable.storage, number: number, type: type]] }; RelPage: PROC [hashTable: ExtendibleHashTable, number: ExtendibleHash.PageNumber, update: ExtendibleHash.UpdateState _ unchanged] = TRUSTED INLINE { hashTable.storPrim.releasePage[storage: hashTable.storage, number: number, update: update] }; END.