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, storage: PageStorage] =
CHECKED
{ RETURN [entryCount: tree.state.entryCount, greatestPage: tree.state.greatestPage, depth: tree.state.depth, storage: tree.storage] };
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;
ReadRecordL:
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 };
ReadEntryL[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;
ReadEntryL:
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[] };
pagePtr: BTreePagePtr;
pse: LONG POINTER TO PathStkEntry;
[] ← tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath];
BEGIN -- More extra nesting so the EXITS are in the scope of the ENABLE
IF pathStk.top=0 THEN GOTO nil;
[ptr: pagePtr, pse: pse] ← tree.ReferenceStack[pathStk];
IF tree.Compare[key, @pagePtr[pse.lastOffset].entry]#greater
THEN
BEGIN -- need to back up to previous entry
tree.BackUpOneEntry[pse];
IF pagePtr[pse.lastOffset].grPage=nilPage
THEN
BEGIN -- this is a leaf page
WHILE pse.lastOffset<entry1Offset
DO -- hit beginning of current page: previous entry is left father
tree.ReleasePage[pse.pageNumber];
pathStk.top ← pathStk.top-1;
IF pathStk.top=0 THEN GOTO nil;
[ptr: pagePtr, pse: pse] ← tree.ReferenceStack[pathStk];
ENDLOOP;
END
ELSE BEGIN
-- this is not a leaf page: previous entry is rightmost left son
page: PageNumber ← pagePtr[pse.lastOffset].grPage;
tree.ReleasePage[pse.pageNumber];
tree.PathToMaxDescendant[pathStk: pathStk, page: pagePtr[pse.lastOffset].grPage];
[ptr: pagePtr, pse: pse] ← tree.ReferenceStack[pathStk];
END;
END;
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;
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;
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;
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] =
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;