LLVM 20.0.0git
RewriteRope.h
Go to the documentation of this file.
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_ADT_REWRITEROPE_H
14#define LLVM_ADT_REWRITEROPE_H
15
17#include "llvm/ADT/StringRef.h"
18#include <cassert>
19#include <cstddef>
20#include <iterator>
21#include <utility>
22
23namespace llvm {
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.
34 unsigned RefCount;
35 char Data[1]; // Variable sized.
36
37 void Retain() { ++RefCount; }
38
39 void Release() {
40 assert(RefCount > 0 && "Reference count is already zero.");
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.
58struct RopePiece {
60 unsigned StartOffs = 0;
61 unsigned EndOffs = 0;
62
63 RopePiece() = default;
65 unsigned End)
66 : StrData(std::move(Str)), StartOffs(Start), EndOffs(End) {}
67
68 const char &operator[](unsigned Offset) const {
69 return StrData->Data[Offset + StartOffs];
70 }
71 char &operator[](unsigned Offset) {
72 return StrData->Data[Offset + StartOffs];
73 }
74
75 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.
87 /// CurNode - The current B+Tree node that we are inspecting.
88 const void /*RopePieceBTreeLeaf*/ *CurNode = nullptr;
89
90 /// CurPiece - The current RopePiece in the B+Tree node that we're
91 /// inspecting.
92 const RopePiece *CurPiece = nullptr;
93
94 /// CurChar - The current byte in the RopePiece we are pointing to.
95 unsigned CurChar = 0;
96
97public:
98 using iterator_category = std::forward_iterator_tag;
99 using value_type = const char;
100 using difference_type = std::ptrdiff_t;
103
105 RopePieceBTreeIterator(const void /*RopePieceBTreeNode*/ *N);
106
107 char operator*() const { return (*CurPiece)[CurChar]; }
108
110 return CurPiece == RHS.CurPiece && CurChar == RHS.CurChar;
111 }
113 return !operator==(RHS);
114 }
115
117 if (CurChar + 1 < CurPiece->size())
118 ++CurChar;
119 else
121 return *this;
122 }
123
124 RopePieceBTreeIterator operator++(int) { // Postincrement
125 RopePieceBTreeIterator tmp = *this;
126 ++*this;
127 return tmp;
128 }
129
131 return llvm::StringRef(&(*CurPiece)[0], CurPiece->size());
132 }
133
134 void MoveToNextPiece();
135};
136
137//===--------------------------------------------------------------------===//
138// RopePieceBTree Class
139//===--------------------------------------------------------------------===//
140
142 void /*RopePieceBTreeNode*/ *Root;
143
144public:
149
151
152 iterator begin() const { return iterator(Root); }
153 iterator end() const { return iterator(); }
154 unsigned size() const;
155 unsigned empty() const { return size() == 0; }
156
157 void clear();
158
159 void insert(unsigned Offset, const RopePiece &R);
160
161 void erase(unsigned Offset, unsigned NumBytes);
162};
163
164//===--------------------------------------------------------------------===//
165// RewriteRope Class
166//===--------------------------------------------------------------------===//
167
168/// RewriteRope - A powerful string class. This class supports extremely
169/// efficient insertions and deletions into the middle of it, even for
170/// ridiculously long strings.
172 RopePieceBTree Chunks;
173
174 /// We allocate space for string data out of a buffer of size AllocChunkSize.
175 /// This keeps track of how much space is left.
177 enum { AllocChunkSize = 4080 };
178 unsigned AllocOffs = AllocChunkSize;
179
180public:
181 RewriteRope() = default;
182 RewriteRope(const RewriteRope &RHS) : Chunks(RHS.Chunks) {}
183
184 // The copy assignment operator is defined as deleted pending further
185 // motivation.
187
190
191 iterator begin() const { return Chunks.begin(); }
192 iterator end() const { return Chunks.end(); }
193 unsigned size() const { return Chunks.size(); }
194
195 void clear() { Chunks.clear(); }
196
197 void assign(const char *Start, const char *End) {
198 clear();
199 if (Start != End)
200 Chunks.insert(0, MakeRopeString(Start, End));
201 }
202
203 void insert(unsigned Offset, const char *Start, const char *End) {
204 assert(Offset <= size() && "Invalid position to insert!");
205 if (Start == End)
206 return;
207 Chunks.insert(Offset, MakeRopeString(Start, End));
208 }
209
210 void erase(unsigned Offset, unsigned NumBytes) {
211 assert(Offset + NumBytes <= size() && "Invalid region to erase!");
212 if (NumBytes == 0)
213 return;
214 Chunks.erase(Offset, NumBytes);
215 }
216
217private:
218 RopePiece MakeRopeString(const char *Start, const char *End);
219};
220
221} // namespace llvm
222
223#endif // LLVM_ADT_REWRITEROPE_H
bool End
Definition: ELF_riscv.cpp:480
This file defines the RefCountedBase, ThreadSafeRefCountedBase, and IntrusiveRefCntPtr classes.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
A smart pointer to a reference-counted object that inherits from RefCountedBase or ThreadSafeRefCount...
RewriteRope - A powerful string class.
Definition: RewriteRope.h:171
RewriteRope()=default
unsigned size() const
Definition: RewriteRope.h:193
RewriteRope & operator=(const RewriteRope &)=delete
void insert(unsigned Offset, const char *Start, const char *End)
Definition: RewriteRope.h:203
iterator end() const
Definition: RewriteRope.h:192
RewriteRope(const RewriteRope &RHS)
Definition: RewriteRope.h:182
void erase(unsigned Offset, unsigned NumBytes)
Definition: RewriteRope.h:210
iterator begin() const
Definition: RewriteRope.h:191
void assign(const char *Start, const char *End)
Definition: RewriteRope.h:197
RopePieceBTreeIterator - This class provides read-only forward iteration over bytes that are in a Rop...
Definition: RewriteRope.h:86
RopePieceBTreeIterator & operator++()
Definition: RewriteRope.h:116
bool operator==(const RopePieceBTreeIterator &RHS) const
Definition: RewriteRope.h:109
std::forward_iterator_tag iterator_category
Definition: RewriteRope.h:98
std::ptrdiff_t difference_type
Definition: RewriteRope.h:100
RopePieceBTreeIterator operator++(int)
Definition: RewriteRope.h:124
llvm::StringRef piece() const
Definition: RewriteRope.h:130
bool operator!=(const RopePieceBTreeIterator &RHS) const
Definition: RewriteRope.h:112
iterator end() const
Definition: RewriteRope.h:153
unsigned size() const
RopePieceBTreeIterator iterator
Definition: RewriteRope.h:150
void insert(unsigned Offset, const RopePiece &R)
void erase(unsigned Offset, unsigned NumBytes)
iterator begin() const
Definition: RewriteRope.h:152
RopePieceBTree & operator=(const RopePieceBTree &)=delete
unsigned empty() const
Definition: RewriteRope.h:155
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1856
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
#define N
RopePiece - This class represents a view into a RopeRefCountString object.
Definition: RewriteRope.h:58
unsigned EndOffs
Definition: RewriteRope.h:61
RopePiece()=default
unsigned StartOffs
Definition: RewriteRope.h:60
char & operator[](unsigned Offset)
Definition: RewriteRope.h:71
RopePiece(llvm::IntrusiveRefCntPtr< RopeRefCountString > Str, unsigned Start, unsigned End)
Definition: RewriteRope.h:64
unsigned size() const
Definition: RewriteRope.h:75
const char & operator[](unsigned Offset) const
Definition: RewriteRope.h:68
llvm::IntrusiveRefCntPtr< RopeRefCountString > StrData
Definition: RewriteRope.h:59
RopeRefCountString - This struct is allocated with 'new char[]' from the heap, and represents a refer...
Definition: RewriteRope.h:33