15fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===--- RewriteRope.cpp - Rope specialized for rewriter --------*- C++ -*-===// 25fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// 35fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// The LLVM Compiler Infrastructure 45fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// 55fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// This file is distributed under the University of Illinois Open Source 65fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// License. See LICENSE.TXT for details. 75fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// 85fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 95fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// 105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// This file implements the RewriteRope class, which is a powerful string. 115fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// 125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 135fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 14305c613af6cfc40e519c75d9d2c84c6fa9a841c0Ted Kremenek#include "clang/Rewrite/Core/RewriteRope.h" 155f9e272e632e951b1efe824cd16acb4d96077930Chris Lattner#include "clang/Basic/LLVM.h" 165618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner#include <algorithm> 175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnerusing namespace clang; 185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 19b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RewriteRope is a "strong" string class, designed to make insertions and 20b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// deletions in the middle of the string nearly constant time (really, they are 21b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// O(log N), but with a very low constant factor). 22b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 23b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// The implementation of this datastructure is a conceptual linear sequence of 24b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopePiece elements. Each RopePiece represents a view on a separately 25b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// allocated and reference counted string. This means that splitting a very 26b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// long string can be done in constant time by splitting a RopePiece that 27b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// references the whole string into two rope pieces that reference each half. 28b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// Once split, another string can be inserted in between the two halves by 29b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// inserting a RopePiece in between the two others. All of this is very 30b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// inexpensive: it takes time proportional to the number of RopePieces, not the 31b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// length of the strings they represent. 32b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 33b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// While a linear sequences of RopePieces is the conceptual model, the actual 34b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// implementation captures them in an adapted B+ Tree. Using a B+ tree (which 35b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// is a tree that keeps the values in the leaves and has where each node 36b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// contains a reasonable number of pointers to children/values) allows us to 37b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// maintain efficient operation when the RewriteRope contains a *huge* number 38b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// of RopePieces. The basic idea of the B+ Tree is that it allows us to find 39b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// the RopePiece corresponding to some offset very efficiently, and it 40b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// automatically balances itself on insertions of RopePieces (which can happen 41b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// for both insertions and erases of string ranges). 42b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 43b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// The one wrinkle on the theory is that we don't attempt to keep the tree 44b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// properly balanced when erases happen. Erases of string data can both insert 45b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// new RopePieces (e.g. when the middle of some other rope piece is deleted, 46b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// which results in two rope pieces, which is just like an insert) or it can 47b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// reduce the number of RopePieces maintained by the B+Tree. In the case when 48b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// the number of RopePieces is reduced, we don't attempt to maintain the 49b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// standard 'invariant' that each node in the tree contains at least 50b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 'WidthFactor' children/values. For our use cases, this doesn't seem to 51b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// matter. 52b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 53b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// The implementation below is primarily implemented in terms of three classes: 54b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopePieceBTreeNode - Common base class for: 55b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// 56b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece 57b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// nodes. This directly represents a chunk of the string with those 58b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopePieces contatenated. 59b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopePieceBTreeInterior - An interior node in the B+ Tree, which manages 60b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// up to '2*WidthFactor' other nodes in the tree. 615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTreeNode Class 655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 665fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnernamespace { 68b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// RopePieceBTreeNode - Common base class of RopePieceBTreeLeaf and 69b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// RopePieceBTreeInterior. This provides some 'virtual' dispatching methods 70b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// and a flag that determines which subclass the instance is. Also 71b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// important, this node knows the full extend of the node, including any 72b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// children that it has. This allows efficient skipping over entire subtrees 73b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// when looking for an offset in the BTree. 745fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner class RopePieceBTreeNode { 755fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner protected: 765fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// WidthFactor - This controls the number of K/V slots held in the BTree: 775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// how wide it is. Each level of the BTree is guaranteed to have at least 785fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// 'WidthFactor' elements in it (either ropepieces or children), (except 795fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// the root, which may have less) and may have at most 2*WidthFactor 805fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// elements. 815fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner enum { WidthFactor = 8 }; 821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 835fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// Size - This is the number of bytes of file this node (including any 845fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// potential children) covers. 855fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned Size; 861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 875fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// IsLeaf - True if this is an instance of RopePieceBTreeLeaf, false if it 885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// is an instance of RopePieceBTreeInterior. 895fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner bool IsLeaf; 901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 91b442e2197066f4341bab807a46338045acd7e3daChris Lattner RopePieceBTreeNode(bool isLeaf) : Size(0), IsLeaf(isLeaf) {} 925fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ~RopePieceBTreeNode() {} 935fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner public: 941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner bool isLeaf() const { return IsLeaf; } 965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned size() const { return Size; } 971eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void Destroy(); 991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1005fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// split - Split the range containing the specified offset so that we are 1015fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a place to do an insertion at the specified 102bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// offset. The offset is relative, so "0" is the start of the node. 103bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 104bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 105bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 106bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *split(unsigned Offset); 1071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1085fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// insert - Insert the specified ropepiece into this tree node at the 1095fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// specified offset. The offset is relative, so "0" is the start of the 110bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node. 111bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 112bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 113bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 114bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R); 1151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1165fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// erase - Remove NumBytes from this node at the specified offset. We are 1175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a split at Offset. 1185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void erase(unsigned Offset, unsigned NumBytes); 1191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner }; 1215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} // end anonymous namespace 1225fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 1235fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 1245fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTreeLeaf Class 1255fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 1265fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 1275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnernamespace { 128b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// RopePieceBTreeLeaf - Directly manages up to '2*WidthFactor' RopePiece 129b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// nodes. This directly represents a chunk of the string with those 130b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// RopePieces contatenated. Since this is a B+Tree, all values (in this case 131b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// instances of RopePiece) are stored in leaves like this. To make iteration 132b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// over the leaves efficient, they maintain a singly linked list through the 133b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// NextLeaf field. This allows the B+Tree forward iterator to be constant 134b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// time for all increments. 1355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner class RopePieceBTreeLeaf : public RopePieceBTreeNode { 1365fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// NumPieces - This holds the number of rope pieces currently active in the 1375fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// Pieces array. 1385fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned char NumPieces; 1391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1405fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// Pieces - This tracks the file chunks currently in this leaf. 1415fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// 1425fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePiece Pieces[2*WidthFactor]; 1431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1445fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// NextLeaf - This is a pointer to the next leaf in the tree, allowing 1455fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// efficient in-order forward iteration of the tree without traversal. 1463d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner RopePieceBTreeLeaf **PrevLeaf, *NextLeaf; 1475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner public: 1483d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner RopePieceBTreeLeaf() : RopePieceBTreeNode(true), NumPieces(0), 1496bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines PrevLeaf(nullptr), NextLeaf(nullptr) {} 1503d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner ~RopePieceBTreeLeaf() { 1513d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner if (PrevLeaf || NextLeaf) 1523d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner removeFromLeafInOrder(); 15390556e369d7d4364a1ee3924316f729bcbda24e5Ted Kremenek clear(); 1543d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner } 1551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner bool isFull() const { return NumPieces == 2*WidthFactor; } 1571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1585fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// clear - Remove all rope pieces from this leaf. 1595fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void clear() { 1605fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (NumPieces) 1615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[--NumPieces] = RopePiece(); 1625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size = 0; 1635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 1641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned getNumPieces() const { return NumPieces; } 1661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner const RopePiece &getPiece(unsigned i) const { 1685fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(i < getNumPieces() && "Invalid piece ID"); 1695fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return Pieces[i]; 1705fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 1711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1725fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner const RopePieceBTreeLeaf *getNextLeafInOrder() const { return NextLeaf; } 1733d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner void insertAfterLeafInOrder(RopePieceBTreeLeaf *Node) { 1746bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines assert(!PrevLeaf && !NextLeaf && "Already in ordering"); 1751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1763d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner NextLeaf = Node->NextLeaf; 1773d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner if (NextLeaf) 1783d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner NextLeaf->PrevLeaf = &NextLeaf; 1793d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner PrevLeaf = &Node->NextLeaf; 1803d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner Node->NextLeaf = this; 1813d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner } 1821eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1833d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner void removeFromLeafInOrder() { 1843d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner if (PrevLeaf) { 1853d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner *PrevLeaf = NextLeaf; 1863d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner if (NextLeaf) 1873d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner NextLeaf->PrevLeaf = PrevLeaf; 1883d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner } else if (NextLeaf) { 1896bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines NextLeaf->PrevLeaf = nullptr; 1903d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner } 1913d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner } 1921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 193b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// FullRecomputeSizeLocally - This method recomputes the 'Size' field by 194b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// summing the size of all RopePieces. 1955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void FullRecomputeSizeLocally() { 1965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size = 0; 1975fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (unsigned i = 0, e = getNumPieces(); i != e; ++i) 1985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size += getPiece(i).size(); 1995fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 2001eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2015fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// split - Split the range containing the specified offset so that we are 2025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a place to do an insertion at the specified 203bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// offset. The offset is relative, so "0" is the start of the node. 204bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 205bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 206bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 207bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *split(unsigned Offset); 2081eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2095fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// insert - Insert the specified ropepiece into this tree node at the 2105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// specified offset. The offset is relative, so "0" is the start of the 211bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node. 212bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 213bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 214bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 215bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R); 2161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// erase - Remove NumBytes from this node at the specified offset. We are 2195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a split at Offset. 2205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void erase(unsigned Offset, unsigned NumBytes); 2211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2225fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner static inline bool classof(const RopePieceBTreeNode *N) { 2235fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return N->isLeaf(); 2245fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 2255fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner }; 2265fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} // end anonymous namespace 2275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 2285fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// split - Split the range containing the specified offset so that we are 2295fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a place to do an insertion at the specified 230bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// offset. The offset is relative, so "0" is the start of the node. 231bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 232bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 233bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 234bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeLeaf::split(unsigned Offset) { 2355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the insertion point. We are guaranteed that there is a split at the 2365fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // specified offset so find it. 2375fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset == 0 || Offset == size()) { 2385fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Fastpath for a common case. There is already a splitpoint at the end. 2396bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 2405fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 2411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2425fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the piece that this offset lands in. 2435fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned PieceOffs = 0; 2445fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0; 2455fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (Offset >= PieceOffs+Pieces[i].size()) { 2465fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner PieceOffs += Pieces[i].size(); 2475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ++i; 2485fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 2491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If there is already a split point at the specified offset, just return 2515fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // success. 2525fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (PieceOffs == Offset) 2536bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 2541eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2555fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Otherwise, we need to split piece 'i' at Offset-PieceOffs. Convert Offset 2565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // to being Piece relative. 2575fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned IntraPieceOffset = Offset-PieceOffs; 2581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2595fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // We do this by shrinking the RopePiece and then doing an insert of the tail. 2605fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePiece Tail(Pieces[i].StrData, Pieces[i].StartOffs+IntraPieceOffset, 2615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[i].EndOffs); 2625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size -= Pieces[i].size(); 2635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[i].EndOffs = Pieces[i].StartOffs+IntraPieceOffset; 2645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size += Pieces[i].size(); 2651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 266bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return insert(Offset, Tail); 2675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 2685fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 2695fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 2705fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// insert - Insert the specified RopePiece into this tree node at the 271bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// specified offset. The offset is relative, so "0" is the start of the node. 272bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 273bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 274bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 275bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeLeaf::insert(unsigned Offset, 276bf26856c2133238ce81d461127eb4d07815014fdChris Lattner const RopePiece &R) { 2775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If this node is not full, insert the piece. 2785fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (!isFull()) { 2795fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the insertion point. We are guaranteed that there is a split at the 2805fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // specified offset so find it. 2815fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0, e = getNumPieces(); 2825fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset == size()) { 2835fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Fastpath for a common case. 2845fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner i = e; 2855fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } else { 2865fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned SlotOffs = 0; 2875fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset > SlotOffs; ++i) 2885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner SlotOffs += getPiece(i).size(); 2895fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(SlotOffs == Offset && "Split didn't occur before insertion!"); 2905fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 2911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 2925fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // For an insertion into a non-full leaf node, just insert the value in 2935fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // its sorted position. This requires moving later values over. 2945fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; i != e; --e) 2955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[e] = Pieces[e-1]; 2965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[i] = R; 2975fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ++NumPieces; 2985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size += R.size(); 2996bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 3005fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 3011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Otherwise, if this is leaf is full, split it in two halves. Since this 3035fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // node is full, it contains 2*WidthFactor values. We move the first 3045fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // 'WidthFactor' values to the LHS child (which we leave in this node) and 3055fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // move the last 'WidthFactor' values into the RHS child. 3061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3075fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Create the new node. 3085fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeLeaf *NewNode = new RopePieceBTreeLeaf(); 3091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Move over the last 'WidthFactor' values from here to NewNode. 3115fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner std::copy(&Pieces[WidthFactor], &Pieces[2*WidthFactor], 3125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner &NewNode->Pieces[0]); 3135fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Replace old pieces with null RopePieces to drop refcounts. 3145fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner std::fill(&Pieces[WidthFactor], &Pieces[2*WidthFactor], RopePiece()); 3151eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3165fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Decrease the number of values in the two nodes. 3175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NewNode->NumPieces = NumPieces = WidthFactor; 3181eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Recompute the two nodes' size. 3205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NewNode->FullRecomputeSizeLocally(); 3215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner FullRecomputeSizeLocally(); 3221eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3235fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Update the list of leaves. 3243d2e8c7b70d5719d00b919708fdd5a45cffda836Chris Lattner NewNode->insertAfterLeafInOrder(this); 3251eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 326bf26856c2133238ce81d461127eb4d07815014fdChris Lattner // These insertions can't fail. 3275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (this->size() >= Offset) 328bf26856c2133238ce81d461127eb4d07815014fdChris Lattner this->insert(Offset, R); 3295fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else 330bf26856c2133238ce81d461127eb4d07815014fdChris Lattner NewNode->insert(Offset - this->size(), R); 331bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return NewNode; 3325fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 3335fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 3345fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// erase - Remove NumBytes from this node at the specified offset. We are 3355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a split at Offset. 3365fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTreeLeaf::erase(unsigned Offset, unsigned NumBytes) { 3375fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Since we are guaranteed that there is a split at Offset, we start by 3385fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // finding the Piece that starts there. 3395fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned PieceOffs = 0; 3405fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0; 3415fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset > PieceOffs; ++i) 3425fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner PieceOffs += getPiece(i).size(); 3435fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(PieceOffs == Offset && "Split didn't occur before erase!"); 3441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3455fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned StartPiece = i; 3461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Figure out how many pieces completely cover 'NumBytes'. We want to remove 3485fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // all of them. 3495fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset+NumBytes > PieceOffs+getPiece(i).size(); ++i) 3505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner PieceOffs += getPiece(i).size(); 3511eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3525fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If we exactly include the last one, include it in the region to delete. 3535fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset+NumBytes == PieceOffs+getPiece(i).size()) 3545fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner PieceOffs += getPiece(i).size(), ++i; 3551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If we completely cover some RopePieces, erase them now. 3575fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (i != StartPiece) { 3585fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned NumDeleted = i-StartPiece; 3595fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; i != getNumPieces(); ++i) 3605fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[i-NumDeleted] = Pieces[i]; 3611eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Drop references to dead rope pieces. 3635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner std::fill(&Pieces[getNumPieces()-NumDeleted], &Pieces[getNumPieces()], 3645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePiece()); 3655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NumPieces -= NumDeleted; 3661eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned CoverBytes = PieceOffs-Offset; 3685fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NumBytes -= CoverBytes; 3695fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size -= CoverBytes; 3705fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 3711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3725fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If we completely removed some stuff, we could be done. 3735fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (NumBytes == 0) return; 3741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3755fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Okay, now might be erasing part of some Piece. If this is the case, then 3765fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // move the start point of the piece. 3775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(getPiece(StartPiece).size() > NumBytes); 3785fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Pieces[StartPiece].StartOffs += NumBytes; 3791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3805fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // The size of this node just shrunk by NumBytes. 3815fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size -= NumBytes; 3825fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 3835fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 3845fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 3855fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTreeInterior Class 3865fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 3875fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 3885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnernamespace { 389b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// RopePieceBTreeInterior - This represents an interior node in the B+Tree, 390b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// which holds up to 2*WidthFactor pointers to child nodes. 3915fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner class RopePieceBTreeInterior : public RopePieceBTreeNode { 3925fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// NumChildren - This holds the number of children currently active in the 3935fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// Children array. 3945fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned char NumChildren; 3955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeNode *Children[2*WidthFactor]; 3965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner public: 39770778c85825a00170c8c70ae351252743463d8ddChris Lattner RopePieceBTreeInterior() : RopePieceBTreeNode(false), NumChildren(0) {} 3981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3995fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeInterior(RopePieceBTreeNode *LHS, RopePieceBTreeNode *RHS) 4005fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner : RopePieceBTreeNode(false) { 4015fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Children[0] = LHS; 4025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Children[1] = RHS; 4035fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NumChildren = 2; 4045fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size = LHS->size() + RHS->size(); 4055fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 4061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 407398a4983cde8d31f0e2d9836010a943a9d6c0427Benjamin Kramer ~RopePieceBTreeInterior() { 408a9ab209752e4afe059f1456871bc442f28914e37Benjamin Kramer for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 409a9ab209752e4afe059f1456871bc442f28914e37Benjamin Kramer Children[i]->Destroy(); 410398a4983cde8d31f0e2d9836010a943a9d6c0427Benjamin Kramer } 411398a4983cde8d31f0e2d9836010a943a9d6c0427Benjamin Kramer 4125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner bool isFull() const { return NumChildren == 2*WidthFactor; } 4131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4145fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned getNumChildren() const { return NumChildren; } 4155fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner const RopePieceBTreeNode *getChild(unsigned i) const { 4165fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(i < NumChildren && "invalid child #"); 4175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return Children[i]; 4185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 4195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeNode *getChild(unsigned i) { 4205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(i < NumChildren && "invalid child #"); 4215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return Children[i]; 4225fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 4231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 424b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// FullRecomputeSizeLocally - Recompute the Size field of this node by 425b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner /// summing up the sizes of the child nodes. 4265fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void FullRecomputeSizeLocally() { 4275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size = 0; 4285fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 4295fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size += getChild(i)->size(); 4305fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 4311eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4335fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// split - Split the range containing the specified offset so that we are 4345fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a place to do an insertion at the specified 435bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// offset. The offset is relative, so "0" is the start of the node. 436bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 437bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 438bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 439bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *split(unsigned Offset); 4401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4425fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// insert - Insert the specified ropepiece into this tree node at the 4435fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// specified offset. The offset is relative, so "0" is the start of the 444bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node. 445bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// 446bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// If there is no space in this subtree for the extra piece, the extra tree 447bf26856c2133238ce81d461127eb4d07815014fdChris Lattner /// node is returned and must be inserted into a parent. 448bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *insert(unsigned Offset, const RopePiece &R); 4491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// HandleChildPiece - A child propagated an insertion result up to us. 4515fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// Insert the new child, and/or propagate the result further up the tree. 452bf26856c2133238ce81d461127eb4d07815014fdChris Lattner RopePieceBTreeNode *HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS); 4531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4545fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// erase - Remove NumBytes from this node at the specified offset. We are 4555fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner /// guaranteed that there is a split at Offset. 4565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner void erase(unsigned Offset, unsigned NumBytes); 4571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4585fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner static inline bool classof(const RopePieceBTreeNode *N) { 4591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return !N->isLeaf(); 4605fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 4615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner }; 4625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} // end anonymous namespace 4635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 4645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// split - Split the range containing the specified offset so that we are 4655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a place to do an insertion at the specified 466bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// offset. The offset is relative, so "0" is the start of the node. 467bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 468bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 469bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 470bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeInterior::split(unsigned Offset) { 4715fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Figure out which child to split. 4725fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset == 0 || Offset == size()) 4736bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; // If we have an exact offset, we're already split. 4741eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4755fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned ChildOffset = 0; 4765fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0; 4775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset >= ChildOffset+getChild(i)->size(); ++i) 4785fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ChildOffset += getChild(i)->size(); 4791eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4805fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If already split there, we're done. 4815fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (ChildOffset == Offset) 4826bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 4831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4845fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Otherwise, recursively split the child. 4851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump if (RopePieceBTreeNode *RHS = getChild(i)->split(Offset-ChildOffset)) 486bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return HandleChildPiece(i, RHS); 4876bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; // Done! 4885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 4895fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 4905fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// insert - Insert the specified ropepiece into this tree node at the 4915fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// specified offset. The offset is relative, so "0" is the start of the 492bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node. 493bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 494bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 495bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 496bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeInterior::insert(unsigned Offset, 497bf26856c2133238ce81d461127eb4d07815014fdChris Lattner const RopePiece &R) { 4985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the insertion point. We are guaranteed that there is a split at the 4995fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // specified offset so find it. 5005fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0, e = getNumChildren(); 5011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned ChildOffs = 0; 5035fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset == size()) { 5045fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Fastpath for a common case. Insert at end of last child. 5055fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner i = e-1; 5065fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ChildOffs = size()-getChild(i)->size(); 5075fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } else { 5085fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset > ChildOffs+getChild(i)->size(); ++i) 5095fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ChildOffs += getChild(i)->size(); 5105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 5111eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size += R.size(); 5131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5145fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Insert at the end of this child. 515bf26856c2133238ce81d461127eb4d07815014fdChris Lattner if (RopePieceBTreeNode *RHS = getChild(i)->insert(Offset-ChildOffs, R)) 516bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return HandleChildPiece(i, RHS); 5171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5186bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 5195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 5205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 5215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// HandleChildPiece - A child propagated an insertion result up to us. 5225fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// Insert the new child, and/or propagate the result further up the tree. 523bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode * 524bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeInterior::HandleChildPiece(unsigned i, RopePieceBTreeNode *RHS) { 5255fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Otherwise the child propagated a subtree up to us as a new child. See if 5265fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // we have space for it here. 5275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (!isFull()) { 528bf26856c2133238ce81d461127eb4d07815014fdChris Lattner // Insert RHS after child 'i'. 5295fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (i + 1 != getNumChildren()) 5305fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner memmove(&Children[i+2], &Children[i+1], 5315fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner (getNumChildren()-i-1)*sizeof(Children[0])); 532bf26856c2133238ce81d461127eb4d07815014fdChris Lattner Children[i+1] = RHS; 5335fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ++NumChildren; 5346bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines return nullptr; 5355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 5361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5375fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Okay, this node is full. Split it in half, moving WidthFactor children to 5385fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // a newly allocated interior node. 5391eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5405fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Create the new node. 5415fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeInterior *NewNode = new RopePieceBTreeInterior(); 5421eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5435fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Move over the last 'WidthFactor' values from here to NewNode. 5445fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner memcpy(&NewNode->Children[0], &Children[WidthFactor], 5455fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner WidthFactor*sizeof(Children[0])); 5461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Decrease the number of values in the two nodes. 5485fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NewNode->NumChildren = NumChildren = WidthFactor; 5491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Finally, insert the two new children in the side the can (now) hold them. 551bf26856c2133238ce81d461127eb4d07815014fdChris Lattner // These insertions can't fail. 5525fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (i < WidthFactor) 553bf26856c2133238ce81d461127eb4d07815014fdChris Lattner this->HandleChildPiece(i, RHS); 5545fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else 555bf26856c2133238ce81d461127eb4d07815014fdChris Lattner NewNode->HandleChildPiece(i-WidthFactor, RHS); 5561eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5575fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Recompute the two nodes' size. 5585fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NewNode->FullRecomputeSizeLocally(); 5595fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner FullRecomputeSizeLocally(); 560bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return NewNode; 5615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 5625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 5635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// erase - Remove NumBytes from this node at the specified offset. We are 5645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a split at Offset. 5655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTreeInterior::erase(unsigned Offset, unsigned NumBytes) { 5665fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // This will shrink this node by NumBytes. 5675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Size -= NumBytes; 5681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5695fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the first child that overlaps with Offset. 5705fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned i = 0; 5715fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner for (; Offset >= getChild(i)->size(); ++i) 5725fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Offset -= getChild(i)->size(); 5731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5745fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Propagate the delete request into overlapping children, or completely 5755fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // delete the children as appropriate. 5765fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (NumBytes) { 5775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner RopePieceBTreeNode *CurChild = getChild(i); 5781eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5795fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If we are deleting something contained entirely in the child, pass on the 5805fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // request. 5815fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset+NumBytes < CurChild->size()) { 5825fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChild->erase(Offset, NumBytes); 5835fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return; 5845fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 5851eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5865fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If this deletion request starts somewhere in the middle of the child, it 5875fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // must be deleting to the end of the child. 5885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (Offset) { 5895fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner unsigned BytesFromChild = CurChild->size()-Offset; 5905fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChild->erase(Offset, BytesFromChild); 5915fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NumBytes -= BytesFromChild; 592b6403af3e697f90308fe8daf82f7b15252d198bcChris Lattner // Start at the beginning of the next child. 593b6403af3e697f90308fe8daf82f7b15252d198bcChris Lattner Offset = 0; 5945fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ++i; 5955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner continue; 5965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 597b6403af3e697f90308fe8daf82f7b15252d198bcChris Lattner 5985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If the deletion request completely covers the child, delete it and move 5995fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // the rest down. 6005fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner NumBytes -= CurChild->size(); 6015fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChild->Destroy(); 6025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner --NumChildren; 603514b24cb534d00fbfa431bdd6fc46def546fe228Chris Lattner if (i != getNumChildren()) 6045fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner memmove(&Children[i], &Children[i+1], 6055fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner (getNumChildren()-i)*sizeof(Children[0])); 6065fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 6075fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6085fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6095fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 6105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTreeNode Implementation 6115fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 6125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6135fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTreeNode::Destroy() { 6145fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 6155fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner delete Leaf; 6165fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else 6175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner delete cast<RopePieceBTreeInterior>(this); 6185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// split - Split the range containing the specified offset so that we are 6215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a place to do an insertion at the specified 622bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// offset. The offset is relative, so "0" is the start of the node. 623bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 624bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 625bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 626bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeNode::split(unsigned Offset) { 6275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(Offset <= size() && "Invalid offset to split!"); 6285fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 629bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return Leaf->split(Offset); 630bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return cast<RopePieceBTreeInterior>(this)->split(Offset); 6315fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6325fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6335fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// insert - Insert the specified ropepiece into this tree node at the 6345fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// specified offset. The offset is relative, so "0" is the start of the 6355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// node. 636bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// 637bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// If there is no space in this subtree for the extra piece, the extra tree 638bf26856c2133238ce81d461127eb4d07815014fdChris Lattner/// node is returned and must be inserted into a parent. 639bf26856c2133238ce81d461127eb4d07815014fdChris LattnerRopePieceBTreeNode *RopePieceBTreeNode::insert(unsigned Offset, 640bf26856c2133238ce81d461127eb4d07815014fdChris Lattner const RopePiece &R) { 6415fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(Offset <= size() && "Invalid offset to insert!"); 6425fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 643bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return Leaf->insert(Offset, R); 644bf26856c2133238ce81d461127eb4d07815014fdChris Lattner return cast<RopePieceBTreeInterior>(this)->insert(Offset, R); 6455fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6465fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// erase - Remove NumBytes from this node at the specified offset. We are 6485fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner/// guaranteed that there is a split at Offset. 6495fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTreeNode::erase(unsigned Offset, unsigned NumBytes) { 6505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(Offset+NumBytes <= size() && "Invalid offset to erase!"); 6515fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(this)) 6525fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return Leaf->erase(Offset, NumBytes); 6535fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return cast<RopePieceBTreeInterior>(this)->erase(Offset, NumBytes); 6545fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6555fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6575fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 6585fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTreeIterator Implementation 6595fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 6605fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6615fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnerstatic const RopePieceBTreeLeaf *getCN(const void *P) { 6625fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return static_cast<const RopePieceBTreeLeaf*>(P); 6635fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6645fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6655fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// begin iterator. 6665fd3e2673a1bd61d5f08f679555d15d23aba9314Chris LattnerRopePieceBTreeIterator::RopePieceBTreeIterator(const void *n) { 6675fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner const RopePieceBTreeNode *N = static_cast<const RopePieceBTreeNode*>(n); 6681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6695fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Walk down the left side of the tree until we get to a leaf. 6705fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (const RopePieceBTreeInterior *IN = dyn_cast<RopePieceBTreeInterior>(N)) 6715fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner N = IN->getChild(0); 6721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6735fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // We must have at least one leaf. 6745fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurNode = cast<RopePieceBTreeLeaf>(N); 6751eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6765fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // If we found a leaf that happens to be empty, skip over it until we get 6775fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // to something full. 6785fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (CurNode && getCN(CurNode)->getNumPieces() == 0) 6795fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurNode = getCN(CurNode)->getNextLeafInOrder(); 6801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6816bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (CurNode) 6825fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurPiece = &getCN(CurNode)->getPiece(0); 6835fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else // Empty tree, this is an end() iterator. 6846bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CurPiece = nullptr; 6855fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChar = 0; 6865fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 6875fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 6885fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTreeIterator::MoveToNextPiece() { 6895fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (CurPiece != &getCN(CurNode)->getPiece(getCN(CurNode)->getNumPieces()-1)) { 6905fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChar = 0; 6915fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner ++CurPiece; 6925fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return; 6935fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 6941eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6955fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // Find the next non-empty leaf node. 6965fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner do 6975fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurNode = getCN(CurNode)->getNextLeafInOrder(); 6985fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner while (CurNode && getCN(CurNode)->getNumPieces() == 0); 6991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7006bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (CurNode) 7015fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurPiece = &getCN(CurNode)->getPiece(0); 7025fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else // Hit end(). 7036bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines CurPiece = nullptr; 7045fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner CurChar = 0; 7055fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7065fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7075fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 7085fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner// RopePieceBTree Implementation 7095fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner//===----------------------------------------------------------------------===// 7105fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7115fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnerstatic RopePieceBTreeNode *getRoot(void *P) { 7125fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return static_cast<RopePieceBTreeNode*>(P); 7135fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7145fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7155fd3e2673a1bd61d5f08f679555d15d23aba9314Chris LattnerRopePieceBTree::RopePieceBTree() { 7165fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Root = new RopePieceBTreeLeaf(); 7175fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7185fd3e2673a1bd61d5f08f679555d15d23aba9314Chris LattnerRopePieceBTree::RopePieceBTree(const RopePieceBTree &RHS) { 7195fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner assert(RHS.empty() && "Can't copy non-empty tree yet"); 7205fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Root = new RopePieceBTreeLeaf(); 7215fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7225fd3e2673a1bd61d5f08f679555d15d23aba9314Chris LattnerRopePieceBTree::~RopePieceBTree() { 7235fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner getRoot(Root)->Destroy(); 7245fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7255fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7265fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnerunsigned RopePieceBTree::size() const { 7275fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner return getRoot(Root)->size(); 7285fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7295fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7305fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTree::clear() { 7315fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner if (RopePieceBTreeLeaf *Leaf = dyn_cast<RopePieceBTreeLeaf>(getRoot(Root))) 7325fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Leaf->clear(); 7335fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner else { 7345fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner getRoot(Root)->Destroy(); 7355fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner Root = new RopePieceBTreeLeaf(); 7365fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner } 7375fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7385fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7395fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTree::insert(unsigned Offset, const RopePiece &R) { 7405fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // #1. Split at Offset. 741bf26856c2133238ce81d461127eb4d07815014fdChris Lattner if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) 742bf26856c2133238ce81d461127eb4d07815014fdChris Lattner Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 7431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7445fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // #2. Do the insertion. 745bf26856c2133238ce81d461127eb4d07815014fdChris Lattner if (RopePieceBTreeNode *RHS = getRoot(Root)->insert(Offset, R)) 746bf26856c2133238ce81d461127eb4d07815014fdChris Lattner Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 7475fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7485fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner 7495fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattnervoid RopePieceBTree::erase(unsigned Offset, unsigned NumBytes) { 7505fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // #1. Split at Offset. 751bf26856c2133238ce81d461127eb4d07815014fdChris Lattner if (RopePieceBTreeNode *RHS = getRoot(Root)->split(Offset)) 752bf26856c2133238ce81d461127eb4d07815014fdChris Lattner Root = new RopePieceBTreeInterior(getRoot(Root), RHS); 7531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7545fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner // #2. Do the erasing. 7555fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner getRoot(Root)->erase(Offset, NumBytes); 7565fd3e2673a1bd61d5f08f679555d15d23aba9314Chris Lattner} 7575618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner 7585618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner//===----------------------------------------------------------------------===// 7595618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner// RewriteRope Implementation 7605618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner//===----------------------------------------------------------------------===// 7615618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner 762b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// MakeRopeString - This copies the specified byte range into some instance of 763b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// RopeRefCountString, and return a RopePiece that represents it. This uses 764b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// the AllocBuffer object to aggregate requests for small strings into one 765b9b309481369196b64bbf73e540d0c9b487e56a5Chris Lattner/// allocation instead of doing tons of tiny allocations. 7665618d88b93056bae76845b1503cce6ba0a6080f1Chris LattnerRopePiece RewriteRope::MakeRopeString(const char *Start, const char *End) { 7675618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner unsigned Len = End-Start; 768c66d0aa934f2afd412f50881a5e959bb8582cf14Chris Lattner assert(Len && "Zero length RopePiece is invalid!"); 7691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7705618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner // If we have space for this string in the current alloc buffer, use it. 7715618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner if (AllocOffs+Len <= AllocChunkSize) { 7725618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner memcpy(AllocBuffer->Data+AllocOffs, Start, Len); 7735618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner AllocOffs += Len; 7745618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner return RopePiece(AllocBuffer, AllocOffs-Len, AllocOffs); 7755618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner } 7761eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7775618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner // If we don't have enough room because this specific allocation is huge, 7785618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner // just allocate a new rope piece for it alone. 7795618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner if (Len > AllocChunkSize) { 7805618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner unsigned Size = End-Start+sizeof(RopeRefCountString)-1; 7811eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump RopeRefCountString *Res = 782bf26856c2133238ce81d461127eb4d07815014fdChris Lattner reinterpret_cast<RopeRefCountString *>(new char[Size]); 7835618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner Res->RefCount = 0; 7845618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner memcpy(Res->Data, Start, End-Start); 7855618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner return RopePiece(Res, 0, End-Start); 7865618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner } 7871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7885618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner // Otherwise, this was a small request but we just don't have space for it 7895618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner // Make a new chunk and share it with later allocations. 7901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7916bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines if (AllocBuffer) 7926bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines AllocBuffer->dropRef(); 7931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7943f61c18dd765c27bf900b22dc3a5f2a68e2364a1Zhongxing Xu unsigned AllocSize = offsetof(RopeRefCountString, Data) + AllocChunkSize; 7955618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner AllocBuffer = reinterpret_cast<RopeRefCountString *>(new char[AllocSize]); 7965618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner AllocBuffer->RefCount = 0; 7975618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner memcpy(AllocBuffer->Data, Start, Len); 7985618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner AllocOffs = Len; 7991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 8008f99993856b4647a094bf1c2b703c4acc003f577Ted Kremenek // Start out the new allocation with a refcount of 1, since we have an 8018f99993856b4647a094bf1c2b703c4acc003f577Ted Kremenek // internal reference to it. 8028f99993856b4647a094bf1c2b703c4acc003f577Ted Kremenek AllocBuffer->addRef(); 8035618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner return RopePiece(AllocBuffer, 0, Len); 8045618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner} 8055618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner 8065618d88b93056bae76845b1503cce6ba0a6080f1Chris Lattner 807