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