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