ext/scintilla/src/SplitVector.h

   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 template <typename T>
  13 class SplitVector {
  14 protected:
  15         T *body;
  16         int size;
  17         int lengthBody;
  18         int part1Length;
  19         int gapLength;  /// invariant: gapLength == size - lengthBody
  20         int growSize;
  21
  22         /// Move the gap to a particular position so that insertion and
  23         /// deletion at that point will not require much copying and
  24         /// hence be fast.
  25         void GapTo(int position) {
  26                 if (position != part1Length) {
  27                         if (position < part1Length) {
  28                                 memmove(
  29                                         body + position + gapLength,
  30                                         body + position,
  31                                         sizeof(T) * (part1Length - position));
  32                         } else {        // position > part1Length
  33                                 memmove(
  34                                         body + part1Length,
  35                                         body + part1Length + gapLength,
  36                                         sizeof(T) * (position - part1Length));
  37                         }
  38                         part1Length = position;
  39                 }
  40         }
  41
  42         /// Check that there is room in the buffer for an insertion,
  43         /// reallocating if more space needed.
  44         void RoomFor(int insertionLength) {
  45                 if (gapLength <= insertionLength) {
  46                         while (growSize < size / 6)
  47                                 growSize *= 2;
  48                         ReAllocate(size + insertionLength + growSize);
  49                 }
  50         }
  51
  52         void Init() {
  53                 body = NULL;
  54                 growSize = 8;
  55                 size = 0;
  56                 lengthBody = 0;
  57                 part1Length = 0;
  58                 gapLength = 0;
  59         }
  60
  61 public:
  62         /// Construct a split buffer.
  63         SplitVector() {
  64                 Init();
  65         }
  66
  67         ~SplitVector() {
  68                 delete []body;
  69                 body = 0;
  70         }
  71
  72         int GetGrowSize() const {
  73                 return growSize;
  74         }
  75
  76         void SetGrowSize(int growSize_) {
  77                 growSize = growSize_;
  78         }
  79
  80         /// Reallocate the storage for the buffer to be newSize and
  81         /// copy exisiting contents to the new buffer.
  82         /// Must not be used to decrease the size of the buffer.
  83         void ReAllocate(int newSize) {
  84                 if (newSize > size) {
  85                         // Move the gap to the end
  86                         GapTo(lengthBody);
  87                         T *newBody = new T[newSize];
  88                         if ((size != 0) && (body != 0)) {
  89                                 memmove(newBody, body, sizeof(T) * lengthBody);
  90                                 delete []body;
  91                         }
  92                         body = newBody;
  93                         gapLength += newSize - size;
  94                         size = newSize;
  95                 }
  96         }
  97
  98         /// Retrieve the character at a particular position.
  99         /// Retrieving positions outside the range of the buffer returns 0.
 100         /// The assertions here are disabled since calling code can be
 101         /// simpler if out of range access works and returns 0.
 102         T ValueAt(int position) const {
 103                 if (position < part1Length) {
 104                         //PLATFORM_ASSERT(position >= 0);
 105                         if (position < 0) {
 106                                 return 0;
 107                         } else {
 108                                 return body[position];
 109                         }
 110                 } else {
 111                         //PLATFORM_ASSERT(position < lengthBody);
 112                         if (position >= lengthBody) {
 113                                 return 0;
 114                         } else {
 115                                 return body[gapLength + position];
 116                         }
 117                 }
 118         }
 119
 120         void SetValueAt(int position, T v) {
 121                 if (position < part1Length) {
 122                         PLATFORM_ASSERT(position >= 0);
 123                         if (position < 0) {
 124                                 ;
 125                         } else {
 126                                 body[position] = v;
 127                         }
 128                 } else {
 129                         PLATFORM_ASSERT(position < lengthBody);
 130                         if (position >= lengthBody) {
 131                                 ;
 132                         } else {
 133                                 body[gapLength + position] = v;
 134                         }
 135                 }
 136         }
 137
 138         T &operator[](int position) const {
 139                 PLATFORM_ASSERT(position >= 0 && position < lengthBody);
 140                 if (position < part1Length) {
 141                         return body[position];
 142                 } else {
 143                         return body[gapLength + position];
 144                 }
 145         }
 146
 147         /// Retrieve the length of the buffer.
 148         int Length() const {
 149                 return lengthBody;
 150         }
 151
 152         /// Insert a single value into the buffer.
 153         /// Inserting at positions outside the current range fails.
 154         void Insert(int position, T v) {
 155                 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
 156                 if ((position < 0) || (position > lengthBody)) {
 157                         return;
 158                 }
 159                 RoomFor(1);
 160                 GapTo(position);
 161                 body[part1Length] = v;
 162                 lengthBody++;
 163                 part1Length++;
 164                 gapLength--;
 165         }
 166
 167         /// Insert a number of elements into the buffer setting their value.
 168         /// Inserting at positions outside the current range fails.
 169         void InsertValue(int position, int insertLength, T v) {
 170                 PLATFORM_ASSERT((position >= 0) && (position <= lengthBody));
 171                 if (insertLength > 0) {
 172                         if ((position < 0) || (position > lengthBody)) {
 173                                 return;
 174                         }
 175                         RoomFor(insertLength);
 176                         GapTo(position);
 177                         for (int i = 0; i < insertLength; i++)
 178                                 body[part1Length + i] = v;
 179                         lengthBody += insertLength;
 180                         part1Length += insertLength;
 181                         gapLength -= insertLength;
 182                 }
 183         }
 184
 185         /// Ensure at least length elements allocated,
 186         /// appending zero valued elements if needed.
 187         void EnsureLength(int wantedLength) {
 188                 if (Length() < wantedLength) {
 189                         InsertValue(Length(), wantedLength - Length(), 0);
 190                 }
 191         }
 192
 193         /// Insert text into the buffer from an array.
 194         void InsertFromArray(int positionToInsert, const T s[], int positionFrom, int insertLength) {
 195                 PLATFORM_ASSERT((positionToInsert >= 0) && (positionToInsert <= lengthBody));
 196                 if (insertLength > 0) {
 197                         if ((positionToInsert < 0) || (positionToInsert > lengthBody)) {
 198                                 return;
 199                         }
 200                         RoomFor(insertLength);
 201                         GapTo(positionToInsert);
 202                         memmove(body + part1Length, s + positionFrom, sizeof(T) * insertLength);
 203                         lengthBody += insertLength;
 204                         part1Length += insertLength;
 205                         gapLength -= insertLength;
 206                 }
 207         }
 208
 209         /// Delete one element from the buffer.
 210         void Delete(int position) {
 211                 PLATFORM_ASSERT((position >= 0) && (position < lengthBody));
 212                 if ((position < 0) || (position >= lengthBody)) {
 213                         return;
 214                 }
 215                 DeleteRange(position, 1);
 216         }
 217
 218         /// Delete a range from the buffer.
 219         /// Deleting positions outside the current range fails.
 220         void DeleteRange(int position, int deleteLength) {
 221                 PLATFORM_ASSERT((position >= 0) && (position + deleteLength <= lengthBody));
 222                 if ((position < 0) || ((position + deleteLength) > lengthBody)) {
 223                         return;
 224                 }
 225                 if ((position == 0) && (deleteLength == lengthBody)) {
 226                         // Full deallocation returns storage and is faster
 227                         delete []body;
 228                         Init();
 229                 } else if (deleteLength > 0) {
 230                         GapTo(position);
 231                         lengthBody -= deleteLength;
 232                         gapLength += deleteLength;
 233                 }
 234         }
 235
 236         /// Delete all the buffer contents.
 237         void DeleteAll() {
 238                 DeleteRange(0, lengthBody);
 239         }
 240
 241         // Retrieve a range of elements into an array
 242         void GetRange(T *buffer, int position, int retrieveLength) const {
 243                 // Split into up to 2 ranges, before and after the split then use memcpy on each.
 244                 int range1Length = 0;
 245                 if (position < part1Length) {
 246                         int part1AfterPosition = part1Length - position;
 247                         range1Length = retrieveLength;
 248                         if (range1Length > part1AfterPosition)
 249                                 range1Length = part1AfterPosition;
 250                 }
 251                 memcpy(buffer, body + position, range1Length * sizeof(T));
 252                 buffer += range1Length;
 253                 position = position + range1Length + gapLength;
 254                 int range2Length = retrieveLength - range1Length;
 255                 memcpy(buffer, body + position, range2Length * sizeof(T));
 256         }
 257
 258         T *BufferPointer() {
 259                 RoomFor(1);
 260                 GapTo(lengthBody);
 261                 body[lengthBody] = 0;
 262                 return body;
 263         }
 264 };
 265
 266 #endif