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 | |
12 | namespace Scintilla::Internal { |
13 | |
14 | template <typename T> |
15 | class SplitVector { |
16 | protected: |
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 | |
72 | public: |
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 | |