<> <> <> <> <<1. Validate's repair of the entryCount is slightly flakey since the tree is unlocked between the EnumerateEntries that counts the entries and the setting of the entryCount.>> DIRECTORY BTree, BTreeInternal, File USING [wordsPerPage], PrincOpsUtils USING [BITSHIFT, LongCopy, LongZero]; BTreeRead: MONITOR LOCKS tree USING tree: Tree IMPORTS BTreeInternal, PrincOpsUtils EXPORTS BTree, BTreeInternal = BEGIN OPEN BTree, BTreeInternal; <> Tree: TYPE = REF TreeObject; TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject; PathStk: TYPE = REF PathStkObject; PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject; New: PUBLIC SAFE PROCEDURE [repPrim: RepresentationPrimitives, storPrim: PageStoragePrimitives, minEntrySize: CARDINAL _ 1, initialState: State[closed..suspended] _ closed] RETURNS [tree: Tree] = CHECKED BEGIN tree _ NEW [TreeObject _ [state: [], repPrim: repPrim, storPrim: storPrim, minEntrySize: minEntrySize, objectState: initialState]]; END; Open: PUBLIC SAFE PROCEDURE [tree: Tree, storage: PageStorage, pageSize: PageSize _ File.wordsPerPage, initialize: BOOLEAN _ FALSE, maintainRecomputableState: BOOLEAN _ TRUE] = TRUSTED BEGIN DO -- first ensure that it's not already open tree.Lock[update, FALSE]; IF tree.objectState#open THEN EXIT; tree.Unlock[]; SetState[tree, closed]; ENDLOOP; tree.state _ [pageSize: pageSize]; tree.maxFreeWords _ pageSize-pageOverhead; tree.maxRecordsPerPage _ tree.maxFreeWords/(tree.minEntrySize+entryOverhead); tree.awfullyFull _ (9*tree.maxFreeWords)/10; tree.prettyFull _ (2*tree.maxFreeWords)/3; tree.fairlyFull _ tree.maxFreeWords/2; tree.breathingSpace _ tree.maxFreeWords-tree.awfullyFull; tree.storage _ storage; tree.maintainRecomputableState _ maintainRecomputableState; tree.id _ (treeID _ treeID+1); -- this doesn't assign a reliably unique ID, since treeID is not protected by any monitor; but it doesn't really matter since the ID is merely protecting against client blunders anyway. BEGIN ENABLE UNWIND => tree.Unlock[]; IF initialize THEN BEGIN statePtr: LONG POINTER TO TreeState _ tree.ReferencePage[statePage, new]; PrincOpsUtils.LongZero[statePtr, pageSize]; IF ~maintainRecomputableState THEN tree.state.entryCount _ LAST[LONG CARDINAL]; statePtr^ _ tree.state; tree.ReleasePage[statePage, endOfUpdate]; END ELSE BEGIN statePtr: LONG POINTER TO TreeState _ tree.ReferencePage[statePage, read]; IF statePtr.seal#sealValue THEN ERROR Error[badSeal]; IF statePtr.pageSize#pageSize THEN ERROR Error[wrongPageSize]; tree.state _ statePtr^; tree.ReleasePage[statePage]; IF tree.state.updateInProgress THEN SIGNAL UpdateInProgress; END; tree.state.updateInProgress _ FALSE; END; tree.objectState _ open; tree.Unlock[]; END; SetState: PUBLIC SAFE PROCEDURE [tree: Tree, state: State[closed..suspended]] = TRUSTED BEGIN DO WaitUnlocked: ENTRY PROCEDURE [tree: Tree] = INLINE {IF tree.longUpdate THEN WAIT tree.unlocked}; tree.Lock[update, FALSE]; IF tree.objectState#open OR ~tree.longUpdate THEN EXIT; tree.Unlock[]; WaitUnlocked[tree]; -- this actually wakes up every time the tree is unlocked, including the call to Unlock from SetUpdateInProgress ENDLOOP; <> tree.objectState _ state; tree.storage _ NIL; tree.offsetTable _ NIL; tree.defaultPathStk _ NIL; tree.entryTable _ NIL; tree.heap _ NIL; tree.Unlock[]; END; GetState: PUBLIC ENTRY SAFE PROCEDURE [tree: Tree] RETURNS [state: State, entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL, storage: PageStorage] = CHECKED { RETURN [state: tree.objectState, entryCount: tree.state.entryCount, greatestPage: tree.state.greatestPage, depth: tree.state.depth, storage: tree.storage] }; Validate: PUBLIC SAFE PROCEDURE [tree: Tree] = TRUSTED BEGIN CheckPair: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = BEGIN size: CARDINAL = tree.EntrySize[entry]; IF size+entryOverhead > tree.maxFreeWords THEN ERROR Error[entrySizesWrong]; entryCount _ entryCount+1; IF firstEntry THEN firstEntry _ FALSE ELSE IF tree.CompareEntries[prevEntry, entry]#less THEN ERROR Error[entriesOutOfOrder]; PrincOpsUtils.LongCopy[to: prevEntry, from: entry, nwords: size]; RETURN [TRUE]; END; -- CheckPair PrevRecord: TYPE = RECORD [entry: SEQUENCE maxLength: [0..LAST[PageSize]] OF WORD]; prevRecord: REF PrevRecord = NEW[PrevRecord[tree.state.pageSize-reservedWordsPerPage]]; prevEntry: Entry = BASE[DESCRIPTOR[prevRecord.entry]]; entryCount: LONG CARDINAL _ 0; firstEntry: BOOLEAN _ TRUE; [] _ EnumerateEntries[tree: tree, key: NIL, Proc: CheckPair]; IF tree.maintainRecomputableState AND entryCount#tree.state.entryCount THEN BEGIN tree.Lock[update]; tree.state.entryCount _ entryCount; tree.WriteStatePage[endOfUpdate]; tree.Unlock[]; END; END; ReadRecord: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [record: Record] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] = { record _ IF entry#NIL THEN tree.NewRecordFromEntry[entry] ELSE NIL }; ReadEntry[tree: tree, key: key, relation: relation, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; EnumerateRecords: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: PROCEDURE [record: Record] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = TRUSTED BEGIN EntryProc: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = { RETURN [Proc[tree.NewRecordFromEntry[entry]]] }; exhausted _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc]; END; ReadEntry: PUBLIC PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] = BEGIN SELECT relation FROM less, lessEqual, equal => BEGIN pathStkWasNil: BOOLEAN _ pathStk=NIL; tree.Lock[read]; IF pathStkWasNil THEN BEGIN IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk _ tree.GetDefaultPathStk[]; END; <> BEGIN ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] }; equal: BOOLEAN; [equal: equal] _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; IF equal AND relation=less THEN [] _ PathToPreviousEntry[tree, pathStk]; IF pathStk.top=0 OR (~equal AND relation=equal) THEN Proc[NIL] ELSE BEGIN pagePtr: BTreePagePtr; pse: LONG POINTER TO PathStkEntry; [ptr: pagePtr, pse: pse] _ tree.ReferenceStack[pathStk]; Proc[@pagePtr[pse.lastOffset].entry ! UNWIND => tree.ReleasePage[pse.pageNumber]]; tree.ReleasePage[pse.pageNumber]; END; END; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; END; greaterEqual, greater => BEGIN CallWhenRelationSatisfied: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] = BEGIN IF key=NIL OR tree.Compare[key, entry] <= maxComparison THEN {Proc[entry]; RETURN [FALSE]} ELSE RETURN [TRUE]; END; maxComparison: Comparison _ IF relation=greaterEqual THEN equal ELSE less; exhausted: BOOLEAN _ EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallWhenRelationSatisfied]; IF exhausted THEN Proc[NIL]; END; ENDCASE => ERROR; END; EnumerateEntries: PUBLIC PROCEDURE [tree: Tree, key: Key, relation: Relation _ equal, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = BEGIN pathStkWasNil: BOOLEAN _ pathStk=NIL; tree.Lock[read]; IF pathStkWasNil THEN BEGIN IF useExistingPath THEN ERROR Error[nilPathStk]; pathStk _ tree.GetDefaultPathStk[]; END; <> BEGIN ENABLE UNWIND => { IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] }; leafStkTop: PathStkIndex; pse: LONG POINTER TO PathStkEntry; pagePtr: BTreePagePtr _ NIL; skipFirstEntry: BOOLEAN _ FALSE; equal: BOOLEAN; [equal: equal, depth: leafStkTop] _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; IF pathStk.top=0 THEN BEGIN -- key is less than any existing entry in the tree. Set PathStk to first record in leftmost leaf page. IF leafStkTop=0 THEN GOTO exhausted; -- empty tree pathStk.top _ leafStkTop; pathStk.path[leafStkTop].lastOffset _ entry1Offset; END ELSE SELECT relation FROM less => IF equal AND ~PathToPreviousEntry[tree, pathStk] THEN {pathStk.top _ leafStkTop; pathStk.path[leafStkTop].lastOffset _ entry1Offset}; lessEqual => NULL; equal, greaterEqual => skipFirstEntry _ ~equal; greater => skipFirstEntry _ TRUE; ENDCASE; exhausted _ FALSE; pse _ @pathStk.path[pathStk.top]; DO offset: PageOffset _ pse.lastOffset; endOffset: PageOffset; IF pagePtr=NIL THEN BEGIN pagePtr _ tree.ReferencePage[pse.pageNumber]; endOffset _ nilOffset+(tree.state.pageSize-pagePtr.freeWords); END; IF offset>=endOffset THEN BEGIN -- ran off end of page. Pop up a level and do the next entry in the father page tree.ReleasePage[pse.pageNumber]; IF offset>endOffset THEN ERROR Error[entrySizesWrong]; pagePtr _ NIL; IF (pathStk.top _ pathStk.top-1) = 0 THEN BEGIN -- ran off end of tree. PathStk is no longer valid. pathStk.version _ LAST[LONG CARDINAL]; GOTO exhausted; END; pse _ pse - SIZE[PathStkEntry]; END ELSE BEGIN -- enumerate this entry nxtPgNo: PageNumber _ pagePtr[offset].grPage; pse.offset _ offset + tree.BTreeEntrySize[@pagePtr[offset]]; IF skipFirstEntry THEN skipFirstEntry _ FALSE ELSE IF ~Proc[@pagePtr[offset].entry ! UNWIND => tree.ReleasePage[pse.pageNumber]] THEN EXIT; WHILE nxtPgNo#nilPage DO <> tree.ReleasePage[pse.pageNumber]; pathStk.top _ pathStk.top+1; pse _ pse + SIZE[PathStkEntry]; pagePtr _ tree.ReferencePage[nxtPgNo]; pse.pageNumber _ nxtPgNo; pse.nextToLastOffset _ nilOffset; pse.lastOffset _ entry0Offset; pse.offset _ entry1Offset; endOffset _ nilOffset+(tree.state.pageSize-pagePtr.freeWords); nxtPgNo _ pagePtr.minPage; ENDLOOP; END; pse.nextToLastOffset _ pse.lastOffset; pse.lastOffset _ pse.offset; ENDLOOP; IF pagePtr#NIL THEN tree.ReleasePage[pse.pageNumber]; EXITS exhausted => exhausted _ TRUE; END; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; END; SalvageEntries: PUBLIC PROCEDURE [tree: Tree, Proc: UNSAFE PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN]] RETURNS [exhausted: BOOLEAN] = BEGIN tree.Lock[read]; FOR page: PageNumber IN [statePage+1 .. tree.state.greatestPage] DO ENABLE UNWIND => tree.Unlock[]; pagePtr: BTreePagePtr = tree.ReferencePage[page]; IF pagePtr.freeWords IN [0 .. CARDINAL[tree.state.pageSize-pageOverhead]] THEN BEGIN offset: PageOffset _ entry1Offset; endOffset: PageOffset = nilOffset+(tree.state.pageSize-pagePtr.freeWords); WHILE offsetendOffset THEN EXIT; IF ~Proc[@pagePtr[offset].entry] THEN GOTO aborted; offset _ offset+entSize; ENDLOOP; END; tree.ReleasePage[page]; REPEAT aborted => exhausted _ FALSE; FINISHED => exhausted _ TRUE; ENDLOOP; tree.Unlock[]; END; NewPathStk: PUBLIC SAFE PROCEDURE RETURNS [pathStk: PathStk] = CHECKED BEGIN pathStk _ NEW[PathStkObject]; pathStk.version _ LAST[LONG CARDINAL]; -- not valid END; <> PathEntryLE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk, useExistingPath: BOOLEAN _ FALSE] RETURNS [equal: BOOLEAN, depth: PathStkIndex] = BEGIN BinSearchPage: PROCEDURE RETURNS [firstG: EntryOrdinal] = <> BEGIN firstBadOffset: PageOffset = nilOffset + (tree.state.pageSize - pagePtr.freeWords); midOffset: PageOffset _ PrincOpsUtils.BITSHIFT[firstBadOffset, -1]; curOffset: PageOffset _ entry1Offset; l, r: EntryOrdinal _ 2; <> IF key#NIL THEN DO IF curOffset>=midOffset THEN BEGIN IF curOffset>=firstBadOffset OR tree.Compare[key, @pagePtr[curOffset].entry] = less THEN EXIT; midOffset _ firstBadOffset; l _ r; END; curOffset _ curOffset + tree.BTreeEntrySize[@pagePtr[curOffset]]; r _ r+1; offsetTable[r] _ curOffset; ENDLOOP; IF curOffset>firstBadOffset THEN ERROR Error[entrySizesWrong]; <> WHILE l r _ m; equal => {equal _ TRUE; RETURN [m+1]}; greater => l _ m+1; ENDCASE; ENDLOOP; RETURN [r]; END; -- BinSearchPage pse: LONG POINTER TO PathStkEntry; offsetTable: OffsetTable; curPage: PageNumber; pagePtr: BTreePagePtr; equal _ FALSE; IF useExistingPath AND pathStk.treeID=tree.id AND pathStk.version=tree.version AND key#NIL THEN BEGIN -- supplied PathStk is still valid. See if it is for the correct key. depth _ pathStk.top; IF depth=0 THEN GOTO dontUse; -- who knows whether this is the min key or not? WHILE pathStk.path[depth].leastSon # nilPage DO depth _ depth+1; ENDLOOP; [pse: pse, ptr: pagePtr] _ tree.ReferenceStack[pathStk]; SELECT tree.Compare[key, @pagePtr[pse.lastOffset].entry] FROM less => useExistingPath _ FALSE; -- wrong key equal => equal _ TRUE; -- correct key greater => BEGIN IF depth=pathStk.top AND pse.offset < nilOffset+(tree.state.pageSize-pagePtr.freeWords) AND tree.Compare[key, @pagePtr[pse.offset].entry]=less THEN NULL -- key falls between this entry and next; ok ELSE useExistingPath _ FALSE; -- wrong key, or too hard to decide END; ENDCASE; tree.ReleasePage[pse.pageNumber]; IF useExistingPath THEN RETURN; EXITS dontUse => NULL; END; <> pathStk.top _ 0; pathStk.path[0] _ []; offsetTable _ GetOffsetTable[tree]; offsetTable[0] _ nilOffset; offsetTable[1] _ entry0Offset; offsetTable[2] _ entry1Offset; depth _ 0; pse _ @pathStk.path[0]; curPage _ tree.state.rootPage; WHILE curPage#nilPage DO firstG: EntryOrdinal; pagePtr _ tree.ReferencePage[curPage]; depth _ depth+1; pse _ pse+SIZE[PathStkEntry]; pse.pageNumber _ curPage; firstG _ BinSearchPage[ ! UNWIND => {tree.ReleasePage[curPage]; ReturnOffsetTable[tree, offsetTable]}]; pse.offset _ offsetTable[firstG]; pse.lastOffset _ offsetTable[firstG-1]; pse.nextToLastOffset _ offsetTable[firstG-2]; pse.leastSon _ pagePtr.minPage; IF firstG>2 THEN pathStk.top _ depth; -- real entry in this page AssignRefESR[@pse.eslFront, NIL]; AssignRefESR[@pse.eslRear, NIL]; curPage _ pagePtr[pse.lastOffset].grPage; tree.ReleasePage[pse.pageNumber]; ENDLOOP; pathStk.treeID _ tree.id; pathStk.version _ tree.version; ReturnOffsetTable[tree, offsetTable]; END; ReferenceStack: PUBLIC PROCEDURE [tree: Tree, pathStk: PathStk, type: ReferenceType _ read] RETURNS [pse: LONG POINTER TO PathStkEntry, ptr: PagePtr] = BEGIN pse _ @pathStk.path[pathStk.top]; ptr _ tree.ReferencePage[pse.pageNumber, type]; END; BackUpOneEntry: PUBLIC PROCEDURE [tree: Tree, pse: LONG POINTER TO PathStkEntry] = BEGIN tree.RepairOffsets[pse]; pse.offset _ pse.lastOffset; tree.RepairOffsets[pse]; END; RepairOffsets: PUBLIC PROCEDURE [tree: Tree, pse: LONG POINTER TO PathStkEntry] = BEGIN CheckProgression: PROCEDURE [offset1, offset2: PageOffset] RETURNS [ok: BOOLEAN] = BEGIN RETURN [SELECT TRUE FROM offset2=entry0Offset => offset1=nilOffset, offset2=entry1Offset => offset1=entry0Offset, offset1>=offset2 => FALSE, ENDCASE => offset1+tree.BTreeEntrySize[@pagePtr[offset1]] = offset2]; END; -- CheckProgression pagePtr: BTreePagePtr = tree.ReferencePage[pse.pageNumber]; IF ~(CheckProgression[pse.lastOffset, pse.offset] AND CheckProgression[pse.nextToLastOffset, pse.lastOffset]) THEN BEGIN newOffset: PageOffset _ entry1Offset; lastOffset: PageOffset _ entry0Offset; nextToLastOffset: PageOffset _ nilOffset; WHILE newOffset#pse.offset DO nextToLastOffset _ lastOffset; lastOffset _ newOffset; newOffset _ newOffset+tree.BTreeEntrySize[@pagePtr[newOffset]]; ENDLOOP; pse.lastOffset _ lastOffset; pse.nextToLastOffset _ nextToLastOffset; END; tree.ReleasePage[pse.pageNumber]; END; PathToMaxDescendant: PUBLIC PROCEDURE [tree: Tree, pathStk: PathStk, page: PageNumber] = BEGIN pse: LONG POINTER TO PathStkEntry; pagePtr: BTreePagePtr; WHILE page#nilPage DO pathStk.top _ pathStk.top+1; pse _ @pathStk.path[pathStk.top]; pse.pageNumber _ page; pagePtr _ tree.ReferencePage[page]; pse.offset _ nilOffset+(tree.state.pageSize-pagePtr.freeWords); pse.lastOffset _ entry1Offset; pse.nextToLastOffset _ entry0Offset; tree.RepairOffsets[pse]; AssignRefESR[@pse.eslFront, NIL]; AssignRefESR[@pse.eslRear, NIL]; pse.leastSon _ nilPage; page _ pagePtr[pse.lastOffset].grPage; tree.ReleasePage[pse.pageNumber]; ENDLOOP; END; WriteStatePage: PUBLIC PROCEDURE [tree: Tree, update: UpdateState _ unchanged] = BEGIN statePtr: LONG POINTER TO TreeState = tree.ReferencePage[statePage, write]; statePtr^ _ tree.state; tree.ReleasePage[statePage, update]; END; Lock: PUBLIC ENTRY PROCEDURE [tree: Tree, mode: LockMode, checkState: BOOLEAN _ TRUE] = BEGIN DO SELECT tree.objectState FROM closed => IF checkState THEN RETURN WITH ERROR Error[closed]; suspended => IF checkState THEN {WAIT tree.unlocked; LOOP}; open => NULL ENDCASE; SELECT mode FROM read => IF tree.lockCount>=0 THEN {tree.lockCount _ tree.lockCount+1; EXIT}; update => IF tree.lockCount=0 THEN {tree.lockCount _ -1; EXIT}; ENDCASE; WAIT tree.unlocked; -- wait for tree to be unlocked ENDLOOP; END; Unlock: PUBLIC ENTRY PROCEDURE [tree: Tree] = BEGIN IF tree.lockCount=0 THEN ERROR Bug[treeNotLocked]; tree.lockCount _ MAX[tree.lockCount-1, 0]; IF tree.lockCount=0 THEN BROADCAST tree.unlocked; -- BROADCAST, not NOTIFY, because releasing a write lock might make multiple readers eligible to enter simultaneously. END; GetHeapAndTable: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = BEGIN pathStk.heap _ tree.heap; tree.heap _ NIL; pathStk.entryTable _ tree.entryTable; tree.entryTable _ NIL; IF pathStk.heap#NIL THEN heapsReused _ heapsReused+1 ELSE BEGIN pathStk.heap _ NEW[Heap[tree.maxRecordsPerPage+1]]; -- heap holds at most one page's worth of entries at any given time pathStk.entryTable _ NEW[EntryTable[3*tree.maxRecordsPerPage+1]]; -- may have to index scroll containing up to 3 pages' worth of entries heapsCreated _ heapsCreated+1; END; END; ReturnHeapAndTable: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = BEGIN IF tree.heap=NIL THEN { tree.heap _ pathStk.heap; tree.entryTable _ pathStk.entryTable }; pathStk.heap _ NIL; pathStk.entryTable _ NIL; END; GetDefaultPathStk: PUBLIC ENTRY PROCEDURE [tree: Tree] RETURNS [pathStk: PathStk] = BEGIN pathStk _ tree.defaultPathStk; tree.defaultPathStk _ NIL; IF pathStk=NIL THEN { pathStk _ NewPathStk[]; pathStksCreated _ pathStksCreated+1 } ELSE { pathStk.version _ LAST [LONG CARDINAL]; pathStksReused _ pathStksReused+1 }; END; ReturnDefaultPathStk: PUBLIC ENTRY PROCEDURE [tree: Tree, pathStk: PathStk] = { IF tree.defaultPathStk=NIL THEN tree.defaultPathStk _ pathStk }; Error: PUBLIC SAFE ERROR [reason: Reason] = CODE; UpdateInProgress: PUBLIC SAFE SIGNAL = CODE; Bug: PUBLIC ERROR [type: BugType] = CODE; <> PathToPreviousEntry: PROCEDURE [tree: Tree, pathStk: PathStk] RETURNS [ok: BOOLEAN] = <> BEGIN pagePtr: BTreePagePtr; pse: LONG POINTER TO PathStkEntry _ @pathStk.path[pathStk.top]; IF pathStk.top=0 THEN RETURN [FALSE]; tree.BackUpOneEntry[pse]; [ptr: pagePtr, pse: pse] _ tree.ReferenceStack[pathStk]; IF pagePtr[pse.lastOffset].grPage=nilPage THEN BEGIN -- this is a leaf page WHILE pse.lastOffset> BEGIN offsetTable _ tree.offsetTable; tree.offsetTable _ NIL; IF offsetTable#NIL THEN offsetTablesReused _ offsetTablesReused+1 ELSE BEGIN offsetTable _ NEW[OffsetTableObject[tree.maxRecordsPerPage+2]]; offsetTablesCreated _ offsetTablesCreated+1; END; END; ReturnOffsetTable: ENTRY PROCEDURE [tree: Tree, offsetTable: OffsetTable] = <> { IF tree.offsetTable=NIL THEN tree.offsetTable _ offsetTable }; treeID: CARDINAL _ 0; offsetTablesReused, offsetTablesCreated: LONG CARDINAL _ 0; heapsReused, heapsCreated: LONG CARDINAL _ 0; pathStksReused, pathStksCreated: LONG CARDINAL _ 0; END.