Addition of PositionCache module which adds cacing of string

to position information and segments long pieces of text so they
can be handled more efficiently.

1 files changed, 586 insertions, 0 deletions

diff --git a/src/PositionCache.cxx b/src/PositionCache.cxx
new file mode 100644
index 000000000..01b8f68f1
--- /dev/null
+++ b/src/PositionCache.cxx
@@ -0,0 +1,586 @@
+// Scintilla source code edit control
+/** @file PositionCache.cxx
+ ** Classes for caching layout information.
+ **/
+// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
+// The License.txt file describes the conditions under which this software may be distributed.
+
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <ctype.h>
+
+#include "Platform.h"
+
+#include "Scintilla.h"
+
+#include "ContractionState.h"
+#include "SVector.h"
+#include "SplitVector.h"
+#include "Partitioning.h"
+#include "CellBuffer.h"
+#include "KeyMap.h"
+#include "RunStyles.h"
+#include "Indicator.h"
+#include "XPM.h"
+#include "LineMarker.h"
+#include "Style.h"
+#include "ViewStyle.h"
+#include "CharClassify.h"
+#include "Decoration.h"
+#include "Document.h"
+#include "PositionCache.h"
+
+static inline bool IsControlCharacter(int ch) {
+	// iscntrl returns true for lots of chars > 127 which are displayable
+	return ch >= 0 && ch < ' ';
+}
+
+LineLayout::LineLayout(int maxLineLength_) :
+	lineStarts(0),
+	lenLineStarts(0),
+	lineNumber(-1),
+	inCache(false),
+	maxLineLength(-1),
+	numCharsInLine(0),
+	validity(llInvalid),
+	xHighlightGuide(0),
+	highlightColumn(0),
+	selStart(0),
+	selEnd(0),
+	containsCaret(false),
+	edgeColumn(0),
+	chars(0),
+	styles(0),
+	styleBitsSet(0),
+	indicators(0),
+	positions(0),
+	hsStart(0),
+	hsEnd(0),
+	widthLine(wrapWidthInfinite),
+	lines(1) {
+	Resize(maxLineLength_);
+}
+
+LineLayout::~LineLayout() {
+	Free();
+}
+
+void LineLayout::Resize(int maxLineLength_) {
+	if (maxLineLength_ > maxLineLength) {
+		Free();
+		chars = new char[maxLineLength_ + 1];
+		styles = new unsigned char[maxLineLength_ + 1];
+		indicators = new char[maxLineLength_ + 1];
+		// Extra position allocated as sometimes the Windows
+		// GetTextExtentExPoint API writes an extra element.
+		positions = new int[maxLineLength_ + 1 + 1];
+		maxLineLength = maxLineLength_;
+	}
+}
+
+void LineLayout::Free() {
+	delete []chars;
+	chars = 0;
+	delete []styles;
+	styles = 0;
+	delete []indicators;
+	indicators = 0;
+	delete []positions;
+	positions = 0;
+	delete []lineStarts;
+	lineStarts = 0;
+}
+
+void LineLayout::Invalidate(validLevel validity_) {
+	if (validity > validity_)
+		validity = validity_;
+}
+
+int LineLayout::LineStart(int line) const {
+	if (line <= 0) {
+		return 0;
+	} else if ((line >= lines) || !lineStarts) {
+		return numCharsInLine;
+	} else {
+		return lineStarts[line];
+	}
+}
+
+int LineLayout::LineLastVisible(int line) const {
+	if (line < 0) {
+		return 0;
+	} else if ((line >= lines-1) || !lineStarts) {
+		int startLine = LineStart(line);
+		int endLine = numCharsInLine;
+		while ((endLine > startLine) && IsEOLChar(chars[endLine-1])) {
+			endLine--;
+		}
+		return endLine;
+	} else {
+		return lineStarts[line+1];
+	}
+}
+
+void LineLayout::SetLineStart(int line, int start) {
+	if ((line >= lenLineStarts) && (line != 0)) {
+		int newMaxLines = line + 20;
+		int *newLineStarts = new int[newMaxLines];
+		if (!newLineStarts)
+			return;
+		for (int i = 0; i < newMaxLines; i++) {
+			if (i < lenLineStarts)
+				newLineStarts[i] = lineStarts[i];
+			else
+				newLineStarts[i] = 0;
+		}
+		delete []lineStarts;
+		lineStarts = newLineStarts;
+		lenLineStarts = newMaxLines;
+	}
+	lineStarts[line] = start;
+}
+
+void LineLayout::SetBracesHighlight(Range rangeLine, Position braces[],
+                                    char bracesMatchStyle, int xHighlight) {
+	if (rangeLine.ContainsCharacter(braces[0])) {
+		int braceOffset = braces[0] - rangeLine.start;
+		if (braceOffset < numCharsInLine) {
+			bracePreviousStyles[0] = styles[braceOffset];
+			styles[braceOffset] = bracesMatchStyle;
+		}
+	}
+	if (rangeLine.ContainsCharacter(braces[1])) {
+		int braceOffset = braces[1] - rangeLine.start;
+		if (braceOffset < numCharsInLine) {
+			bracePreviousStyles[1] = styles[braceOffset];
+			styles[braceOffset] = bracesMatchStyle;
+		}
+	}
+	if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
+	        (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
+		xHighlightGuide = xHighlight;
+	}
+}
+
+void LineLayout::RestoreBracesHighlight(Range rangeLine, Position braces[]) {
+	if (rangeLine.ContainsCharacter(braces[0])) {
+		int braceOffset = braces[0] - rangeLine.start;
+		if (braceOffset < numCharsInLine) {
+			styles[braceOffset] = bracePreviousStyles[0];
+		}
+	}
+	if (rangeLine.ContainsCharacter(braces[1])) {
+		int braceOffset = braces[1] - rangeLine.start;
+		if (braceOffset < numCharsInLine) {
+			styles[braceOffset] = bracePreviousStyles[1];
+		}
+	}
+	xHighlightGuide = 0;
+}
+
+int LineLayout::FindBefore(int x, int lower, int upper) const {
+	do {
+		int middle = (upper + lower + 1) / 2; 	// Round high
+		int posMiddle = positions[middle];
+		if (x < posMiddle) {
+			upper = middle - 1;
+		} else {
+			lower = middle;
+		}
+	} while (lower < upper);
+	return lower;
+}
+
+LineLayoutCache::LineLayoutCache() :
+	level(0), length(0), size(0), cache(0),
+	allInvalidated(false), styleClock(-1), useCount(0) {
+	Allocate(0);
+}
+
+LineLayoutCache::~LineLayoutCache() {
+	Deallocate();
+}
+
+void LineLayoutCache::Allocate(int length_) {
+	PLATFORM_ASSERT(cache == NULL);
+	allInvalidated = false;
+	length = length_;
+	size = length;
+	if (size > 1) {
+		size = (size / 16 + 1) * 16;
+	}
+	if (size > 0) {
+		cache = new LineLayout * [size];
+	}
+	for (int i = 0; i < size; i++)
+		cache[i] = 0;
+}
+
+void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
+	PLATFORM_ASSERT(useCount == 0);
+	int lengthForLevel = 0;
+	if (level == llcCaret) {
+		lengthForLevel = 1;
+	} else if (level == llcPage) {
+		lengthForLevel = linesOnScreen + 1;
+	} else if (level == llcDocument) {
+		lengthForLevel = linesInDoc;
+	}
+	if (lengthForLevel > size) {
+		Deallocate();
+		Allocate(lengthForLevel);
+	} else {
+		if (lengthForLevel < length) {
+			for (int i = lengthForLevel; i < length; i++) {
+				delete cache[i];
+				cache[i] = 0;
+			}
+		}
+		length = lengthForLevel;
+	}
+	PLATFORM_ASSERT(length == lengthForLevel);
+	PLATFORM_ASSERT(cache != NULL || length == 0);
+}
+
+void LineLayoutCache::Deallocate() {
+	PLATFORM_ASSERT(useCount == 0);
+	for (int i = 0; i < length; i++)
+		delete cache[i];
+	delete []cache;
+	cache = 0;
+	length = 0;
+	size = 0;
+}
+
+void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
+	if (cache && !allInvalidated) {
+		for (int i = 0; i < length; i++) {
+			if (cache[i]) {
+				cache[i]->Invalidate(validity_);
+			}
+		}
+		if (validity_ == LineLayout::llInvalid) {
+			allInvalidated = true;
+		}
+	}
+}
+
+void LineLayoutCache::SetLevel(int level_) {
+	allInvalidated = false;
+	if ((level_ != -1) && (level != level_)) {
+		level = level_;
+		Deallocate();
+	}
+}
+
+LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
+                                      int linesOnScreen, int linesInDoc) {
+	AllocateForLevel(linesOnScreen, linesInDoc);
+	if (styleClock != styleClock_) {
+		Invalidate(LineLayout::llCheckTextAndStyle);
+		styleClock = styleClock_;
+	}
+	allInvalidated = false;
+	int pos = -1;
+	LineLayout *ret = 0;
+	if (level == llcCaret) {
+		pos = 0;
+	} else if (level == llcPage) {
+		if (lineNumber == lineCaret) {
+			pos = 0;
+		} else if (length > 1) {
+			pos = 1 + (lineNumber % (length - 1));
+		}
+	} else if (level == llcDocument) {
+		pos = lineNumber;
+	}
+	if (pos >= 0) {
+		PLATFORM_ASSERT(useCount == 0);
+		if (cache && (pos < length)) {
+			if (cache[pos]) {
+				if ((cache[pos]->lineNumber != lineNumber) ||
+				        (cache[pos]->maxLineLength < maxChars)) {
+					delete cache[pos];
+					cache[pos] = 0;
+				}
+			}
+			if (!cache[pos]) {
+				cache[pos] = new LineLayout(maxChars);
+			}
+			if (cache[pos]) {
+				cache[pos]->lineNumber = lineNumber;
+				cache[pos]->inCache = true;
+				ret = cache[pos];
+				useCount++;
+			}
+		}
+	}
+
+	if (!ret) {
+		ret = new LineLayout(maxChars);
+		ret->lineNumber = lineNumber;
+	}
+
+	return ret;
+}
+
+void LineLayoutCache::Dispose(LineLayout *ll) {
+	allInvalidated = false;
+	if (ll) {
+		if (!ll->inCache) {
+			delete ll;
+		} else {
+			useCount--;
+		}
+	}
+}
+
+void BreakFinder::Insert(int val) {
+	if (val > nextBreak) {
+		for (unsigned int j = 0; j<saeLen; j++) {
+			if (val == selAndEdge[j]) {
+				return;
+			} if (val < selAndEdge[j]) {
+				for (unsigned int k = saeLen; j>k; k--) {
+					selAndEdge[k] = selAndEdge[k-1];
+				}
+				saeLen++;
+				selAndEdge[j] = val;
+				return;
+			}
+		}
+		// Not less than any so append
+		selAndEdge[saeLen++] = val;
+	}
+}
+
+BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_, int xStart) :
+	ll(ll_),
+	lineStart(lineStart_),
+	lineEnd(lineEnd_),
+	posLineStart(posLineStart_),
+	nextBreak(lineStart_),
+	saeLen(0),
+	saeCurrentPos(0),
+	saeNext(0),
+	subBreak(-1) {
+	for (unsigned int j=0; j < sizeof(selAndEdge) / sizeof(selAndEdge[0]); j++) {
+		selAndEdge[j] = 0;
+	}
+
+	// Search for first visible break
+	// First find the first visible character
+	nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
+	// Now back to a style break
+	while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
+		nextBreak--;
+	}
+
+	if (ll->selStart != ll->selEnd) {
+		Insert(ll->selStart - posLineStart - 1);
+		Insert(ll->selEnd - posLineStart - 1);
+	}
+
+	Insert(ll->edgeColumn - 1);
+	Insert(lineEnd - 1);
+	saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
+}
+
+int BreakFinder::First() {
+	return nextBreak;
+}
+
+int BreakFinder::Next() {
+	if (subBreak == -1) {
+		int prev = nextBreak;
+		while (nextBreak < lineEnd) {
+			if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
+					(nextBreak == saeNext) ||
+					IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
+				if (nextBreak == saeNext) {
+					saeCurrentPos++;
+					saeNext = (saeLen > saeCurrentPos) ? selAndEdge[saeCurrentPos] : -1;
+				}
+				nextBreak++;
+				if ((nextBreak - prev) < lengthStartSubdivision) {
+					return nextBreak;
+				}
+				break;
+			}
+			nextBreak++;
+		}
+		if ((nextBreak - prev) < lengthStartSubdivision) {
+			return nextBreak;
+		}
+		subBreak = prev;
+	}
+	// Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
+	// For very long runs add extra breaks after spaces or if no spaces before low punctuation.
+	if ((nextBreak - subBreak) <= lengthEachSubdivision) {
+		subBreak = -1;
+		return nextBreak;
+	} else {
+		int lastGoodBreak = -1;
+		int lastOKBreak = -1;
+		int j;
+		for (j = subBreak + 1; j <= nextBreak; j++) {
+			if (IsSpaceOrTab(ll->chars[j - 1]) && !IsSpaceOrTab(ll->chars[j])) {
+				lastGoodBreak = j;
+			}
+			if (ll->chars[j] < 'A') {
+				lastOKBreak = j;
+			}
+			if (((j - subBreak) >= lengthEachSubdivision) && ((lastGoodBreak >= 0) || (lastOKBreak >= 0))) {
+				break;
+			}
+		}
+		if (lastGoodBreak >= 0) {
+			subBreak = lastGoodBreak;
+		} else if (lastOKBreak >= 0) {
+			subBreak = lastOKBreak;
+		} else {
+			subBreak = nextBreak;
+		}
+		if (subBreak >= nextBreak) {
+			subBreak = -1;
+			return nextBreak;
+		} else {
+			return subBreak;
+		}
+	}
+}
+
+PositionCacheEntry::PositionCacheEntry() :
+	styleNumber(0), len(0), clock(0), positions(0) {
+}
+
+void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
+	unsigned int len_, int *positions_, unsigned int clock_) {
+	Clear();
+	styleNumber = styleNumber_;
+	len = len_;
+	clock = clock_;
+	if (s_ && positions_) {
+		positions = new short[len + (len + 1) / 2];
+		for (unsigned int i=0;i<len;i++) {
+			positions[i] = static_cast<short>(positions_[i]);
+		}
+		memcpy(reinterpret_cast<char *>(positions + len), s_, len);
+	}
+}
+
+PositionCacheEntry::~PositionCacheEntry() {
+	Clear();
+}
+
+void PositionCacheEntry::Clear() {
+	delete []positions;
+	positions = 0;
+	styleNumber = 0;
+	len = 0;
+	clock = 0;
+}
+
+bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
+	unsigned int len_, int *positions_) const {
+	if ((styleNumber == styleNumber_) && (len == len_) &&
+		(memcmp(reinterpret_cast<char *>(positions + len), s_, len)== 0)) {
+		for (unsigned int i=0;i<len;i++) {
+			positions_[i] = positions[i];
+		}
+		return true;
+	} else {
+		return false;
+	}
+}
+
+int PositionCacheEntry::Hash(unsigned int styleNumber, const char *s, unsigned int len) {
+	unsigned int ret = s[0] << 7;
+	for (unsigned int i=0; i<len; i++) {
+		ret *= 1000003;
+		ret ^= s[i];
+	}
+	ret *= 1000003;
+	ret ^= len;
+	ret *= 1000003;
+	ret ^= styleNumber;
+	return ret;
+}
+
+bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) {
+	return clock > other.clock;
+}
+
+void PositionCacheEntry::ResetClock() {
+	if (clock > 0) {
+		clock = 1;
+	}
+}
+
+PositionCache::PositionCache() {
+	size = 0x400;
+	clock = 1;
+	pces = new PositionCacheEntry[size];
+	allClear = true;
+}
+
+PositionCache::~PositionCache() {
+	Clear();
+	delete []pces;
+}
+
+void PositionCache::Clear() {
+	if (!allClear) {
+		for (size_t i=0;i<size;i++) {
+			pces[i].Clear();
+		}
+	}
+	clock = 1;
+	allClear = true;
+}
+
+void PositionCache::SetSize(size_t size_) {
+	Clear();
+	delete []pces;
+	size = size_;
+	pces = new PositionCacheEntry[size];
+}
+
+void PositionCache::MeasureWidths(Surface *surface, ViewStyle &vstyle, unsigned int styleNumber,
+	const char *s, unsigned int len, int *positions) {
+	allClear = false;
+	int probe = -1;
+	if ((size > 0) && (len < 30)) {
+		// Only store short strings in the cache so it doesn't churn with
+		// long comments with only a single comment.
+
+		// Two way associative: try two probe positions.
+		int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
+		probe = hashValue % size;
+		if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
+			return;
+		}
+		int probe2 = (hashValue * 37) % size;
+		if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
+			return;
+		}
+		// Not found. Choose the oldest of the two slots to replace
+		if (pces[probe].NewerThan(pces[probe2])) {
+			probe = probe2;
+		}
+	}
+	surface->MeasureWidths(vstyle.styles[styleNumber].font, s, len, positions);
+	if (probe >= 0) {
+		clock++;
+		if (clock > 60000) {
+			// Since there are only 16 bits for the clock, wrap it round and
+			// reset all cache entries so none get stuck with a high clock.
+			for (size_t i=0;i<size;i++) {
+				pces[i].ResetClock();
+			}
+			clock = 2;
+		}
+		pces[probe].Set(styleNumber, s, len, positions, clock);
+	}
+}