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