DeltaTree.cpp revision 3b7ff0d143014ea86328e8fa9196a7537dce7bea
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> 173b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner#include <cstdio> 188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing namespace clang; 198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing llvm::cast; 208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing llvm::dyn_cast; 218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner struct SourceDelta; 248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeNode; 258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeInteriorNode; 268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The DeltaTree class is a multiway search tree (BTree) structure with some 298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// fancy features. B-Trees are are generally more memory and cache efficient 308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// than binary trees, because they store multiple keys/values in each node. 318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing 338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// fast lookup by FileIndex. However, an added (important) bonus is that it 348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// can also efficiently tell us the full accumulated delta for a specific 358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// file offset as well, without traversing the whole tree. 368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The nodes of the tree are made up of instances of two classes: 388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the 398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// former and adds children pointers. Each node knows the full delta of all 408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// entries (recursively) contained inside of it, which allows us to get the 418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// full delta implied by a whole subtree in constant time. 428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta - As code in the original input buffer is added and deleted, 458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta records are used to keep track of how the input SourceLocation 468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// object is mapped into the output buffer. 478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner struct SourceDelta { 488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned FileLoc; 498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Delta; 508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static SourceDelta get(unsigned Loc, int D) { 528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta Delta; 538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.FileLoc = Loc; 548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.Delta = D; 558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Delta; 568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end anonymous namespace 598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 60b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 61b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattnerstruct InsertResult { 62b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *LHS, *RHS; 63b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner SourceDelta Split; 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 1123b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 1133b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// this node. If insertion is easy, do it and return false. Otherwise, 1143b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// split the node, populate InsertRes with info about the split, and return 1153b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// true. 1163b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); 1173b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 118b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner void DoSplit(InsertResult &InsertRes); 119b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 120b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 1218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// local walk over our contained deltas. 1238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void RecomputeFullDeltaLocally(); 1248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void Destroy(); 1268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeNode *) { return true; } 1288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end anonymous namespace 1308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 1328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. 1338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// This class tracks them. 1348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeInteriorNode : public DeltaTreeNode { 1358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *Children[2*WidthFactor]; 1368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ~DeltaTreeInteriorNode() { 1378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) 1388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Children[i]->Destroy(); 1398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner friend class DeltaTreeNode; 1418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner public: 1428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} 1438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeInteriorNode(DeltaTreeNode *FirstChild) 1458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner : DeltaTreeNode(false /*nonleaf*/) { 1468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta = FirstChild->FullDelta; 1478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Children[0] = FirstChild; 1488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1503b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeInteriorNode(const InsertResult &IR) 1513b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner : DeltaTreeNode(false /*nonleaf*/) { 1523b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Children[0] = IR.LHS; 1533b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Children[1] = IR.RHS; 1543b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[0] = IR.Split; 1553b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta; 1563b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner NumValuesUsed = 1; 1573b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 1583b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 1598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *getChild(unsigned i) const { 1608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *getChild(unsigned i) { 1648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeInteriorNode *) { return true; } 1698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } 1708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// Destroy - A 'virtual' destructor. 1758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::Destroy() { 1768100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (isLeaf()) 1778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete this; 1788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner else 1798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete cast<DeltaTreeInteriorNode>(this); 1808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// local walk over our contained deltas. 1848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::RecomputeFullDeltaLocally() { 1858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int NewFullDelta = 0; 1868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) 1878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += Values[i].Delta; 1888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) 1898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) 1908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += IN->getChild(i)->getFullDelta(); 1918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta = NewFullDelta; 1928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1943b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 1953b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// this node. If insertion is easy, do it and return false. Otherwise, 1963b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// split the node, populate InsertRes with info about the split, and return 1973b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// true. 1983b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattnerbool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, 1993b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertResult *InsertRes) { 2008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Maintain full delta for this node. 2018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += Delta; 2028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Find the insertion point, the first delta whose index is >= FileIndex. 2048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned i = 0, e = getNumValuesUsed(); 2058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (i != e && FileIndex > getValue(i).FileLoc) 2068100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++i; 2078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found an a record for exactly this file index, just merge this 2093b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // value into the pre-existing record and finish early. 2108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e && getValue(i).FileLoc == FileIndex) { 2113b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // NOTE: Delta could drop to zero here. This means that the delta entry is 2123b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // useless and could be removed. Supporting erases is more complex than 2133b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in 2143b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the tree. 2158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Values[i].Delta += Delta; 2163b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 2178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2183b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2193b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, we found an insertion point, and we know that the value at the 2203b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // specified index is > FileIndex. Handle the leaf case first. 2213b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (isLeaf()) { 2223b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!isFull()) { 2233b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // For an insertion into a non-full leaf node, just insert the value in 2243b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // its sorted position. This requires moving later values over. 2253b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (i != e) 2263b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); 2273b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[i] = SourceDelta::get(FileIndex, Delta); 2283b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++NumValuesUsed; 2293b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 2308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2323b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, if this is leaf is full, split the node at its median, insert 2333b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the value into one of the children, and return the result. 2343b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner assert(InsertRes && "No result location specified"); 2353b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DoSplit(*InsertRes); 2363b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2373b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (InsertRes->Split.FileLoc > FileIndex) 2383b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertRes->LHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/); 2393b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner else 2403b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertRes->RHS->DoInsertion(FileIndex, Delta, 0 /*can't fail*/); 2413b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return true; 2423b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 2433b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2443b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, this is an interior node. Send the request down the tree. 2453b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this); 2463b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) 2473b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; // If there was space in the child, just return. 2483b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2493b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Okay, this split the subtree, producing a new value and two children to 2503b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // insert here. If this node is non-full, we can just insert it directly. 2513b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!isFull()) { 2523b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Now that we have two nodes and a new element, insert the perclated value 2533b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // into ourself by moving all the later values/children down, then inserting 2543b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the new one. 2558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e) 2563b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&IN->Children[i+2], &IN->Children[i+1], 2573b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(IN->Children[0])); 2583b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i] = InsertRes->LHS; 2593b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i+1] = InsertRes->RHS; 2603b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2613b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (e != i) 2623b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0])); 2633b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[i] = InsertRes->Split; 2648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValuesUsed; 2653b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 2668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2673b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2683b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Finally, if this interior node was full and a node is percolated up, split 2693b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // ourself and return that up the chain. Start by saving all our info to 2703b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // avoid having the split clobber it. 2713b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i] = InsertRes->LHS; 2723b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeNode *SubRHS = InsertRes->RHS; 2733b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner SourceDelta SubSplit = InsertRes->Split; 2743b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2753b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Do the split. 2763b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DoSplit(*InsertRes); 2778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2783b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Figure out where to insert SubRHS/NewSplit. 2793b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeInteriorNode *InsertSide; 2803b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (SubSplit.FileLoc < InsertRes->Split.FileLoc) 2813b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS); 2823b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner else 2833b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS); 2843b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2853b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // We now have a non-empty interior node 'InsertSide' to insert 2863b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // SubRHS/SubSplit into. Find out where to insert SubSplit. 2878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2883b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Find the insertion point, the first delta whose index is >SubSplit.FileLoc. 2893b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner i = 0; e = InsertSide->getNumValuesUsed(); 2903b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) 2913b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++i; 2928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2933b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Now we know that i is the place to insert the split value into. Insert it 2943b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // and the child right after it. 2953b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (i != e) 2963b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1], 2973b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(IN->Children[0])); 2983b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->Children[i+1] = SubRHS; 2998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3003b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (e != i) 3013b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&InsertSide->Values[i+1], &InsertSide->Values[i], 3023b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(Values[0])); 3033b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->Values[i] = SubSplit; 3043b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++InsertSide->NumValuesUsed; 3053b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta(); 3063b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return true; 3078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3093b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values) 3103b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// into two subtrees each with "WidthFactor-1" values and a pivot value. 3113b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// Return the pieces in InsertRes. 312b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattnervoid DeltaTreeNode::DoSplit(InsertResult &InsertRes) { 313b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner assert(isFull() && "Why split a non-full node?"); 314b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 315b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Since this node is full, it contains 2*WidthFactor-1 values. We move 316b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // the first 'WidthFactor-1' values to the LHS child (which we leave in this 317b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // node), propagate one value up, and move the last 'WidthFactor-1' values 318b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the RHS child. 319b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 320b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Create the new child node. 321b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *NewNode; 322b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 323b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // If this is an interior node, also move over 'WidthFactor' children 324b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the new node. 325b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); 326b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&New->Children[0], &IN->Children[WidthFactor], 327b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner WidthFactor*sizeof(IN->Children[0])); 328b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = New; 329b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } else { 330b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Just create the new leaf node. 331b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = new DeltaTreeNode(); 332b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } 333b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 334b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Move over the last 'WidthFactor-1' values from here to NewNode. 335b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&NewNode->Values[0], &Values[WidthFactor], 336b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner (WidthFactor-1)*sizeof(Values[0])); 337b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 338b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Decrease the number of values in the two nodes. 339b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; 340b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 341b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Recompute the two nodes' full delta. 342b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->RecomputeFullDeltaLocally(); 343b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner RecomputeFullDeltaLocally(); 344b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 345b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.LHS = this; 346b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.RHS = NewNode; 347b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.Split = Values[WidthFactor-1]; 348b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner} 349b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 350b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 3518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// DeltaTree Implementation 3548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 35622cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner//#define VERIFY_TREE 3578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 35822cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 3598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// VerifyTree - Walk the btree performing assertions on various properties to 3608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// verify consistency. This is useful for debugging new changes to the tree. 3618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic void VerifyTree(const DeltaTreeNode *N) { 3628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N); 3638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (IN == 0) { 3648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify leaves, just ensure that FullDelta matches up and the elements 3658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // are in proper order. 3668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { 3688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); 3708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += N->getValue(i).Delta; 3718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return; 3748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3768100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify interior nodes: Ensure that FullDelta matches up and the 3778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // elements are in proper order and the children are in proper order. 3788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { 3808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &IVal = N->getValue(i); 3818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *IChild = IN->getChild(i); 3828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); 3848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IVal.Delta; 3858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IChild->getFullDelta(); 3868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The largest value in child #i should be smaller than FileLoc. 3888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < 3898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner IVal.FileLoc); 3908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The smallest value in child #i+1 should be larger than FileLoc. 3928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); 3938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner VerifyTree(IChild); 3948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); 3978100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 40022cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif // VERIFY_TREE 4018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic DeltaTreeNode *getRoot(void *Root) { 4038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return (DeltaTreeNode*)Root; 4048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4068100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree() { 4078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 4088100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4098100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree(const DeltaTree &RHS) { 4108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Currently we only support copying when the RHS is empty. 4118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && 4128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner "Can only copy empty tree"); 4138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 4148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4168100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::~DeltaTree() { 4178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner getRoot(Root)->Destroy(); 4188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// getDeltaAt - Return the accumulated delta at the specified file offset. 4218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// This includes all insertions or delections that occurred *before* the 4228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// specified file index. 4238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerint DeltaTree::getDeltaAt(unsigned FileIndex) const { 4248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *Node = getRoot(Root); 4258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Result = 0; 4278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Walk down the tree. 4298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (1) { 4308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // For all nodes, include any local deltas before the specified file 4318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // index by summing them up directly. Keep track of how many were 4328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // included. 4338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned NumValsGreater = 0; 4348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; 4358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValsGreater) { 4368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &Val = Node->getValue(NumValsGreater); 4378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (Val.FileLoc >= FileIndex) 4398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner break; 4408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += Val.Delta; 4418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we have an interior node, include information about children and 4448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // recurse. Otherwise, if we have a leaf, we're done. 4458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node); 4468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (!IN) return Result; 4478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Include any children to the left of the values we skipped, all of 4498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // their deltas should be included as well. 4508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0; i != NumValsGreater; ++i) 4518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += IN->getChild(i)->getFullDelta(); 4528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found exactly the value we were looking for, break off the 4548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // search early. There is no need to search the RHS of the value for 4558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partial results. 4568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (NumValsGreater != Node->getNumValuesUsed() && 4578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node->getValue(NumValsGreater).FileLoc == FileIndex) 4588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Result; 4598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Otherwise, traverse down the tree. The selected subtree may be 4618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partially included in the range. 4628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node = IN->getChild(NumValsGreater); 4638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // NOT REACHED. 4658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// AddDelta - When a change is made that shifts around the text buffer, 4688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// this method is used to record that info. It inserts a delta of 'Delta' 4698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// into the current DeltaTree at offset FileIndex. 4708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTree::AddDelta(unsigned FileIndex, int Delta) { 4718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(Delta && "Adding a noop?"); 472b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *MyRoot = getRoot(Root); 4738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4743b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertResult InsertRes; 4753b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { 4763b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Root = MyRoot = new DeltaTreeInteriorNode(InsertRes); 4773b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 4788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 47922cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 480b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner VerifyTree(MyRoot); 48122cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif 4828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 484