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