-- BTreeDelete.mesa <<-- Operation for deleting BTree entries.>> <<-- Last Edited by: Taft, March 24, 1983 5:06 pm>> DIRECTORY BTree, BTreeInternal; BTreeDelete: PROGRAM IMPORTS BTree, BTreeInternal EXPORTS BTree = BEGIN OPEN BTree, BTreeInternal; -- BTree. 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 -- 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 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; -- 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; dpse: LONG POINTER TO PathStkEntry; 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 -- 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, endOfUpdate]; END ELSE BEGIN tree.AdjustTreeState[update: startOfUpdate, deltaEntryCount: -1]; dpse _ pse; WHILE descendantPg#nilPage DO -- Deletion surrogate is one with greatest key less than victim's pathStk.top _ pathStk.top+1; dpse _ @pathStk.path[pathStk.top]; dpse.pageNumber _ descendantPg; pagePtr _ tree.ReferencePage[descendantPg]; dpse.offset _ nilOffset+(tree.state.pageSize-pagePtr.freeWords); tree.ReleasePage[descendantPg]; dpse.lastOffset _ entry1Offset; dpse.nextToLastOffset _ entry0Offset; tree.RepairOffsets[dpse]; AssignRefESR[@dpse.eslFront, NIL]; AssignRefESR[@dpse.eslRear, NIL]; dpse.leastSon _ nilPage; pagePtr _ tree.ReferencePage[dpse.pageNumber]; descendantPg _ pagePtr[dpse.lastOffset].grPage; tree.ReleasePage[dpse.pageNumber]; ENDLOOP; IF pathStk.top > origStkTop THEN BEGIN 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.