1 //===--- RewriteRope.h - Rope specialized for rewriter ----------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the RewriteRope class, which is a powerful string class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CLANG_REWRITEROPE_H 15 #define LLVM_CLANG_REWRITEROPE_H 16 17 #include <cstring> 18 #include <cassert> 19 #include <cstddef> 20 #include <iterator> 21 22 namespace clang { 23 //===--------------------------------------------------------------------===// 24 // RopeRefCountString Class 25 //===--------------------------------------------------------------------===// 26 27 /// RopeRefCountString - This struct is allocated with 'new char[]' from the 28 /// heap, and represents a reference counted chunk of string data. When its 29 /// ref count drops to zero, it is delete[]'d. This is primarily managed 30 /// through the RopePiece class below. 31 struct RopeRefCountString { 32 unsigned RefCount; 33 char Data[1]; // Variable sized. 34 35 void addRef() { 36 if (this) ++RefCount; 37 } 38 39 void dropRef() { 40 if (this && --RefCount == 0) 41 delete [] (char*)this; 42 } 43 }; 44 45 //===--------------------------------------------------------------------===// 46 // RopePiece Class 47 //===--------------------------------------------------------------------===// 48 49 /// RopePiece - This class represents a view into a RopeRefCountString object. 50 /// This allows references to string data to be efficiently chopped up and 51 /// moved around without having to push around the string data itself. 52 /// 53 /// For example, we could have a 1M RopePiece and want to insert something 54 /// into the middle of it. To do this, we split it into two RopePiece objects 55 /// that both refer to the same underlying RopeRefCountString (just with 56 /// different offsets) which is a nice constant time operation. 57 struct RopePiece { 58 RopeRefCountString *StrData; 59 unsigned StartOffs; 60 unsigned EndOffs; 61 62 RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {} 63 64 RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End) 65 : StrData(Str), StartOffs(Start), EndOffs(End) { 66 StrData->addRef(); 67 } 68 RopePiece(const RopePiece &RP) 69 : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) { 70 StrData->addRef(); 71 } 72 73 ~RopePiece() { 74 StrData->dropRef(); 75 } 76 77 void operator=(const RopePiece &RHS) { 78 if (StrData != RHS.StrData) { 79 StrData->dropRef(); 80 StrData = RHS.StrData; 81 StrData->addRef(); 82 } 83 StartOffs = RHS.StartOffs; 84 EndOffs = RHS.EndOffs; 85 } 86 87 const char &operator[](unsigned Offset) const { 88 return StrData->Data[Offset+StartOffs]; 89 } 90 char &operator[](unsigned Offset) { 91 return StrData->Data[Offset+StartOffs]; 92 } 93 94 unsigned size() const { return EndOffs-StartOffs; } 95 }; 96 97 //===--------------------------------------------------------------------===// 98 // RopePieceBTreeIterator Class 99 //===--------------------------------------------------------------------===// 100 101 /// RopePieceBTreeIterator - This class provides read-only forward iteration 102 /// over bytes that are in a RopePieceBTree. This first iterates over bytes 103 /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf, 104 /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree. 105 class RopePieceBTreeIterator : 106 public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> { 107 /// CurNode - The current B+Tree node that we are inspecting. 108 const void /*RopePieceBTreeLeaf*/ *CurNode; 109 /// CurPiece - The current RopePiece in the B+Tree node that we're 110 /// inspecting. 111 const RopePiece *CurPiece; 112 /// CurChar - The current byte in the RopePiece we are pointing to. 113 unsigned CurChar; 114 public: 115 // begin iterator. 116 RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N); 117 // end iterator 118 RopePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {} 119 120 char operator*() const { 121 return (*CurPiece)[CurChar]; 122 } 123 124 bool operator==(const RopePieceBTreeIterator &RHS) const { 125 return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar; 126 } 127 bool operator!=(const RopePieceBTreeIterator &RHS) const { 128 return !operator==(RHS); 129 } 130 131 RopePieceBTreeIterator& operator++() { // Preincrement 132 if (CurChar+1 < CurPiece->size()) 133 ++CurChar; 134 else 135 MoveToNextPiece(); 136 return *this; 137 } 138 inline RopePieceBTreeIterator operator++(int) { // Postincrement 139 RopePieceBTreeIterator tmp = *this; ++*this; return tmp; 140 } 141 private: 142 void MoveToNextPiece(); 143 }; 144 145 //===--------------------------------------------------------------------===// 146 // RopePieceBTree Class 147 //===--------------------------------------------------------------------===// 148 149 class RopePieceBTree { 150 void /*RopePieceBTreeNode*/ *Root; 151 void operator=(const RopePieceBTree &); // DO NOT IMPLEMENT 152 public: 153 RopePieceBTree(); 154 RopePieceBTree(const RopePieceBTree &RHS); 155 ~RopePieceBTree(); 156 157 typedef RopePieceBTreeIterator iterator; 158 iterator begin() const { return iterator(Root); } 159 iterator end() const { return iterator(); } 160 unsigned size() const; 161 unsigned empty() const { return size() == 0; } 162 163 void clear(); 164 165 void insert(unsigned Offset, const RopePiece &R); 166 167 void erase(unsigned Offset, unsigned NumBytes); 168 }; 169 170 //===--------------------------------------------------------------------===// 171 // RewriteRope Class 172 //===--------------------------------------------------------------------===// 173 174 /// RewriteRope - A powerful string class. This class supports extremely 175 /// efficient insertions and deletions into the middle of it, even for 176 /// ridiculously long strings. 177 class RewriteRope { 178 RopePieceBTree Chunks; 179 180 /// We allocate space for string data out of a buffer of size AllocChunkSize. 181 /// This keeps track of how much space is left. 182 RopeRefCountString *AllocBuffer; 183 unsigned AllocOffs; 184 enum { AllocChunkSize = 4080 }; 185 186 public: 187 RewriteRope() : AllocBuffer(0), AllocOffs(AllocChunkSize) {} 188 RewriteRope(const RewriteRope &RHS) 189 : Chunks(RHS.Chunks), AllocBuffer(0), AllocOffs(AllocChunkSize) { 190 } 191 192 ~RewriteRope() { 193 // If we had an allocation buffer, drop our reference to it. 194 AllocBuffer->dropRef(); 195 } 196 197 typedef RopePieceBTree::iterator iterator; 198 typedef RopePieceBTree::iterator const_iterator; 199 iterator begin() const { return Chunks.begin(); } 200 iterator end() const { return Chunks.end(); } 201 unsigned size() const { return Chunks.size(); } 202 203 void clear() { 204 Chunks.clear(); 205 } 206 207 void assign(const char *Start, const char *End) { 208 clear(); 209 if (Start != End) 210 Chunks.insert(0, MakeRopeString(Start, End)); 211 } 212 213 void insert(unsigned Offset, const char *Start, const char *End) { 214 assert(Offset <= size() && "Invalid position to insert!"); 215 if (Start == End) return; 216 Chunks.insert(Offset, MakeRopeString(Start, End)); 217 } 218 219 void erase(unsigned Offset, unsigned NumBytes) { 220 assert(Offset+NumBytes <= size() && "Invalid region to erase!"); 221 if (NumBytes == 0) return; 222 Chunks.erase(Offset, NumBytes); 223 } 224 225 private: 226 RopePiece MakeRopeString(const char *Start, const char *End); 227 }; 228 229 } // end namespace clang 230 231 #endif 232
