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