-- BTreeRead.mesa
-- This contains everything you need to open and read BTrees.
-- Last Edited by: Taft, May 3, 1983 5:15 pm
-- Loose ends:
-- 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,
Environment USING [wordsPerPage],
Inline USING [BITSHIFT, LongCOPY],
SafeStorage USING [NewZone];
BTreeRead: MONITOR LOCKS tree USING tree: Tree
IMPORTS BTreeInternal, Inline, SafeStorage
EXPORTS BTree, BTreeInternal
= BEGIN OPEN BTree, BTreeInternal;
-- BTree.
Tree: TYPE = REF TreeObject;
TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject;
PathStk: TYPE = REF PathStkObject;
PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject;
Open: PUBLIC SAFE PROCEDURE [repPrim: RepresentationPrimitives, storage: PageStorage, storPrim: PageStoragePrimitives, pageSize: PageSize ← Environment.wordsPerPage, minEntrySize: CARDINAL ← 1, initialize: BOOLEAN ← FALSE, maintainRecomputableState: BOOLEAN ← TRUE] RETURNS [tree: Tree] = TRUSTED
BEGIN
tree ← staticZone.NEW [TreeObject ← [state: [pageSize: pageSize], storage: storage, repPrim: repPrim, minEntrySize: minEntrySize, storPrim: storPrim, maintainRecomputableState: maintainRecomputableState]];
tree.maxFreeWords ← pageSize-pageOverhead;
tree.maxRecordsPerPage ← tree.maxFreeWords/(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.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.
tree.Lock[IF initialize THEN update ELSE read];
BEGIN ENABLE UNWIND => tree.Unlock[];
IF initialize THEN
BEGIN
statePtr: LONG POINTER TO TreeState ← tree.ReferencePage[statePage, new];
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.Unlock[];
END;
ReOpen: PUBLIC SAFE PROCEDURE [tree: Tree] = TRUSTED
BEGIN
tree.Lock[update];
BEGIN ENABLE UNWIND => tree.Unlock[];
statePtr: LONG POINTER TO TreeState ← tree.ReferencePage[statePage, read];
tree.state ← statePtr^;
tree.ReleasePage[statePage];
tree.version ← tree.version+1; -- this invalidates any extant PathStks
END;
tree.Unlock[];
END;
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];
Inline.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 = tempZone.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;
GetState: PUBLIC SAFE PROCEDURE [tree: Tree] RETURNS [entryCount: LONG CARDINAL, greatestPage: PageNumber, depth: CARDINAL] = CHECKED
{ RETURN [entryCount: tree.state.entryCount, greatestPage: tree.state.greatestPage, depth: tree.state.depth] };
ReadRecord: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, 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, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
END;
ReadRecordLE: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, 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 };
ReadEntryLE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
END;
ReadRecordGE: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, 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 };
ReadEntryGE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
END;
ReadRecordG: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, 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 };
ReadEntryG[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: EntryProc];
END;
EnumerateRecords: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, 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, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] =
BEGIN
CallIfEqual: PROCEDURE [entry: Entry] =
BEGIN
IF key#NIL AND entry#NIL AND tree.Compare[key, entry] = equal THEN Proc[entry]
ELSE Proc[NIL];
END;
ReadEntryLE[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallIfEqual];
END;
ReadEntryLE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] =
BEGIN
pathStkWasNil: BOOLEAN ← pathStk=NIL;
tree.Lock[read];
IF pathStkWasNil THEN
BEGIN
IF useExistingPath THEN ERROR Error[nilPathStk];
pathStk ← tree.GetDefaultPathStk[];
END;
-- Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
BEGIN ENABLE UNWIND =>
{ IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] };
[] ← tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath];
IF pathStk.top=0 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;
ReadEntryGE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] =
BEGIN
CallWhenGE: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] =
BEGIN
IF key=NIL OR tree.Compare[key, entry] <= equal THEN { Proc[entry]; RETURN [FALSE] }
ELSE RETURN [TRUE];
END;
exhausted: BOOLEAN ← EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallWhenGE];
IF exhausted THEN Proc[NIL];
END;
ReadEntryG: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk ← NIL, useExistingPath: BOOLEAN ← FALSE, Proc: UNSAFE PROCEDURE [entry: Entry]] =
BEGIN
CallWhenG: PROCEDURE [entry: Entry] RETURNS [continue: BOOLEAN] =
BEGIN
IF key=NIL OR tree.Compare[key, entry] = less THEN { Proc[entry]; RETURN [FALSE] }
ELSE RETURN [TRUE];
END;
exhausted: BOOLEAN ← EnumerateEntries[tree: tree, key: key, pathStk: pathStk, useExistingPath: useExistingPath, Proc: CallWhenG];
IF exhausted THEN Proc[NIL];
END;
EnumerateEntries: PUBLIC PROCEDURE [tree: Tree, key: Key, 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;
-- Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
BEGIN ENABLE UNWIND =>
{ IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] };
leafStkTop: PathStkIndex;
pse: LONG POINTER TO PathStkEntry;
pagePtr: BTreePagePtr ← NIL;
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;
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 ~Proc[@pagePtr[offset].entry !
UNWIND => tree.ReleasePage[pse.pageNumber]] THEN EXIT;
WHILE nxtPgNo#nilPage DO
-- In a non-leaf page, find the leftmost right descendant of the entry we just did.
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;
NewPathStk: PUBLIC SAFE PROCEDURE RETURNS [pathStk: PathStk] = CHECKED
BEGIN
pathStk ← staticZone.NEW[PathStkObject];
pathStk.version ← LAST[LONG CARDINAL]; -- not valid
END;
-- BTreeInternal.
PathEntryLE: PUBLIC PROCEDURE [tree: Tree, key: Key, pathStk: PathStk, useExistingPath: BOOLEAN ← FALSE] RETURNS [depth: PathStkIndex] =
BEGIN
BinSearchPage: PROCEDURE RETURNS [firstG: EntryOrdinal] =
-- Returns an index r such that offsetTable[r] is the offset of the first entry strictly greater than key, and fills in offsetTable[2] through offsetTable[r] with the offsets of all entries up to and including that one.
BEGIN
firstBadOffset: PageOffset = nilOffset + (tree.state.pageSize - pagePtr.freeWords);
midOffset: PageOffset ← Inline.BITSHIFT[firstBadOffset, -1];
curOffset: PageOffset ← entry1Offset;
l, r: EntryOrdinal ← 2;
-- Scan records linearly and build offsetTable until half the in-use portion of the BTree page has been examined. Then do one key comparison to detemine which half of the page to direct our attention to, and build the rest of offsetTable only if necessary. On the average this saves 25% of the work of building offsetTables, and costs no extra comparison since the first comparison would examine a middle record anyway (not necessarily the same one).
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];
-- At this point, offsetTable[r] is the offset of the first non-entry, which we assume to have an infinite key (which we shall never test). We shall leave r pointing at the offset of the first entry strictly greater than key.
WHILE l<r DO
m: EntryOrdinal ← Inline.BITSHIFT[l+r, -1];
SELECT tree.Compare[key, @pagePtr[offsetTable[m]].entry] FROM
less => r ← m;
equal => RETURN [m+1];
greater => l ← m+1;
ENDCASE;
ENDLOOP;
RETURN [r];
END; -- BinSearchPage
pse: LONG POINTER TO PathStkEntry;
offsetTable: OffsetTable;
curPage: PageNumber;
pagePtr: BTreePagePtr;
IF useExistingPath AND pathStk.treeID=tree.id AND pathStk.version=tree.version 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 => NULL; -- 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;
-- Perform the normal BTree lookup
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;
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] =
BEGIN
SELECT mode FROM
read =>
BEGIN
WHILE tree.lockCount<0 DO WAIT tree.unlocked; ENDLOOP;
tree.lockCount ← tree.lockCount+1;
END;
update =>
BEGIN
WHILE tree.lockCount#0 DO WAIT tree.unlocked; ENDLOOP;
tree.lockCount ← -1;
END;
ENDCASE;
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 ← staticZone.NEW[Heap[tree.maxRecordsPerPage+1]]; -- heap holds at most one page's worth of entries at any given time
pathStk.entryTable ← staticZone.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;
staticZone: PUBLIC ZONE = SafeStorage.NewZone[sr: prefixed];
tempZone: PUBLIC ZONE = SafeStorage.NewZone[sr: prefixed];
Bug: PUBLIC ERROR [type: BugType] = CODE;
-- Private
GetOffsetTable: ENTRY PROCEDURE [tree: Tree] RETURNS [offsetTable: OffsetTable] =
-- Obtains the OffsetTable associated with the BTree, if it is available; otherwise makes a new one.
BEGIN
offsetTable ← tree.offsetTable;
tree.offsetTable ← NIL;
IF offsetTable#NIL THEN offsetTablesReused ← offsetTablesReused+1
ELSE BEGIN
offsetTable ← staticZone.NEW[OffsetTableObject[tree.maxRecordsPerPage+2]];
offsetTablesCreated ← offsetTablesCreated+1;
END;
END;
ReturnOffsetTable: ENTRY PROCEDURE [tree: Tree, offsetTable: OffsetTable] =
-- Gives back the 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.