VMProtect/third-party/scintilla/SplitVector.h
VNGhostMans 5ec92ee05e first commit
Version 3.x.x
2023-05-14 20:21:09 +07:00

292 lines
7.2 KiB
C++

// Scintilla source code edit control
/** @file SplitVector.h
** Main data structure for holding arrays that handle insertions
** and deletions efficiently.
**/
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
// The License.txt file describes the conditions under which this software may be distributed.
#ifndef SPLITVECTOR_H
#define SPLITVECTOR_H
#ifdef SCI_NAMESPACE
namespace Scintilla {
#endif
template <typename T>
class SplitVector {
protected:
T *body;
int size;
int lengthBody;
int part1Length;
int gapLength; /// invariant: gapLength == size - lengthBody
int growSize;
/// Move the gap to a particular position so that insertion and
/// deletion at that point will not require much copying and
/// hence be fast.
void GapTo(int position) {
if (position != part1Length) {
if (position < part1Length) {
memmove(
body + position + gapLength,
body + position,
sizeof(T) * (part1Length - position));
} else { // position > part1Length
memmove(
body + part1Length,
body + part1Length + gapLength,
sizeof(T) * (position - part1Length));
}
part1Length = position;
}
}
/// Check that there is room in the buffer for an insertion,
/// reallocating if more space needed.
void RoomFor(int insertionLength) {
if (gapLength <= insertionLength) {
while (growSize < size / 6)
growSize *= 2;
ReAllocate(size + insertionLength + growSize);
}
}
void Init() {
body = NULL;
growSize = 8;
size = 0;
lengthBody = 0;
part1Length = 0;
gapLength = 0;
}
public:
/// Construct a split buffer.
SplitVector() {
Init();
}
~SplitVector() {
delete []body;
body = 0;
}
int GetGrowSize() const {
return growSize;
}
void SetGrowSize(int growSize_) {
growSize = growSize_;
}
/// Reallocate the storage for the buffer to be newSize and
/// copy exisiting contents to the new buffer.
/// Must not be used to decrease the size of the buffer.
void ReAllocate(int newSize) {
if (newSize > size) {
// Move the gap to the end
GapTo(lengthBody);
T *newBody = new T[newSize];
if ((size != 0) && (body != 0)) {
memmove(newBody, body, sizeof(T) * lengthBody);
delete []body;
}
body = newBody;
gapLength += newSize - size;
size = newSize;
}
}
/// Retrieve the character at a particular position.
/// Retrieving positions outside the range of the buffer returns 0.
/// The assertions here are disabled since calling code can be
/// simpler if out of range access works and returns 0.
T ValueAt(int position) const {
if (position < part1Length) {
//PLATFORM_ASSERT(position >= 0);
if (position < 0) {
return 0;
} else {
return body[position];
}
} else {
//PLATFORM_ASSERT(position < lengthBody);
if (position >= lengthBody) {
return 0;
} else {
return body[gapLength + position];
}
}
}
void SetValueAt(int position, T v) {
if (position < part1Length) {
PLATFORM_ASSERT(position >= 0);
if (position < 0) {
;
} else {
body[position] = v;
}
} else {
PLATFORM_ASSERT(position < lengthBody);
if (position >= lengthBody) {
;
} else {
body[gapLength + position] = v;
}
}
}
T &operator[](int position) const {
PLATFORM_ASSERT(position >= 0 && position < lengthBody);
if (position < part1Length) {
return body[position];
} else {
return body[gapLength + position];
}
}
/// Retrieve the length of the buffer.
int Length() const {
return lengthBody;
}
/// Insert a single value into the buffer.
/// Inserting at positions outside the current range fails.
void Insert(int position, T v) {
PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
if ((position < 0) || (position > lengthBody)) {
return;
}
RoomFor(1);
GapTo(position);
body[part1Length] = v;
lengthBody++;
part1Length++;
gapLength--;
}
/// Insert a number of elements into the buffer setting their value.
/// Inserting at positions outside the current range fails.
void InsertValue(int position, int insertLength, T v) {
PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
if (insertLength > 0) {
if ((position < 0) || (position > lengthBody)) {
return;
}
RoomFor(insertLength);
GapTo(position);
std::fill(&body[part1Length], &body[part1Length + insertLength], v);
lengthBody += insertLength;
part1Length += insertLength;
gapLength -= insertLength;
}
}
/// Ensure at least length elements allocated,
/// appending zero valued elements if needed.
void EnsureLength(int wantedLength) {
if (Length() < wantedLength) {
InsertValue(Length(), wantedLength - Length(), 0);
}
}
/// Insert text into the buffer from an array.
void InsertFromArray(int positionToInsert, const T s[], int positionFrom, int insertLength) {
PLATFORM_ASSERT((positionToInsert >= 0) && (positionToInsert <= lengthBody));
if (insertLength > 0) {
if ((positionToInsert < 0) || (positionToInsert > lengthBody)) {
return;
}
RoomFor(insertLength);
GapTo(positionToInsert);
memmove(body + part1Length, s + positionFrom, sizeof(T) * insertLength);
lengthBody += insertLength;
part1Length += insertLength;
gapLength -= insertLength;
}
}
/// Delete one element from the buffer.
void Delete(int position) {
PLATFORM_ASSERT((position >= 0) && (position < lengthBody));
if ((position < 0) || (position >= lengthBody)) {
return;
}
DeleteRange(position, 1);
}
/// Delete a range from the buffer.
/// Deleting positions outside the current range fails.
void DeleteRange(int position, int deleteLength) {
PLATFORM_ASSERT((position >= 0) && (position + deleteLength <= lengthBody));
if ((position < 0) || ((position + deleteLength) > lengthBody)) {
return;
}
if ((position == 0) && (deleteLength == lengthBody)) {
// Full deallocation returns storage and is faster
delete []body;
Init();
} else if (deleteLength > 0) {
GapTo(position);
lengthBody -= deleteLength;
gapLength += deleteLength;
}
}
/// Delete all the buffer contents.
void DeleteAll() {
DeleteRange(0, lengthBody);
}
// Retrieve a range of elements into an array
void GetRange(T *buffer, int position, int retrieveLength) const {
// Split into up to 2 ranges, before and after the split then use memcpy on each.
int range1Length = 0;
if (position < part1Length) {
int part1AfterPosition = part1Length - position;
range1Length = retrieveLength;
if (range1Length > part1AfterPosition)
range1Length = part1AfterPosition;
}
memcpy(buffer, body + position, range1Length * sizeof(T));
buffer += range1Length;
position = position + range1Length + gapLength;
int range2Length = retrieveLength - range1Length;
memcpy(buffer, body + position, range2Length * sizeof(T));
}
T *BufferPointer() {
RoomFor(1);
GapTo(lengthBody);
body[lengthBody] = 0;
return body;
}
T *RangePointer(int position, int rangeLength) {
if (position < part1Length) {
if ((position + rangeLength) > part1Length) {
// Range overlaps gap, so move gap to start of range.
GapTo(position);
return body + position + gapLength;
} else {
return body + position ;
}
} else {
return body + position + gapLength;
}
}
int GapPosition() const {
return part1Length;
}
};
#ifdef SCI_NAMESPACE
}
#endif
#endif