ExtendibleHashInternal.mesa
Copyright Ó 1988 by Xerox Corporation. All rights reserved.
Bob Hagmann October 5, 1988 9:39:58 am PDT
DIRECTORY
ExtendibleHash;
ExtendibleHashInternal: CEDAR DEFINITIONS
= BEGIN
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.
HashState: TYPE = MACHINE DEPENDENT RECORD [
Read-only fields which do not change during the life of the hash:
seal (0): CARD ← sealValue,
pageSize (1*WORDS[INT]): ExtendibleHash.PageSize ← TRASH, -- in words
Read-write fields, protected by the hash internal lock:
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
];
Representation of a hash table data page
HashPageEntriesOffset: INT = 3;
HashPage: TYPE = MACHINE DEPENDENT RECORD [
freeWords (0): CARD,
number of free words at end of this page (freePageMarker indicates this page is in the free list)
usedWords (1*WORDS[INT]): CARD,
number of used words for entries
nextOverflowPage (2*WORDS[INT]): ExtendibleHash.PageNumber,
If not nilPage, then the page number of the next overflow page in the chain
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
Volatile data structures
Volatile state of open hash.
ExtendibleHashTable: TYPE = REF ExtendibleHashTableRep;
ExtendibleHashTableRep: TYPE = MONITORED RECORD [
Copy of permanent state in statePage. Access to this copy is protected by the internal monitor.
state: HashState,
Read-only fields which do not change during the lifetime of the ExtendibleHashTableRep:
storPrim: ExtendibleHash.PageStoragePrimitives,
Read-only fields which do not change while a hash is open, and which are protected by the monitor lock when they do change:
objectState: ExtendibleHash.State ← closed,
storage: ExtendibleHash.PageStorage ← NIL,
Read-write fields, protected by the monitor:
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
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.
];
Dictionary: TYPE = REF DictionaryRep;
DictionaryRep: TYPE = RECORD [
SEQUENCE nSlots: NAT OF ExtendibleHash.PageNumber
];
Convenient access to the client-provided procedures
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.