Coverage Report

Created: 2019-02-23 12:57

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