1// Scintilla source code edit control
2/** @file SplitVector.h
3 ** Main data structure for holding arrays that handle insertions
4 ** and deletions efficiently.
5 **/
6// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
7// The License.txt file describes the conditions under which this software may be distributed.
8
9#ifndef SPLITVECTOR_H
10#define SPLITVECTOR_H
11
12namespace Scintilla::Internal {
13
14template <typename T>
15class SplitVector {
16protected:
17 std::vector<T> body;
18 T empty; /// Returned as the result of out-of-bounds access.
19 ptrdiff_t lengthBody;
20 ptrdiff_t part1Length;
21 ptrdiff_t gapLength; /// invariant: gapLength == body.size() - lengthBody
22 ptrdiff_t growSize;
23
24 /// Move the gap to a particular position so that insertion and
25 /// deletion at that point will not require much copying and
26 /// hence be fast.
27 void GapTo(ptrdiff_t position) noexcept {
28 if (position != part1Length) {
29 try {
30 if (gapLength > 0) { // If gap to move
31 // This can never fail but std::move and std::move_backward are not noexcept.
32 if (position < part1Length) {
33 // Moving the gap towards start so moving elements towards end
34 std::move_backward(
35 body.data() + position,
36 body.data() + part1Length,
37 body.data() + gapLength + part1Length);
38 } else { // position > part1Length
39 // Moving the gap towards end so moving elements towards start
40 std::move(
41 body.data() + part1Length + gapLength,
42 body.data() + gapLength + position,
43 body.data() + part1Length);
44 }
45 }
46 part1Length = position;
47 } catch (...) {
48 // Ignore any exception
49 }
50 }
51 }
52
53 /// Check that there is room in the buffer for an insertion,
54 /// reallocating if more space needed.
55 void RoomFor(ptrdiff_t insertionLength) {
56 if (gapLength < insertionLength) {
57 while (growSize < static_cast<ptrdiff_t>(body.size() / 6))
58 growSize *= 2;
59 ReAllocate(body.size() + insertionLength + growSize);
60 }
61 }
62
63 void Init() {
64 body.clear();
65 body.shrink_to_fit();
66 lengthBody = 0;
67 part1Length = 0;
68 gapLength = 0;
69 growSize = 8;
70 }
71
72public:
73 /// Construct a split buffer.
74 SplitVector() : empty(), lengthBody(0), part1Length(0), gapLength(0), growSize(8) {
75 }
76
77 // Deleted so SplitVector objects can not be copied.
78 SplitVector(const SplitVector &) = delete;
79 SplitVector(SplitVector &&) = delete;
80 void operator=(const SplitVector &) = delete;
81 void operator=(SplitVector &&) = delete;
82
83 ~SplitVector() {
84 }
85
86 ptrdiff_t GetGrowSize() const noexcept {
87 return growSize;
88 }
89
90 void SetGrowSize(ptrdiff_t growSize_) noexcept {
91 growSize = growSize_;
92 }
93
94 /// Reallocate the storage for the buffer to be newSize and
95 /// copy existing contents to the new buffer.
96 /// Must not be used to decrease the size of the buffer.
97 void ReAllocate(ptrdiff_t newSize) {
98 if (newSize < 0)
99 throw std::runtime_error("SplitVector::ReAllocate: negative size.");
100
101 if (newSize > static_cast<ptrdiff_t>(body.size())) {
102 // Move the gap to the end
103 GapTo(lengthBody);
104 gapLength += newSize - static_cast<ptrdiff_t>(body.size());
105 // RoomFor implements a growth strategy but so does vector::resize so
106 // ensure vector::resize allocates exactly the amount wanted by
107 // calling reserve first.
108 body.reserve(newSize);
109 body.resize(newSize);
110 }
111 }
112
113 /// Retrieve the element at a particular position.
114 /// Retrieving positions outside the range of the buffer returns empty or 0.
115 const T& ValueAt(ptrdiff_t position) const noexcept {
116 if (position < part1Length) {
117 if (position < 0) {
118 return empty;
119 } else {
120 return body[position];
121 }
122 } else {
123 if (position >= lengthBody) {
124 return empty;
125 } else {
126 return body[gapLength + position];
127 }
128 }
129 }
130
131 /// Set the element at a particular position.
132 /// Setting positions outside the range of the buffer performs no assignment
133 /// but asserts in debug builds.
134 template <typename ParamType>
135 void SetValueAt(ptrdiff_t position, ParamType&& v) noexcept {
136 if (position < part1Length) {
137 PLATFORM_ASSERT(position >= 0);
138 if (position < 0) {
139 ;
140 } else {
141 body[position] = std::forward<ParamType>(v);
142 }
143 } else {
144 PLATFORM_ASSERT(position < lengthBody);
145 if (position >= lengthBody) {
146 ;
147 } else {
148 body[gapLength + position] = std::forward<ParamType>(v);
149 }
150 }
151 }
152
153 /// Retrieve the element at a particular position.
154 /// The position must be within bounds or an assertion is triggered.
155 const T &operator[](ptrdiff_t position) const noexcept {
156 PLATFORM_ASSERT(position >= 0 && position < lengthBody);
157 if (position < part1Length) {
158 return body[position];
159 } else {
160 return body[gapLength + position];
161 }
162 }
163
164 /// Retrieve reference to the element at a particular position.
165 /// This, instead of the const variant, can be used to mutate in-place.
166 /// The position must be within bounds or an assertion is triggered.
167 T &operator[](ptrdiff_t position) noexcept {
168 PLATFORM_ASSERT(position >= 0 && position < lengthBody);
169 if (position < part1Length) {
170 return body[position];
171 } else {
172 return body[gapLength + position];
173 }
174 }
175
176 /// Retrieve the length of the buffer.
177 ptrdiff_t Length() const noexcept {
178 return lengthBody;
179 }
180
181 /// Insert a single value into the buffer.
182 /// Inserting at positions outside the current range fails.
183 void Insert(ptrdiff_t position, T v) {
184 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
185 if ((position < 0) || (position > lengthBody)) {
186 return;
187 }
188 RoomFor(1);
189 GapTo(position);
190 body[part1Length] = std::move(v);
191 lengthBody++;
192 part1Length++;
193 gapLength--;
194 }
195
196 /// Insert a number of elements into the buffer setting their value.
197 /// Inserting at positions outside the current range fails.
198 void InsertValue(ptrdiff_t position, ptrdiff_t insertLength, T v) {
199 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
200 if (insertLength > 0) {
201 if ((position < 0) || (position > lengthBody)) {
202 return;
203 }
204 RoomFor(insertLength);
205 GapTo(position);
206 std::fill(body.data() + part1Length, body.data() + part1Length + insertLength, v);
207 lengthBody += insertLength;
208 part1Length += insertLength;
209 gapLength -= insertLength;
210 }
211 }
212
213 /// Add some new empty elements.
214 /// InsertValue is good for value objects but not for unique_ptr objects
215 /// since they can only be moved from once.
216 /// Callers can write to the returned pointer to transform inputs without copies.
217 T *InsertEmpty(ptrdiff_t position, ptrdiff_t insertLength) {
218 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
219 if (insertLength > 0) {
220 if ((position < 0) || (position > lengthBody)) {
221 return nullptr;
222 }
223 RoomFor(insertLength);
224 GapTo(position);
225 for (ptrdiff_t elem = part1Length; elem < part1Length + insertLength; elem++) {
226 T emptyOne = {};
227 body[elem] = std::move(emptyOne);
228 }
229 lengthBody += insertLength;
230 part1Length += insertLength;
231 gapLength -= insertLength;
232 }
233 return body.data() + position;
234 }
235
236 /// Ensure at least length elements allocated,
237 /// appending zero valued elements if needed.
238 void EnsureLength(ptrdiff_t wantedLength) {
239 if (Length() < wantedLength) {
240 InsertEmpty(Length(), wantedLength - Length());
241 }
242 }
243
244 /// Insert text into the buffer from an array.
245 void InsertFromArray(ptrdiff_t positionToInsert, const T s[], ptrdiff_t positionFrom, ptrdiff_t insertLength) {
246 PLATFORM_ASSERT((positionToInsert >= 0) && (positionToInsert <= lengthBody));
247 if (insertLength > 0) {
248 if ((positionToInsert < 0) || (positionToInsert > lengthBody)) {
249 return;
250 }
251 RoomFor(insertLength);
252 GapTo(positionToInsert);
253 std::copy(s + positionFrom, s + positionFrom + insertLength, body.data() + part1Length);
254 lengthBody += insertLength;
255 part1Length += insertLength;
256 gapLength -= insertLength;
257 }
258 }
259
260 /// Delete one element from the buffer.
261 void Delete(ptrdiff_t position) {
262 PLATFORM_ASSERT((position >= 0) && (position < lengthBody));
263 DeleteRange(position, 1);
264 }
265
266 /// Delete a range from the buffer.
267 /// Deleting positions outside the current range fails.
268 /// Cannot be noexcept as vector::shrink_to_fit may be called and it may throw.
269 void DeleteRange(ptrdiff_t position, ptrdiff_t deleteLength) {
270 PLATFORM_ASSERT((position >= 0) && (position + deleteLength <= lengthBody));
271 if ((position < 0) || ((position + deleteLength) > lengthBody)) {
272 return;
273 }
274 if ((position == 0) && (deleteLength == lengthBody)) {
275 // Full deallocation returns storage and is faster
276 Init();
277 } else if (deleteLength > 0) {
278 GapTo(position);
279 lengthBody -= deleteLength;
280 gapLength += deleteLength;
281 }
282 }
283
284 /// Delete all the buffer contents.
285 void DeleteAll() {
286 DeleteRange(0, lengthBody);
287 }
288
289 /// Retrieve a range of elements into an array
290 void GetRange(T *buffer, ptrdiff_t position, ptrdiff_t retrieveLength) const {
291 // Split into up to 2 ranges, before and after the split then use memcpy on each.
292 ptrdiff_t range1Length = 0;
293 if (position < part1Length) {
294 const ptrdiff_t part1AfterPosition = part1Length - position;
295 range1Length = retrieveLength;
296 if (range1Length > part1AfterPosition)
297 range1Length = part1AfterPosition;
298 }
299 std::copy(body.data() + position, body.data() + position + range1Length, buffer);
300 buffer += range1Length;
301 position = position + range1Length + gapLength;
302 const ptrdiff_t range2Length = retrieveLength - range1Length;
303 std::copy(body.data() + position, body.data() + position + range2Length, buffer);
304 }
305
306 /// Compact the buffer and return a pointer to the first element.
307 /// Also ensures there is an empty element beyond logical end in case its
308 /// passed to a function expecting a NUL terminated string.
309 T *BufferPointer() {
310 RoomFor(1);
311 GapTo(lengthBody);
312 T emptyOne = {};
313 body[lengthBody] = std::move(emptyOne);
314 return body.data();
315 }
316
317 /// Return a pointer to a range of elements, first rearranging the buffer if
318 /// needed to make that range contiguous.
319 T *RangePointer(ptrdiff_t position, ptrdiff_t rangeLength) noexcept {
320 if (position < part1Length) {
321 if ((position + rangeLength) > part1Length) {
322 // Range overlaps gap, so move gap to start of range.
323 GapTo(position);
324 return body.data() + position + gapLength;
325 } else {
326 return body.data() + position;
327 }
328 } else {
329 return body.data() + position + gapLength;
330 }
331 }
332
333 /// Return a pointer to a single element.
334 /// Does not rearrange the buffer.
335 const T *ElementPointer(ptrdiff_t position) const noexcept {
336 if (position < part1Length) {
337 return body.data() + position;
338 } else {
339 return body.data() + position + gapLength;
340 }
341 }
342
343 /// Return the position of the gap within the buffer.
344 ptrdiff_t GapPosition() const noexcept {
345 return part1Length;
346 }
347};
348
349}
350
351#endif
352