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 > size) {
  89                         // Move the gap to the end
  90                         GapTo(lengthBody);
  91                         T *newBody = new T[newSize];
  92                         if ((size != 0) && (body != 0)) {
  93                                 memmove(newBody, body, sizeof(T) * lengthBody);
  94                                 delete []body;
  95                         }
  96                         body = newBody;
  97                         gapLength += newSize - size;
  98                         size = newSize;
  99                 }
 100         }
 101
 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);
 109                         if (position < 0) {
 110                                 return 0;
 111                         } else {
 112                                 return body[position];
 113                         }
 114                 } else {
 115                         //PLATFORM_ASSERT(position < lengthBody);
 116                         if (position >= lengthBody) {
 117                                 return 0;
 118                         } else {
 119                                 return body[gapLength + position];
 120                         }
 121                 }
 122         }
 123
 124         void SetValueAt(int position, T v) {
 125                 if (position < part1Length) {
 126                         PLATFORM_ASSERT(position >= 0);
 127                         if (position < 0) {
 128                                 ;
 129                         } else {
 130                                 body[position] = v;
 131                         }
 132                 } else {
 133                         PLATFORM_ASSERT(position < lengthBody);
 134                         if (position >= lengthBody) {
 135                                 ;
 136                         } else {
 137                                 body[gapLength + position] = v;
 138                         }
 139                 }
 140         }
 141
 142         T &operator[](int position) const {
 143                 PLATFORM_ASSERT(position >= 0 && position < lengthBody);
 144                 if (position < part1Length) {
 145                         return body[position];
 146                 } else {
 147                         return body[gapLength + position];
 148                 }
 149         }
 150
 151         /// Retrieve the length of the buffer.
 152         int Length() const {
 153                 return lengthBody;
 154         }
 155
 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)) {
 161                         return;
 162                 }
 163                 RoomFor(1);
 164                 GapTo(position);
 165                 body[part1Length] = v;
 166                 lengthBody++;
 167                 part1Length++;
 168                 gapLength--;
 169         }
 170
 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)) {
 177                                 return;
 178                         }
 179                         RoomFor(insertLength);
 180                         GapTo(position);
 181                         std::fill(&body[part1Length], &body[part1Length + insertLength], v);
 182                         lengthBody += insertLength;
 183                         part1Length += insertLength;
 184                         gapLength -= insertLength;
 185                 }
 186         }
 187
 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);
 193                 }
 194         }
 195
 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)) {
 201                                 return;
 202                         }
 203                         RoomFor(insertLength);
 204                         GapTo(positionToInsert);
 205                         memmove(body + part1Length, s + positionFrom, sizeof(T) * insertLength);
 206                         lengthBody += insertLength;
 207                         part1Length += insertLength;
 208                         gapLength -= insertLength;
 209                 }
 210         }
 211
 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)) {
 216                         return;
 217                 }
 218                 DeleteRange(position, 1);
 219         }
 220
 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)) {
 226                         return;
 227                 }
 228                 if ((position == 0) && (deleteLength == lengthBody)) {
 229                         // Full deallocation returns storage and is faster
 230                         delete []body;
 231                         Init();
 232                 } else if (deleteLength > 0) {
 233                         GapTo(position);
 234                         lengthBody -= deleteLength;
 235                         gapLength += deleteLength;
 236                 }
 237         }
 238
 239         /// Delete all the buffer contents.
 240         void DeleteAll() {
 241                 DeleteRange(0, lengthBody);
 242         }
 243
 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;
 253                 }
 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));
 259         }
 260
 261         T *BufferPointer() {
 262                 RoomFor(1);
 263                 GapTo(lengthBody);
 264                 body[lengthBody] = 0;
 265                 return body;
 266         }
 267
 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.
 272                                 GapTo(position);
 273                                 return body + position + gapLength;
 274                         } else {
 275                                 return body + position ;
 276                         }
 277                 } else {
 278                         return body + position + gapLength;
 279                 }
 280         }
 281
 282         int GapPosition() const {
 283                 return part1Length;
 284         }
 285 };
 286
 287 #ifdef SCI_NAMESPACE
 288 }
 289 #endif
 290
 291 #endif