aboutsummaryrefslogtreecommitdiffhomepage
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/CellBuffer.cxx500
-rw-r--r--src/CellBuffer.h69
-rw-r--r--src/Document.cxx4
-rw-r--r--src/DocumentAccessor.cxx2
-rw-r--r--src/Editor.cxx4
-rw-r--r--src/Partitioning.h184
-rw-r--r--src/ScintillaBase.cxx2
-rw-r--r--src/SplitVector.h221
8 files changed, 603 insertions, 383 deletions
diff --git a/src/CellBuffer.cxx b/src/CellBuffer.cxx
index bd124d011..7096d4419 100644
--- a/src/CellBuffer.cxx
+++ b/src/CellBuffer.cxx
@@ -14,6 +14,8 @@
#include "Scintilla.h"
#include "SVector.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
#include "CellBuffer.h"
MarkerHandleSet::MarkerHandleSet() {
@@ -30,7 +32,7 @@ MarkerHandleSet::~MarkerHandleSet() {
root = 0;
}
-int MarkerHandleSet::Length() {
+int MarkerHandleSet::Length() const {
int c = 0;
MarkerHandleNumber *mhn = root;
while (mhn) {
@@ -40,7 +42,7 @@ int MarkerHandleSet::Length() {
return c;
}
-int MarkerHandleSet::NumberFromHandle(int handle) {
+int MarkerHandleSet::NumberFromHandle(int handle) const {
MarkerHandleNumber *mhn = root;
while (mhn) {
if (mhn->handle == handle) {
@@ -51,7 +53,7 @@ int MarkerHandleSet::NumberFromHandle(int handle) {
return - 1;
}
-int MarkerHandleSet::MarkValue() {
+int MarkerHandleSet::MarkValue() const {
unsigned int m = 0;
MarkerHandleNumber *mhn = root;
while (mhn) {
@@ -61,7 +63,7 @@ int MarkerHandleSet::MarkValue() {
return m;
}
-bool MarkerHandleSet::Contains(int handle) {
+bool MarkerHandleSet::Contains(int handle) const {
MarkerHandleNumber *mhn = root;
while (mhn) {
if (mhn->handle == handle) {
@@ -90,7 +92,7 @@ void MarkerHandleSet::RemoveHandle(int handle) {
if (mhn->handle == handle) {
*pmhn = mhn->next;
delete mhn;
- return ;
+ return;
}
pmhn = &((*pmhn)->next);
}
@@ -121,210 +123,154 @@ void MarkerHandleSet::CombineWith(MarkerHandleSet *other) {
other->root = 0;
}
-LineVector::LineVector() {
- linesData = 0;
- lines = 0;
- size = 0;
- levels = 0;
- sizeLevels = 0;
+LineVector::LineVector() : starts(256) {
handleCurrent = 1;
- growSize = 1000;
Init();
}
LineVector::~LineVector() {
- for (int line = 0; line < lines; line++) {
- delete linesData[line].handleSet;
- linesData[line].handleSet = 0;
+ starts.DeleteAll();
+ for (int line = 0; line < markers.Length(); line++) {
+ delete markers[line];
+ markers[line] = 0;
}
- delete []linesData;
- linesData = 0;
- delete []levels;
- levels = 0;
+ markers.DeleteAll();
+ levels.DeleteAll();
}
void LineVector::Init() {
- for (int line = 0; line < lines; line++) {
- delete linesData[line].handleSet;
- linesData[line].handleSet = 0;
+ starts.DeleteAll();
+ for (int line = 0; line < markers.Length(); line++) {
+ delete markers[line];
+ markers[line] = 0;
}
- delete []linesData;
- linesData = new LineData[static_cast<int>(growSize)];
- size = growSize;
- lines = 1;
- delete []levels;
- levels = 0;
- sizeLevels = 0;
-}
-
-void LineVector::Expand(int sizeNew) {
- LineData *linesDataNew = new LineData[sizeNew];
- if (linesDataNew) {
- for (int i = 0; i < size; i++)
- linesDataNew[i] = linesData[i];
- // Do not delete handleSets here as they are transferred to new linesData
- delete []linesData;
- linesData = linesDataNew;
- size = sizeNew;
- } else {
- Platform::DebugPrintf("No memory available\n");
- // TODO: Blow up
- }
-
+ markers.DeleteAll();
+ levels.DeleteAll();
}
void LineVector::ExpandLevels(int sizeNew) {
- if (sizeNew == -1)
- sizeNew = size;
- int *levelsNew = new int[sizeNew];
- if (levelsNew) {
- int i = 0;
- for (; i < sizeLevels; i++)
- levelsNew[i] = levels[i];
- for (; i < sizeNew; i++)
- levelsNew[i] = SC_FOLDLEVELBASE;
- delete []levels;
- levels = levelsNew;
- sizeLevels = sizeNew;
- } else {
- Platform::DebugPrintf("No memory available\n");
- // TODO: Blow up
- }
-
+ levels.InsertValue(levels.Length(), sizeNew - levels.Length(), SC_FOLDLEVELBASE);
}
void LineVector::ClearLevels() {
- delete []levels;
- levels = 0;
- sizeLevels = 0;
-}
-
-void LineVector::InsertValue(int pos, int value) {
- //Platform::DebugPrintf("InsertValue[%d] = %d\n", pos, value);
- if ((lines + 2) >= size) {
- if (growSize * 6 < size)
- growSize *= 2;
- Expand(size + growSize);
- if (levels) {
- ExpandLevels(size + growSize);
- }
- }
- lines++;
- for (int i = lines; i > pos; i--) {
- linesData[i] = linesData[i - 1];
- }
- linesData[pos].startPosition = value;
- linesData[pos].handleSet = 0;
- if (levels) {
- for (int j = lines; j > pos; j--) {
- levels[j] = levels[j - 1];
+ levels.DeleteAll();
+}
+
+int LineVector::SetLevel(int line, int level) {
+ int prev = 0;
+ if ((line >= 0) && (line < Lines())) {
+ if (!levels.Length()) {
+ ExpandLevels(Lines() + 1);
}
- if (pos == 0) {
- levels[pos] = SC_FOLDLEVELBASE;
- } else if (pos == (lines - 1)) { // Last line will not be a folder
- levels[pos] = SC_FOLDLEVELBASE;
- } else {
- levels[pos] = levels[pos - 1] & ~SC_FOLDLEVELWHITEFLAG;
+ prev = levels[line];
+ if (prev != level) {
+ levels[line] = level;
}
}
+ return prev;
}
-void LineVector::SetValue(int pos, int value) {
- //Platform::DebugPrintf("SetValue[%d] = %d\n", pos, value);
- if ((pos + 2) >= size) {
- //Platform::DebugPrintf("Resize %d %d\n", size,pos);
- Expand(pos + growSize);
- //Platform::DebugPrintf("end Resize %d %d\n", size,pos);
- lines = pos;
- if (levels) {
- ExpandLevels(pos + growSize);
+int LineVector::GetLevel(int line) {
+ if (levels.Length() && (line >= 0) && (line < Lines())) {
+ return levels[line];
+ } else {
+ return SC_FOLDLEVELBASE;
+ }
+}
+
+void LineVector::InsertText(int line, int delta) {
+ starts.InsertText(line, delta);
+}
+
+void LineVector::InsertLine(int line, int position) {
+ starts.InsertPartition(line, position);
+ if (markers.Length()) {
+ markers.Insert(line, 0);
+ }
+ if (levels.Length()) {
+ int level = SC_FOLDLEVELBASE;
+ if ((line > 0) && (line < Lines())) {
+ level = levels[line-1] & ~SC_FOLDLEVELWHITEFLAG;
}
+ levels.InsertValue(line, 1, level);
}
- linesData[pos].startPosition = value;
}
-void LineVector::Remove(int pos) {
- //Platform::DebugPrintf("Remove %d\n", pos);
+void LineVector::SetLineStart(int line, int position) {
+ starts.SetPartitionStartPosition(line, position);
+}
+
+void LineVector::RemoveLine(int line) {
+ starts.RemovePartition(line);
// Retain the markers from the deleted line by oring them into the previous line
- if (pos > 0) {
- MergeMarkers(pos - 1);
- }
- for (int i = pos; i < lines; i++) {
- linesData[i] = linesData[i + 1];
+ if (markers.Length()) {
+ if (line > 0) {
+ MergeMarkers(line - 1);
+ }
+ markers.Delete(line);
}
- if (levels) {
+ if (levels.Length()) {
// Move up following lines but merge header flag from this line
// to line before to avoid a temporary disappearence causing expansion.
- int firstHeader = levels[pos] & SC_FOLDLEVELHEADERFLAG;
- for (int j = pos; j < lines; j++) {
- levels[j] = levels[j + 1];
- }
- if (pos > 0)
- levels[pos-1] |= firstHeader;
+ int firstHeader = levels[line] & SC_FOLDLEVELHEADERFLAG;
+ levels.Delete(line);
+ if (line > 0)
+ levels[line-1] |= firstHeader;
}
- lines--;
}
int LineVector::LineFromPosition(int pos) {
- //Platform::DebugPrintf("LineFromPostion %d lines=%d end = %d\n", pos, lines, linesData[lines].startPosition);
- if (lines == 0)
+ return starts.PartitionFromPosition(pos);
+}
+
+int LineVector::MarkValue(int line) {
+ if (markers.Length() && markers.ValueAt(line))
+ return markers.ValueAt(line)->MarkValue();
+ else
return 0;
- //Platform::DebugPrintf("LineFromPosition %d\n", pos);
- if (pos >= linesData[lines].startPosition)
- return lines - 1;
- int lower = 0;
- int upper = lines;
- do {
- int middle = (upper + lower + 1) / 2; // Round high
- if (pos < linesData[middle].startPosition) {
- upper = middle - 1;
- } else {
- lower = middle;
- }
- } while (lower < upper);
- //Platform::DebugPrintf("LineFromPostion %d %d %d\n", pos, lower, linesData[lower].startPosition, linesData[lower > 1 ? lower - 1 : 0].startPosition);
- return lower;
}
int LineVector::AddMark(int line, int markerNum) {
handleCurrent++;
- if (!linesData[line].handleSet) {
+ if (!markers.Length()) {
+ // No existing markers so allocate one element per line
+ markers.InsertValue(0, Lines(), 0);
+ }
+ if (!markers[line]) {
// Need new structure to hold marker handle
- linesData[line].handleSet = new MarkerHandleSet;
- if (!linesData[line].handleSet)
+ markers[line] = new MarkerHandleSet();
+ if (!markers[line])
return - 1;
}
- linesData[line].handleSet->InsertHandle(handleCurrent, markerNum);
+ markers[line]->InsertHandle(handleCurrent, markerNum);
return handleCurrent;
}
void LineVector::MergeMarkers(int pos) {
- if (linesData[pos + 1].handleSet != NULL) {
- if (linesData[pos].handleSet == NULL )
- linesData[pos].handleSet = new MarkerHandleSet;
- linesData[pos].handleSet->CombineWith(linesData[pos + 1].handleSet);
- delete linesData[pos + 1].handleSet;
- linesData[pos + 1].handleSet = NULL;
+ if (markers[pos + 1] != NULL) {
+ if (markers[pos] == NULL)
+ markers[pos] = new MarkerHandleSet;
+ markers[pos]->CombineWith(markers[pos + 1]);
+ delete markers[pos + 1];
+ markers[pos + 1] = NULL;
}
}
void LineVector::DeleteMark(int line, int markerNum, bool all) {
- if (linesData[line].handleSet) {
+ if (markers.Length() && markers[line]) {
if (markerNum == -1) {
- delete linesData[line].handleSet;
- linesData[line].handleSet = 0;
+ delete markers[line];
+ markers[line] = NULL;
} else {
- bool performedDeletion =
- linesData[line].handleSet->RemoveNumber(markerNum);
+ bool performedDeletion = markers[line]->RemoveNumber(markerNum);
while (all && performedDeletion) {
- performedDeletion =
- linesData[line].handleSet->RemoveNumber(markerNum);
+ performedDeletion = markers[line]->RemoveNumber(markerNum);
}
- if (linesData[line].handleSet->Length() == 0) {
- delete linesData[line].handleSet;
- linesData[line].handleSet = 0;
+ if (markers[line]->Length() == 0) {
+ delete markers[line];
+ markers[line] = NULL;
}
}
}
@@ -333,23 +279,25 @@ void LineVector::DeleteMark(int line, int markerNum, bool all) {
void LineVector::DeleteMarkFromHandle(int markerHandle) {
int line = LineFromHandle(markerHandle);
if (line >= 0) {
- linesData[line].handleSet->RemoveHandle(markerHandle);
- if (linesData[line].handleSet->Length() == 0) {
- delete linesData[line].handleSet;
- linesData[line].handleSet = 0;
+ markers[line]->RemoveHandle(markerHandle);
+ if (markers[line]->Length() == 0) {
+ delete markers[line];
+ markers[line] = NULL;
}
}
}
int LineVector::LineFromHandle(int markerHandle) {
- for (int line = 0; line < lines; line++) {
- if (linesData[line].handleSet) {
- if (linesData[line].handleSet->Contains(markerHandle)) {
- return line;
+ if (markers.Length()) {
+ for (int line = 0; line < Lines(); line++) {
+ if (markers[line]) {
+ if (markers[line]->Contains(markerHandle)) {
+ return line;
+ }
}
}
}
- return - 1;
+ return -1;
}
Action::Action() {
@@ -437,7 +385,7 @@ void UndoHistory::EnsureUndoRoom() {
int lenActionsNew = lenActions * 2;
Action *actionsNew = new Action[lenActionsNew];
if (!actionsNew)
- return ;
+ return;
for (int act = 0; act <= currentAction; act++)
actionsNew[act].Grab(&actions[act]);
delete []actions;
@@ -488,7 +436,7 @@ void UndoHistory::AppendAction(actionType at, int position, char *data, int leng
currentAction++;
}
} else {
- //Platform::DebugPrintf("action coalesced\n");
+ // Action coalesced.
}
} else {
@@ -603,91 +551,12 @@ void UndoHistory::CompletedRedoStep() {
currentAction++;
}
-CellBuffer::CellBuffer(int initialLength) {
- body = new char[initialLength];
- size = initialLength;
- length = 0;
- part1len = 0;
- gaplen = initialLength;
- part2body = body + gaplen;
+CellBuffer::CellBuffer() {
readOnly = false;
collectingUndo = true;
- growSize = 4000;
}
CellBuffer::~CellBuffer() {
- delete []body;
- body = 0;
-}
-
-void CellBuffer::GapTo(int position) {
- if (position == part1len)
- return ;
- if (position < part1len) {
- int diff = part1len - position;
- //Platform::DebugPrintf("Move gap backwards to %d diff = %d part1len=%d length=%d \n", position,diff, part1len, length);
- for (int i = 0; i < diff; i++)
- body[part1len + gaplen - i - 1] = body[part1len - i - 1];
- } else { // position > part1len
- int diff = position - part1len;
- //Platform::DebugPrintf("Move gap forwards to %d diff =%d\n", position,diff);
- for (int i = 0; i < diff; i++)
- body[part1len + i] = body[part1len + gaplen + i];
- }
- part1len = position;
- part2body = body + gaplen;
-}
-
-void CellBuffer::RoomFor(int insertionLength) {
- //Platform::DebugPrintf("need room %d %d\n", gaplen, insertionLength);
- if (gaplen <= insertionLength) {
- //Platform::DebugPrintf("need room %d %d\n", gaplen, insertionLength);
- if (growSize * 6 < size)
- growSize *= 2;
- int newSize = size + insertionLength + growSize;
- Allocate(newSize);
- }
-}
-
-// To make it easier to write code that uses ByteAt, a position outside the range of the buffer
-// can be retrieved. All characters outside the range have the value '\0'.
-char CellBuffer::ByteAt(int position) {
- if (position < part1len) {
- if (position < 0) {
- return '\0';
- } else {
- return body[position];
- }
- } else {
- if (position >= length) {
- return '\0';
- } else {
- return part2body[position];
- }
- }
-}
-
-void CellBuffer::SetByteAt(int position, char ch) {
-
- if (position < 0) {
- //Platform::DebugPrintf("Bad position %d\n",position);
- return ;
- }
- if (position >= length + 11) {
- Platform::DebugPrintf("Very Bad position %d of %d\n", position, length);
- //exit(2);
- return ;
- }
- if (position >= length) {
- //Platform::DebugPrintf("Bad position %d of %d\n",position,length);
- return ;
- }
-
- if (position < part1len) {
- body[position] = ch;
- } else {
- part2body[position] = ch;
- }
}
char CellBuffer::CharAt(int position) {
@@ -696,20 +565,19 @@ char CellBuffer::CharAt(int position) {
void CellBuffer::GetCharRange(char *buffer, int position, int lengthRetrieve) {
if (lengthRetrieve < 0)
- return ;
+ return;
if (position < 0)
- return ;
+ return;
int bytePos = position * 2;
- if ((bytePos + lengthRetrieve * 2) > length) {
+ if ((bytePos + lengthRetrieve * 2) > body.Length()) {
Platform::DebugPrintf("Bad GetCharRange %d for %d of %d\n", bytePos,
- lengthRetrieve, length);
- return ;
+ lengthRetrieve, body.Length());
+ return;
}
- GapTo(0); // Move the buffer so its easy to subscript into it
- char *pb = part2body + bytePos;
+ int i = bytePos;
while (lengthRetrieve--) {
- *buffer++ = *pb;
- pb += 2;
+ *buffer++ = body.ValueAt(i);
+ i += 2;
}
}
@@ -740,7 +608,7 @@ bool CellBuffer::SetStyleAt(int position, char style, char mask) {
style &= mask;
char curVal = ByteAt(position * 2 + 1);
if ((curVal & mask) != style) {
- SetByteAt(position*2 + 1, static_cast<char>((curVal & ~mask) | style));
+ body.SetValueAt(position*2 + 1, static_cast<char>((curVal & ~mask) | style));
return true;
} else {
return false;
@@ -751,11 +619,11 @@ bool CellBuffer::SetStyleFor(int position, int lengthStyle, char style, char mas
int bytePos = position * 2 + 1;
bool changed = false;
PLATFORM_ASSERT(lengthStyle == 0 ||
- (lengthStyle > 0 && lengthStyle + position < length));
+ (lengthStyle > 0 && lengthStyle + position < body.Length()));
while (lengthStyle--) {
char curVal = ByteAt(bytePos);
if ((curVal & mask) != style) {
- SetByteAt(bytePos, static_cast<char>((curVal & ~mask) | style));
+ body.SetValueAt(bytePos, static_cast<char>((curVal & ~mask) | style));
changed = true;
}
bytePos += 2;
@@ -783,38 +651,29 @@ const char *CellBuffer::DeleteChars(int position, int deleteLength, bool &startS
}
int CellBuffer::ByteLength() {
- return length;
+ return body.Length();
}
int CellBuffer::Length() {
return ByteLength() / 2;
}
+
void CellBuffer::Allocate(int newSize) {
- if (newSize > length) {
- GapTo(length);
- char *newBody = new char[newSize];
- memcpy(newBody, body, length);
- delete []body;
- body = newBody;
- gaplen += newSize - size;
- part2body = body + gaplen;
- size = newSize;
- }
+ body.ReAllocate(newSize);
}
int CellBuffer::Lines() {
- //Platform::DebugPrintf("Lines = %d\n", lv.lines);
- return lv.lines;
+ return lv.Lines();
}
int CellBuffer::LineStart(int line) {
if (line < 0)
return 0;
- else if (line > lv.lines)
+ else if (line >= Lines())
return Length();
else
- return lv.linesData[line].startPosition;
+ return lv.LineStart(line);
}
bool CellBuffer::IsReadOnly() {
@@ -834,14 +693,14 @@ bool CellBuffer::IsSavePoint() {
}
int CellBuffer::AddMark(int line, int markerNum) {
- if ((line >= 0) && (line < lv.lines)) {
+ if ((line >= 0) && (line < Lines())) {
return lv.AddMark(line, markerNum);
}
return - 1;
}
void CellBuffer::DeleteMark(int line, int markerNum) {
- if ((line >= 0) && (line < lv.lines)) {
+ if ((line >= 0) && (line < Lines())) {
lv.DeleteMark(line, markerNum, false);
}
}
@@ -851,13 +710,13 @@ void CellBuffer::DeleteMarkFromHandle(int markerHandle) {
}
int CellBuffer::GetMark(int line) {
- if ((line >= 0) && (line < lv.lines) && (lv.linesData[line].handleSet))
- return lv.linesData[line].handleSet->MarkValue();
+ if ((line >= 0) && (line < Lines()))
+ return lv.MarkValue(line);
return 0;
}
void CellBuffer::DeleteAllMarks(int markerNum) {
- for (int line = 0; line < lv.lines; line++) {
+ for (int line = 0; line < Lines(); line++) {
lv.DeleteMark(line, markerNum, true);
}
}
@@ -869,51 +728,38 @@ int CellBuffer::LineFromHandle(int markerHandle) {
// Without undo
void CellBuffer::BasicInsertString(int position, char *s, int insertLength) {
- //Platform::DebugPrintf("Inserting at %d for %d\n", position, insertLength);
if (insertLength == 0)
- return ;
+ return;
PLATFORM_ASSERT(insertLength > 0);
- RoomFor(insertLength);
- GapTo(position);
- memcpy(body + part1len, s, insertLength);
- length += insertLength;
- part1len += insertLength;
- gaplen -= insertLength;
- part2body = body + gaplen;
+ body.InsertFromArray(position, s, 0, insertLength);
int lineInsert = lv.LineFromPosition(position / 2) + 1;
// Point all the lines after the insertion point further along in the buffer
- for (int lineAfter = lineInsert; lineAfter <= lv.lines; lineAfter++) {
- lv.linesData[lineAfter].startPosition += insertLength / 2;
- }
+ lv.InsertText(lineInsert-1, insertLength / 2);
char chPrev = ' ';
if ((position - 2) >= 0)
chPrev = ByteAt(position - 2);
char chAfter = ' ';
- if ((position + insertLength) < length)
+ if ((position + insertLength) < body.Length())
chAfter = ByteAt(position + insertLength);
if (chPrev == '\r' && chAfter == '\n') {
- //Platform::DebugPrintf("Splitting a crlf pair at %d\n", lineInsert);
// Splitting up a crlf pair at position
- lv.InsertValue(lineInsert, position / 2);
+ lv.InsertLine(lineInsert, position / 2);
lineInsert++;
}
char ch = ' ';
for (int i = 0; i < insertLength; i += 2) {
ch = s[i];
if (ch == '\r') {
- //Platform::DebugPrintf("Inserting cr at %d\n", lineInsert);
- lv.InsertValue(lineInsert, (position + i) / 2 + 1);
+ lv.InsertLine(lineInsert, (position + i) / 2 + 1);
lineInsert++;
} else if (ch == '\n') {
if (chPrev == '\r') {
- //Platform::DebugPrintf("Patching cr before lf at %d\n", lineInsert-1);
// Patch up what was end of line
- lv.SetValue(lineInsert - 1, (position + i) / 2 + 1);
+ lv.SetLineStart(lineInsert - 1, (position + i) / 2 + 1);
} else {
- //Platform::DebugPrintf("Inserting lf at %d\n", lineInsert);
- lv.InsertValue(lineInsert, (position + i) / 2 + 1);
+ lv.InsertLine(lineInsert, (position + i) / 2 + 1);
lineInsert++;
}
}
@@ -922,44 +768,37 @@ void CellBuffer::BasicInsertString(int position, char *s, int insertLength) {
// Joining two lines where last insertion is cr and following text starts with lf
if (chAfter == '\n') {
if (ch == '\r') {
- //Platform::DebugPrintf("Joining cr before lf at %d\n", lineInsert-1);
// End of line already in buffer so drop the newly created one
- lv.Remove(lineInsert - 1);
+ lv.RemoveLine(lineInsert - 1);
}
}
}
void CellBuffer::BasicDeleteChars(int position, int deleteLength) {
- //Platform::DebugPrintf("Deleting at %d for %d\n", position, deleteLength);
if (deleteLength == 0)
- return ;
+ return;
- if ((position == 0) && (deleteLength == length)) {
+ if ((position == 0) && (deleteLength == body.Length())) {
// If whole buffer is being deleted, faster to reinitialise lines data
// than to delete each line.
- //printf("Whole buffer being deleted\n");
lv.Init();
} else {
// Have to fix up line positions before doing deletion as looking at text in buffer
// to work out which lines have been removed
int lineRemove = lv.LineFromPosition(position / 2) + 1;
- // Point all the lines after the insertion point further along in the buffer
- for (int lineAfter = lineRemove; lineAfter <= lv.lines; lineAfter++) {
- lv.linesData[lineAfter].startPosition -= deleteLength / 2;
- }
+ lv.InsertText(lineRemove-1, - (deleteLength / 2));
char chPrev = ' ';
if (position >= 2)
chPrev = ByteAt(position - 2);
char chBefore = chPrev;
char chNext = ' ';
- if (position < length)
+ if (position < body.Length())
chNext = ByteAt(position);
bool ignoreNL = false;
if (chPrev == '\r' && chNext == '\n') {
- //Platform::DebugPrintf("Deleting lf after cr, move line end to cr at %d\n", lineRemove);
// Move back one
- lv.SetValue(lineRemove, position / 2);
+ lv.SetLineStart(lineRemove, position / 2);
lineRemove++;
ignoreNL = true; // First \n is not real deletion
}
@@ -967,20 +806,17 @@ void CellBuffer::BasicDeleteChars(int position, int deleteLength) {
char ch = chNext;
for (int i = 0; i < deleteLength; i += 2) {
chNext = ' ';
- if ((position + i + 2) < length)
+ if ((position + i + 2) < body.Length())
chNext = ByteAt(position + i + 2);
- //Platform::DebugPrintf("Deleting %d %x\n", i, ch);
if (ch == '\r') {
if (chNext != '\n') {
- //Platform::DebugPrintf("Removing cr end of line\n");
- lv.Remove(lineRemove);
+ lv.RemoveLine(lineRemove);
}
} else if (ch == '\n') {
if (ignoreNL) {
ignoreNL = false; // Further \n are real deletions
} else {
- //Platform::DebugPrintf("Removing lf end of line\n");
- lv.Remove(lineRemove);
+ lv.RemoveLine(lineRemove);
}
}
@@ -989,19 +825,15 @@ void CellBuffer::BasicDeleteChars(int position, int deleteLength) {
// May have to fix up end if last deletion causes cr to be next to lf
// or removes one of a crlf pair
char chAfter = ' ';
- if ((position + deleteLength) < length)
+ if ((position + deleteLength) < body.Length())
chAfter = ByteAt(position + deleteLength);
if (chBefore == '\r' && chAfter == '\n') {
- //d.printf("Joining cr before lf at %d\n", lineRemove);
// Using lineRemove-1 as cr ended line before start of deletion
- lv.Remove(lineRemove - 1);
- lv.SetValue(lineRemove - 1, position / 2 + 1);
+ lv.RemoveLine(lineRemove - 1);
+ lv.SetLineStart(lineRemove - 1, position / 2 + 1);
}
}
- GapTo(position);
- length -= deleteLength;
- gaplen += deleteLength;
- part2body = body + gaplen;
+ body.DeleteRange(position, deleteLength);
}
bool CellBuffer::SetUndoCollection(bool collectUndo) {
@@ -1097,25 +929,11 @@ int CellBuffer::GetMaxLineState() {
}
int CellBuffer::SetLevel(int line, int level) {
- int prev = 0;
- if ((line >= 0) && (line < lv.lines)) {
- if (!lv.levels) {
- lv.ExpandLevels();
- }
- prev = lv.levels[line];
- if (lv.levels[line] != level) {
- lv.levels[line] = level;
- }
- }
- return prev;
+ return lv.SetLevel(line, level);
}
int CellBuffer::GetLevel(int line) {
- if (lv.levels && (line >= 0) && (line < lv.lines)) {
- return lv.levels[line];
- } else {
- return SC_FOLDLEVELBASE;
- }
+ return lv.GetLevel(line);
}
void CellBuffer::ClearLevels() {
diff --git a/src/CellBuffer.h b/src/CellBuffer.h
index 92bbfa0da..7faeecd23 100644
--- a/src/CellBuffer.h
+++ b/src/CellBuffer.h
@@ -27,10 +27,10 @@ class MarkerHandleSet {
public:
MarkerHandleSet();
~MarkerHandleSet();
- int Length();
- int NumberFromHandle(int handle);
- int MarkValue(); ///< Bit set of marker numbers.
- bool Contains(int handle);
+ int Length() const;
+ int NumberFromHandle(int handle) const;
+ int MarkValue() const; ///< Bit set of marker numbers.
+ bool Contains(int handle) const;
bool InsertHandle(int handle, int markerNum);
void RemoveHandle(int handle);
bool RemoveNumber(int markerNum);
@@ -38,43 +38,40 @@ public:
};
/**
- * Each line stores the starting position of the first character of the line in the cell buffer
- * and potentially a marker handle set. Often a line will not have any attached markers.
- */
-struct LineData {
- int startPosition;
- MarkerHandleSet *handleSet;
- LineData() : startPosition(0), handleSet(0) {
- }
-};
-
-/**
* The line vector contains information about each of the lines in a cell buffer.
*/
class LineVector {
-public:
- int growSize;
- int lines;
- LineData *linesData;
- int size;
- int *levels;
- int sizeLevels;
+ Partitioning starts;
+ SplitVector<MarkerHandleSet *> markers;
+ SplitVector<int> levels;
/// Handles are allocated sequentially and should never have to be reused as 32 bit ints are very big.
int handleCurrent;
+public:
+
LineVector();
~LineVector();
void Init();
- void Expand(int sizeNew);
void ExpandLevels(int sizeNew=-1);
void ClearLevels();
- void InsertValue(int pos, int value);
- void SetValue(int pos, int value);
- void Remove(int pos);
+ int SetLevel(int line, int level);
+ int GetLevel(int line);
+
+ void InsertText(int line, int delta);
+ void InsertLine(int line, int position);
+ void SetLineStart(int line, int position);
+ void RemoveLine(int line);
+ int Lines() {
+ return starts.Partitions();
+ }
int LineFromPosition(int pos);
+ int LineStart(int line) {
+ return starts.PositionFromPartition(line);
+ }
+ int MarkValue(int line);
int AddMark(int line, int marker);
void MergeMarkers(int pos);
void DeleteMark(int line, int markerNum, bool all);
@@ -150,16 +147,8 @@ public:
*/
class CellBuffer {
private:
- char *body; ///< The cell buffer itself.
- int size; ///< Allocated size of the buffer.
- int length; ///< Total length of the data.
- int part1len; ///< Length of the first part.
- int gaplen; ///< Length of the gap between the two parts.
- char *part2body; ///< The second part of the cell buffer.
- ///< Doesn't point after the gap but set so that
- ///< part2body[position] is consistent with body[position].
+ SplitVector<char> body;
bool readOnly;
- int growSize;
bool collectingUndo;
UndoHistory uh;
@@ -168,15 +157,13 @@ private:
SVector lineStates;
- void GapTo(int position);
- void RoomFor(int insertionLength);
-
- inline char ByteAt(int position);
- void SetByteAt(int position, char ch);
+ char ByteAt(int position) {
+ return body.ValueAt(position);
+ }
public:
- CellBuffer(int initialLength = 4000);
+ CellBuffer();
~CellBuffer();
/// Retrieving positions outside the range of the buffer works and returns 0
diff --git a/src/Document.cxx b/src/Document.cxx
index e530b0423..2e21cfe7b 100644
--- a/src/Document.cxx
+++ b/src/Document.cxx
@@ -14,6 +14,8 @@
#include "Scintilla.h"
#include "SVector.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
#include "CellBuffer.h"
#include "CharClassify.h"
#include "Document.h"
@@ -858,7 +860,7 @@ int Document::ExtendWordSelect(int pos, int delta, bool onlyWordCharacters) {
while (pos > 0 && (WordCharClass(cb.CharAt(pos - 1)) == ccStart))
pos--;
} else {
- if (!onlyWordCharacters)
+ if (!onlyWordCharacters && pos < Length())
ccStart = WordCharClass(cb.CharAt(pos));
while (pos < (Length()) && (WordCharClass(cb.CharAt(pos)) == ccStart))
pos++;
diff --git a/src/DocumentAccessor.cxx b/src/DocumentAccessor.cxx
index c695c5f51..f3c36db32 100644
--- a/src/DocumentAccessor.cxx
+++ b/src/DocumentAccessor.cxx
@@ -16,6 +16,8 @@
#include "SVector.h"
#include "Accessor.h"
#include "DocumentAccessor.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
#include "CellBuffer.h"
#include "Scintilla.h"
#include "CharClassify.h"
diff --git a/src/Editor.cxx b/src/Editor.cxx
index b2d29da13..b0bd99e83 100644
--- a/src/Editor.cxx
+++ b/src/Editor.cxx
@@ -19,6 +19,8 @@
#include "ContractionState.h"
#include "SVector.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
#include "CellBuffer.h"
#include "KeyMap.h"
#include "Indicator.h"
@@ -1915,6 +1917,7 @@ static bool IsSpaceOrTab(char ch) {
LineLayout *Editor::RetrieveLineLayout(int lineNumber) {
int posLineStart = pdoc->LineStart(lineNumber);
int posLineEnd = pdoc->LineStart(lineNumber + 1);
+ PLATFORM_ASSERT(posLineEnd >= posLineStart);
int lineCaret = pdoc->LineFromPosition(currentPos);
return llc.Retrieve(lineNumber, lineCaret,
posLineEnd - posLineStart, pdoc->GetStyleClock(),
@@ -1930,6 +1933,7 @@ void Editor::LayoutLine(int line, Surface *surface, ViewStyle &vstyle, LineLayou
if (!ll)
return;
PLATFORM_ASSERT(line < pdoc->LinesTotal());
+ PLATFORM_ASSERT(ll->chars != NULL);
int posLineStart = pdoc->LineStart(line);
int posLineEnd = pdoc->LineStart(line + 1);
// If the line is very long, limit the treatment to a length that should fit in the viewport
diff --git a/src/Partitioning.h b/src/Partitioning.h
new file mode 100644
index 000000000..e30189d75
--- /dev/null
+++ b/src/Partitioning.h
@@ -0,0 +1,184 @@
+// Scintilla source code edit control
+/** @file Partitioning.h
+ ** Data structure used to partition an interval. Used for holding line start/end positions.
+ **/
+// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
+// The License.txt file describes the conditions under which this software may be distributed.
+
+#ifndef PARTITIONING_H
+#define PARTITIONING_H
+
+/// A split vector of integers with a method for adding a value to all elements
+/// in a range.
+/// Used by the Partitioning class.
+
+class SplitVectorWithRangeAdd : public SplitVector<int> {
+public:
+ SplitVectorWithRangeAdd(int growSize_) {
+ SetGrowSize(growSize_);
+ ReAllocate(growSize_);
+ }
+ ~SplitVectorWithRangeAdd() {
+ }
+ void RangeAddDelta(int start, int end, int delta) {
+ // end is 1 past end, so end-start is number of elements to change
+ int i = 0;
+ int rangeLength = end - start;
+ int range1Length = rangeLength;
+ int part1Left = part1Length - start;
+ if (range1Length > part1Left)
+ range1Length = part1Left;
+ while (i < range1Length) {
+ body[start++] += delta;
+ i++;
+ }
+ start += gapLength;
+ while (i < rangeLength) {
+ body[start++] += delta;
+ i++;
+ }
+ }
+};
+
+/// Divide an interval into multiple partitions.
+/// Useful for breaking a document down into sections such as lines.
+
+class Partitioning {
+private:
+ // To avoid calculating all the partition positions whenever any text is inserted
+ // there may be a step somewhere in the list.
+ int stepPartition;
+ int stepLength;
+ SplitVectorWithRangeAdd *body;
+
+ // Move step forward
+ void ApplyStep(int partitionUpTo) {
+ if (stepLength != 0) {
+ body->RangeAddDelta(stepPartition+1, partitionUpTo + 1, stepLength);
+ }
+ stepPartition = partitionUpTo;
+ if (stepPartition >= body->Length()-1) {
+ stepPartition = body->Length()-1;
+ stepLength = 0;
+ }
+ }
+
+ // Move step backward
+ void BackStep(int partitionDownTo) {
+ if (stepLength != 0) {
+ body->RangeAddDelta(partitionDownTo+1, stepPartition+1, -stepLength);
+ }
+ stepPartition = partitionDownTo;
+ }
+
+ void Allocate(int growSize) {
+ body = new SplitVectorWithRangeAdd(growSize);
+ stepPartition = 0;
+ stepLength = 0;
+ body->Insert(0, 0); // This value stays 0 for ever
+ body->Insert(1, 0); // This is the end of the first partition and will be the start of the second
+ }
+
+public:
+ Partitioning(int growSize) {
+ Allocate(growSize);
+ }
+
+ ~Partitioning() {
+ delete body;
+ body = NULL;
+ }
+
+ int Partitions() {
+ return body->Length()-1;
+ }
+
+ void InsertPartition(int partition, int pos) {
+ if (stepPartition < partition) {
+ ApplyStep(partition);
+ }
+ body->Insert(partition, pos);
+ stepPartition++;
+ }
+
+ void SetPartitionStartPosition(int partition, int pos) {
+ ApplyStep(partition+1);
+ if ((partition < 0) || (partition > body->Length())) {
+ return;
+ }
+ body->SetValueAt(partition, pos);
+ }
+
+ void InsertText(int partitionInsert, int delta) {
+ // Point all the partitions after the insertion point further along in the buffer
+ if (stepLength != 0) {
+ if (partitionInsert >= stepPartition) {
+ // Fill in up to the new insertion point
+ ApplyStep(partitionInsert);
+ stepLength += delta;
+ } else if (partitionInsert >= (stepPartition - body->Length() / 10)) {
+ // Close to step but before so move step back
+ BackStep(partitionInsert);
+ stepLength += delta;
+ } else {
+ ApplyStep(body->Length()-1);
+ stepPartition = partitionInsert;
+ stepLength = delta;
+ }
+ } else {
+ stepPartition = partitionInsert;
+ stepLength = delta;
+ }
+ }
+
+ void RemovePartition(int partition) {
+ if (partition > stepPartition) {
+ ApplyStep(partition);
+ stepPartition--;
+ } else {
+ stepPartition--;
+ }
+ body->Delete(partition);
+ }
+
+ int PositionFromPartition(int partition) {
+ PLATFORM_ASSERT(partition >= 0);
+ PLATFORM_ASSERT(partition < body->Length());
+ if ((partition < 0) || (partition >= body->Length())) {
+ return 0;
+ }
+ int pos = body->ValueAt(partition);
+ if (partition > stepPartition)
+ pos += stepLength;
+ return pos;
+ }
+
+ int PartitionFromPosition(int pos) {
+ if (body->Length() <= 1)
+ return 0;
+ if (pos >= (PositionFromPartition(body->Length()-1)))
+ return body->Length() - 1 - 1;
+ int lower = 0;
+ int upper = body->Length()-1;
+ do {
+ int middle = (upper + lower + 1) / 2; // Round high
+ int posMiddle = body->ValueAt(middle);
+ if (middle > stepPartition)
+ posMiddle += stepLength;
+ if (pos < posMiddle) {
+ upper = middle - 1;
+ } else {
+ lower = middle;
+ }
+ } while (lower < upper);
+ return lower;
+ }
+
+ void DeleteAll() {
+ int growSize = body->GetGrowSize();
+ delete body;
+ Allocate(growSize);
+ }
+};
+
+#endif
diff --git a/src/ScintillaBase.cxx b/src/ScintillaBase.cxx
index bcb0a77e2..e43411261 100644
--- a/src/ScintillaBase.cxx
+++ b/src/ScintillaBase.cxx
@@ -22,6 +22,8 @@
#endif
#include "ContractionState.h"
#include "SVector.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
#include "CellBuffer.h"
#include "CallTip.h"
#include "KeyMap.h"
diff --git a/src/SplitVector.h b/src/SplitVector.h
new file mode 100644
index 000000000..2847108fa
--- /dev/null
+++ b/src/SplitVector.h
@@ -0,0 +1,221 @@
+// 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
+
+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) {
+ if (growSize * 6 < size)
+ growSize *= 2;
+ ReAllocate(size + insertionLength + growSize);
+ }
+ }
+
+public:
+ /// Construct a split buffer.
+ SplitVector() {
+ body = NULL;
+ growSize = 8;
+ size = 0;
+ lengthBody = 0;
+ part1Length = 0;
+ gapLength = 0;
+ }
+
+ ~SplitVector() {
+ delete []body;
+ body = NULL;
+ }
+
+ void Create(int initialLength_, int growSize_);
+
+ 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 != NULL)) {
+ 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.
+ 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) {
+ if (insertLength > 0) {
+ RoomFor(insertLength);
+ GapTo(position);
+ for (int i = 0; i < insertLength; i++)
+ body[part1Length + i] = v;
+ lengthBody += insertLength;
+ part1Length += insertLength;
+ gapLength -= insertLength;
+ }
+ }
+
+ /// Insert text into the buffer from an array.
+ void InsertFromArray(int positionToInsert, T s[], int positionFrom, int insertLength) {
+ 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) {
+ 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 (deleteLength > 0) {
+ GapTo(position);
+ lengthBody -= deleteLength;
+ gapLength += deleteLength;
+ }
+ }
+
+ /// Delete all the buffer contents.
+ void DeleteAll() {
+ DeleteRange(0, lengthBody);
+ }
+
+};
+
+#endif