contrib/llvm/tools/clang/include/clang/Rewrite/RewriteRope.h

   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