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 "llvm/Support/Compiler.h"
20#include <cassert>
21#include <cstddef>
22#include <cstring>
23#include <iterator>
24
25namespace clang {
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;
62    unsigned EndOffs;
63
64    RopePiece() : StrData(nullptr), StartOffs(0), EndOffs(0) {}
65
66    RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
67              unsigned End)
68        : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
69
70    const char &operator[](unsigned Offset) const {
71      return StrData->Data[Offset+StartOffs];
72    }
73    char &operator[](unsigned Offset) {
74      return StrData->Data[Offset+StartOffs];
75    }
76
77    unsigned size() const { return EndOffs-StartOffs; }
78  };
79
80  //===--------------------------------------------------------------------===//
81  // RopePieceBTreeIterator Class
82  //===--------------------------------------------------------------------===//
83
84  /// RopePieceBTreeIterator - This class provides read-only forward iteration
85  /// over bytes that are in a RopePieceBTree.  This first iterates over bytes
86  /// in a RopePiece, then iterates over RopePiece's in a RopePieceBTreeLeaf,
87  /// then iterates over RopePieceBTreeLeaf's in a RopePieceBTree.
88  class RopePieceBTreeIterator :
89      public std::iterator<std::forward_iterator_tag, const char, ptrdiff_t> {
90    /// CurNode - The current B+Tree node that we are inspecting.
91    const void /*RopePieceBTreeLeaf*/ *CurNode;
92    /// CurPiece - The current RopePiece in the B+Tree node that we're
93    /// inspecting.
94    const RopePiece *CurPiece;
95    /// CurChar - The current byte in the RopePiece we are pointing to.
96    unsigned CurChar;
97  public:
98    // begin iterator.
99    RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
100    // end iterator
101    RopePieceBTreeIterator()
102      : CurNode(nullptr), CurPiece(nullptr), CurChar(0) {}
103
104    char operator*() const {
105      return (*CurPiece)[CurChar];
106    }
107
108    bool operator==(const RopePieceBTreeIterator &RHS) const {
109      return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
110    }
111    bool operator!=(const RopePieceBTreeIterator &RHS) const {
112      return !operator==(RHS);
113    }
114
115    RopePieceBTreeIterator& operator++() {   // Preincrement
116      if (CurChar+1 < CurPiece->size())
117        ++CurChar;
118      else
119        MoveToNextPiece();
120      return *this;
121    }
122    inline 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    void operator=(const RopePieceBTree &) = delete;
140  public:
141    RopePieceBTree();
142    RopePieceBTree(const RopePieceBTree &RHS);
143    ~RopePieceBTree();
144
145    typedef RopePieceBTreeIterator iterator;
146    iterator begin() const { return iterator(Root); }
147    iterator end() const { return iterator(); }
148    unsigned size() const;
149    unsigned empty() const { return size() == 0; }
150
151    void clear();
152
153    void insert(unsigned Offset, const RopePiece &R);
154
155    void erase(unsigned Offset, unsigned NumBytes);
156  };
157
158  //===--------------------------------------------------------------------===//
159  // RewriteRope Class
160  //===--------------------------------------------------------------------===//
161
162/// RewriteRope - A powerful string class.  This class supports extremely
163/// efficient insertions and deletions into the middle of it, even for
164/// ridiculously long strings.
165class RewriteRope {
166  RopePieceBTree Chunks;
167
168  /// We allocate space for string data out of a buffer of size AllocChunkSize.
169  /// This keeps track of how much space is left.
170  llvm::IntrusiveRefCntPtr<RopeRefCountString> AllocBuffer;
171  unsigned AllocOffs;
172  enum { AllocChunkSize = 4080 };
173
174public:
175  RewriteRope() :  AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {}
176  RewriteRope(const RewriteRope &RHS)
177    : Chunks(RHS.Chunks), AllocBuffer(nullptr), AllocOffs(AllocChunkSize) {
178  }
179
180  typedef RopePieceBTree::iterator iterator;
181  typedef RopePieceBTree::iterator const_iterator;
182  iterator begin() const { return Chunks.begin(); }
183  iterator end() const  { return Chunks.end(); }
184  unsigned size() const { return Chunks.size(); }
185
186  void clear() {
187    Chunks.clear();
188  }
189
190  void assign(const char *Start, const char *End) {
191    clear();
192    if (Start != End)
193      Chunks.insert(0, MakeRopeString(Start, End));
194  }
195
196  void insert(unsigned Offset, const char *Start, const char *End) {
197    assert(Offset <= size() && "Invalid position to insert!");
198    if (Start == End) return;
199    Chunks.insert(Offset, MakeRopeString(Start, End));
200  }
201
202  void erase(unsigned Offset, unsigned NumBytes) {
203    assert(Offset+NumBytes <= size() && "Invalid region to erase!");
204    if (NumBytes == 0) return;
205    Chunks.erase(Offset, NumBytes);
206  }
207
208private:
209  RopePiece MakeRopeString(const char *Start, const char *End);
210};
211
212} // end namespace clang
213
214#endif
215