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
23namespace 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.
183class 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
192public:
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
232private:
233  RopePiece MakeRopeString(const char *Start, const char *End);
234};
235
236} // end namespace clang
237
238#endif
239