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.
23 int gapLength
; /// invariant: gapLength == size - lengthBody
26 /// Move the gap to a particular position so that insertion and
27 /// deletion at that point will not require much copying and
29 void GapTo(int position
) {
30 if (position
!= part1Length
) {
31 if (position
< part1Length
) {
33 body
+ position
+ gapLength
,
35 sizeof(T
) * (part1Length
- position
));
36 } else { // position > part1Length
39 body
+ part1Length
+ gapLength
,
40 sizeof(T
) * (position
- part1Length
));
42 part1Length
= position
;
46 /// Check that there is room in the buffer for an insertion,
47 /// reallocating if more space needed.
48 void RoomFor(int insertionLength
) {
49 if (gapLength
<= insertionLength
) {
50 while (growSize
< size
/ 6)
52 ReAllocate(size
+ insertionLength
+ growSize
);
66 /// Construct a split buffer.
76 int GetGrowSize() const {
80 void SetGrowSize(int growSize_
) {
84 /// Reallocate the storage for the buffer to be newSize and
85 /// copy exisiting contents to the new buffer.
86 /// Must not be used to decrease the size of the buffer.
87 void ReAllocate(int newSize
) {
89 // Move the gap to the end
91 T
*newBody
= new T
[newSize
];
92 if ((size
!= 0) && (body
!= 0)) {
93 memmove(newBody
, body
, sizeof(T
) * lengthBody
);
97 gapLength
+= newSize
- size
;
102 /// Retrieve the character at a particular position.
103 /// Retrieving positions outside the range of the buffer returns 0.
104 /// The assertions here are disabled since calling code can be
105 /// simpler if out of range access works and returns 0.
106 T
ValueAt(int position
) const {
107 if (position
< part1Length
) {
108 //PLATFORM_ASSERT(position >= 0);
112 return body
[position
];
115 //PLATFORM_ASSERT(position < lengthBody);
116 if (position
>= lengthBody
) {
119 return body
[gapLength
+ position
];
124 void SetValueAt(int position
, T v
) {
125 if (position
< part1Length
) {
126 PLATFORM_ASSERT(position
>= 0);
133 PLATFORM_ASSERT(position
< lengthBody
);
134 if (position
>= lengthBody
) {
137 body
[gapLength
+ position
] = v
;
142 T
&operator[](int position
) const {
143 PLATFORM_ASSERT(position
>= 0 && position
< lengthBody
);
144 if (position
< part1Length
) {
145 return body
[position
];
147 return body
[gapLength
+ position
];
151 /// Retrieve the length of the buffer.
156 /// Insert a single value into the buffer.
157 /// Inserting at positions outside the current range fails.
158 void Insert(int position
, T v
) {
159 PLATFORM_ASSERT((position
>= 0) && (position
<= lengthBody
));
160 if ((position
< 0) || (position
> lengthBody
)) {
165 body
[part1Length
] = v
;
171 /// Insert a number of elements into the buffer setting their value.
172 /// Inserting at positions outside the current range fails.
173 void InsertValue(int position
, int insertLength
, T v
) {
174 PLATFORM_ASSERT((position
>= 0) && (position
<= lengthBody
));
175 if (insertLength
> 0) {
176 if ((position
< 0) || (position
> lengthBody
)) {
179 RoomFor(insertLength
);
181 std::fill(&body
[part1Length
], &body
[part1Length
+ insertLength
], v
);
182 lengthBody
+= insertLength
;
183 part1Length
+= insertLength
;
184 gapLength
-= insertLength
;
188 /// Ensure at least length elements allocated,
189 /// appending zero valued elements if needed.
190 void EnsureLength(int wantedLength
) {
191 if (Length() < wantedLength
) {
192 InsertValue(Length(), wantedLength
- Length(), 0);
196 /// Insert text into the buffer from an array.
197 void InsertFromArray(int positionToInsert
, const T s
[], int positionFrom
, int insertLength
) {
198 PLATFORM_ASSERT((positionToInsert
>= 0) && (positionToInsert
<= lengthBody
));
199 if (insertLength
> 0) {
200 if ((positionToInsert
< 0) || (positionToInsert
> lengthBody
)) {
203 RoomFor(insertLength
);
204 GapTo(positionToInsert
);
205 memmove(body
+ part1Length
, s
+ positionFrom
, sizeof(T
) * insertLength
);
206 lengthBody
+= insertLength
;
207 part1Length
+= insertLength
;
208 gapLength
-= insertLength
;
212 /// Delete one element from the buffer.
213 void Delete(int position
) {
214 PLATFORM_ASSERT((position
>= 0) && (position
< lengthBody
));
215 if ((position
< 0) || (position
>= lengthBody
)) {
218 DeleteRange(position
, 1);
221 /// Delete a range from the buffer.
222 /// Deleting positions outside the current range fails.
223 void DeleteRange(int position
, int deleteLength
) {
224 PLATFORM_ASSERT((position
>= 0) && (position
+ deleteLength
<= lengthBody
));
225 if ((position
< 0) || ((position
+ deleteLength
) > lengthBody
)) {
228 if ((position
== 0) && (deleteLength
== lengthBody
)) {
229 // Full deallocation returns storage and is faster
232 } else if (deleteLength
> 0) {
234 lengthBody
-= deleteLength
;
235 gapLength
+= deleteLength
;
239 /// Delete all the buffer contents.
241 DeleteRange(0, lengthBody
);
244 // Retrieve a range of elements into an array
245 void GetRange(T
*buffer
, int position
, int retrieveLength
) const {
246 // Split into up to 2 ranges, before and after the split then use memcpy on each.
247 int range1Length
= 0;
248 if (position
< part1Length
) {
249 int part1AfterPosition
= part1Length
- position
;
250 range1Length
= retrieveLength
;
251 if (range1Length
> part1AfterPosition
)
252 range1Length
= part1AfterPosition
;
254 memcpy(buffer
, body
+ position
, range1Length
* sizeof(T
));
255 buffer
+= range1Length
;
256 position
= position
+ range1Length
+ gapLength
;
257 int range2Length
= retrieveLength
- range1Length
;
258 memcpy(buffer
, body
+ position
, range2Length
* sizeof(T
));
264 body
[lengthBody
] = 0;
268 T
*RangePointer(int position
, int rangeLength
) {
269 if (position
< part1Length
) {
270 if ((position
+ rangeLength
) > part1Length
) {
271 // Range overlaps gap, so move gap to start of range.
273 return body
+ position
+ gapLength
;
275 return body
+ position
;
278 return body
+ position
+ gapLength
;
282 int GapPosition() const {