1243791Sdim//===--- RewriteRope.h - Rope specialized for rewriter ----------*- C++ -*-===// 2243791Sdim// 3243791Sdim// The LLVM Compiler Infrastructure 4243791Sdim// 5243791Sdim// This file is distributed under the University of Illinois Open Source 6243791Sdim// License. See LICENSE.TXT for details. 7243791Sdim// 8243791Sdim//===----------------------------------------------------------------------===// 9243791Sdim// 10243791Sdim// This file defines the RewriteRope class, which is a powerful string class. 11243791Sdim// 12243791Sdim//===----------------------------------------------------------------------===// 13243791Sdim 14243791Sdim#ifndef LLVM_CLANG_REWRITEROPE_H 15243791Sdim#define LLVM_CLANG_REWRITEROPE_H 16243791Sdim 17243791Sdim#include "llvm/Support/Compiler.h" 18243791Sdim#include <cassert> 19243791Sdim#include <cstddef> 20252723Sdim#include <cstring> 21243791Sdim#include <iterator> 22243791Sdim 23243791Sdimnamespace clang { 24243791Sdim //===--------------------------------------------------------------------===// 25243791Sdim // RopeRefCountString Class 26243791Sdim //===--------------------------------------------------------------------===// 27243791Sdim 28243791Sdim /// RopeRefCountString - This struct is allocated with 'new char[]' from the 29243791Sdim /// heap, and represents a reference counted chunk of string data. When its 30243791Sdim /// ref count drops to zero, it is delete[]'d. This is primarily managed 31243791Sdim /// through the RopePiece class below. 32243791Sdim struct RopeRefCountString { 33243791Sdim unsigned RefCount; 34243791Sdim char Data[1]; // Variable sized. 35243791Sdim 36243791Sdim void addRef() { 37243791Sdim ++RefCount; 38243791Sdim } 39243791Sdim 40243791Sdim void dropRef() { 41243791Sdim if (--RefCount == 0) 42243791Sdim delete [] (char*)this; 43243791Sdim } 44243791Sdim }; 45243791Sdim 46243791Sdim //===--------------------------------------------------------------------===// 47243791Sdim // RopePiece Class 48243791Sdim //===--------------------------------------------------------------------===// 49243791Sdim 50243791Sdim /// RopePiece - This class represents a view into a RopeRefCountString object. 51243791Sdim /// This allows references to string data to be efficiently chopped up and 52243791Sdim /// moved around without having to push around the string data itself. 53243791Sdim /// 54243791Sdim /// For example, we could have a 1M RopePiece and want to insert something 55243791Sdim /// into the middle of it. To do this, we split it into two RopePiece objects 56243791Sdim /// that both refer to the same underlying RopeRefCountString (just with 57243791Sdim /// different offsets) which is a nice constant time operation. 58243791Sdim struct RopePiece { 59243791Sdim RopeRefCountString *StrData; 60243791Sdim unsigned StartOffs; 61243791Sdim unsigned EndOffs; 62243791Sdim 63243791Sdim RopePiece() : StrData(0), StartOffs(0), EndOffs(0) {} 64243791Sdim 65243791Sdim RopePiece(RopeRefCountString *Str, unsigned Start, unsigned End) 66243791Sdim : StrData(Str), StartOffs(Start), EndOffs(End) { 67243791Sdim if (StrData) 68243791Sdim StrData->addRef(); 69243791Sdim } 70243791Sdim RopePiece(const RopePiece &RP) 71243791Sdim : StrData(RP.StrData), StartOffs(RP.StartOffs), EndOffs(RP.EndOffs) { 72243791Sdim if (StrData) 73243791Sdim StrData->addRef(); 74243791Sdim } 75243791Sdim 76243791Sdim ~RopePiece() { 77243791Sdim if (StrData) 78243791Sdim StrData->dropRef(); 79243791Sdim } 80243791Sdim 81243791Sdim void operator=(const RopePiece &RHS) { 82243791Sdim if (StrData != RHS.StrData) { 83243791Sdim if (StrData) 84243791Sdim StrData->dropRef(); 85243791Sdim StrData = RHS.StrData; 86243791Sdim if (StrData) 87243791Sdim StrData->addRef(); 88243791Sdim } 89243791Sdim StartOffs = RHS.StartOffs; 90243791Sdim EndOffs = RHS.EndOffs; 91243791Sdim } 92243791Sdim 93243791Sdim const char &operator[](unsigned Offset) const { 94243791Sdim return StrData->Data[Offset+StartOffs]; 95243791Sdim } 96243791Sdim char &operator[](unsigned Offset) { 97243791Sdim return StrData->Data[Offset+StartOffs]; 98243791Sdim } 99243791Sdim 100243791Sdim unsigned size() const { return EndOffs-StartOffs; } 101243791Sdim }; 102243791Sdim 103243791Sdim //===--------------------------------------------------------------------===// 104243791Sdim // RopePieceBTreeIterator Class 105243791Sdim //===--------------------------------------------------------------------===// 106243791Sdim 107243791Sdim /// RopePieceBTreeIterator - This class provides read-only forward iteration 108243791Sdim /// over bytes that are in a RopePieceBTree. This first iterates over bytes 109243791Sdim /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf, 110243791Sdim /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree. 111243791Sdim class RopePieceBTreeIterator : 112243791Sdim public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> { 113243791Sdim /// CurNode - The current B+Tree node that we are inspecting. 114243791Sdim const void /*RopePieceBTreeLeaf*/ *CurNode; 115243791Sdim /// CurPiece - The current RopePiece in the B+Tree node that we're 116243791Sdim /// inspecting. 117243791Sdim const RopePiece *CurPiece; 118243791Sdim /// CurChar - The current byte in the RopePiece we are pointing to. 119243791Sdim unsigned CurChar; 120243791Sdim public: 121243791Sdim // begin iterator. 122243791Sdim RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N); 123243791Sdim // end iterator 124243791Sdim RopePieceBTreeIterator() : CurNode(0), CurPiece(0), CurChar(0) {} 125243791Sdim 126243791Sdim char operator*() const { 127243791Sdim return (*CurPiece)[CurChar]; 128243791Sdim } 129243791Sdim 130243791Sdim bool operator==(const RopePieceBTreeIterator &RHS) const { 131243791Sdim return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar; 132243791Sdim } 133243791Sdim bool operator!=(const RopePieceBTreeIterator &RHS) const { 134243791Sdim return !operator==(RHS); 135243791Sdim } 136243791Sdim 137243791Sdim RopePieceBTreeIterator& operator++() { // Preincrement 138243791Sdim if (CurChar+1 < CurPiece->size()) 139243791Sdim ++CurChar; 140243791Sdim else 141243791Sdim MoveToNextPiece(); 142243791Sdim return *this; 143243791Sdim } 144243791Sdim inline RopePieceBTreeIterator operator++(int) { // Postincrement 145243791Sdim RopePieceBTreeIterator tmp = *this; ++*this; return tmp; 146243791Sdim } 147243791Sdim private: 148243791Sdim void MoveToNextPiece(); 149243791Sdim }; 150243791Sdim 151243791Sdim //===--------------------------------------------------------------------===// 152243791Sdim // RopePieceBTree Class 153243791Sdim //===--------------------------------------------------------------------===// 154243791Sdim 155243791Sdim class RopePieceBTree { 156243791Sdim void /*RopePieceBTreeNode*/ *Root; 157243791Sdim void operator=(const RopePieceBTree &) LLVM_DELETED_FUNCTION; 158243791Sdim public: 159243791Sdim RopePieceBTree(); 160243791Sdim RopePieceBTree(const RopePieceBTree &RHS); 161243791Sdim ~RopePieceBTree(); 162243791Sdim 163243791Sdim typedef RopePieceBTreeIterator iterator; 164243791Sdim iterator begin() const { return iterator(Root); } 165243791Sdim iterator end() const { return iterator(); } 166243791Sdim unsigned size() const; 167243791Sdim unsigned empty() const { return size() == 0; } 168243791Sdim 169243791Sdim void clear(); 170243791Sdim 171243791Sdim void insert(unsigned Offset, const RopePiece &R); 172243791Sdim 173243791Sdim void erase(unsigned Offset, unsigned NumBytes); 174243791Sdim }; 175243791Sdim 176243791Sdim //===--------------------------------------------------------------------===// 177243791Sdim // RewriteRope Class 178243791Sdim //===--------------------------------------------------------------------===// 179243791Sdim 180243791Sdim/// RewriteRope - A powerful string class. This class supports extremely 181243791Sdim/// efficient insertions and deletions into the middle of it, even for 182243791Sdim/// ridiculously long strings. 183243791Sdimclass RewriteRope { 184243791Sdim RopePieceBTree Chunks; 185243791Sdim 186243791Sdim /// We allocate space for string data out of a buffer of size AllocChunkSize. 187243791Sdim /// This keeps track of how much space is left. 188243791Sdim RopeRefCountString *AllocBuffer; 189243791Sdim unsigned AllocOffs; 190243791Sdim enum { AllocChunkSize = 4080 }; 191243791Sdim 192243791Sdimpublic: 193243791Sdim RewriteRope() : AllocBuffer(0), AllocOffs(AllocChunkSize) {} 194243791Sdim RewriteRope(const RewriteRope &RHS) 195243791Sdim : Chunks(RHS.Chunks), AllocBuffer(0), AllocOffs(AllocChunkSize) { 196243791Sdim } 197243791Sdim 198243791Sdim ~RewriteRope() { 199243791Sdim // If we had an allocation buffer, drop our reference to it. 200243791Sdim if (AllocBuffer) 201243791Sdim AllocBuffer->dropRef(); 202243791Sdim } 203243791Sdim 204243791Sdim typedef RopePieceBTree::iterator iterator; 205243791Sdim typedef RopePieceBTree::iterator const_iterator; 206243791Sdim iterator begin() const { return Chunks.begin(); } 207243791Sdim iterator end() const { return Chunks.end(); } 208243791Sdim unsigned size() const { return Chunks.size(); } 209243791Sdim 210243791Sdim void clear() { 211243791Sdim Chunks.clear(); 212243791Sdim } 213243791Sdim 214243791Sdim void assign(const char *Start, const char *End) { 215243791Sdim clear(); 216243791Sdim if (Start != End) 217243791Sdim Chunks.insert(0, MakeRopeString(Start, End)); 218243791Sdim } 219243791Sdim 220243791Sdim void insert(unsigned Offset, const char *Start, const char *End) { 221243791Sdim assert(Offset <= size() && "Invalid position to insert!"); 222243791Sdim if (Start == End) return; 223243791Sdim Chunks.insert(Offset, MakeRopeString(Start, End)); 224243791Sdim } 225243791Sdim 226243791Sdim void erase(unsigned Offset, unsigned NumBytes) { 227243791Sdim assert(Offset+NumBytes <= size() && "Invalid region to erase!"); 228243791Sdim if (NumBytes == 0) return; 229243791Sdim Chunks.erase(Offset, NumBytes); 230243791Sdim } 231243791Sdim 232243791Sdimprivate: 233243791Sdim RopePiece MakeRopeString(const char *Start, const char *End); 234243791Sdim}; 235243791Sdim 236243791Sdim} // end namespace clang 237243791Sdim 238243791Sdim#endif 239