Coverage Report

Created: 2018-07-22 10:17

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/clang/include/clang/Rewrite/Core/RewriteRope.h
Line
Count
Source (jump to first uncovered line)
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
4.53M
    void Retain() { ++RefCount; }
39
40
4.53M
    void Release() {
41
4.53M
      assert(RefCount > 0 && "Reference count is already zero.");
42
4.53M
      if (--RefCount == 0)
43
15.4k
        delete [] (char*)this;
44
4.53M
    }
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
2.76M
    RopePiece() = default;
65
    RopePiece(llvm::IntrusiveRefCntPtr<RopeRefCountString> Str, unsigned Start,
66
              unsigned End)
67
873k
        : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
68
69
14.6M
    const char &operator[](unsigned Offset) const {
70
14.6M
      return StrData->Data[Offset+StartOffs];
71
14.6M
    }
72
0
    char &operator[](unsigned Offset) {
73
0
      return StrData->Data[Offset+StartOffs];
74
0
    }
75
76
42.3M
    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
14.0k
    RopePieceBTreeIterator() = default;
101
    RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
102
103
14.6M
    char operator*() const {
104
14.6M
      return (*CurPiece)[CurChar];
105
14.6M
    }
106
107
15.4M
    bool operator==(const RopePieceBTreeIterator &RHS) const {
108
15.4M
      return CurPiece == RHS.CurPiece && 
CurChar == RHS.CurChar18.3k
;
109
15.4M
    }
110
15.4M
    bool operator!=(const RopePieceBTreeIterator &RHS) const {
111
15.4M
      return !operator==(RHS);
112
15.4M
    }
113
114
16.2M
    RopePieceBTreeIterator& operator++() {   // Preincrement
115
16.2M
      if (CurChar+1 < CurPiece->size())
116
15.4M
        ++CurChar;
117
804k
      else
118
804k
        MoveToNextPiece();
119
16.2M
      return *this;
120
16.2M
    }
121
122
0
    RopePieceBTreeIterator operator++(int) { // Postincrement
123
0
      RopePieceBTreeIterator tmp = *this; ++*this; return tmp;
124
0
    }
125
126
84.2k
    llvm::StringRef piece() const {
127
84.2k
      return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
128
84.2k
    }
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
13.2k
    iterator begin() const { return iterator(Root); }
149
14.0k
    iterator end() const { return iterator(); }
150
    unsigned size() const;
151
0
    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
12.5k
  RewriteRope() = default;
178
25.0k
  RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
179
180
  using iterator = RopePieceBTree::iterator;
181
  using const_iterator = RopePieceBTree::iterator;
182
183
13.2k
  iterator begin() const { return Chunks.begin(); }
184
14.0k
  iterator end() const { return Chunks.end(); }
185
6
  unsigned size() const { return Chunks.size(); }
186
187
12.5k
  void clear() {
188
12.5k
    Chunks.clear();
189
12.5k
  }
190
191
12.5k
  void assign(const char *Start, const char *End) {
192
12.5k
    clear();
193
12.5k
    if (Start != End)
194
12.5k
      Chunks.insert(0, MakeRopeString(Start, End));
195
12.5k
  }
196
197
516k
  void insert(unsigned Offset, const char *Start, const char *End) {
198
516k
    assert(Offset <= size() && "Invalid position to insert!");
199
516k
    if (Start == End) 
return2.06k
;
200
514k
    Chunks.insert(Offset, MakeRopeString(Start, End));
201
514k
  }
202
203
259k
  void erase(unsigned Offset, unsigned NumBytes) {
204
259k
    assert(Offset+NumBytes <= size() && "Invalid region to erase!");
205
259k
    if (NumBytes == 0) 
return3.21k
;
206
256k
    Chunks.erase(Offset, NumBytes);
207
256k
  }
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