DIRECTORY BTree USING [Error, Key, PageNumber, ReferencePage, ReleasePage], BTreeInternal USING [AdjustTreeState, AppendEntSeqRecord, BackUpAndRemoveEntry, BackUpOneEntry, BTreeEntrySize, BTreePagePtr, Bug, entry0Offset, entry1Offset, EntSeqRecord, FreePage, GetDefaultPathStk, GetHeapAndTable, InsertRecords, Lock, MakeEntSeqRecord, nilOffset, nilPage, PathEntryLE, PathStk, PathStkEntry, PathStkIndex, PathStkObject, PathToMaxDescendant, PushEntSeqRecord, ReferencePage, ReferenceStack, ReleasePage, RemoveEntry, RepairOffsets, ReturnDefaultPathStk, ReturnHeapAndTable, Tree, TreeObject, Unlock]; BTreeDelete: PROGRAM IMPORTS BTree, BTreeInternal EXPORTS BTree = BEGIN OPEN BTree, BTreeInternal; Tree: TYPE = REF TreeObject; TreeObject: PUBLIC TYPE = BTreeInternal.TreeObject; PathStk: TYPE = REF PathStkObject; PathStkObject: PUBLIC TYPE = BTreeInternal.PathStkObject; DeleteKey: PUBLIC SAFE PROCEDURE [tree: Tree, key: Key, pathStk: PathStk _ NIL, useExistingPath: BOOLEAN _ FALSE] RETURNS [found: BOOLEAN] = TRUSTED BEGIN FatherMayNeedWork: PROCEDURE RETURNS [needsWork: BOOLEAN] = BEGIN 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 }; 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 ChangeInFather: PROCEDURE RETURNS [needsWork: BOOLEAN] = BEGIN IF pse.eslFront=NIL THEN RETURN [FALSE]; tree.InsertRecords[pathStk]; RETURN [pathStk.top#0 AND pathStk.path[pathStk.top-1].eslFront#NIL]; END; -- ChangeInFather pathStkWasNil: BOOLEAN _ pathStk=NIL; pse: LONG POINTER TO PathStkEntry; tree.Lock[update]; 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[] }; 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 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]; 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; IF pathStkWasNil THEN tree.ReturnDefaultPathStk[pathStk]; tree.Unlock[]; RETURN [TRUE]; END; END. fBTreeDelete.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Operation for deleting BTree entries. Taft, January 17, 1984 11:17 am Russ Atkinson (RRA) February 1, 1985 5:23:29 pm PST BTree. This code assumes that the son page is pointed to by the fatherPage[lastOffset].grPage and that this condition is preserved by InsertRecords. 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. Extra nesting required so that pathStkWasNil is visible in the catch phrase (yecch)! 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. Deletion surrogate is one with greatest key less than victim's Κ™– "Cedar" style˜headšœ™Icodešœ Οmœ1™Mšžœ˜—Mšœ0˜0M˜'M˜.M˜#M˜M˜!M˜Mšœ˜M˜M˜M˜!Mšž˜—šžœžœ -˜8Mšœžœ˜M˜!Mšœ2˜2Mšœ%˜%M˜M˜4M˜7M˜'M˜-M˜?M˜M˜$M˜!M˜Mšžœ˜—M˜Mšžœžœ˜Mšžœ ˜—šŸœž œžœ žœ˜8Mšž˜Mš žœžœžœžœžœ˜(M˜Mšžœžœ&žœ˜DMšžœ ˜—Mšœžœ žœ˜%Mšœžœžœžœ˜"M˜šžœž˜Mšž˜Mšžœžœžœ˜0M˜#Mšžœ˜—šœT™Tšžœžœžœ˜Mšœžœžœ5˜L—M˜Mšœžœ˜M˜Mšœžœ w˜ŽMšœžœ˜Mšœ`˜`šžœž˜Mšž˜Mšžœžœ$˜9Mšœ˜Mšžœžœ˜Mšžœ˜—M˜Mšœ8˜8M˜4Mšœ$žœl˜“M˜!Mšœ 7˜VMšœ•™•Mšœ *˜Dšžœž˜Mšž˜Mšœ=˜=Mšœ4˜4Mšœ˜Mšœ!žœžœ žœ˜UMšž˜—šžœž˜ MšœA˜AMšœ>™>M˜?šžœž˜ Mšž˜Mšœžœžœžœ+˜@Mšœ žœ˜M˜1Mšœ: ˜QMšœ+˜+Mšž˜—Mšžœ˜ M˜šž˜šœ žœ˜)Mšžœ&˜,—Mš žœžœ žœžœž˜FMšžœ˜!Mšžœ˜—M˜M˜!Mšœ>˜>Mšžœ˜—Mšžœ˜—Mšžœžœ$˜9M˜Mšžœžœ˜Mšžœ˜—Mšžœ˜——…—"