contrib/llvm/tools/clang/include/clang/Rewrite/Core/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 "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