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