ext/scintilla/src/PositionCache.cxx

   1 // Scintilla source code edit control
   2 /** @file PositionCache.cxx
   3  ** Classes for caching layout information.
   4  **/
   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.
   7
   8 #include <stdlib.h>
   9 #include <string.h>
  10 #include <stdio.h>
  11 #include <ctype.h>
  12
  13 #include <stdexcept>
  14 #include <string>
  15 #include <vector>
  16 #include <map>
  17 #include <algorithm>
  18 #include <memory>
  19
  20 #include "Platform.h"
  21
  22 #include "ILexer.h"
  23 #include "Scintilla.h"
  24
  25 #include "Position.h"
  26 #include "SplitVector.h"
  27 #include "Partitioning.h"
  28 #include "RunStyles.h"
  29 #include "ContractionState.h"
  30 #include "CellBuffer.h"
  31 #include "KeyMap.h"
  32 #include "Indicator.h"
  33 #include "XPM.h"
  34 #include "LineMarker.h"
  35 #include "Style.h"
  36 #include "ViewStyle.h"
  37 #include "CharClassify.h"
  38 #include "Decoration.h"
  39 #include "CaseFolder.h"
  40 #include "Document.h"
  41 #include "UniConversion.h"
  42 #include "Selection.h"
  43 #include "PositionCache.h"
  44
  45 #ifdef SCI_NAMESPACE
  46 using namespace Scintilla;
  47 #endif
  48
  49 LineLayout::LineLayout(int maxLineLength_) :
  50         lineStarts(0),
  51         lenLineStarts(0),
  52         lineNumber(-1),
  53         inCache(false),
  54         maxLineLength(-1),
  55         numCharsInLine(0),
  56         numCharsBeforeEOL(0),
  57         validity(llInvalid),
  58         xHighlightGuide(0),
  59         highlightColumn(0),
  60         containsCaret(false),
  61         edgeColumn(0),
  62         chars(0),
  63         styles(0),
  64         positions(0),
  65         hotspot(0,0),
  66         widthLine(wrapWidthInfinite),
  67         lines(1),
  68         wrapIndent(0) {
  69         bracePreviousStyles[0] = 0;
  70         bracePreviousStyles[1] = 0;
  71         Resize(maxLineLength_);
  72 }
  73
  74 LineLayout::~LineLayout() {
  75         Free();
  76 }
  77
  78 void LineLayout::Resize(int maxLineLength_) {
  79         if (maxLineLength_ > maxLineLength) {
  80                 Free();
  81                 chars = new char[maxLineLength_ + 1];
  82                 styles = new unsigned char[maxLineLength_ + 1];
  83                 // Extra position allocated as sometimes the Windows
  84                 // GetTextExtentExPoint API writes an extra element.
  85                 positions = new XYPOSITION[maxLineLength_ + 1 + 1];
  86                 maxLineLength = maxLineLength_;
  87         }
  88 }
  89
  90 void LineLayout::Free() {
  91         delete []chars;
  92         chars = 0;
  93         delete []styles;
  94         styles = 0;
  95         delete []positions;
  96         positions = 0;
  97         delete []lineStarts;
  98         lineStarts = 0;
  99 }
 100
 101 void LineLayout::Invalidate(validLevel validity_) {
 102         if (validity > validity_)
 103                 validity = validity_;
 104 }
 105
 106 int LineLayout::LineStart(int line) const {
 107         if (line <= 0) {
 108                 return 0;
 109         } else if ((line >= lines) || !lineStarts) {
 110                 return numCharsInLine;
 111         } else {
 112                 return lineStarts[line];
 113         }
 114 }
 115
 116 int LineLayout::LineLastVisible(int line) const {
 117         if (line < 0) {
 118                 return 0;
 119         } else if ((line >= lines-1) || !lineStarts) {
 120                 return numCharsBeforeEOL;
 121         } else {
 122                 return lineStarts[line+1];
 123         }
 124 }
 125
 126 Range LineLayout::SubLineRange(int subLine) const {
 127         return Range(LineStart(subLine), LineLastVisible(subLine));
 128 }
 129
 130 bool LineLayout::InLine(int offset, int line) const {
 131         return ((offset >= LineStart(line)) && (offset < LineStart(line + 1))) ||
 132                 ((offset == numCharsInLine) && (line == (lines-1)));
 133 }
 134
 135 void LineLayout::SetLineStart(int line, int start) {
 136         if ((line >= lenLineStarts) && (line != 0)) {
 137                 int newMaxLines = line + 20;
 138                 int *newLineStarts = new int[newMaxLines];
 139                 for (int i = 0; i < newMaxLines; i++) {
 140                         if (i < lenLineStarts)
 141                                 newLineStarts[i] = lineStarts[i];
 142                         else
 143                                 newLineStarts[i] = 0;
 144                 }
 145                 delete []lineStarts;
 146                 lineStarts = newLineStarts;
 147                 lenLineStarts = newMaxLines;
 148         }
 149         lineStarts[line] = start;
 150 }
 151
 152 void LineLayout::SetBracesHighlight(Range rangeLine, const Position braces[],
 153                                     char bracesMatchStyle, int xHighlight, bool ignoreStyle) {
 154         if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
 155                 int braceOffset = braces[0] - rangeLine.start;
 156                 if (braceOffset < numCharsInLine) {
 157                         bracePreviousStyles[0] = styles[braceOffset];
 158                         styles[braceOffset] = bracesMatchStyle;
 159                 }
 160         }
 161         if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
 162                 int braceOffset = braces[1] - rangeLine.start;
 163                 if (braceOffset < numCharsInLine) {
 164                         bracePreviousStyles[1] = styles[braceOffset];
 165                         styles[braceOffset] = bracesMatchStyle;
 166                 }
 167         }
 168         if ((braces[0] >= rangeLine.start && braces[1] <= rangeLine.end) ||
 169                 (braces[1] >= rangeLine.start && braces[0] <= rangeLine.end)) {
 170                 xHighlightGuide = xHighlight;
 171         }
 172 }
 173
 174 void LineLayout::RestoreBracesHighlight(Range rangeLine, const Position braces[], bool ignoreStyle) {
 175         if (!ignoreStyle && rangeLine.ContainsCharacter(braces[0])) {
 176                 int braceOffset = braces[0] - rangeLine.start;
 177                 if (braceOffset < numCharsInLine) {
 178                         styles[braceOffset] = bracePreviousStyles[0];
 179                 }
 180         }
 181         if (!ignoreStyle && rangeLine.ContainsCharacter(braces[1])) {
 182                 int braceOffset = braces[1] - rangeLine.start;
 183                 if (braceOffset < numCharsInLine) {
 184                         styles[braceOffset] = bracePreviousStyles[1];
 185                 }
 186         }
 187         xHighlightGuide = 0;
 188 }
 189
 190 int LineLayout::FindBefore(XYPOSITION x, int lower, int upper) const {
 191         do {
 192                 int middle = (upper + lower + 1) / 2;   // Round high
 193                 XYPOSITION posMiddle = positions[middle];
 194                 if (x < posMiddle) {
 195                         upper = middle - 1;
 196                 } else {
 197                         lower = middle;
 198                 }
 199         } while (lower < upper);
 200         return lower;
 201 }
 202
 203
 204 int LineLayout::FindPositionFromX(XYPOSITION x, Range range, bool charPosition) const {
 205         int pos = FindBefore(x, range.start, range.end);
 206         while (pos < range.end) {
 207                 if (charPosition) {
 208                         if (x < (positions[pos + 1])) {
 209                                 return pos;
 210                         }
 211                 } else {
 212                         if (x < ((positions[pos] + positions[pos + 1]) / 2)) {
 213                                 return pos;
 214                         }
 215                 }
 216                 pos++;
 217         }
 218         return range.end;
 219 }
 220
 221 Point LineLayout::PointFromPosition(int posInLine, int lineHeight, PointEnd pe) const {
 222         Point pt;
 223         // In case of very long line put x at arbitrary large position
 224         if (posInLine > maxLineLength) {
 225                 pt.x = positions[maxLineLength] - positions[LineStart(lines)];
 226         }
 227
 228         for (int subLine = 0; subLine < lines; subLine++) {
 229                 const Range rangeSubLine = SubLineRange(subLine);
 230                 if (posInLine >= rangeSubLine.start) {
 231                         pt.y = static_cast<XYPOSITION>(subLine*lineHeight);
 232                         if (posInLine <= rangeSubLine.end) {
 233                                 pt.x = positions[posInLine] - positions[rangeSubLine.start];
 234                                 if (rangeSubLine.start != 0)    // Wrapped lines may be indented
 235                                         pt.x += wrapIndent;
 236                                 if (pe & peSubLineEnd)  // Return end of first subline not start of next
 237                                         break;
 238                         } else if ((pe & peLineEnd) && (subLine == (lines-1))) {
 239                                 pt.x = positions[numCharsInLine] - positions[rangeSubLine.start];
 240                                 if (rangeSubLine.start != 0)    // Wrapped lines may be indented
 241                                         pt.x += wrapIndent;
 242                         }
 243                 } else {
 244                         break;
 245                 }
 246         }
 247         return pt;
 248 }
 249
 250 int LineLayout::EndLineStyle() const {
 251         return styles[numCharsBeforeEOL > 0 ? numCharsBeforeEOL-1 : 0];
 252 }
 253
 254 LineLayoutCache::LineLayoutCache() :
 255         level(0),
 256         allInvalidated(false), styleClock(-1), useCount(0) {
 257         Allocate(0);
 258 }
 259
 260 LineLayoutCache::~LineLayoutCache() {
 261         Deallocate();
 262 }
 263
 264 void LineLayoutCache::Allocate(size_t length_) {
 265         PLATFORM_ASSERT(cache.empty());
 266         allInvalidated = false;
 267         cache.resize(length_);
 268 }
 269
 270 void LineLayoutCache::AllocateForLevel(int linesOnScreen, int linesInDoc) {
 271         PLATFORM_ASSERT(useCount == 0);
 272         size_t lengthForLevel = 0;
 273         if (level == llcCaret) {
 274                 lengthForLevel = 1;
 275         } else if (level == llcPage) {
 276                 lengthForLevel = linesOnScreen + 1;
 277         } else if (level == llcDocument) {
 278                 lengthForLevel = linesInDoc;
 279         }
 280         if (lengthForLevel > cache.size()) {
 281                 Deallocate();
 282                 Allocate(lengthForLevel);
 283         } else {
 284                 if (lengthForLevel < cache.size()) {
 285                         for (size_t i = lengthForLevel; i < cache.size(); i++) {
 286                                 delete cache[i];
 287                                 cache[i] = 0;
 288                         }
 289                 }
 290                 cache.resize(lengthForLevel);
 291         }
 292         PLATFORM_ASSERT(cache.size() == lengthForLevel);
 293 }
 294
 295 void LineLayoutCache::Deallocate() {
 296         PLATFORM_ASSERT(useCount == 0);
 297         for (size_t i = 0; i < cache.size(); i++)
 298                 delete cache[i];
 299         cache.clear();
 300 }
 301
 302 void LineLayoutCache::Invalidate(LineLayout::validLevel validity_) {
 303         if (!cache.empty() && !allInvalidated) {
 304                 for (size_t i = 0; i < cache.size(); i++) {
 305                         if (cache[i]) {
 306                                 cache[i]->Invalidate(validity_);
 307                         }
 308                 }
 309                 if (validity_ == LineLayout::llInvalid) {
 310                         allInvalidated = true;
 311                 }
 312         }
 313 }
 314
 315 void LineLayoutCache::SetLevel(int level_) {
 316         allInvalidated = false;
 317         if ((level_ != -1) && (level != level_)) {
 318                 level = level_;
 319                 Deallocate();
 320         }
 321 }
 322
 323 LineLayout *LineLayoutCache::Retrieve(int lineNumber, int lineCaret, int maxChars, int styleClock_,
 324                                       int linesOnScreen, int linesInDoc) {
 325         AllocateForLevel(linesOnScreen, linesInDoc);
 326         if (styleClock != styleClock_) {
 327                 Invalidate(LineLayout::llCheckTextAndStyle);
 328                 styleClock = styleClock_;
 329         }
 330         allInvalidated = false;
 331         int pos = -1;
 332         LineLayout *ret = 0;
 333         if (level == llcCaret) {
 334                 pos = 0;
 335         } else if (level == llcPage) {
 336                 if (lineNumber == lineCaret) {
 337                         pos = 0;
 338                 } else if (cache.size() > 1) {
 339                         pos = 1 + (lineNumber % (cache.size() - 1));
 340                 }
 341         } else if (level == llcDocument) {
 342                 pos = lineNumber;
 343         }
 344         if (pos >= 0) {
 345                 PLATFORM_ASSERT(useCount == 0);
 346                 if (!cache.empty() && (pos < static_cast<int>(cache.size()))) {
 347                         if (cache[pos]) {
 348                                 if ((cache[pos]->lineNumber != lineNumber) ||
 349                                         (cache[pos]->maxLineLength < maxChars)) {
 350                                         delete cache[pos];
 351                                         cache[pos] = 0;
 352                                 }
 353                         }
 354                         if (!cache[pos]) {
 355                                 cache[pos] = new LineLayout(maxChars);
 356                         }
 357                         cache[pos]->lineNumber = lineNumber;
 358                         cache[pos]->inCache = true;
 359                         ret = cache[pos];
 360                         useCount++;
 361                 }
 362         }
 363
 364         if (!ret) {
 365                 ret = new LineLayout(maxChars);
 366                 ret->lineNumber = lineNumber;
 367         }
 368
 369         return ret;
 370 }
 371
 372 void LineLayoutCache::Dispose(LineLayout *ll) {
 373         allInvalidated = false;
 374         if (ll) {
 375                 if (!ll->inCache) {
 376                         delete ll;
 377                 } else {
 378                         useCount--;
 379                 }
 380         }
 381 }
 382
 383 // Simply pack the (maximum 4) character bytes into an int
 384 static inline int KeyFromString(const char *charBytes, size_t len) {
 385         PLATFORM_ASSERT(len <= 4);
 386         int k=0;
 387         for (size_t i=0; i<len && charBytes[i]; i++) {
 388                 k = k * 0x100;
 389                 k += static_cast<unsigned char>(charBytes[i]);
 390         }
 391         return k;
 392 }
 393
 394 SpecialRepresentations::SpecialRepresentations() {
 395         std::fill(startByteHasReprs, startByteHasReprs+0x100, static_cast<short>(0));
 396 }
 397
 398 void SpecialRepresentations::SetRepresentation(const char *charBytes, const char *value) {
 399         MapRepresentation::iterator it = mapReprs.find(KeyFromString(charBytes, UTF8MaxBytes));
 400         if (it == mapReprs.end()) {
 401                 // New entry so increment for first byte
 402                 startByteHasReprs[static_cast<unsigned char>(charBytes[0])]++;
 403         }
 404         mapReprs[KeyFromString(charBytes, UTF8MaxBytes)] = Representation(value);
 405 }
 406
 407 void SpecialRepresentations::ClearRepresentation(const char *charBytes) {
 408         MapRepresentation::iterator it = mapReprs.find(KeyFromString(charBytes, UTF8MaxBytes));
 409         if (it != mapReprs.end()) {
 410                 mapReprs.erase(it);
 411                 startByteHasReprs[static_cast<unsigned char>(charBytes[0])]--;
 412         }
 413 }
 414
 415 const Representation *SpecialRepresentations::RepresentationFromCharacter(const char *charBytes, size_t len) const {
 416         PLATFORM_ASSERT(len <= 4);
 417         if (!startByteHasReprs[static_cast<unsigned char>(charBytes[0])])
 418                 return 0;
 419         MapRepresentation::const_iterator it = mapReprs.find(KeyFromString(charBytes, len));
 420         if (it != mapReprs.end()) {
 421                 return &(it->second);
 422         }
 423         return 0;
 424 }
 425
 426 bool SpecialRepresentations::Contains(const char *charBytes, size_t len) const {
 427         PLATFORM_ASSERT(len <= 4);
 428         if (!startByteHasReprs[static_cast<unsigned char>(charBytes[0])])
 429                 return false;
 430         MapRepresentation::const_iterator it = mapReprs.find(KeyFromString(charBytes, len));
 431         return it != mapReprs.end();
 432 }
 433
 434 void SpecialRepresentations::Clear() {
 435         mapReprs.clear();
 436         std::fill(startByteHasReprs, startByteHasReprs+0x100, static_cast<short>(0));
 437 }
 438
 439 void BreakFinder::Insert(int val) {
 440         if (val > nextBreak) {
 441                 const std::vector<int>::iterator it = std::lower_bound(selAndEdge.begin(), selAndEdge.end(), val);
 442                 if (it == selAndEdge.end()) {
 443                         selAndEdge.push_back(val);
 444                 } else if (*it != val) {
 445                         selAndEdge.insert(it, 1, val);
 446                 }
 447         }
 448 }
 449
 450 BreakFinder::BreakFinder(const LineLayout *ll_, const Selection *psel, Range lineRange_, int posLineStart_,
 451         int xStart, bool breakForSelection, const Document *pdoc_, const SpecialRepresentations *preprs_, const ViewStyle *pvsDraw) :
 452         ll(ll_),
 453         lineRange(lineRange_),
 454         posLineStart(posLineStart_),
 455         nextBreak(lineRange_.start),
 456         saeCurrentPos(0),
 457         saeNext(0),
 458         subBreak(-1),
 459         pdoc(pdoc_),
 460         encodingFamily(pdoc_->CodePageFamily()),
 461         preprs(preprs_) {
 462
 463         // Search for first visible break
 464         // First find the first visible character
 465         if (xStart > 0.0f)
 466                 nextBreak = ll->FindBefore(static_cast<XYPOSITION>(xStart), lineRange.start, lineRange.end);
 467         // Now back to a style break
 468         while ((nextBreak > lineRange.start) && (ll->styles[nextBreak] == ll->styles[nextBreak - 1])) {
 469                 nextBreak--;
 470         }
 471
 472         if (breakForSelection) {
 473                 SelectionPosition posStart(posLineStart);
 474                 SelectionPosition posEnd(posLineStart + lineRange.end);
 475                 SelectionSegment segmentLine(posStart, posEnd);
 476                 for (size_t r=0; r<psel->Count(); r++) {
 477                         SelectionSegment portion = psel->Range(r).Intersect(segmentLine);
 478                         if (!(portion.start == portion.end)) {
 479                                 if (portion.start.IsValid())
 480                                         Insert(portion.start.Position() - posLineStart);
 481                                 if (portion.end.IsValid())
 482                                         Insert(portion.end.Position() - posLineStart);
 483                         }
 484                 }
 485         }
 486         if (pvsDraw && pvsDraw->indicatorsSetFore > 0) {
 487                 for (Decoration *deco = pdoc->decorations.root; deco; deco = deco->next) {
 488                         if (pvsDraw->indicators[deco->indicator].OverridesTextFore()) {
 489                                 int startPos = deco->rs.EndRun(posLineStart);
 490                                 while (startPos < (posLineStart + lineRange.end)) {
 491                                         Insert(startPos - posLineStart);
 492                                         startPos = deco->rs.EndRun(startPos);
 493                                 }
 494                         }
 495                 }
 496         }
 497         Insert(ll->edgeColumn);
 498         Insert(lineRange.end);
 499         saeNext = (!selAndEdge.empty()) ? selAndEdge[0] : -1;
 500 }
 501
 502 BreakFinder::~BreakFinder() {
 503 }
 504
 505 TextSegment BreakFinder::Next() {
 506         if (subBreak == -1) {
 507                 int prev = nextBreak;
 508                 while (nextBreak < lineRange.end) {
 509                         int charWidth = 1;
 510                         if (encodingFamily == efUnicode)
 511                                 charWidth = UTF8DrawBytes(reinterpret_cast<unsigned char *>(ll->chars) + nextBreak, lineRange.end - nextBreak);
 512                         else if (encodingFamily == efDBCS)
 513                                 charWidth = pdoc->IsDBCSLeadByte(ll->chars[nextBreak]) ? 2 : 1;
 514                         const Representation *repr = preprs->RepresentationFromCharacter(ll->chars + nextBreak, charWidth);
 515                         if (((nextBreak > 0) && (ll->styles[nextBreak] != ll->styles[nextBreak - 1])) ||
 516                                         repr ||
 517                                         (nextBreak == saeNext)) {
 518                                 while ((nextBreak >= saeNext) && (saeNext < lineRange.end)) {
 519                                         saeCurrentPos++;
 520                                         saeNext = (saeCurrentPos < selAndEdge.size()) ? selAndEdge[saeCurrentPos] : lineRange.end;
 521                                 }
 522                                 if ((nextBreak > prev) || repr) {
 523                                         // Have a segment to report
 524                                         if (nextBreak == prev) {
 525                                                 nextBreak += charWidth;
 526                                         } else {
 527                                                 repr = 0;       // Optimize -> should remember repr
 528                                         }
 529                                         if ((nextBreak - prev) < lengthStartSubdivision) {
 530                                                 return TextSegment(prev, nextBreak - prev, repr);
 531                                         } else {
 532                                                 break;
 533                                         }
 534                                 }
 535                         }
 536                         nextBreak += charWidth;
 537                 }
 538                 if ((nextBreak - prev) < lengthStartSubdivision) {
 539                         return TextSegment(prev, nextBreak - prev);
 540                 }
 541                 subBreak = prev;
 542         }
 543         // Splitting up a long run from prev to nextBreak in lots of approximately lengthEachSubdivision.
 544         // For very long runs add extra breaks after spaces or if no spaces before low punctuation.
 545         int startSegment = subBreak;
 546         if ((nextBreak - subBreak) <= lengthEachSubdivision) {
 547                 subBreak = -1;
 548                 return TextSegment(startSegment, nextBreak - startSegment);
 549         } else {
 550                 subBreak += pdoc->SafeSegment(ll->chars + subBreak, nextBreak-subBreak, lengthEachSubdivision);
 551                 if (subBreak >= nextBreak) {
 552                         subBreak = -1;
 553                         return TextSegment(startSegment, nextBreak - startSegment);
 554                 } else {
 555                         return TextSegment(startSegment, subBreak - startSegment);
 556                 }
 557         }
 558 }
 559
 560 bool BreakFinder::More() const {
 561         return (subBreak >= 0) || (nextBreak < lineRange.end);
 562 }
 563
 564 PositionCacheEntry::PositionCacheEntry() :
 565         styleNumber(0), len(0), clock(0), positions(0) {
 566 }
 567
 568 void PositionCacheEntry::Set(unsigned int styleNumber_, const char *s_,
 569         unsigned int len_, XYPOSITION *positions_, unsigned int clock_) {
 570         Clear();
 571         styleNumber = styleNumber_;
 572         len = len_;
 573         clock = clock_;
 574         if (s_ && positions_) {
 575                 positions = new XYPOSITION[len + (len / 4) + 1];
 576                 for (unsigned int i=0; i<len; i++) {
 577                         positions[i] = positions_[i];
 578                 }
 579                 memcpy(reinterpret_cast<char *>(reinterpret_cast<void *>(positions + len)), s_, len);
 580         }
 581 }
 582
 583 PositionCacheEntry::~PositionCacheEntry() {
 584         Clear();
 585 }
 586
 587 void PositionCacheEntry::Clear() {
 588         delete []positions;
 589         positions = 0;
 590         styleNumber = 0;
 591         len = 0;
 592         clock = 0;
 593 }
 594
 595 bool PositionCacheEntry::Retrieve(unsigned int styleNumber_, const char *s_,
 596         unsigned int len_, XYPOSITION *positions_) const {
 597         if ((styleNumber == styleNumber_) && (len == len_) &&
 598                 (memcmp(reinterpret_cast<char *>(reinterpret_cast<void *>(positions + len)), s_, len)== 0)) {
 599                 for (unsigned int i=0; i<len; i++) {
 600                         positions_[i] = positions[i];
 601                 }
 602                 return true;
 603         } else {
 604                 return false;
 605         }
 606 }
 607
 608 unsigned int PositionCacheEntry::Hash(unsigned int styleNumber_, const char *s, unsigned int len_) {
 609         unsigned int ret = s[0] << 7;
 610         for (unsigned int i=0; i<len_; i++) {
 611                 ret *= 1000003;
 612                 ret ^= s[i];
 613         }
 614         ret *= 1000003;
 615         ret ^= len_;
 616         ret *= 1000003;
 617         ret ^= styleNumber_;
 618         return ret;
 619 }
 620
 621 bool PositionCacheEntry::NewerThan(const PositionCacheEntry &other) const {
 622         return clock > other.clock;
 623 }
 624
 625 void PositionCacheEntry::ResetClock() {
 626         if (clock > 0) {
 627                 clock = 1;
 628         }
 629 }
 630
 631 PositionCache::PositionCache() {
 632         clock = 1;
 633         pces.resize(0x400);
 634         allClear = true;
 635 }
 636
 637 PositionCache::~PositionCache() {
 638         Clear();
 639 }
 640
 641 void PositionCache::Clear() {
 642         if (!allClear) {
 643                 for (size_t i=0; i<pces.size(); i++) {
 644                         pces[i].Clear();
 645                 }
 646         }
 647         clock = 1;
 648         allClear = true;
 649 }
 650
 651 void PositionCache::SetSize(size_t size_) {
 652         Clear();
 653         pces.resize(size_);
 654 }
 655
 656 void PositionCache::MeasureWidths(Surface *surface, const ViewStyle &vstyle, unsigned int styleNumber,
 657         const char *s, unsigned int len, XYPOSITION *positions, Document *pdoc) {
 658
 659         allClear = false;
 660         size_t probe = pces.size();     // Out of bounds
 661         if ((!pces.empty()) && (len < 30)) {
 662                 // Only store short strings in the cache so it doesn't churn with
 663                 // long comments with only a single comment.
 664
 665                 // Two way associative: try two probe positions.
 666                 unsigned int hashValue = PositionCacheEntry::Hash(styleNumber, s, len);
 667                 probe = hashValue % pces.size();
 668                 if (pces[probe].Retrieve(styleNumber, s, len, positions)) {
 669                         return;
 670                 }
 671                 unsigned int probe2 = (hashValue * 37) % pces.size();
 672                 if (pces[probe2].Retrieve(styleNumber, s, len, positions)) {
 673                         return;
 674                 }
 675                 // Not found. Choose the oldest of the two slots to replace
 676                 if (pces[probe].NewerThan(pces[probe2])) {
 677                         probe = probe2;
 678                 }
 679         }
 680         if (len > BreakFinder::lengthStartSubdivision) {
 681                 // Break up into segments
 682                 unsigned int startSegment = 0;
 683                 XYPOSITION xStartSegment = 0;
 684                 while (startSegment < len) {
 685                         unsigned int lenSegment = pdoc->SafeSegment(s + startSegment, len - startSegment, BreakFinder::lengthEachSubdivision);
 686                         FontAlias fontStyle = vstyle.styles[styleNumber].font;
 687                         surface->MeasureWidths(fontStyle, s + startSegment, lenSegment, positions + startSegment);
 688                         for (unsigned int inSeg = 0; inSeg < lenSegment; inSeg++) {
 689                                 positions[startSegment + inSeg] += xStartSegment;
 690                         }
 691                         xStartSegment = positions[startSegment + lenSegment - 1];
 692                         startSegment += lenSegment;
 693                 }
 694         } else {
 695                 FontAlias fontStyle = vstyle.styles[styleNumber].font;
 696                 surface->MeasureWidths(fontStyle, s, len, positions);
 697         }
 698         if (probe < pces.size()) {
 699                 // Store into cache
 700                 clock++;
 701                 if (clock > 60000) {
 702                         // Since there are only 16 bits for the clock, wrap it round and
 703                         // reset all cache entries so none get stuck with a high clock.
 704                         for (size_t i=0; i<pces.size(); i++) {
 705                                 pces[i].ResetClock();
 706                         }
 707                         clock = 2;
 708                 }
 709                 pces[probe].Set(styleNumber, s, len, positions, clock);
 710         }
 711 }