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_REWRITE_CORE_REWRITEROPE_H
  15 #define LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H
  16
  17 #include "llvm/ADT/IntrusiveRefCntPtr.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include <cassert>
  20 #include <cstddef>
  21 #include <iterator>
  22 #include <utility>
  23
  24 namespace clang {
  25
  26   //===--------------------------------------------------------------------===//
  27   // RopeRefCountString Class
  28   //===--------------------------------------------------------------------===//
  29
  30   /// RopeRefCountString - This struct is allocated with 'new char[]' from the
  31   /// heap, and represents a reference counted chunk of string data.  When its
  32   /// ref count drops to zero, it is delete[]'d.  This is primarily managed
  33   /// through the RopePiece class below.
  34   struct RopeRefCountString {
  35     unsigned RefCount;
  36     char Data[1];  //  Variable sized.
  37
  38     void Retain() { ++RefCount; }
  39
  40     void Release() {
  41       assert(RefCount > 0 && "Reference count is already zero.");
  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     llvm::IntrusiveRefCntPtr<RopeRefCountString> StrData;
  61     unsigned StartOffs = 0;
  62     unsigned EndOffs = 0;
  63
  64     RopePiece() = default;
  65     RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
  66               unsigned End)
  67         : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
  68
  69     const char &operator[](unsigned Offset) const {
  70       return StrData->Data[Offset+StartOffs];
  71     }
  72     char &operator[](unsigned Offset) {
  73       return StrData->Data[Offset+StartOffs];
  74     }
  75
  76     unsigned size() const { return EndOffs-StartOffs; }
  77   };
  78
  79   //===--------------------------------------------------------------------===//
  80   // RopePieceBTreeIterator Class
  81   //===--------------------------------------------------------------------===//
  82
  83   /// RopePieceBTreeIterator - This class provides read-only forward iteration
  84   /// over bytes that are in a RopePieceBTree.  This first iterates over bytes
  85   /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
  86   /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
  87   class RopePieceBTreeIterator :
  88       public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> {
  89     /// CurNode - The current B+Tree node that we are inspecting.
  90     const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;
  91
  92     /// CurPiece - The current RopePiece in the B+Tree node that we're
  93     /// inspecting.
  94     const RopePiece *CurPiece = nullptr;
  95
  96     /// CurChar - The current byte in the RopePiece we are pointing to.
  97     unsigned CurChar = 0;
  98
  99   public:
 100     RopePieceBTreeIterator() = default;
 101     RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
 102
 103     char operator*() const {
 104       return (*CurPiece)[CurChar];
 105     }
 106
 107     bool operator==(const RopePieceBTreeIterator &RHS) const {
 108       return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
 109     }
 110     bool operator!=(const RopePieceBTreeIterator &RHS) const {
 111       return !operator==(RHS);
 112     }
 113
 114     RopePieceBTreeIterator& operator++() {   // Preincrement
 115       if (CurChar+1 < CurPiece->size())
 116         ++CurChar;
 117       else
 118         MoveToNextPiece();
 119       return *this;
 120     }
 121
 122     RopePieceBTreeIterator operator++(int) { // Postincrement
 123       RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
 124     }
 125
 126     llvm::StringRef piece() const {
 127       return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
 128     }
 129
 130     void MoveToNextPiece();
 131   };
 132
 133   //===--------------------------------------------------------------------===//
 134   // RopePieceBTree Class
 135   //===--------------------------------------------------------------------===//
 136
 137   class RopePieceBTree {
 138     void /*RopePieceBTreeNode*/ *Root;
 139
 140   public:
 141     RopePieceBTree();
 142     RopePieceBTree(const RopePieceBTree &RHS);
 143     RopePieceBTree &operator=(const RopePieceBTree &) = delete;
 144     ~RopePieceBTree();
 145
 146     using iterator = RopePieceBTreeIterator;
 147
 148     iterator begin() const { return iterator(Root); }
 149     iterator end() const { return iterator(); }
 150     unsigned size() const;
 151     unsigned empty() const { return size() == 0; }
 152
 153     void clear();
 154
 155     void insert(unsigned Offset, const RopePiece &R);
 156
 157     void erase(unsigned Offset, unsigned NumBytes);
 158   };
 159
 160   //===--------------------------------------------------------------------===//
 161   // RewriteRope Class
 162   //===--------------------------------------------------------------------===//
 163
 164 /// RewriteRope - A powerful string class.  This class supports extremely
 165 /// efficient insertions and deletions into the middle of it, even for
 166 /// ridiculously long strings.
 167 class RewriteRope {
 168   RopePieceBTree Chunks;
 169
 170   /// We allocate space for string data out of a buffer of size AllocChunkSize.
 171   /// This keeps track of how much space is left.
 172   llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;
 173   enum { AllocChunkSize = 4080 };
 174   unsigned AllocOffs = AllocChunkSize;
 175
 176 public:
 177   RewriteRope() = default;
 178   RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
 179
 180   using iterator = RopePieceBTree::iterator;
 181   using const_iterator = RopePieceBTree::iterator;
 182
 183   iterator begin() const { return Chunks.begin(); }
 184   iterator end() const { return Chunks.end(); }
 185   unsigned size() const { return Chunks.size(); }
 186
 187   void clear() {
 188     Chunks.clear();
 189   }
 190
 191   void assign(const char *Start, const char *End) {
 192     clear();
 193     if (Start != End)
 194       Chunks.insert(0, MakeRopeString(Start, End));
 195   }
 196
 197   void insert(unsigned Offset, const char *Start, const char *End) {
 198     assert(Offset <= size() && "Invalid position to insert!");
 199     if (Start == End) return;
 200     Chunks.insert(Offset, MakeRopeString(Start, End));
 201   }
 202
 203   void erase(unsigned Offset, unsigned NumBytes) {
 204     assert(Offset+NumBytes <= size() && "Invalid region to erase!");
 205     if (NumBytes == 0) return;
 206     Chunks.erase(Offset, NumBytes);
 207   }
 208
 209 private:
 210   RopePiece MakeRopeString(const char *Start, const char *End);
 211 };
 212
 213 } // namespace clang
 214
 215 #endif // LLVM_CLANG_REWRITE_CORE_REWRITEROPE_H