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 22namespace 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 ++RefCount; 37 } 38 39 void dropRef() { 40 if (--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 if (StrData) 67 StrData->addRef(); 68 } 69 RopePiece(const RopePiece &RP) 70 : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) { 71 if (StrData) 72 StrData->addRef(); 73 } 74 75 ~RopePiece() { 76 if (StrData) 77 StrData->dropRef(); 78 } 79 80 void operator=(const RopePiece &RHS) { 81 if (StrData != RHS.StrData) { 82 if (StrData) 83 StrData->dropRef(); 84 StrData = RHS.StrData; 85 if (StrData) 86 StrData->addRef(); 87 } 88 StartOffs = RHS.StartOffs; 89 EndOffs = RHS.EndOffs; 90 } 91 92 const char &operator[](unsigned Offset) const { 93 return StrData->Data[Offset+StartOffs]; 94 } 95 char &operator[](unsigned Offset) { 96 return StrData->Data[Offset+StartOffs]; 97 } 98 99 unsigned size() const { return EndOffs-StartOffs; } 100 }; 101 102 //===--------------------------------------------------------------------===// 103 // RopePieceBTreeIterator Class 104 //===--------------------------------------------------------------------===// 105 106 /// RopePieceBTreeIterator - This class provides read-only forward iteration 107 /// over bytes that are in a RopePieceBTree. This first iterates over bytes 108 /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf, 109 /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree. 110 class RopePieceBTreeIterator : 111 public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> { 112 /// CurNode - The current B+Tree node that we are inspecting. 113 const void /*RopePieceBTreeLeaf*/ *CurNode; 114 /// CurPiece - The current RopePiece in the B+Tree node that we're 115 /// inspecting. 116 const RopePiece *CurPiece; 117 /// CurChar - The current byte in the RopePiece we are pointing to. 118 unsigned CurChar; 119 public: 120 // begin iterator. 121 RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N); 122 // end iterator 123 RopePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {} 124 125 char operator*() const { 126 return (*CurPiece)[CurChar]; 127 } 128 129 bool operator==(const RopePieceBTreeIterator &RHS) const { 130 return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar; 131 } 132 bool operator!=(const RopePieceBTreeIterator &RHS) const { 133 return !operator==(RHS); 134 } 135 136 RopePieceBTreeIterator& operator++() { // Preincrement 137 if (CurChar+1 < CurPiece->size()) 138 ++CurChar; 139 else 140 MoveToNextPiece(); 141 return *this; 142 } 143 inline RopePieceBTreeIterator operator++(int) { // Postincrement 144 RopePieceBTreeIterator tmp = *this; ++*this; return tmp; 145 } 146 private: 147 void MoveToNextPiece(); 148 }; 149 150 //===--------------------------------------------------------------------===// 151 // RopePieceBTree Class 152 //===--------------------------------------------------------------------===// 153 154 class RopePieceBTree { 155 void /*RopePieceBTreeNode*/ *Root; 156 void operator=(const RopePieceBTree &); // DO NOT IMPLEMENT 157 public: 158 RopePieceBTree(); 159 RopePieceBTree(const RopePieceBTree &RHS); 160 ~RopePieceBTree(); 161 162 typedef RopePieceBTreeIterator iterator; 163 iterator begin() const { return iterator(Root); } 164 iterator end() const { return iterator(); } 165 unsigned size() const; 166 unsigned empty() const { return size() == 0; } 167 168 void clear(); 169 170 void insert(unsigned Offset, const RopePiece &R); 171 172 void erase(unsigned Offset, unsigned NumBytes); 173 }; 174 175 //===--------------------------------------------------------------------===// 176 // RewriteRope Class 177 //===--------------------------------------------------------------------===// 178 179/// RewriteRope - A powerful string class. This class supports extremely 180/// efficient insertions and deletions into the middle of it, even for 181/// ridiculously long strings. 182class RewriteRope { 183 RopePieceBTree Chunks; 184 185 /// We allocate space for string data out of a buffer of size AllocChunkSize. 186 /// This keeps track of how much space is left. 187 RopeRefCountString *AllocBuffer; 188 unsigned AllocOffs; 189 enum { AllocChunkSize = 4080 }; 190 191public: 192 RewriteRope() : AllocBuffer(0), AllocOffs(AllocChunkSize) {} 193 RewriteRope(const RewriteRope &RHS) 194 : Chunks(RHS.Chunks), AllocBuffer(0), AllocOffs(AllocChunkSize) { 195 } 196 197 ~RewriteRope() { 198 // If we had an allocation buffer, drop our reference to it. 199 if (AllocBuffer) 200 AllocBuffer->dropRef(); 201 } 202 203 typedef RopePieceBTree::iterator iterator; 204 typedef RopePieceBTree::iterator const_iterator; 205 iterator begin() const { return Chunks.begin(); } 206 iterator end() const { return Chunks.end(); } 207 unsigned size() const { return Chunks.size(); } 208 209 void clear() { 210 Chunks.clear(); 211 } 212 213 void assign(const char *Start, const char *End) { 214 clear(); 215 if (Start != End) 216 Chunks.insert(0, MakeRopeString(Start, End)); 217 } 218 219 void insert(unsigned Offset, const char *Start, const char *End) { 220 assert(Offset <= size() && "Invalid position to insert!"); 221 if (Start == End) return; 222 Chunks.insert(Offset, MakeRopeString(Start, End)); 223 } 224 225 void erase(unsigned Offset, unsigned NumBytes) { 226 assert(Offset+NumBytes <= size() && "Invalid region to erase!"); 227 if (NumBytes == 0) return; 228 Chunks.erase(Offset, NumBytes); 229 } 230 231private: 232 RopePiece MakeRopeString(const char *Start, const char *End); 233}; 234 235} // end namespace clang 236 237#endif 238