+// 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 "SplitVector.h"
+#include "Partitioning.h"
+#include "RunStyles.h"
+#include "ContractionState.h"
+#include "CellBuffer.h"
+#include "KeyMap.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"
+
+#ifdef SCI_NAMESPACE
+using namespace Scintilla;
+#endif
+
+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];
+ }
+}
+
+bool LineLayout::InLine(int offset, int line) const {
+ return ((offset >= LineStart(line)) && (offset < LineStart(line + 1)) ||
+ ((offset == numCharsInLine) && (line == (lines-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) {
+ // Expand if needed
+ if (saeLen >= saeSize) {
+ saeSize *= 2;
+ int *selAndEdgeNew = new int[saeSize];
+ for (unsigned int j = 0; j<saeLen; j++) {
+ selAndEdgeNew[j] = selAndEdge[j];
+ }
+ delete []selAndEdge;
+ selAndEdge = selAndEdgeNew;
+ }
+
+ 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; k>j; k--) {
+ selAndEdge[k] = selAndEdge[k-1];
+ }
+ saeLen++;
+ selAndEdge[j] = val;
+ return;
+ }
+ }
+ // Not less than any so append
+ selAndEdge[saeLen++] = val;
+ }
+}
+
+extern bool BadUTF(const char *s, int len, int &trailBytes);
+
+static int NextBadU(const char *s, int p, int len, int &trailBytes) {
+ while (p < len) {
+ p++;
+ if (BadUTF(s + p, len - p, trailBytes))
+ return p;
+ }
+ return -1;
+}
+
+BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_, bool utf8_, int xStart) :
+ ll(ll_),
+ lineStart(lineStart_),
+ lineEnd(lineEnd_),
+ posLineStart(posLineStart_),
+ utf8(utf8_),
+ nextBreak(lineStart_),
+ saeSize(0),
+ saeLen(0),
+ saeCurrentPos(0),
+ saeNext(0),
+ subBreak(-1) {
+ saeSize = 8;
+ selAndEdge = new int[saeSize];
+ for (unsigned int j=0; j < saeSize; 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);
+
+ if (utf8) {
+ int trailBytes=0;
+ for (int pos = -1;;) {
+ pos = NextBadU(ll->chars, pos, lineEnd, trailBytes);
+ if (pos < 0)
+ break;
+ Insert(pos-1);
+ Insert(pos);
+ }
+ }
+ saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
+}
+
+BreakFinder::~BreakFinder() {
+ delete []selAndEdge;
+}
+
+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);
+ }
+}
projects / wxWidgets.git / commitdiff
