11541Srgrimes//===- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ------------------===// 21541Srgrimes// 31541Srgrimes// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 41541Srgrimes// See https://llvm.org/LICENSE.txt for license information. 51541Srgrimes// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 61541Srgrimes// 71541Srgrimes//===----------------------------------------------------------------------===// 812623Sphk// 912623Sphk// This file implements the DeltaTree and related classes. 1012623Sphk// 111541Srgrimes//===----------------------------------------------------------------------===// 121541Srgrimes 131541Srgrimes#include "clang/Rewrite/Core/DeltaTree.h" 141541Srgrimes#include "clang/Basic/LLVM.h" 151541Srgrimes#include "llvm/Support/Casting.h" 161541Srgrimes#include <cassert> 171541Srgrimes#include <cstring> 181541Srgrimes 191541Srgrimesusing namespace clang; 201541Srgrimes 211541Srgrimes/// The DeltaTree class is a multiway search tree (BTree) structure with some 221541Srgrimes/// fancy features. B-Trees are generally more memory and cache efficient 231541Srgrimes/// than binary trees, because they store multiple keys/values in each node. 241541Srgrimes/// 251541Srgrimes/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing 261541Srgrimes/// fast lookup by FileIndex. However, an added (important) bonus is that it 271541Srgrimes/// can also efficiently tell us the full accumulated delta for a specific 281541Srgrimes/// file offset as well, without traversing the whole tree. 291541Srgrimes/// 301541Srgrimes/// The nodes of the tree are made up of instances of two classes: 311541Srgrimes/// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the 321541Srgrimes/// former and adds children pointers. Each node knows the full delta of all 331541Srgrimes/// entries (recursively) contained inside of it, which allows us to get the 341541Srgrimes/// full delta implied by a whole subtree in constant time. 351541Srgrimes 361541Srgrimesnamespace { 371541Srgrimes 381541Srgrimes /// SourceDelta - As code in the original input buffer is added and deleted, 391541Srgrimes /// SourceDelta records are used to keep track of how the input SourceLocation 4044078Sdfr /// object is mapped into the output buffer. 411541Srgrimes struct SourceDelta { 421541Srgrimes unsigned FileLoc; 4331778Seivind int Delta; 4431778Seivind 451541Srgrimes static SourceDelta get(unsigned Loc, int D) { 4624744Sbde SourceDelta Delta; 471541Srgrimes Delta.FileLoc = Loc; 481541Srgrimes Delta.Delta = D; 4912623Sphk return Delta; 5012662Sdg } 5115103Sphk }; 5215103Sphk 5312645Sbde /// DeltaTreeNode - The common part of all nodes. 5412662Sdg /// 5512645Sbde class DeltaTreeNode { 5630354Sphk public: 5730309Sphk struct InsertResult { 5812429Sphk DeltaTreeNode *LHS, *RHS; 5912429Sphk SourceDelta Split; 6012429Sphk }; 6112429Sphk 6212429Sphk private: 6312429Sphk friend class DeltaTreeInteriorNode; 6412429Sphk 6512429Sphk /// WidthFactor - This controls the number of K/V slots held in the BTree: 6612429Sphk /// how wide it is. Each level of the BTree is guaranteed to have at least 6712429Sphk /// WidthFactor-1 K/V pairs (except the root) and may have at most 6812429Sphk /// 2*WidthFactor-1 K/V pairs. 6944078Sdfr enum { WidthFactor = 8 }; 7012152Sphk 7112623Sphk /// Values - This tracks the SourceDelta's currently in this node. 7212623Sphk SourceDelta Values[2*WidthFactor-1]; 7312623Sphk 7444078Sdfr /// NumValuesUsed - This tracks the number of values this node currently 7512623Sphk /// holds. 7612429Sphk unsigned char NumValuesUsed = 0; 7744078Sdfr 7812152Sphk /// IsLeaf - This is true if this is a leaf of the btree. If false, this is 7944078Sdfr /// an interior node, and is actually an instance of DeltaTreeInteriorNode. 8044078Sdfr bool IsLeaf; 8144078Sdfr 8244078Sdfr /// FullDelta - This is the full delta of all the values in this node and 8312197Sbde /// all children nodes. 8444078Sdfr int FullDelta = 0; 8544078Sdfr 8644078Sdfr public: 8744078Sdfr DeltaTreeNode(bool isLeaf = true) : IsLeaf(isLeaf) {} 8844078Sdfr 8944078Sdfr bool isLeaf() const { return IsLeaf; } 9044078Sdfr int getFullDelta() const { return FullDelta; } 9144078Sdfr bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; } 9244078Sdfr 9344078Sdfr unsigned getNumValuesUsed() const { return NumValuesUsed; } 9444078Sdfr 9544078Sdfr const SourceDelta &getValue(unsigned i) const { 9644078Sdfr assert(i < NumValuesUsed && "Invalid value #"); 9744078Sdfr return Values[i]; 9844078Sdfr } 9944078Sdfr 10044078Sdfr SourceDelta &getValue(unsigned i) { 10144078Sdfr assert(i < NumValuesUsed && "Invalid value #"); 10244078Sdfr return Values[i]; 10344078Sdfr } 10444078Sdfr 10544078Sdfr /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 10644078Sdfr /// this node. If insertion is easy, do it and return false. Otherwise, 10744078Sdfr /// split the node, populate InsertRes with info about the split, and return 10844078Sdfr /// true. 10944078Sdfr bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); 11044078Sdfr 11144078Sdfr void DoSplit(InsertResult &InsertRes); 11212152Sphk 11312131Sphk 11444078Sdfr /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 11512152Sphk /// local walk over our contained deltas. 11644078Sdfr void RecomputeFullDeltaLocally(); 11744078Sdfr 11812152Sphk void Destroy(); 11944078Sdfr }; 12044078Sdfr 12144078Sdfr /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. 12244078Sdfr /// This class tracks them. 12344078Sdfr class DeltaTreeInteriorNode : public DeltaTreeNode { 12444078Sdfr friend class DeltaTreeNode; 12544078Sdfr 12644078Sdfr DeltaTreeNode *Children[2*WidthFactor]; 12744078Sdfr 12844078Sdfr ~DeltaTreeInteriorNode() { 12912623Sphk for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) 13044078Sdfr Children[i]->Destroy(); 13144078Sdfr } 13244078Sdfr 13344078Sdfr public: 13444078Sdfr DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} 13544078Sdfr 13612152Sphk DeltaTreeInteriorNode(const InsertResult &IR) 13712152Sphk : DeltaTreeNode(false /*nonleaf*/) { 13844078Sdfr Children[0] = IR.LHS; 13944078Sdfr Children[1] = IR.RHS; 14044078Sdfr Values[0] = IR.Split; 14144078Sdfr FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta; 14212152Sphk NumValuesUsed = 1; 14344078Sdfr } 14438869Sbde 14544078Sdfr const DeltaTreeNode *getChild(unsigned i) const { 14638869Sbde assert(i < getNumValuesUsed()+1 && "Invalid child"); 14738869Sbde return Children[i]; 14844078Sdfr } 14944078Sdfr 15012623Sphk DeltaTreeNode *getChild(unsigned i) { 15112623Sphk assert(i < getNumValuesUsed()+1 && "Invalid child"); 15212623Sphk return Children[i]; 15312650Sphk } 15412650Sphk 15512650Sphk static bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } 15612650Sphk }; 15712650Sphk 15812650Sphk} // namespace 15912650Sphk 16012650Sphk/// Destroy - A 'virtual' destructor. 16112623Sphkvoid DeltaTreeNode::Destroy() { 16212623Sphk if (isLeaf()) 16342467Sphk delete this; 16412623Sphk else 16512650Sphk delete cast<DeltaTreeInteriorNode>(this); 16612623Sphk} 16712623Sphk 16812152Sphk/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 16944078Sdfr/// local walk over our contained deltas. 17012152Sphkvoid DeltaTreeNode::RecomputeFullDeltaLocally() { 17144078Sdfr int NewFullDelta = 0; 17244078Sdfr for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) 17312152Sphk NewFullDelta += Values[i].Delta; 17444078Sdfr if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) 17512152Sphk for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) 17612152Sphk NewFullDelta += IN->getChild(i)->getFullDelta(); 17712152Sphk FullDelta = NewFullDelta; 17812152Sphk} 17944078Sdfr 18012152Sphk/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 18112152Sphk/// this node. If insertion is easy, do it and return false. Otherwise, 18244078Sdfr/// split the node, populate InsertRes with info about the split, and return 18344078Sdfr/// true. 18412152Sphkbool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, 18544078Sdfr InsertResult *InsertRes) { 18615241Sphk // Maintain full delta for this node. 18715241Sphk FullDelta += Delta; 18844078Sdfr 18912243Sphk // Find the insertion point, the first delta whose index is >= FileIndex. 19015241Sphk unsigned i = 0, e = getNumValuesUsed(); 19144078Sdfr while (i != e && FileIndex > getValue(i).FileLoc) 19212152Sphk ++i; 19344078Sdfr 19412152Sphk // If we found an a record for exactly this file index, just merge this 19512152Sphk // value into the pre-existing record and finish early. 19612152Sphk if (i != e && getValue(i).FileLoc == FileIndex) { 19712152Sphk // NOTE: Delta could drop to zero here. This means that the delta entry is 19812152Sphk // useless and could be removed. Supporting erases is more complex than 19912152Sphk // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in 20012152Sphk // the tree. 20112152Sphk Values[i].Delta += Delta; 20212152Sphk return false; 20312152Sphk } 20412152Sphk 20512152Sphk // Otherwise, we found an insertion point, and we know that the value at the 20612152Sphk // specified index is > FileIndex. Handle the leaf case first. 20712152Sphk if (isLeaf()) { 20812152Sphk if (!isFull()) { 20944078Sdfr // For an insertion into a non-full leaf node, just insert the value in 21012152Sphk // its sorted position. This requires moving later values over. 21112152Sphk if (i != e) 21212152Sphk memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); 21312152Sphk Values[i] = SourceDelta::get(FileIndex, Delta); 21412623Sphk ++NumValuesUsed; 21512152Sphk return false; 21612623Sphk } 21712623Sphk 21812623Sphk // Otherwise, if this is leaf is full, split the node at its median, insert 21912623Sphk // the value into one of the children, and return the result. 22012623Sphk assert(InsertRes && "No result location specified"); 22144078Sdfr DoSplit(*InsertRes); 22244078Sdfr 22344078Sdfr if (InsertRes->Split.FileLoc > FileIndex) 22412623Sphk InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 22512131Sphk else 22612623Sphk InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 22712623Sphk return true; 22841514Sarchie } 22912623Sphk 23012623Sphk // Otherwise, this is an interior node. Send the request down the tree. 23112623Sphk auto *IN = cast<DeltaTreeInteriorNode>(this); 23212623Sphk if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) 23312623Sphk return false; // If there was space in the child, just return. 23412623Sphk 23512623Sphk // Okay, this split the subtree, producing a new value and two children to 23612623Sphk // insert here. If this node is non-full, we can just insert it directly. 23712623Sphk if (!isFull()) { 23812623Sphk // Now that we have two nodes and a new element, insert the perclated value 23944078Sdfr // into ourself by moving all the later values/children down, then inserting 24044078Sdfr // the new one. 24112623Sphk if (i != e) 24212131Sphk memmove(&IN->Children[i+2], &IN->Children[i+1], 24312623Sphk (e-i)*sizeof(IN->Children[0])); 24412623Sphk IN->Children[i] = InsertRes->LHS; 24512623Sphk IN->Children[i+1] = InsertRes->RHS; 24644078Sdfr 24744078Sdfr if (e != i) 24812623Sphk memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0])); 24912623Sphk Values[i] = InsertRes->Split; 25012623Sphk ++NumValuesUsed; 25112623Sphk return false; 25212623Sphk } 25312623Sphk 25444078Sdfr // Finally, if this interior node was full and a node is percolated up, split 25512623Sphk // ourself and return that up the chain. Start by saving all our info to 25612623Sphk // avoid having the split clobber it. 25744078Sdfr IN->Children[i] = InsertRes->LHS; 25812623Sphk DeltaTreeNode *SubRHS = InsertRes->RHS; 25912623Sphk SourceDelta SubSplit = InsertRes->Split; 26044078Sdfr 26112623Sphk // Do the split. 26212623Sphk DoSplit(*InsertRes); 26312623Sphk 26412623Sphk // Figure out where to insert SubRHS/NewSplit. 26512623Sphk DeltaTreeInteriorNode *InsertSide; 26612623Sphk if (SubSplit.FileLoc < InsertRes->Split.FileLoc) 26712623Sphk InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS); 26812623Sphk else 26912623Sphk InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS); 27044078Sdfr 27144078Sdfr // We now have a non-empty interior node 'InsertSide' to insert 27212623Sphk // SubRHS/SubSplit into. Find out where to insert SubSplit. 27344078Sdfr 27412623Sphk // Find the insertion point, the first delta whose index is >SubSplit.FileLoc. 27512623Sphk i = 0; e = InsertSide->getNumValuesUsed(); 27644078Sdfr while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) 27744078Sdfr ++i; 27844078Sdfr 27912623Sphk // Now we know that i is the place to insert the split value into. Insert it 28012623Sphk // and the child right after it. 28144078Sdfr if (i != e) 28212623Sphk memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1], 28344078Sdfr (e-i)*sizeof(IN->Children[0])); 28412623Sphk InsertSide->Children[i+1] = SubRHS; 28512623Sphk 28644078Sdfr if (e != i) 28715241Sphk memmove(&InsertSide->Values[i+1], &InsertSide->Values[i], 28844078Sdfr (e-i)*sizeof(Values[0])); 28915241Sphk InsertSide->Values[i] = SubSplit; 29015241Sphk ++InsertSide->NumValuesUsed; 29112623Sphk InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta(); 29212623Sphk return true; 29344078Sdfr} 29412623Sphk 29512623Sphk/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values) 29644078Sdfr/// into two subtrees each with "WidthFactor-1" values and a pivot value. 29744078Sdfr/// Return the pieces in InsertRes. 29812623Sphkvoid DeltaTreeNode::DoSplit(InsertResult &InsertRes) { 29944078Sdfr assert(isFull() && "Why split a non-full node?"); 30012623Sphk 30144078Sdfr // Since this node is full, it contains 2*WidthFactor-1 values. We move 30212623Sphk // the first 'WidthFactor-1' values to the LHS child (which we leave in this 30344078Sdfr // node), propagate one value up, and move the last 'WidthFactor-1' values 30412623Sphk // into the RHS child. 30515241Sphk 30612623Sphk // Create the new child node. 30744078Sdfr DeltaTreeNode *NewNode; 30812623Sphk if (auto *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 30912623Sphk // If this is an interior node, also move over 'WidthFactor' children 31044078Sdfr // into the new node. 31112623Sphk DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); 31212623Sphk memcpy(&New->Children[0], &IN->Children[WidthFactor], 31344078Sdfr WidthFactor*sizeof(IN->Children[0])); 31412623Sphk NewNode = New; 31544078Sdfr } else { 31612623Sphk // Just create the new leaf node. 31715241Sphk NewNode = new DeltaTreeNode(); 31812623Sphk } 31912623Sphk 32012623Sphk // Move over the last 'WidthFactor-1' values from here to NewNode. 32112623Sphk memcpy(&NewNode->Values[0], &Values[WidthFactor], 32212623Sphk (WidthFactor-1)*sizeof(Values[0])); 32312623Sphk 32412623Sphk // Decrease the number of values in the two nodes. 32512623Sphk NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; 32612623Sphk 32712623Sphk // Recompute the two nodes' full delta. 32812623Sphk NewNode->RecomputeFullDeltaLocally(); 32912623Sphk RecomputeFullDeltaLocally(); 33012623Sphk 33144078Sdfr InsertRes.LHS = this; 33212623Sphk InsertRes.RHS = NewNode; 33312623Sphk InsertRes.Split = Values[WidthFactor-1]; 33412623Sphk} 33512623Sphk 33612623Sphk//===----------------------------------------------------------------------===// 33712650Sphk// DeltaTree Implementation 33812623Sphk//===----------------------------------------------------------------------===// 33912623Sphk 34012623Sphk//#define VERIFY_TREE 34112623Sphk 34212623Sphk#ifdef VERIFY_TREE 34312623Sphk/// VerifyTree - Walk the btree performing assertions on various properties to 34444078Sdfr/// verify consistency. This is useful for debugging new changes to the tree. 34512623Sphkstatic void VerifyTree(const DeltaTreeNode *N) { 34644078Sdfr const auto *IN = dyn_cast<DeltaTreeInteriorNode>(N); 34744078Sdfr if (IN == 0) { 34844078Sdfr // Verify leaves, just ensure that FullDelta matches up and the elements 34912623Sphk // are in proper order. 35012623Sphk int FullDelta = 0; 35112623Sphk for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { 35212623Sphk if (i) 35312623Sphk assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); 35412623Sphk FullDelta += N->getValue(i).Delta; 35512623Sphk } 35612623Sphk assert(FullDelta == N->getFullDelta()); 35712623Sphk return; 35812623Sphk } 35912623Sphk 36012623Sphk // Verify interior nodes: Ensure that FullDelta matches up and the 36112623Sphk // elements are in proper order and the children are in proper order. 36212623Sphk int FullDelta = 0; 36312623Sphk for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { 36412623Sphk const SourceDelta &IVal = N->getValue(i); 36512623Sphk const DeltaTreeNode *IChild = IN->getChild(i); 36644078Sdfr if (i) 36712623Sphk assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); 36844078Sdfr FullDelta += IVal.Delta; 36944078Sdfr FullDelta += IChild->getFullDelta(); 37044078Sdfr 37112623Sphk // The largest value in child #i should be smaller than FileLoc. 37212623Sphk assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < 37344078Sdfr IVal.FileLoc); 37412623Sphk 37512623Sphk // The smallest value in child #i+1 should be larger than FileLoc. 37612623Sphk assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); 37744078Sdfr VerifyTree(IChild); 37844078Sdfr } 37912623Sphk 38012623Sphk FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); 38112623Sphk 38244078Sdfr assert(FullDelta == N->getFullDelta()); 38312623Sphk} 38412623Sphk#endif // VERIFY_TREE 38544078Sdfr 38612623Sphkstatic DeltaTreeNode *getRoot(void *Root) { 38712623Sphk return (DeltaTreeNode*)Root; 38844078Sdfr} 38944078Sdfr 39012623SphkDeltaTree::DeltaTree() { 39112623Sphk Root = new DeltaTreeNode(); 39212623Sphk} 39312623Sphk 39412623SphkDeltaTree::DeltaTree(const DeltaTree &RHS) { 39512623Sphk // Currently we only support copying when the RHS is empty. 39612623Sphk assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && 39712623Sphk "Can only copy empty tree"); 39812623Sphk Root = new DeltaTreeNode(); 39912623Sphk} 40012623Sphk 40112623SphkDeltaTree::~DeltaTree() { 40212623Sphk getRoot(Root)->Destroy(); 40312623Sphk} 40412623Sphk 40512623Sphk/// getDeltaAt - Return the accumulated delta at the specified file offset. 40612623Sphk/// This includes all insertions or delections that occurred *before* the 40712623Sphk/// specified file index. 40812623Sphkint DeltaTree::getDeltaAt(unsigned FileIndex) const { 40912623Sphk const DeltaTreeNode *Node = getRoot(Root); 41012623Sphk 41112623Sphk int Result = 0; 41212623Sphk 41312623Sphk // Walk down the tree. 41412623Sphk while (true) { 41512623Sphk // For all nodes, include any local deltas before the specified file 41612623Sphk // index by summing them up directly. Keep track of how many were 41712623Sphk // included. 41812623Sphk unsigned NumValsGreater = 0; 41912623Sphk for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; 42012623Sphk ++NumValsGreater) { 42112623Sphk const SourceDelta &Val = Node->getValue(NumValsGreater); 42212623Sphk 42312623Sphk if (Val.FileLoc >= FileIndex) 42412623Sphk break; 42512623Sphk Result += Val.Delta; 42612623Sphk } 42712650Sphk 42812623Sphk // If we have an interior node, include information about children and 42912623Sphk // recurse. Otherwise, if we have a leaf, we're done. 43012623Sphk const auto *IN = dyn_cast<DeltaTreeInteriorNode>(Node); 43112910Sphk if (!IN) return Result; 43212623Sphk 43312623Sphk // Include any children to the left of the values we skipped, all of 43412623Sphk // their deltas should be included as well. 43512623Sphk for (unsigned i = 0; i != NumValsGreater; ++i) 43612623Sphk Result += IN->getChild(i)->getFullDelta(); 43712650Sphk 43812623Sphk // If we found exactly the value we were looking for, break off the 43944078Sdfr // search early. There is no need to search the RHS of the value for 44044078Sdfr // partial results. 44144078Sdfr if (NumValsGreater != Node->getNumValuesUsed() && 44212623Sphk Node->getValue(NumValsGreater).FileLoc == FileIndex) 44344078Sdfr return Result+IN->getChild(NumValsGreater)->getFullDelta(); 44412623Sphk 44512623Sphk // Otherwise, traverse down the tree. The selected subtree may be 44644078Sdfr // partially included in the range. 44744078Sdfr Node = IN->getChild(NumValsGreater); 44812623Sphk } 44944078Sdfr // NOT REACHED. 45044078Sdfr} 45112623Sphk 45212623Sphk/// AddDelta - When a change is made that shifts around the text buffer, 45312650Sphk/// this method is used to record that info. It inserts a delta of 'Delta' 45444078Sdfr/// into the current DeltaTree at offset FileIndex. 45544078Sdfrvoid DeltaTree::AddDelta(unsigned FileIndex, int Delta) { 45612623Sphk assert(Delta && "Adding a noop?"); 45712623Sphk DeltaTreeNode *MyRoot = getRoot(Root); 45812623Sphk 45912623Sphk DeltaTreeNode::InsertResult InsertRes; 46012623Sphk if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { 46112623Sphk Root = new DeltaTreeInteriorNode(InsertRes); 46244078Sdfr#ifdef VERIFY_TREE 46312623Sphk MyRoot = Root; 46412623Sphk#endif 46512623Sphk } 46612623Sphk 46744078Sdfr#ifdef VERIFY_TREE 46812623Sphk VerifyTree(MyRoot); 46912650Sphk#endif 47044078Sdfr} 47112650Sphk