1
// Scintilla source code edit control
2
/** @file PositionCache.cxx
3
** Classes for caching layout information.
5
// Copyright 1998-2007 by Neil Hodgson <neilh@scintilla.org>
6
// The License.txt file describes the conditions under which this software may be distributed.
18
#include "Scintilla.h"
20
#include "SplitVector.h"
21
#include "Partitioning.h"
22
#include "RunStyles.h"
23
#include "ContractionState.h"
24
#include "CellBuffer.h"
26
#include "Indicator.h"
28
#include "LineMarker.h"
30
#include "ViewStyle.h"
31
#include "CharClassify.h"
32
#include "Decoration.h"
34
#include "Selection.h"
35
#include "PositionCache.h"
38
using namespace Scintilla;
41
static inline bool IsControlCharacter(int ch) {
42
// iscntrl returns true for lots of chars > 127 which are displayable
43
return ch >= 0 && ch < ' ';
46
LineLayout::LineLayout(int maxLineLength_) :
67
widthLine(wrapWidthInfinite),
70
Resize(maxLineLength_);
73
LineLayout::~LineLayout() {
77
void LineLayout::Resize(int maxLineLength_) {
78
if (maxLineLength_ > maxLineLength) {
80
chars = new char[maxLineLength_ + 1];
81
styles = new unsigned char[maxLineLength_ + 1];
82
indicators = new char[maxLineLength_ + 1];
83
// Extra position allocated as sometimes the Windows
84
// GetTextExtentExPoint API writes an extra element.
85
positions = new int[maxLineLength_ + 1 + 1];
86
maxLineLength = maxLineLength_;
90
void LineLayout::Free() {
103
void LineLayout::Invalidate(validLevel validity_) {
104
if (validity > validity_)
105
validity = validity_;
108
int LineLayout::LineStart(int line) const {
111
} else if ((line >= lines) || !lineStarts) {
112
return numCharsInLine;
114
return lineStarts[line];
118
int LineLayout::LineLastVisible(int line) const {
121
} else if ((line >= lines-1) || !lineStarts) {
122
return numCharsBeforeEOL;
124
return lineStarts[line+1];
128
bool LineLayout::InLine(int offset, int line) const {
129
return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
130
((offset == numCharsInLine) && (line == (lines-1)));
133
void LineLayout::SetLineStart(int line, int start) {
134
if ((line >= lenLineStarts) && (line != 0)) {
135
int newMaxLines = line + 20;
136
int *newLineStarts = new int[newMaxLines];
137
for (int i = 0; i < newMaxLines; i++) {
138
if (i < lenLineStarts)
139
newLineStarts[i] = lineStarts[i];
141
newLineStarts[i] = 0;
144
lineStarts = newLineStarts;
145
lenLineStarts = newMaxLines;
147
lineStarts[line] = start;
150
void LineLayout::SetBracesHighlight(Range rangeLine, Position braces[],
151
char bracesMatchStyle, int xHighlight) {
152
if (rangeLine.ContainsCharacter(braces[0])) {
153
int braceOffset = braces[0] - rangeLine.start;
154
if (braceOffset < numCharsInLine) {
155
bracePreviousStyles[0] = styles[braceOffset];
156
styles[braceOffset] = bracesMatchStyle;
159
if (rangeLine.ContainsCharacter(braces[1])) {
160
int braceOffset = braces[1] - rangeLine.start;
161
if (braceOffset < numCharsInLine) {
162
bracePreviousStyles[1] = styles[braceOffset];
163
styles[braceOffset] = bracesMatchStyle;
166
if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
167
(braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
168
xHighlightGuide = xHighlight;
172
void LineLayout::RestoreBracesHighlight(Range rangeLine, Position braces[]) {
173
if (rangeLine.ContainsCharacter(braces[0])) {
174
int braceOffset = braces[0] - rangeLine.start;
175
if (braceOffset < numCharsInLine) {
176
styles[braceOffset] = bracePreviousStyles[0];
179
if (rangeLine.ContainsCharacter(braces[1])) {
180
int braceOffset = braces[1] - rangeLine.start;
181
if (braceOffset < numCharsInLine) {
182
styles[braceOffset] = bracePreviousStyles[1];
188
int LineLayout::FindBefore(int x, int lower, int upper) const {
190
int middle = (upper + lower + 1) / 2; // Round high
191
int posMiddle = positions[middle];
197
} while (lower < upper);
201
int LineLayout::EndLineStyle() const {
202
return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0];
205
LineLayoutCache::LineLayoutCache() :
206
level(0), length(0), size(0), cache(0),
207
allInvalidated(false), styleClock(-1), useCount(0) {
211
LineLayoutCache::~LineLayoutCache() {
215
void LineLayoutCache::Allocate(int length_) {
216
PLATFORM_ASSERT(cache == NULL);
217
allInvalidated = false;
221
size = (size / 16 + 1) * 16;
224
cache = new LineLayout * [size];
226
for (int i = 0; i < size; i++)
230
void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
231
PLATFORM_ASSERT(useCount == 0);
232
int lengthForLevel = 0;
233
if (level == llcCaret) {
235
} else if (level == llcPage) {
236
lengthForLevel = linesOnScreen + 1;
237
} else if (level == llcDocument) {
238
lengthForLevel = linesInDoc;
240
if (lengthForLevel > size) {
242
Allocate(lengthForLevel);
244
if (lengthForLevel < length) {
245
for (int i = lengthForLevel; i < length; i++) {
250
length = lengthForLevel;
252
PLATFORM_ASSERT(length == lengthForLevel);
253
PLATFORM_ASSERT(cache != NULL || length == 0);
256
void LineLayoutCache::Deallocate() {
257
PLATFORM_ASSERT(useCount == 0);
258
for (int i = 0; i < length; i++)
266
void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
267
if (cache && !allInvalidated) {
268
for (int i = 0; i < length; i++) {
270
cache[i]->Invalidate(validity_);
273
if (validity_ == LineLayout::llInvalid) {
274
allInvalidated = true;
279
void LineLayoutCache::SetLevel(int level_) {
280
allInvalidated = false;
281
if ((level_ != -1) && (level != level_)) {
287
LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
288
int linesOnScreen, int linesInDoc) {
289
AllocateForLevel(linesOnScreen, linesInDoc);
290
if (styleClock != styleClock_) {
291
Invalidate(LineLayout::llCheckTextAndStyle);
292
styleClock = styleClock_;
294
allInvalidated = false;
297
if (level == llcCaret) {
299
} else if (level == llcPage) {
300
if (lineNumber == lineCaret) {
302
} else if (length > 1) {
303
pos = 1 + (lineNumber % (length - 1));
305
} else if (level == llcDocument) {
309
PLATFORM_ASSERT(useCount == 0);
310
if (cache && (pos < length)) {
312
if ((cache[pos]->lineNumber != lineNumber) ||
313
(cache[pos]->maxLineLength < maxChars)) {
319
cache[pos] = new LineLayout(maxChars);
322
cache[pos]->lineNumber = lineNumber;
323
cache[pos]->inCache = true;
331
ret = new LineLayout(maxChars);
332
ret->lineNumber = lineNumber;
338
void LineLayoutCache::Dispose(LineLayout *ll) {
339
allInvalidated = false;
349
void BreakFinder::Insert(int val) {
351
if (saeLen >= saeSize) {
353
int *selAndEdgeNew = new int[saeSize];
354
for (unsigned int j = 0; j<saeLen; j++) {
355
selAndEdgeNew[j] = selAndEdge[j];
358
selAndEdge = selAndEdgeNew;
361
if (val >= nextBreak) {
362
for (unsigned int j = 0; j<saeLen; j++) {
363
if (val == selAndEdge[j]) {
366
if (val < selAndEdge[j]) {
367
for (unsigned int k = saeLen; k>j; k--) {
368
selAndEdge[k] = selAndEdge[k-1];
375
// Not less than any so append
376
selAndEdge[saeLen++] = val;
380
extern bool BadUTF(const char *s, int len, int &trailBytes);
382
static int NextBadU(const char *s, int p, int len, int &trailBytes) {
385
if (BadUTF(s + p, len - p, trailBytes))
391
BreakFinder::BreakFinder(LineLayout *ll_, int lineStart_, int lineEnd_, int posLineStart_, bool utf8_, int xStart, bool breakForSelection) :
393
lineStart(lineStart_),
395
posLineStart(posLineStart_),
397
nextBreak(lineStart_),
404
selAndEdge = new int[saeSize];
405
for (unsigned int j=0; j < saeSize; j++) {
409
// Search for first visible break
410
// First find the first visible character
411
nextBreak = ll->FindBefore(xStart, lineStart, lineEnd);
412
// Now back to a style break
413
while ((nextBreak > lineStart) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
417
if (breakForSelection) {
418
SelectionPosition posStart(posLineStart);
419
SelectionPosition posEnd(posLineStart + lineEnd);
420
SelectionSegment segmentLine(posStart, posEnd);
421
for (size_t r=0; r<ll->psel->Count(); r++) {
422
SelectionSegment portion = ll->psel->Range(r).Intersect(segmentLine);
423
if (!(portion.start == portion.end)) {
424
if (portion.start.IsValid())
425
Insert(portion.start.Position() - posLineStart - 1);
426
if (portion.end.IsValid())
427
Insert(portion.end.Position() - posLineStart - 1);
432
Insert(ll->edgeColumn - 1);
437
for (int pos = -1;;) {
438
pos = NextBadU(ll->chars, pos, lineEnd, trailBytes);
445
saeNext = (saeLen > 0) ? selAndEdge[0] : -1;
448
BreakFinder::~BreakFinder() {
452
int BreakFinder::First() const {
456
static bool IsTrailByte(int ch) {
457
return (ch >= 0x80) && (ch < (0x80 + 0x40));
460
int BreakFinder::Next() {
461
if (subBreak == -1) {
462
int prev = nextBreak;
463
while (nextBreak < lineEnd) {
464
if ((ll->styles[nextBreak] != ll->styles[nextBreak + 1]) ||
465
(nextBreak == saeNext) ||
466
IsControlCharacter(ll->chars[nextBreak]) || IsControlCharacter(ll->chars[nextBreak + 1])) {
467
if (nextBreak == saeNext) {
469
saeNext = (saeLen > saeCurrentPos) ? selAndEdge[saeCurrentPos] : -1;
472
if ((nextBreak - prev) < lengthStartSubdivision) {
479
if ((nextBreak - prev) < lengthStartSubdivision) {
484
// Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
485
// For very long runs add extra breaks after spaces or if no spaces before low punctuation.
486
if ((nextBreak - subBreak) <= lengthEachSubdivision) {
490
int lastGoodBreak = -1;
491
int lastOKBreak = -1;
492
int lastUTF8Break = -1;
494
for (j = subBreak + 1; j <= nextBreak; j++) {
495
if (IsSpaceOrTab(ll->chars[j - 1]) && !IsSpaceOrTab(ll->chars[j])) {
498
if (static_cast<unsigned char>(ll->chars[j]) < 'A') {
501
if (utf8 && !IsTrailByte(static_cast<unsigned char>(ll->chars[j]))) {
504
if (((j - subBreak) >= lengthEachSubdivision) &&
505
((lastGoodBreak >= 0) || (lastOKBreak >= 0) || (lastUTF8Break >= 0))) {
509
if (lastGoodBreak >= 0) {
510
subBreak = lastGoodBreak;
511
} else if (lastOKBreak >= 0) {
512
subBreak = lastOKBreak;
513
} else if (lastUTF8Break >= 0) {
514
subBreak = lastUTF8Break;
516
subBreak = nextBreak;
518
if (subBreak >= nextBreak) {
527
PositionCacheEntry::PositionCacheEntry() :
528
styleNumber(0), len(0), clock(0), positions(0) {
531
void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
532
unsigned int len_, int *positions_, unsigned int clock_) {
534
styleNumber = styleNumber_;
537
if (s_ && positions_) {
538
positions = new short[len + (len + 1) / 2];
539
for (unsigned int i=0; i<len; i++) {
540
positions[i] = static_cast<short>(positions_[i]);
542
memcpy(reinterpret_cast<char *>(positions + len), s_, len);
546
PositionCacheEntry::~PositionCacheEntry() {
550
void PositionCacheEntry::Clear() {
558
bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
559
unsigned int len_, int *positions_) const {
560
if ((styleNumber == styleNumber_) && (len == len_) &&
561
(memcmp(reinterpret_cast<char *>(positions + len), s_, len)== 0)) {
562
for (unsigned int i=0; i<len; i++) {
563
positions_[i] = positions[i];
571
int PositionCacheEntry::Hash(unsigned int styleNumber, const char *s, unsigned int len) {
572
unsigned int ret = s[0] << 7;
573
for (unsigned int i=0; i<len; i++) {
584
bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const {
585
return clock > other.clock;
588
void PositionCacheEntry::ResetClock() {
594
PositionCache::PositionCache() {
597
pces = new PositionCacheEntry[size];
601
PositionCache::~PositionCache() {
606
void PositionCache::Clear() {
608
for (size_t i=0; i<size; i++) {
616
void PositionCache::SetSize(size_t size_) {
620
pces = new PositionCacheEntry[size];
623
void PositionCache::MeasureWidths(Surface *surface, ViewStyle &vstyle, unsigned int styleNumber,
624
const char *s, unsigned int len, int *positions) {
627
if ((size > 0) && (len < 30)) {
628
// Only store short strings in the cache so it doesn't churn with
629
// long comments with only a single comment.
631
// Two way associative: try two probe positions.
632
int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
633
probe = hashValue % size;
634
if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
637
int probe2 = (hashValue * 37) % size;
638
if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
641
// Not found. Choose the oldest of the two slots to replace
642
if (pces[probe].NewerThan(pces[probe2])) {
646
surface->MeasureWidths(vstyle.styles[styleNumber].font, s, len, positions);
650
// Since there are only 16 bits for the clock, wrap it round and
651
// reset all cache entries so none get stuck with a high clock.
652
for (size_t i=0; i<size; i++) {
653
pces[i].ResetClock();
657
pces[probe].Set(styleNumber, s, len, positions, clock);
added
removed
scintilla/PositionCache.cxx
