FatherMayNeedWork:
PROCEDURE
RETURNS [needsWork:
BOOLEAN] =
BEGIN
This code assumes that the son page is pointed to by the fatherPage[lastOffset].grPage and that this condition is preserved by InsertRecords.
pagePtr, otherPtr: BTreePagePtr;
fatherPSE: LONG POINTER TO PathStkEntry;
fatherFreeWords: CARDINAL;
pse ← @pathStk.path[pathStk.top];
needsWork ← ChangeInFather[];
pagePtr ← tree.ReferencePage[pse.pageNumber];
IF pathStk.top=1
AND pagePtr.freeWords=tree.maxFreeWords
THEN
BEGIN -- Bye-bye, old root page!
tree.state.rootPage ← pagePtr.minPage;
tree.state.depth ← tree.state.depth-1;
tree.ReleasePage[pse.pageNumber];
tree.FreePage[pse.pageNumber];
RETURN [FALSE];
END;
IF pathStk.top=1
OR tree.maxFreeWords-pagePtr.freeWords >= tree.prettyFull
THEN
{ tree.ReleasePage[pse.pageNumber]; RETURN };
Page is not sufficiently full. Try to merge with left or right brother page. This is done by extracting the entire contents of this page (plus one father entry) into the ESL, freeing this page, repositioning to the brother page, and calling InsertRecords. Of course, there may not actually be enough space in the brother page(s), in which case InsertRecords will turn around and allocate a new page. But in any event the overall balance of the tree should be improved.
AppendEntSeqRecord[pse: pse, esr: MakeEntSeqRecord[entSeq: @pagePtr.entries, length: tree.maxFreeWords-pagePtr.freeWords]];
fatherPSE ← @pathStk.path[pathStk.top-1];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber];
fatherFreeWords ← otherPtr.freeWords;
tree.ReleasePage[fatherPSE.pageNumber];
IF fatherPSE.offset < nilOffset+(tree.state.pageSize-fatherFreeWords)
OR fatherPSE.eslFront#
NIL
THEN
BEGIN -- the current page has a right brother
rtBroPg: PageNumber;
esr: REF EntSeqRecord;
[esr: esr, grPage: rtBroPg] ← tree.RemoveEntry[fatherPSE];
AppendEntSeqRecord[pse: pse, esr: esr];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber, write];
IF otherPtr[fatherPSE.lastOffset].grPage # pse.pageNumber
THEN
ERROR Bug[mcCreightWasWrong];
otherPtr[fatherPSE.lastOffset].grPage ← rtBroPg;
tree.ReleasePage[fatherPSE.pageNumber];
otherPtr ← tree.ReferencePage[rtBroPg, write];
otherPtr.minPage ← pagePtr.minPage;
tree.ReleasePage[rtBroPg];
tree.ReleasePage[pse.pageNumber];
tree.FreePage[pse.pageNumber];
pse.pageNumber ← rtBroPg;
pse.offset ← entry1Offset;
pse.lastOffset ← entry0Offset;
pse.nextToLastOffset ← nilOffset;
END
ELSE
BEGIN
-- the current page surely has a left brother
esr: REF EntSeqRecord;
tree.ReleasePage[pse.pageNumber];
[esr: esr] ← tree.BackUpAndRemoveEntry[fatherPSE];
PushEntSeqRecord[pse: pse, esr: esr];
tree.FreePage[pse.pageNumber];
otherPtr ← tree.ReferencePage[fatherPSE.pageNumber];
pse.pageNumber ← otherPtr[fatherPSE.lastOffset].grPage;
tree.ReleasePage[fatherPSE.pageNumber];
pagePtr ← tree.ReferencePage[pse.pageNumber];
pse.offset ← nilOffset+(tree.state.pageSize-pagePtr.freeWords);
pse.lastOffset ← entry1Offset;
pse.nextToLastOffset ← entry0Offset;
tree.ReleasePage[pse.pageNumber];
tree.RepairOffsets[pse];
END;
[] ← ChangeInFather[];
RETURN [TRUE];
END; -- FatherMayNeedWork
Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)!
BEGIN
ENABLE
UNWIND =>
{ IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[] };
origStkTop: PathStkIndex;
pagePtr: BTreePagePtr ← NIL;
descendantPg: PageNumber;
simpleDelete: BOOLEAN; -- entry is "simple" to delete if it is in a leaf page and removing it will still leave the page at least "prettyFull".
equal: BOOLEAN;
[equal: equal] ← tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath];
IF ~equal
THEN
BEGIN
IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk];
tree.Unlock[];
RETURN [FALSE];
END;
origStkTop ← pathStk.top;
[ptr: pagePtr, pse: pse] ← tree.ReferenceStack[pathStk];
descendantPg ← pagePtr[pse.nextToLastOffset].grPage;
simpleDelete ← descendantPg=nilPage AND tree.maxFreeWords - (pagePtr.freeWords + tree.BTreeEntrySize[@pagePtr[pse.lastOffset]]) >= tree.prettyFull;
tree.ReleasePage[pse.pageNumber];
tree.version ← tree.version+1; -- invalidate existing PathStks that refer to this tree
Set up to delete the entry. If it is in a leaf page, we just remove it. If it is in an interior page, we must find a leaf entry to replace it with.
tree.BackUpOneEntry[pse]; -- pse.offset should index deletion victim
IF simpleDelete
THEN
BEGIN
tree.AdjustTreeState[update: unchanged, deltaEntryCount: -1];
pagePtr ← tree.ReferencePage[pse.pageNumber, write];
[] ← tree.RemoveEntry[pse];
tree.ReleasePage[pse.pageNumber, IF tree.longUpdate THEN unchanged ELSE endOfUpdate];
END
ELSE
BEGIN
tree.AdjustTreeState[update: startOfUpdate, deltaEntryCount: -1];
Deletion surrogate is one with greatest key less than victim's
tree.PathToMaxDescendant[pathStk: pathStk, page: descendantPg];
IF pathStk.top > origStkTop
THEN
BEGIN
dpse: LONG POINTER TO PathStkEntry = @pathStk.path[pathStk.top];
leafESR: REF EntSeqRecord;
[esr: leafESR] ← tree.BackUpAndRemoveEntry[dpse];
[grPage: leafESR.entSeqP.grPage] ← tree.RemoveEntry[pse]; -- discard returned ESR
AppendEntSeqRecord[pse: pse, esr: leafESR];
END
ELSE [] ← tree.RemoveEntry[pse];
tree.GetHeapAndTable[pathStk];
DO
needsWork:
BOOLEAN ← FatherMayNeedWork[ !
UNWIND => tree.ReturnHeapAndTable[pathStk]];
IF pathStk.top=0 OR (~needsWork AND pathStk.top<=origStkTop) THEN EXIT
ELSE pathStk.top ← pathStk.top-1;
ENDLOOP;
pathStk.top ← 0;
tree.ReturnHeapAndTable[pathStk];
tree.AdjustTreeState[update: endOfUpdate, deltaEntryCount: 0];
END;
END;