DeltaTree.cpp revision b169e903c5d235710b829d4b4922fd8f90ee90b1
18100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===--- DeltaTree.cpp - B-Tree for Rewrite Delta tracking ----------------===// 28100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// 38100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// The LLVM Compiler Infrastructure 48100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// 58100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// This file is distributed under the University of Illinois Open Source 68100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// License. See LICENSE.TXT for details. 78100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// 88100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 98100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// 108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// This file implements the DeltaTree and related classes. 118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// 128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner#include "clang/Rewrite/DeltaTree.h" 158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner#include "llvm/Support/Casting.h" 168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner#include <cstring> 178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing namespace clang; 188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing llvm::cast; 198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing llvm::dyn_cast; 208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner struct SourceDelta; 238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeNode; 248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeInteriorNode; 258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The DeltaTree class is a multiway search tree (BTree) structure with some 288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// fancy features. B-Trees are are generally more memory and cache efficient 298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// than binary trees, because they store multiple keys/values in each node. 308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing 328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// fast lookup by FileIndex. However, an added (important) bonus is that it 338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// can also efficiently tell us the full accumulated delta for a specific 348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// file offset as well, without traversing the whole tree. 358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The nodes of the tree are made up of instances of two classes: 378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the 388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// former and adds children pointers. Each node knows the full delta of all 398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// entries (recursively) contained inside of it, which allows us to get the 408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// full delta implied by a whole subtree in constant time. 418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta - As code in the original input buffer is added and deleted, 448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta records are used to keep track of how the input SourceLocation 458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// object is mapped into the output buffer. 468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner struct SourceDelta { 478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned FileLoc; 488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Delta; 498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static SourceDelta get(unsigned Loc, int D) { 518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta Delta; 528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.FileLoc = Loc; 538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.Delta = D; 548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Delta; 558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end anonymous namespace 588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 59b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 60b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattnerstruct InsertResult { 61b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *LHS, *RHS; 62b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner SourceDelta Split; 63b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertResult() : LHS(0) {} 64b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner}; 65b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 66b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// DeltaTreeNode - The common part of all nodes. 698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// 708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeNode { 718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner friend class DeltaTreeInteriorNode; 728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// WidthFactor - This controls the number of K/V slots held in the BTree: 748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// how wide it is. Each level of the BTree is guaranteed to have at least 758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// WidthFactor-1 K/V pairs (unless the whole tree is less full than that) 768100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// and may have at most 2*WidthFactor-1 K/V pairs. 778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner enum { WidthFactor = 8 }; 788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// Values - This tracks the SourceDelta's currently in this node. 808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// 818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta Values[2*WidthFactor-1]; 828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// NumValuesUsed - This tracks the number of values this node currently 848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// holds. 858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned char NumValuesUsed; 868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// IsLeaf - This is true if this is a leaf of the btree. If false, this is 888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// an interior node, and is actually an instance of DeltaTreeInteriorNode. 898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool IsLeaf; 908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// FullDelta - This is the full delta of all the values in this node and 928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// all children nodes. 938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta; 948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner public: 958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode(bool isLeaf = true) 96b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {} 978100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool isLeaf() const { return IsLeaf; } 998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int getFullDelta() const { return FullDelta; } 1008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; } 1018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned getNumValuesUsed() const { return NumValuesUsed; } 1038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &getValue(unsigned i) const { 1048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < NumValuesUsed && "Invalid value #"); 1058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Values[i]; 1068100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta &getValue(unsigned i) { 1088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < NumValuesUsed && "Invalid value #"); 1098100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Values[i]; 1108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 112b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner void DoSplit(InsertResult &InsertRes); 113b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 114b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 1158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// AddDeltaNonFull - Add a delta to this tree and/or it's children, knowing 1168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// that this node is not currently full. 1178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void AddDeltaNonFull(unsigned FileIndex, int Delta); 1188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// local walk over our contained deltas. 1218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void RecomputeFullDeltaLocally(); 1228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void Destroy(); 1248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeNode *) { return true; } 1268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end anonymous namespace 1288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 1308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. 1318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// This class tracks them. 1328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeInteriorNode : public DeltaTreeNode { 1338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *Children[2*WidthFactor]; 1348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ~DeltaTreeInteriorNode() { 1358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) 1368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Children[i]->Destroy(); 1378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner friend class DeltaTreeNode; 1398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner public: 1408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} 1418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeInteriorNode(DeltaTreeNode *FirstChild) 1438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner : DeltaTreeNode(false /*nonleaf*/) { 1448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta = FirstChild->FullDelta; 1458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Children[0] = FirstChild; 1468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *getChild(unsigned i) const { 1498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *getChild(unsigned i) { 1538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeInteriorNode *) { return true; } 1588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } 1598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner private: 1608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void SplitChild(unsigned ChildNo); 1618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// Destroy - A 'virtual' destructor. 1668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::Destroy() { 1678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (isLeaf()) 1688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete this; 1698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner else 1708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete cast<DeltaTreeInteriorNode>(this); 1718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// local walk over our contained deltas. 1758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::RecomputeFullDeltaLocally() { 1768100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int NewFullDelta = 0; 1778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) 1788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += Values[i].Delta; 1798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) 1808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) 1818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += IN->getChild(i)->getFullDelta(); 1828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta = NewFullDelta; 1838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// AddDeltaNonFull - Add a delta to this tree and/or it's children, knowing 1878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// that this node is not currently full. 1888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::AddDeltaNonFull(unsigned FileIndex, int Delta) { 1898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(!isFull() && "AddDeltaNonFull on a full tree?"); 1908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Maintain full delta for this node. 1928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += Delta; 1938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Find the insertion point, the first delta whose index is >= FileIndex. 1958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned i = 0, e = getNumValuesUsed(); 1968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (i != e && FileIndex > getValue(i).FileLoc) 1978100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++i; 1988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found an a record for exactly this file index, just merge this 2008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // value into the preexisting record and finish early. 2018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e && getValue(i).FileLoc == FileIndex) { 2028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // NOTE: Delta could drop to zero here. This means that the next delta 2038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // entry is useless and could be removed. Supporting erases is 2048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // significantly more complex though, so we just leave an entry with 2058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Delta=0 in the tree. 2068100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Values[i].Delta += Delta; 2078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return; 2088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2098100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 2118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Insertion into an interior node propagates the value down to a child. 2128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *Child = IN->getChild(i); 2138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If the child tree is full, split it, pulling an element up into our 2158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // node. 2168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (Child->isFull()) { 2178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner IN->SplitChild(i); 2188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta &MedianVal = getValue(i); 2198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If the median value we pulled up is exactly our insert position, add 2218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // the delta and return. 2228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (MedianVal.FileLoc == FileIndex) { 2238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner MedianVal.Delta += Delta; 2248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return; 2258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If the median value pulled up is less than our current search point, 2288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // include those deltas and search down the RHS now. 2298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (MedianVal.FileLoc < FileIndex) 2308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Child = IN->getChild(i+1); 2318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Child->AddDeltaNonFull(FileIndex, Delta); 2348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } else { 2358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // For an insertion into a non-full leaf node, just insert the value in 2368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // its sorted position. This requires moving later values over. 2378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e) 2388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); 2398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Values[i] = SourceDelta::get(FileIndex, Delta); 2408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValuesUsed; 2418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 2438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// SplitChild - At this point, we know that the current node is not full and 2458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// that the specified child of this node is. Split the child in half at its 2468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// median, propagating one value up into us. Child may be either an interior 2478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// or leaf node. 2488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeInteriorNode::SplitChild(unsigned ChildNo) { 2498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *Child = getChild(ChildNo); 2508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(!isFull() && Child->isFull() && "Inconsistent constraints"); 2518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 252b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertResult SplitRes; 253b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner Child->DoSplit(SplitRes); 2548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Now that we have two nodes and a new element, insert the median value 2568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // into ourself by moving all the later values/children down, then inserting 2578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // the new one. 2588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (getNumValuesUsed() != ChildNo) 2598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner memmove(&Children[ChildNo+2], &Children[ChildNo+1], 2608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner (getNumValuesUsed()-ChildNo)*sizeof(Children[0])); 261b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner Children[ChildNo] = SplitRes.LHS; 262b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner Children[ChildNo+1] = SplitRes.RHS; 2638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (getNumValuesUsed() != ChildNo) 2658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner memmove(&Values[ChildNo+1], &Values[ChildNo], 2668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner (getNumValuesUsed()-ChildNo)*sizeof(Values[0])); 267b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner Values[ChildNo] = SplitRes.Split; 2688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValuesUsed; 2698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 2708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 271b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattnervoid DeltaTreeNode::DoSplit(InsertResult &InsertRes) { 272b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner assert(isFull() && "Why split a non-full node?"); 273b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 274b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Since this node is full, it contains 2*WidthFactor-1 values. We move 275b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // the first 'WidthFactor-1' values to the LHS child (which we leave in this 276b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // node), propagate one value up, and move the last 'WidthFactor-1' values 277b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the RHS child. 278b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 279b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Create the new child node. 280b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *NewNode; 281b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 282b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // If this is an interior node, also move over 'WidthFactor' children 283b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the new node. 284b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); 285b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&New->Children[0], &IN->Children[WidthFactor], 286b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner WidthFactor*sizeof(IN->Children[0])); 287b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = New; 288b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } else { 289b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Just create the new leaf node. 290b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = new DeltaTreeNode(); 291b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } 292b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 293b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Move over the last 'WidthFactor-1' values from here to NewNode. 294b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&NewNode->Values[0], &Values[WidthFactor], 295b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner (WidthFactor-1)*sizeof(Values[0])); 296b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 297b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Decrease the number of values in the two nodes. 298b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; 299b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 300b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Recompute the two nodes' full delta. 301b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->RecomputeFullDeltaLocally(); 302b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner RecomputeFullDeltaLocally(); 303b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 304b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.LHS = this; 305b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.RHS = NewNode; 306b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.Split = Values[WidthFactor-1]; 307b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner} 308b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 309b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 3108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// DeltaTree Implementation 3138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 31522cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner//#define VERIFY_TREE 3168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 31722cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 3188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// VerifyTree - Walk the btree performing assertions on various properties to 3198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// verify consistency. This is useful for debugging new changes to the tree. 3208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic void VerifyTree(const DeltaTreeNode *N) { 3218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N); 3228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (IN == 0) { 3238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify leaves, just ensure that FullDelta matches up and the elements 3248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // are in proper order. 3258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { 3278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); 3298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += N->getValue(i).Delta; 3308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return; 3338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify interior nodes: Ensure that FullDelta matches up and the 3368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // elements are in proper order and the children are in proper order. 3378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { 3398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &IVal = N->getValue(i); 3408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *IChild = IN->getChild(i); 3418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); 3438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IVal.Delta; 3448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IChild->getFullDelta(); 3458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The largest value in child #i should be smaller than FileLoc. 3478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < 3488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner IVal.FileLoc); 3498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The smallest value in child #i+1 should be larger than FileLoc. 3518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); 3528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner VerifyTree(IChild); 3538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); 3568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 35922cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif // VERIFY_TREE 3608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic DeltaTreeNode *getRoot(void *Root) { 3628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return (DeltaTreeNode*)Root; 3638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3658100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree() { 3668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 3678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3688100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree(const DeltaTree &RHS) { 3698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Currently we only support copying when the RHS is empty. 3708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && 3718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner "Can only copy empty tree"); 3728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 3738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3758100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::~DeltaTree() { 3768100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner getRoot(Root)->Destroy(); 3778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// getDeltaAt - Return the accumulated delta at the specified file offset. 3808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// This includes all insertions or delections that occurred *before* the 3818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// specified file index. 3828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerint DeltaTree::getDeltaAt(unsigned FileIndex) const { 3838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *Node = getRoot(Root); 3848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Result = 0; 3868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Walk down the tree. 3888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (1) { 3898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // For all nodes, include any local deltas before the specified file 3908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // index by summing them up directly. Keep track of how many were 3918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // included. 3928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned NumValsGreater = 0; 3938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; 3948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValsGreater) { 3958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &Val = Node->getValue(NumValsGreater); 3968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3978100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (Val.FileLoc >= FileIndex) 3988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner break; 3998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += Val.Delta; 4008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we have an interior node, include information about children and 4038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // recurse. Otherwise, if we have a leaf, we're done. 4048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node); 4058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (!IN) return Result; 4068100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Include any children to the left of the values we skipped, all of 4088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // their deltas should be included as well. 4098100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0; i != NumValsGreater; ++i) 4108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += IN->getChild(i)->getFullDelta(); 4118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found exactly the value we were looking for, break off the 4138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // search early. There is no need to search the RHS of the value for 4148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partial results. 4158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (NumValsGreater != Node->getNumValuesUsed() && 4168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node->getValue(NumValsGreater).FileLoc == FileIndex) 4178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Result; 4188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Otherwise, traverse down the tree. The selected subtree may be 4208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partially included in the range. 4218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node = IN->getChild(NumValsGreater); 4228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // NOT REACHED. 4248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// AddDelta - When a change is made that shifts around the text buffer, 4288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// this method is used to record that info. It inserts a delta of 'Delta' 4298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// into the current DeltaTree at offset FileIndex. 4308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTree::AddDelta(unsigned FileIndex, int Delta) { 4318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(Delta && "Adding a noop?"); 432b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *MyRoot = getRoot(Root); 4338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If the root is full, create a new dummy (non-empty) interior node that 4358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // points to it, allowing the old root to be split. 436b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner if (MyRoot->isFull()) 437b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner Root = MyRoot = new DeltaTreeInteriorNode(MyRoot); 4388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 439b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner MyRoot->AddDeltaNonFull(FileIndex, Delta); 4408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 44122cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 442b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner VerifyTree(MyRoot); 44322cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif 4448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 446