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 14305c613af6cfc40e519c75d9d2c84c6fa9a841c0Ted Kremenek#include "clang/Rewrite/Core/DeltaTree.h" 155f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner#include "clang/Basic/LLVM.h" 163b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner#include <cstdio> 1755fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include <cstring> 188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerusing namespace clang; 198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The DeltaTree class is a multiway search tree (BTree) structure with some 213ea5cf8889f48809a94e886d013a911128664c88Chris Lattner/// fancy features. B-Trees are generally more memory and cache efficient 228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// than binary trees, because they store multiple keys/values in each node. 238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTree implements a key/value mapping from FileIndex to Delta, allowing 258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// fast lookup by FileIndex. However, an added (important) bonus is that it 268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// can also efficiently tell us the full accumulated delta for a specific 278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// file offset as well, without traversing the whole tree. 288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// 298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// The nodes of the tree are made up of instances of two classes: 308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// DeltaTreeNode and DeltaTreeInteriorNode. The later subclasses the 318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// former and adds children pointers. Each node knows the full delta of all 328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// entries (recursively) contained inside of it, which allows us to get the 338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// full delta implied by a whole subtree in constant time. 341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta - As code in the original input buffer is added and deleted, 378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// SourceDelta records are used to keep track of how the input SourceLocation 388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// object is mapped into the output buffer. 398100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner struct SourceDelta { 408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned FileLoc; 418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Delta; 421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static SourceDelta get(unsigned Loc, int D) { 448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta Delta; 458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.FileLoc = Loc; 468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Delta.Delta = D; 478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Delta; 488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 506991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor 518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// DeltaTreeNode - The common part of all nodes. 528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// 538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeNode { 546991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor public: 556991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor struct InsertResult { 566991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor DeltaTreeNode *LHS, *RHS; 576991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor SourceDelta Split; 586991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor }; 596991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor 606991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor private: 618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner friend class DeltaTreeInteriorNode; 621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// WidthFactor - This controls the number of K/V slots held in the BTree: 648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// how wide it is. Each level of the BTree is guaranteed to have at least 65febe719596ee68605944da5f2e03258e18e6df8cChris Lattner /// WidthFactor-1 K/V pairs (except the root) and may have at most 66febe719596ee68605944da5f2e03258e18e6df8cChris Lattner /// 2*WidthFactor-1 K/V pairs. 678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner enum { WidthFactor = 8 }; 681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// Values - This tracks the SourceDelta's currently in this node. 708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// 718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta Values[2*WidthFactor-1]; 721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// NumValuesUsed - This tracks the number of values this node currently 748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// holds. 758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned char NumValuesUsed; 761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// IsLeaf - This is true if this is a leaf of the btree. If false, this is 788100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// an interior node, and is actually an instance of DeltaTreeInteriorNode. 798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool IsLeaf; 801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// FullDelta - This is the full delta of all the values in this node and 828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// all children nodes. 838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta; 848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner public: 858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode(bool isLeaf = true) 86b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner : NumValuesUsed(0), IsLeaf(isLeaf), FullDelta(0) {} 871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool isLeaf() const { return IsLeaf; } 898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int getFullDelta() const { return FullDelta; } 908100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner bool isFull() const { return NumValuesUsed == 2*WidthFactor-1; } 911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned getNumValuesUsed() const { return NumValuesUsed; } 938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &getValue(unsigned i) const { 948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < NumValuesUsed && "Invalid value #"); 958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Values[i]; 968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 978100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner SourceDelta &getValue(unsigned i) { 988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < NumValuesUsed && "Invalid value #"); 998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Values[i]; 1008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1023b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 1033b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// this node. If insertion is easy, do it and return false. Otherwise, 1043b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// split the node, populate InsertRes with info about the split, and return 1053b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner /// true. 1063b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner bool DoInsertion(unsigned FileIndex, int Delta, InsertResult *InsertRes); 1073b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 108b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner void DoSplit(InsertResult &InsertRes); 1091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// local walk over our contained deltas. 1138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void RecomputeFullDeltaLocally(); 1141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner void Destroy(); 1168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} // end anonymous namespace 1188100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnernamespace { 1208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// DeltaTreeInteriorNode - When isLeaf = false, a node has child pointers. 1218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner /// This class tracks them. 1228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner class DeltaTreeInteriorNode : public DeltaTreeNode { 1238100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *Children[2*WidthFactor]; 1248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ~DeltaTreeInteriorNode() { 1258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = NumValuesUsed+1; i != e; ++i) 1268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Children[i]->Destroy(); 1278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1288100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner friend class DeltaTreeNode; 1298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner public: 1308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeInteriorNode() : DeltaTreeNode(false /*nonleaf*/) {} 1311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump DeltaTreeInteriorNode(const InsertResult &IR) 1333b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner : DeltaTreeNode(false /*nonleaf*/) { 1343b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Children[0] = IR.LHS; 1353b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Children[1] = IR.RHS; 1363b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[0] = IR.Split; 1373b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner FullDelta = IR.LHS->getFullDelta()+IR.RHS->getFullDelta()+IR.Split.Delta; 1383b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner NumValuesUsed = 1; 1393b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 1401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *getChild(unsigned i) const { 1428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner DeltaTreeNode *getChild(unsigned i) { 1468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(i < getNumValuesUsed()+1 && "Invalid child"); 1478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return Children[i]; 1488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner static inline bool classof(const DeltaTreeNode *N) { return !N->isLeaf(); } 1518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner }; 1528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// Destroy - A 'virtual' destructor. 1568100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::Destroy() { 1578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (isLeaf()) 1588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete this; 1598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner else 1608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner delete cast<DeltaTreeInteriorNode>(this); 1618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// RecomputeFullDeltaLocally - Recompute the FullDelta field by doing a 1648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// local walk over our contained deltas. 1658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTreeNode::RecomputeFullDeltaLocally() { 1668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int NewFullDelta = 0; 1678100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed(); i != e; ++i) 1688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += Values[i].Delta; 1698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) 1708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = getNumValuesUsed()+1; i != e; ++i) 1718100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner NewFullDelta += IN->getChild(i)->getFullDelta(); 1728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta = NewFullDelta; 1738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 1748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 1753b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// DoInsertion - Do an insertion of the specified FileIndex/Delta pair into 1763b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// this node. If insertion is easy, do it and return false. Otherwise, 1773b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// split the node, populate InsertRes with info about the split, and return 1783b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// true. 1791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stumpbool DeltaTreeNode::DoInsertion(unsigned FileIndex, int Delta, 1803b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertResult *InsertRes) { 1818100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Maintain full delta for this node. 1828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += Delta; 1831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Find the insertion point, the first delta whose index is >= FileIndex. 1858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned i = 0, e = getNumValuesUsed(); 1868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (i != e && FileIndex > getValue(i).FileLoc) 1878100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++i; 1881eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found an a record for exactly this file index, just merge this 1903b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // value into the pre-existing record and finish early. 1918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e && getValue(i).FileLoc == FileIndex) { 1923b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // NOTE: Delta could drop to zero here. This means that the delta entry is 1933b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // useless and could be removed. Supporting erases is more complex than 1943b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // leaving an entry with Delta=0, so we just leave an entry with Delta=0 in 1953b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the tree. 1968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Values[i].Delta += Delta; 1973b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 1988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 1993b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2003b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, we found an insertion point, and we know that the value at the 2013b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // specified index is > FileIndex. Handle the leaf case first. 2023b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (isLeaf()) { 2033b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!isFull()) { 2043b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // For an insertion into a non-full leaf node, just insert the value in 2053b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // its sorted position. This requires moving later values over. 2063b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (i != e) 2073b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&Values[i+1], &Values[i], sizeof(Values[0])*(e-i)); 2083b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[i] = SourceDelta::get(FileIndex, Delta); 2093b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++NumValuesUsed; 2103b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 2118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2121eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2133b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, if this is leaf is full, split the node at its median, insert 2143b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the value into one of the children, and return the result. 2153b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner assert(InsertRes && "No result location specified"); 2163b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DoSplit(*InsertRes); 2171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2183b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (InsertRes->Split.FileLoc > FileIndex) 2196bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines InsertRes->LHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 2203b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner else 2216bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines InsertRes->RHS->DoInsertion(FileIndex, Delta, nullptr /*can't fail*/); 2223b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return true; 2233b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 2241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2253b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Otherwise, this is an interior node. Send the request down the tree. 2263b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeInteriorNode *IN = cast<DeltaTreeInteriorNode>(this); 2273b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!IN->Children[i]->DoInsertion(FileIndex, Delta, InsertRes)) 2283b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; // If there was space in the child, just return. 2293b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner 2303b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Okay, this split the subtree, producing a new value and two children to 2313b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // insert here. If this node is non-full, we can just insert it directly. 2323b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (!isFull()) { 2333b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Now that we have two nodes and a new element, insert the perclated value 2343b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // into ourself by moving all the later values/children down, then inserting 2353b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // the new one. 2368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i != e) 2373b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&IN->Children[i+2], &IN->Children[i+1], 2383b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(IN->Children[0])); 2393b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i] = InsertRes->LHS; 2403b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i+1] = InsertRes->RHS; 2411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2423b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (e != i) 2433b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&Values[i+1], &Values[i], (e-i)*sizeof(Values[0])); 2443b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Values[i] = InsertRes->Split; 2458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValuesUsed; 2463b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return false; 2478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 2481eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2493b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Finally, if this interior node was full and a node is percolated up, split 2503b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // ourself and return that up the chain. Start by saving all our info to 2513b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // avoid having the split clobber it. 2523b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner IN->Children[i] = InsertRes->LHS; 2533b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeNode *SubRHS = InsertRes->RHS; 2543b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner SourceDelta SubSplit = InsertRes->Split; 2551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2563b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Do the split. 2573b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DoSplit(*InsertRes); 2588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2593b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Figure out where to insert SubRHS/NewSplit. 2603b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner DeltaTreeInteriorNode *InsertSide; 2613b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (SubSplit.FileLoc < InsertRes->Split.FileLoc) 2623b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->LHS); 2633b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner else 2643b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide = cast<DeltaTreeInteriorNode>(InsertRes->RHS); 2651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump // We now have a non-empty interior node 'InsertSide' to insert 2673b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // SubRHS/SubSplit into. Find out where to insert SubSplit. 2681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2693b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Find the insertion point, the first delta whose index is >SubSplit.FileLoc. 2703b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner i = 0; e = InsertSide->getNumValuesUsed(); 2713b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner while (i != e && SubSplit.FileLoc > InsertSide->getValue(i).FileLoc) 2723b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++i; 2731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2743b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // Now we know that i is the place to insert the split value into. Insert it 2753b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner // and the child right after it. 2763b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (i != e) 2773b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&InsertSide->Children[i+2], &InsertSide->Children[i+1], 2783b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(IN->Children[0])); 2793b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->Children[i+1] = SubRHS; 2801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2813b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (e != i) 2823b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner memmove(&InsertSide->Values[i+1], &InsertSide->Values[i], 2833b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner (e-i)*sizeof(Values[0])); 2843b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->Values[i] = SubSplit; 2853b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner ++InsertSide->NumValuesUsed; 2863b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner InsertSide->FullDelta += SubSplit.Delta + SubRHS->getFullDelta(); 2873b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner return true; 2888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 2898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 2903b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// DoSplit - Split the currently full node (which has 2*WidthFactor-1 values) 2913b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// into two subtrees each with "WidthFactor-1" values and a pivot value. 2923b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner/// Return the pieces in InsertRes. 293b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattnervoid DeltaTreeNode::DoSplit(InsertResult &InsertRes) { 294b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner assert(isFull() && "Why split a non-full node?"); 2951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 296b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Since this node is full, it contains 2*WidthFactor-1 values. We move 297b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // the first 'WidthFactor-1' values to the LHS child (which we leave in this 298b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // node), propagate one value up, and move the last 'WidthFactor-1' values 299b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the RHS child. 3001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 301b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Create the new child node. 302b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *NewNode; 303b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner if (DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(this)) { 304b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // If this is an interior node, also move over 'WidthFactor' children 305b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // into the new node. 306b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeInteriorNode *New = new DeltaTreeInteriorNode(); 307b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&New->Children[0], &IN->Children[WidthFactor], 308b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner WidthFactor*sizeof(IN->Children[0])); 309b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = New; 310b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } else { 311b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Just create the new leaf node. 312b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode = new DeltaTreeNode(); 313b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner } 3141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 315b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Move over the last 'WidthFactor-1' values from here to NewNode. 316b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner memcpy(&NewNode->Values[0], &Values[WidthFactor], 317b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner (WidthFactor-1)*sizeof(Values[0])); 3181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 319b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Decrease the number of values in the two nodes. 320b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->NumValuesUsed = NumValuesUsed = WidthFactor-1; 3211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 322b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner // Recompute the two nodes' full delta. 323b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner NewNode->RecomputeFullDeltaLocally(); 324b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner RecomputeFullDeltaLocally(); 3251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 326b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.LHS = this; 327b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.RHS = NewNode; 328b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner InsertRes.Split = Values[WidthFactor-1]; 329b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner} 330b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 331b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner 3328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3338100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner// DeltaTree Implementation 3358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner//===----------------------------------------------------------------------===// 3368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 33722cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner//#define VERIFY_TREE 3388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 33922cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 3408100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// VerifyTree - Walk the btree performing assertions on various properties to 3418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// verify consistency. This is useful for debugging new changes to the tree. 3428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic void VerifyTree(const DeltaTreeNode *N) { 3438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(N); 3448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (IN == 0) { 3458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify leaves, just ensure that FullDelta matches up and the elements 3468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // are in proper order. 3478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = N->getNumValuesUsed(); i != e; ++i) { 3498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(N->getValue(i-1).FileLoc < N->getValue(i).FileLoc); 3518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += N->getValue(i).Delta; 3528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3538100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3548100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return; 3558100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3578100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Verify interior nodes: Ensure that FullDelta matches up and the 3588100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // elements are in proper order and the children are in proper order. 3598100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int FullDelta = 0; 3608100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0, e = IN->getNumValuesUsed(); i != e; ++i) { 3618100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &IVal = N->getValue(i); 3628100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *IChild = IN->getChild(i); 3638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (i) 3648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getValue(i-1).FileLoc < IVal.FileLoc); 3658100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IVal.Delta; 3668100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IChild->getFullDelta(); 3671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3688100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The largest value in child #i should be smaller than FileLoc. 3698100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IChild->getValue(IChild->getNumValuesUsed()-1).FileLoc < 3708100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner IVal.FileLoc); 3711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3728100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // The smallest value in child #i+1 should be larger than FileLoc. 3738100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(IN->getChild(i+1)->getValue(0).FileLoc > IVal.FileLoc); 3748100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner VerifyTree(IChild); 3758100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 3761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3778100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner FullDelta += IN->getChild(IN->getNumValuesUsed())->getFullDelta(); 3781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3798100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(FullDelta == N->getFullDelta()); 3808100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 38122cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif // VERIFY_TREE 3828100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3838100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerstatic DeltaTreeNode *getRoot(void *Root) { 3848100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner return (DeltaTreeNode*)Root; 3858100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3868100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3878100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree() { 3888100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 3898100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3908100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::DeltaTree(const DeltaTree &RHS) { 3918100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Currently we only support copying when the RHS is empty. 3928100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(getRoot(RHS.Root)->getNumValuesUsed() == 0 && 3938100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner "Can only copy empty tree"); 3948100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Root = new DeltaTreeNode(); 3958100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 3968100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 3978100d749514748ab1e9f219d3a6ce2f4c6389140Chris LattnerDeltaTree::~DeltaTree() { 3988100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner getRoot(Root)->Destroy(); 3998100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4008100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4018100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// getDeltaAt - Return the accumulated delta at the specified file offset. 4028100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// This includes all insertions or delections that occurred *before* the 4038100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// specified file index. 4048100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnerint DeltaTree::getDeltaAt(unsigned FileIndex) const { 4058100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeNode *Node = getRoot(Root); 4061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4078100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner int Result = 0; 4081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4098100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Walk down the tree. 4108100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner while (1) { 4118100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // For all nodes, include any local deltas before the specified file 4128100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // index by summing them up directly. Keep track of how many were 4138100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // included. 4148100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner unsigned NumValsGreater = 0; 4158100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned e = Node->getNumValuesUsed(); NumValsGreater != e; 4168100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner ++NumValsGreater) { 4178100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const SourceDelta &Val = Node->getValue(NumValsGreater); 4181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4198100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (Val.FileLoc >= FileIndex) 4208100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner break; 4218100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += Val.Delta; 4228100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4248100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we have an interior node, include information about children and 4258100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // recurse. Otherwise, if we have a leaf, we're done. 4268100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner const DeltaTreeInteriorNode *IN = dyn_cast<DeltaTreeInteriorNode>(Node); 4278100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (!IN) return Result; 4281eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4298100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Include any children to the left of the values we skipped, all of 4308100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // their deltas should be included as well. 4318100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner for (unsigned i = 0; i != NumValsGreater; ++i) 4328100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Result += IN->getChild(i)->getFullDelta(); 4331eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4348100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // If we found exactly the value we were looking for, break off the 4358100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // search early. There is no need to search the RHS of the value for 4368100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partial results. 4378100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner if (NumValsGreater != Node->getNumValuesUsed() && 4388100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node->getValue(NumValsGreater).FileLoc == FileIndex) 43953f9e203c1491c3ae4e733700ad03eae3e74ea10Chris Lattner return Result+IN->getChild(NumValsGreater)->getFullDelta(); 4401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4418100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // Otherwise, traverse down the tree. The selected subtree may be 4428100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // partially included in the range. 4438100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner Node = IN->getChild(NumValsGreater); 4448100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner } 4458100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner // NOT REACHED. 4468100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4478100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 4488100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// AddDelta - When a change is made that shifts around the text buffer, 4498100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// this method is used to record that info. It inserts a delta of 'Delta' 4508100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner/// into the current DeltaTree at offset FileIndex. 4518100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattnervoid DeltaTree::AddDelta(unsigned FileIndex, int Delta) { 4528100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner assert(Delta && "Adding a noop?"); 453b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner DeltaTreeNode *MyRoot = getRoot(Root); 4541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4556991218a7075a4dcff777ea309a8a542b822de17Douglas Gregor DeltaTreeNode::InsertResult InsertRes; 4563b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner if (MyRoot->DoInsertion(FileIndex, Delta, &InsertRes)) { 4573b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner Root = MyRoot = new DeltaTreeInteriorNode(InsertRes); 4583b7ff0d143014ea86328e8fa9196a7537dce7beaChris Lattner } 4591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 46022cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#ifdef VERIFY_TREE 461b169e903c5d235710b829d4b4922fd8f90ee90b1Chris Lattner VerifyTree(MyRoot); 46222cb282b29deb9a7b919a339d450d36a3fc205a6Chris Lattner#endif 4638100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner} 4648100d749514748ab1e9f219d3a6ce2f4c6389140Chris Lattner 465