<> <> <> <> <> 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.