1 // Scintilla source code edit control
2 /** @file SplitVector.h
3 ** Main data structure for holding arrays that handle insertions
4 ** and deletions efficiently.
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.
12 namespace Scintilla::Internal
{
18 T empty
; /// Returned as the result of out-of-bounds access.
20 ptrdiff_t part1Length
;
21 ptrdiff_t gapLength
; /// invariant: gapLength == body.size() - lengthBody
24 /// Move the gap to a particular position so that insertion and
25 /// deletion at that point will not require much copying and
27 void GapTo(ptrdiff_t position
) noexcept
{
28 if (position
!= part1Length
) {
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
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
41 body
.data() + part1Length
+ gapLength
,
42 body
.data() + gapLength
+ position
,
43 body
.data() + part1Length
);
46 part1Length
= position
;
48 // Ignore any exception
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
< body
.size() / 6)
59 ReAllocate(body
.size() + insertionLength
+ growSize
);
73 /// Construct a split buffer.
74 SplitVector(size_t growSize_
=8) : empty(), lengthBody(0), part1Length(0), gapLength(0), growSize(growSize_
) {
77 size_t GetGrowSize() const noexcept
{
81 void SetGrowSize(size_t growSize_
) noexcept
{
85 /// Reallocate the storage for the buffer to be newSize and
86 /// copy existing contents to the new buffer.
87 /// Must not be used to decrease the size of the buffer.
88 void ReAllocate(size_t newSize
) {
89 if (newSize
> body
.size()) {
90 // Move the gap to the end
92 gapLength
+= newSize
- body
.size();
93 // RoomFor implements a growth strategy but so does vector::resize so
94 // ensure vector::resize allocates exactly the amount wanted by
95 // calling reserve first.
96 body
.reserve(newSize
);
101 /// Retrieve the element at a particular position.
102 /// Retrieving positions outside the range of the buffer returns empty or 0.
103 const T
& ValueAt(ptrdiff_t position
) const noexcept
{
104 if (position
< part1Length
) {
108 return body
[position
];
111 if (position
>= lengthBody
) {
114 return body
[gapLength
+ position
];
119 /// Set the element at a particular position.
120 /// Setting positions outside the range of the buffer performs no assignment
121 /// but asserts in debug builds.
122 template <typename ParamType
>
123 void SetValueAt(ptrdiff_t position
, ParamType
&& v
) noexcept
{
124 if (position
< part1Length
) {
125 PLATFORM_ASSERT(position
>= 0);
129 body
[position
] = std::forward
<ParamType
>(v
);
132 PLATFORM_ASSERT(position
< lengthBody
);
133 if (position
>= lengthBody
) {
136 body
[gapLength
+ position
] = std::forward
<ParamType
>(v
);
141 /// Retrieve the element at a particular position.
142 /// The position must be within bounds or an assertion is triggered.
143 const T
&operator[](ptrdiff_t position
) const noexcept
{
144 PLATFORM_ASSERT(position
>= 0 && position
< lengthBody
);
145 if (position
< part1Length
) {
146 return body
[position
];
148 return body
[gapLength
+ position
];
152 /// Retrieve reference to the element at a particular position.
153 /// This, instead of the const variant, can be used to mutate in-place.
154 /// The position must be within bounds or an assertion is triggered.
155 T
&operator[](ptrdiff_t position
) noexcept
{
156 PLATFORM_ASSERT(position
>= 0 && position
< lengthBody
);
157 if (position
< part1Length
) {
158 return body
[position
];
160 return body
[gapLength
+ position
];
164 /// Retrieve the length of the buffer.
165 ptrdiff_t Length() const noexcept
{
169 /// Insert a single value into the buffer.
170 /// Inserting at positions outside the current range fails.
171 void Insert(ptrdiff_t position
, T v
) {
172 PLATFORM_ASSERT((position
>= 0) && (position
<= lengthBody
));
173 if ((position
< 0) || (position
> lengthBody
)) {
178 body
[part1Length
] = std::move(v
);
184 /// Insert a number of elements into the buffer setting their value.
185 /// Inserting at positions outside the current range fails.
186 void InsertValue(ptrdiff_t position
, ptrdiff_t insertLength
, T v
) {
187 PLATFORM_ASSERT((position
>= 0) && (position
<= lengthBody
));
188 if (insertLength
> 0) {
189 if ((position
< 0) || (position
> lengthBody
)) {
192 RoomFor(insertLength
);
194 std::fill(body
.data() + part1Length
, body
.data() + part1Length
+ insertLength
, v
);
195 lengthBody
+= insertLength
;
196 part1Length
+= insertLength
;
197 gapLength
-= insertLength
;
201 /// Add some new empty elements.
202 /// InsertValue is good for value objects but not for unique_ptr objects
203 /// since they can only be moved from once.
204 /// Callers can write to the returned pointer to transform inputs without copies.
205 T
*InsertEmpty(ptrdiff_t position
, ptrdiff_t insertLength
) {
206 PLATFORM_ASSERT((position
>= 0) && (position
<= lengthBody
));
207 if (insertLength
> 0) {
208 if ((position
< 0) || (position
> lengthBody
)) {
211 RoomFor(insertLength
);
213 for (ptrdiff_t elem
= part1Length
; elem
< part1Length
+ insertLength
; elem
++) {
215 body
[elem
] = std::move(emptyOne
);
217 lengthBody
+= insertLength
;
218 part1Length
+= insertLength
;
219 gapLength
-= insertLength
;
221 return body
.data() + position
;
224 /// Ensure at least length elements allocated,
225 /// appending zero valued elements if needed.
226 void EnsureLength(ptrdiff_t wantedLength
) {
227 if (Length() < wantedLength
) {
228 InsertEmpty(Length(), wantedLength
- Length());
232 /// Insert text into the buffer from an array.
233 void InsertFromArray(ptrdiff_t positionToInsert
, const T s
[], ptrdiff_t positionFrom
, ptrdiff_t insertLength
) {
234 PLATFORM_ASSERT((positionToInsert
>= 0) && (positionToInsert
<= lengthBody
));
235 if (insertLength
> 0) {
236 if ((positionToInsert
< 0) || (positionToInsert
> lengthBody
)) {
239 RoomFor(insertLength
);
240 GapTo(positionToInsert
);
241 std::copy(s
+ positionFrom
, s
+ positionFrom
+ insertLength
, body
.data() + part1Length
);
242 lengthBody
+= insertLength
;
243 part1Length
+= insertLength
;
244 gapLength
-= insertLength
;
248 /// Delete one element from the buffer.
249 void Delete(ptrdiff_t position
) {
250 PLATFORM_ASSERT((position
>= 0) && (position
< lengthBody
));
251 DeleteRange(position
, 1);
254 /// Delete a range from the buffer.
255 /// Deleting positions outside the current range fails.
256 /// Cannot be noexcept as vector::shrink_to_fit may be called and it may throw.
257 void DeleteRange(ptrdiff_t position
, ptrdiff_t deleteLength
) {
258 PLATFORM_ASSERT((position
>= 0) && (position
+ deleteLength
<= lengthBody
));
259 if ((position
< 0) || ((position
+ deleteLength
) > lengthBody
)) {
262 if ((position
== 0) && (deleteLength
== lengthBody
)) {
263 // Full deallocation returns storage and is faster
265 } else if (deleteLength
> 0) {
267 lengthBody
-= deleteLength
;
268 gapLength
+= deleteLength
;
272 /// Delete all the buffer contents.
274 DeleteRange(0, lengthBody
);
277 /// Retrieve a range of elements into an array
278 void GetRange(T
*buffer
, ptrdiff_t position
, ptrdiff_t retrieveLength
) const {
279 // Split into up to 2 ranges, before and after the split then use memcpy on each.
280 ptrdiff_t range1Length
= 0;
281 if (position
< part1Length
) {
282 const ptrdiff_t part1AfterPosition
= part1Length
- position
;
283 range1Length
= retrieveLength
;
284 if (range1Length
> part1AfterPosition
)
285 range1Length
= part1AfterPosition
;
287 std::copy(body
.data() + position
, body
.data() + position
+ range1Length
, buffer
);
288 buffer
+= range1Length
;
289 position
= position
+ range1Length
+ gapLength
;
290 const ptrdiff_t range2Length
= retrieveLength
- range1Length
;
291 std::copy(body
.data() + position
, body
.data() + position
+ range2Length
, buffer
);
294 /// Compact the buffer and return a pointer to the first element.
295 /// Also ensures there is an empty element beyond logical end in case its
296 /// passed to a function expecting a NUL terminated string.
301 body
[lengthBody
] = std::move(emptyOne
);
305 /// Return a pointer to a range of elements, first rearranging the buffer if
306 /// needed to make that range contiguous.
307 T
*RangePointer(ptrdiff_t position
, ptrdiff_t rangeLength
) noexcept
{
308 if (position
< part1Length
) {
309 if ((position
+ rangeLength
) > part1Length
) {
310 // Range overlaps gap, so move gap to start of range.
312 return body
.data() + position
+ gapLength
;
314 return body
.data() + position
;
317 return body
.data() + position
+ gapLength
;
321 /// Return a pointer to a single element.
322 /// Does not rearrange the buffer.
323 const T
*ElementPointer(ptrdiff_t position
) const noexcept
{
324 if (position
< part1Length
) {
325 return body
.data() + position
;
327 return body
.data() + position
+ gapLength
;
331 /// Return the position of the gap within the buffer.
332 ptrdiff_t GapPosition() const noexcept
{