DIRECTORY BTree, BTreeInternal; 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". [] _ tree.PathEntryLE[key: key, pathStk: pathStk, useExistingPath: useExistingPath]; origStkTop _ pathStk.top; IF origStkTop=0 THEN RETURN [FALSE]; [ptr: pagePtr, pse: pse] _ tree.ReferenceStack[pathStk]; IF tree.Compare[key, @pagePtr[pse.lastOffset].entry] # equal THEN { tree.ReleasePage[pse.pageNumber]; tree.Unlock[]; RETURN [FALSE] }; 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, 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. BTreeDelete.mesa Operation for deleting BTree entries. Last Edited by: Taft, June 3, 1983 2:54 pm 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 ΚT– "Cedar" style˜Jšœ™J™%J™*unitšΟk ˜ Icodešœ˜Lšœ˜—šœ ˜Lšœ˜Lšœ˜ Lšœœœ˜"—J™J™šœ™Kšœœœ ˜Lšœ œœ˜3Kšœ œœ˜"Lšœœœ˜9šΟn œœœ œ+œœœœ œ˜”Lš˜šžœ œœ œ˜;Lš˜Jšœ™L˜ Lšœ œœœ˜(Lšœœ˜L˜!Lšœ˜L˜-šœœ%˜=LšœΟc˜ L˜&L˜&L˜!L˜Lšœœ˜Lšœ˜—šœœ8˜OLšœ$œ˜-—JšœΨ™ΨLšœ{˜{L˜)L˜4L˜%L˜'šœDœœ˜dLšœŸ'˜-L˜Lšœœ˜Lšœ:˜:L˜'L˜;šœ8˜>Lšœ˜—Lšœ0˜0L˜'L˜.L˜#L˜L˜!L˜Lšœ˜L˜L˜L˜!Lš˜—šœœŸ-˜8Lšœœ˜L˜!Lšœ2˜2Lšœ%˜%L˜L˜4L˜7L˜'L˜-L˜?L˜L˜$L˜!L˜Lšœ˜—L˜Lšœœ˜LšœŸ˜—šžœ œœ œ˜8Lš˜Lš œœœœœ˜(L˜Lšœœ&œ˜DLšœŸ˜—Lšœœ œ˜%Lšœœœœ˜"L˜šœ˜Lš˜Lšœœœ˜0L˜#Lšœ˜—šœT™Tšœœœ˜Lšœœœ5˜L—L˜Lšœœ˜L˜LšœœŸw˜ŽLšœT˜TL˜Lšœœœœ˜$Lšœ8˜8šœ;˜ALšœ3œœ˜D—L˜4Lšœ$œl˜“L˜!LšœŸ7˜VJšœ•™•LšœŸ*˜Dšœ˜Lš˜Lšœ=˜=Lšœ4˜4Lšœ˜L˜.Lš˜—šœ˜ LšœA˜AJšœ>™>J˜?šœ˜ Lš˜Lšœœœœ+˜@Lšœ œ˜L˜1Lšœ:Ÿ˜QLšœ+˜+Lš˜—Lšœ˜ L˜š˜šœ œ˜)Lšœ&˜,—Lš œœ œœ˜FLšœ˜!Lšœ˜—L˜L˜!Lšœ>˜>Lšœ˜—Lšœ˜—Lšœœ$˜9L˜Lšœœ˜Lšœ˜—Kšœ˜—J˜—…—Ψ.