<> <> <> <> <> <<1. Consider storing OffsetTables at the end of BTreePages when they happen to fit. WritePage could easily compute an OffsetTable from the EntryTable it already has, and BinSearchPage could save the expense of constructing the OffsetTable when one is already stored in the page.>> DIRECTORY BTree; BTreeInternal: DEFINITIONS = BEGIN OPEN BTree; <> <> <> TreeState: TYPE = MACHINE DEPENDENT RECORD [ <> seal (0): CARDINAL _ sealValue, pageSize (1): PageSize _ TRASH, -- in words <> rootPage (2): PageNumber _ nilPage, -- BTree page containing the root greatestPage (3): PageNumber _ statePage, -- greatest page that has ever been part of the tree firstFreePage (4): PageNumber _ nilPage, -- head of list of free BTree pages entryCount (5): LONG CARDINAL _ 0, -- number of entries in the tree depth (7): PathStkIndex _ 0, -- number of levels in the tree updateInProgress (8): BOOL _ FALSE]; sealValue: CARDINAL = 046273B; <> BTreePagePtr: TYPE = LONG BASE POINTER TO BTreePage; BTreePage: TYPE = MACHINE DEPENDENT RECORD [ freeWords (0): CARDINAL, <> minPage (1): PageNumber, <> entries (2): --ARRAY [0..?) OF-- BTreeEntry]; PageOffset: TYPE = BTreePagePtr RELATIVE ORDERED POINTER [0..LAST[PageSize]] TO BTreeEntry; BTreeEntry: TYPE = MACHINE DEPENDENT RECORD [ grPage: PageNumber, -- page containing sons greater than this entry but less than the next entry: ClientEntry]; -- client data ClientEntry: TYPE = ARRAY [0..0) OF WORD; nilPage: PageNumber = statePage; -- The "nil" PageNumber is the same as statePage. This is ok because the PageNumber of the statePage is never stored anywhere. freePageMarker: CARDINAL = LAST[CARDINAL]; -- value of freeWords which marks page as being in free list <> pageOverhead: CARDINAL = 2; -- words of overhead in a page; remainder is available for BTreeEntries nilOffset: PageOffset = LOOPHOLE [0]; entry0Offset: PageOffset = LOOPHOLE [1]; -- offset of a ficticious entry whose grPage would overlay BTreePage.minPage entry1Offset: PageOffset = LOOPHOLE [2]; -- offset of first real entry entryOverhead: CARDINAL = 1; -- overhead in an entry; remainder is client data reservedWordsPerPage: [BTree.reservedWordsPerPage..BTree.reservedWordsPerPage] = pageOverhead+entryOverhead; -- just checking maxMaxRecordsPerPage: CARDINAL = (LAST[PageSize] - pageOverhead) / (entryOverhead + 1); -- worst case assuming largest possible page and smallest possible entry <> <> Tree: TYPE = REF TreeObject; TreeObject: TYPE = MONITORED RECORD [ <> state: TreeState, <> repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives, minEntrySize: CARDINAL, -- in words <> objectState: State _ closed, maxRecordsPerPage: CARDINAL _ TRASH, -- function of pageSize and minEntrySize maxFreeWords: CARDINAL _ TRASH, -- non-overhead words per page awfullyFull: CARDINAL _ TRASH, -- words in 9/10 full page prettyFull: CARDINAL _ TRASH, -- words in 2/3 full page fairlyFull: CARDINAL _ TRASH, -- words in 1/2 full page breathingSpace: CARDINAL _ TRASH, -- words in 1/10 full page storage: PageStorage _ NIL, maintainRecomputableState: BOOL _ TRUE, id: CARDINAL _ TRASH, -- distinguishes this TreeObject instance from any other <> version: LONG CARDINAL _ 0, -- number of updates to this tree since it was opened lockCount: INTEGER _ 0, -- + reader count, or -1 for (single) writer unlocked: CONDITION, -- notified when the lock is released longUpdate: BOOL _ FALSE, -- argument of most recent call to SetUpdateInProgress <> offsetTable: OffsetTable _ NIL, -- offsets of entries on a page, indexed by entry ordinal defaultPathStk: PathStk _ NIL, -- used internally when client doesn't pass one entryTable: REF EntryTable _ NIL, -- cumulative lengths and heap offsets of entries in EntSeqRecords heap: REF Heap _ NIL]; -- heap of entries contending for father page <> PathStk: TYPE = REF PathStkObject; PathStkObject: TYPE = RECORD [ treeID: CARDINAL _ 0, -- instance of tree to which this PathStk belongs version: LONG CARDINAL _ 0, -- value of tree.version for which this PathStk is valid entryTable: REF EntryTable _ NIL, -- cumulative lengths and heap offsets of entries in EntSeqRecords heap: REF Heap _ NIL, -- heap of entries contending for father page top: PathStkIndex _ 0, -- the level corresponding to the BTree entry of interest path: ARRAY PathStkIndex OF PathStkEntry]; -- level 1 is the root; level 0 is dummy, and used only when the root page splits and a new root page must be created PathStkEntry: TYPE = RECORD [ pageNumber: PageNumber _ nilPage, -- also appears as grPage of BTreeEntry indexed by lastOffset in previous stack level offset: PageOffset _ nilOffset, -- offset of entry directly along path lastOffset: PageOffset _ nilOffset, -- entry preceding the one designated by offset nextToLastOffset: PageOffset _ nilOffset, -- entry preceding the one designated by lastOffset eslFront: REF EntSeqRecord _ NIL, -- head of list of entries that belong between lastOffset and offset. Do not assign directly to this field (see below). eslRear: REF EntSeqRecord _ NIL, -- tail of list. Do not assign directly to this field (see below). leastSon: PageNumber _ nilPage]; -- least son of entries belonging on this page <<*** DANGER *** DANGER *** DANGER ***>> <> maxLevelsInTree: CARDINAL = 7; -- maximum depth allowed by the implementation. To exceed this without first exhausting the PageNumber space would require an average branching factor of less than 5, which is totally unreasonable for a BTree. PathStkIndex: TYPE = [0..maxLevelsInTree]; <> OffsetTable: TYPE = REF OffsetTableObject; OffsetTableObject: TYPE = RECORD [ offsets: SEQUENCE maxLength: EntryOrdinal OF PageOffset]; EntryOrdinal: TYPE = [0..3*maxMaxRecordsPerPage]; -- an OffsetTableObject needs to hold only one page's worth of entries, but an entryTable may need to hold as many as three pages' worth. EntSeqRecord: TYPE = RECORD [ fwdP: REF EntSeqRecord, -- next in list entSeqP: LONG POINTER TO BTreeEntry, -- pointer to a sequence of entries (within this EntSeqRecord, starting at or after entSeq) entSeqLen: CARDINAL, -- length of the sequence in words entSeq: --ARRAY [0..0) OF BTreeEntry-- SEQUENCE maxLength: [0..LAST[PageSize]] OF WORD]; EntryTable: TYPE = RECORD [ length: EntryOrdinal, -- indexed by entry ordinal in entry sequence list; entry 0 is a dummy and has a cumEntSize of zero. map: SEQUENCE maxLength: EntryOrdinal OF EntryTableRec]; EntryTableRec: TYPE = RECORD [ cumEntSize: CARDINAL, -- cumulative sizes of entries up to and including this one heapPos: HeapIndex]; -- offset of this entry in heap Heap: TYPE = RECORD [ length: HeapIndex, entries: SEQUENCE maxLength: HeapIndex OF EntryOrdinal]; HeapIndex: TYPE = [0..maxMaxRecordsPerPage]; -- There are at most one page's worth of entries in the heap at any given time <> <> Compare: PROC [tree: Tree, key: Key, entry: Entry] RETURNS [Comparison] = INLINE { RETURN [tree.repPrim.compare[key: key, entry: entry]] }; CompareEntries: PROC [tree: Tree, entry1, entry2: Entry] RETURNS [Comparison] = INLINE { RETURN [tree.repPrim.compareEntries[entry1: entry1, entry2: entry2]] }; EntrySize: PROC [tree: Tree, entry: Entry] RETURNS [words: EntSize] = INLINE { RETURN [tree.repPrim.entrySize[entry]] }; EntryFromRecord: PROC [tree: Tree, record: Record] RETURNS [entry: Entry] = INLINE { RETURN [tree.repPrim.entryFromRecord[record]] }; NewRecordFromEntry: PROC [tree: Tree, entry: Entry] RETURNS [record: Record] = INLINE { RETURN [tree.repPrim.newRecordFromEntry[entry]] }; ReferencePage: PROC [tree: Tree, number: PageNumber, type: ReferenceType _ read] RETURNS [ptr: PagePtr] = INLINE { RETURN [tree.storPrim.referencePage[storage: tree.storage, number: number, type: type]] }; ReleasePage: PROC [tree: Tree, number: PageNumber, update: UpdateState _ unchanged] = INLINE { tree.storPrim.releasePage[storage: tree.storage, number: number, update: update] }; <> BTreeEntrySize: PROC [tree: Tree, bte: LONG POINTER TO BTreeEntry] RETURNS [words: EntSize] = INLINE <> { RETURN [entryOverhead+tree.EntrySize[@bte.entry]] }; PathEntryLE: PROC [tree: Tree, key: Key, pathStk: PathStk, useExistingPath: BOOL _ FALSE] RETURNS [equal: BOOL, depth: PathStkIndex]; <> ReferenceStack: PROC [tree: Tree, pathStk: PathStk, type: ReferenceType _ read] RETURNS [pse: LONG POINTER TO PathStkEntry, ptr: PagePtr]; <> BackUpOneEntry: PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry]; <> RepairOffsets: PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry]; <> PathToMaxDescendant: PROC [tree: Tree, pathStk: PathStk, page: PageNumber]; <> AdjustTreeState: PROC [tree: Tree, update: UpdateState, deltaEntryCount: INTEGER]; <> WriteStatePage: PROC [tree: Tree, update: UpdateState _ unchanged]; <> InsertRecords: PROC [tree: Tree, pathStk: PathStk]; <> MakeEntSeqRecord: PROC [entSeq: LONG POINTER TO BTreeEntry, length: CARDINAL] RETURNS [esr: REF EntSeqRecord]; <> AppendEntSeqRecord: PROC [pse: LONG POINTER TO PathStkEntry, esr: REF EntSeqRecord]; <> PushEntSeqRecord: PROC [pse: LONG POINTER TO PathStkEntry, esr: REF EntSeqRecord]; <> AssignRefESR: PROC [ptr: LONG POINTER TO REF EntSeqRecord, ref: REF EntSeqRecord] = INLINE { LOOPHOLE[ptr, REF REF EntSeqRecord]^ _ ref }; <> RemoveEntry: PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry, ignoreESL: BOOL _ FALSE] RETURNS [esr: REF EntSeqRecord, grPage: PageNumber]; <> BackUpAndRemoveEntry: PROC [tree: Tree, pse: LONG POINTER TO PathStkEntry] RETURNS [esr: REF EntSeqRecord, grPage: PageNumber]; <> AllocatePage: PROC [tree: Tree] RETURNS [number: PageNumber]; <> FreePage: PROC [tree: Tree, number: PageNumber]; <> LongMove: PROC [to, from: LONG POINTER, nWords: CARDINAL]; <> Lock: PROC [tree: Tree, mode: LockMode, checkState: BOOL _ TRUE]; <> LockMode: TYPE = {read, update}; Unlock: PROC [tree: Tree]; <> GetHeapAndTable: PROC [tree: Tree, pathStk: PathStk]; <> ReturnHeapAndTable: PROC [tree: Tree, pathStk: PathStk]; <> GetDefaultPathStk: PROC [tree: Tree] RETURNS [pathStk: PathStk]; <> ReturnDefaultPathStk: PROC [tree: Tree, pathStk: PathStk]; <> <> Bug: ERROR [type: BugType]; BugType: TYPE = {depositESL, entriesLeftOver, mcCreightWasWrong, newRootOverflow, pageAlreadyFree, pageNotFree, tooFewEntries, tooManyEntriesInPage, treeNotLocked, twoBrothersNotEnough}; END.