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. ΌExtendibleHashInternal.mesa Copyright Σ 1988 by Xerox Corporation. All rights reserved. Bob Hagmann October 5, 1988 9:39:58 am PDT Permanent state of hash table, kept in statePage The default values are for a freshly-initialized hash table; the TRASH values are not constant but are computed and filled in during Open. Read-only fields which do not change during the life of the hash: Read-write fields, protected by the hash internal lock: Representation of a hash table data page number of free words at end of this page (freePageMarker indicates this page is in the free list) number of used words for entries If not nilPage, then the page number of the next overflow page in the chain Volatile data structures Volatile state of open hash. Copy of permanent state in statePage. Access to this copy is protected by the internal monitor. Read-only fields which do not change during the lifetime of the ExtendibleHashTableRep: Read-only fields which do not change while a hash is open, and which are protected by the monitor lock when they do change: Read-write fields, protected by the monitor: The following fields hold onto preallocated temporary storage. This storage is handed out to clients for the duration of an operation; if multiple client calls are in progress simultaneously, extra temporary storage is allocated for the second and subsequent clients and dropped on the floor when they finish. Convenient access to the client-provided procedures ΚH– "Cedar" style˜codešœ™Kšœ<™