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