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