1 2 /* 3 * Copyright 2012 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 #ifndef SkPathRef_DEFINED 10 #define SkPathRef_DEFINED 11 12 #include "SkRefCnt.h" 13 #include <stddef.h> // ptrdiff_t 14 15 // When we're ready to break the picture format. Changes: 16 // * Write genID. 17 // * SkPathRef read/write counts (which will change the field order) 18 // * SkPathRef reads/writes verbs backwards. 19 #define NEW_PICTURE_FORMAT 0 20 21 /** 22 * Holds the path verbs and points. It is versioned by a generation ID. None of its public methods 23 * modify the contents. To modify or append to the verbs/points wrap the SkPathRef in an 24 * SkPathRef::Editor object. Installing the editor resets the generation ID. It also performs 25 * copy-on-write if the SkPathRef is shared by multipls SkPaths. The caller passes the Editor's 26 * constructor a SkAutoTUnref, which may be updated to point to a new SkPathRef after the editor's 27 * constructor returns. 28 * 29 * The points and verbs are stored in a single allocation. The points are at the begining of the 30 * allocation while the verbs are stored at end of the allocation, in reverse order. Thus the points 31 * and verbs both grow into the middle of the allocation until the meet. To access verb i in the 32 * verb array use ref.verbs()[~i] (because verbs() returns a pointer just beyond the first 33 * logical verb or the last verb in memory). 34 */ 35 36 class SkPathRef; 37 38 // This path ref should never be deleted once it is created. It should not be global but was made 39 // so for checks when SK_DEBUG_PATH_REF is enabled. It we be re-hidden when the debugging code is 40 // reverted. 41 SkPathRef* gEmptyPathRef; 42 43 // Temporary hackery to try to nail down http://code.google.com/p/chromium/issues/detail?id=148637 44 #if SK_DEBUG_PATH_REF 45 #define PR_CONTAINER SkPath::PathRefDebugRef 46 #define SkDEBUGCODE_X(code) code 47 #define SkASSERT_X(cond) SK_DEBUGBREAK(cond) 48 // We put the mutex in a factory function to protect against static-initializion order 49 // fiasco when SkPaths are created before main(). 50 static SkMutex* owners_mutex() { 51 static SkMutex* gOwnersMutex; 52 if (!gOwnersMutex) { 53 gOwnersMutex = new SkMutex(); // leak! 54 } 55 return gOwnersMutex; 56 } 57 // We have a static initializer that calls owners_mutex before main() so that 58 // hopefully that we only wind up with one mutex (assuming no threads created 59 // before static initialization is finished.) 60 static const SkMutex* gOwnersMutexForce = owners_mutex(); 61 #else 62 #define PR_CONTAINER SkAutoTUnref<SkPathRef> 63 #define SkDEBUGCODE_X(code) SkDEBUGCODE(code) 64 #define SkASSERT_X(cond) SkASSERT(cond) 65 #endif 66 67 class SkPathRef : public ::SkRefCnt { 68 public: 69 SK_DECLARE_INST_COUNT(SkPathRef); 70 71 class Editor { 72 public: 73 Editor(PR_CONTAINER* pathRef, 74 int incReserveVerbs = 0, 75 int incReservePoints = 0) { 76 if (pathRef->get()->getRefCnt() > 1) { 77 SkPathRef* copy = SkNEW(SkPathRef); 78 copy->copy(*pathRef->get(), incReserveVerbs, incReservePoints); 79 pathRef->reset(copy); 80 } else { 81 (*pathRef)->incReserve(incReserveVerbs, incReservePoints); 82 } 83 fPathRef = pathRef->get(); 84 fPathRef->fGenerationID = 0; 85 SkDEBUGCODE_X(sk_atomic_inc(&fPathRef->fEditorsAttached);) 86 } 87 88 ~Editor() { SkDEBUGCODE_X(sk_atomic_dec(&fPathRef->fEditorsAttached);) } 89 90 /** 91 * Returns the array of points. 92 */ 93 SkPoint* points() { return fPathRef->fPoints; } 94 95 /** 96 * Gets the ith point. Shortcut for this->points() + i 97 */ 98 SkPoint* atPoint(int i) { 99 SkASSERT((unsigned) i < (unsigned) fPathRef->fPointCnt); 100 return this->points() + i; 101 }; 102 103 /** 104 * Adds the verb and allocates space for the number of points indicated by the verb. The 105 * return value is a pointer to where the points for the verb should be written. 106 */ 107 SkPoint* growForVerb(SkPath::Verb verb) { 108 fPathRef->validate(); 109 return fPathRef->growForVerb(verb); 110 } 111 112 /** 113 * Allocates space for additional verbs and points and returns pointers to the new verbs and 114 * points. verbs will point one beyond the first new verb (index it using [~<i>]). pts points 115 * at the first new point (indexed normally [<i>]). 116 */ 117 void grow(int newVerbs, int newPts, uint8_t** verbs, SkPoint** pts) { 118 SkASSERT(NULL != verbs); 119 SkASSERT(NULL != pts); 120 fPathRef->validate(); 121 int oldVerbCnt = fPathRef->fVerbCnt; 122 int oldPointCnt = fPathRef->fPointCnt; 123 SkASSERT(verbs && pts); 124 fPathRef->grow(newVerbs, newPts); 125 *verbs = fPathRef->fVerbs - oldVerbCnt; 126 *pts = fPathRef->fPoints + oldPointCnt; 127 fPathRef->validate(); 128 } 129 130 /** 131 * Resets the path ref to a new verb and point count. The new verbs and points are 132 * uninitialized. 133 */ 134 void resetToSize(int newVerbCnt, int newPointCnt) { 135 fPathRef->resetToSize(newVerbCnt, newPointCnt); 136 } 137 /** 138 * Gets the path ref that is wrapped in the Editor. 139 */ 140 SkPathRef* pathRef() { return fPathRef; } 141 142 private: 143 SkPathRef* fPathRef; 144 }; 145 146 public: 147 #if SK_DEBUG_PATH_REF 148 void addOwner(SkPath* owner) { 149 SkAutoMutexAcquire ac(owners_mutex()); 150 for (int i = 0; i < fOwners.count(); ++i) { 151 SkASSERT_X(fOwners[i] != owner); 152 } 153 *fOwners.append() = owner; 154 SkASSERT_X((this->getRefCnt() == fOwners.count()) || 155 (this == gEmptyPathRef && this->getRefCnt() == fOwners.count() + 1)); 156 } 157 158 void removeOwner(SkPath* owner) { 159 SkAutoMutexAcquire ac(owners_mutex()); 160 SkASSERT_X((this->getRefCnt() == fOwners.count()) || 161 (this == gEmptyPathRef && this->getRefCnt() == fOwners.count() + 1)); 162 bool found = false; 163 for (int i = 0; !found && i < fOwners.count(); ++i) { 164 found = (owner == fOwners[i]); 165 if (found) { 166 fOwners.remove(i); 167 } 168 } 169 SkASSERT_X(found); 170 } 171 #endif 172 173 /** 174 * Gets a path ref with no verbs or points. 175 */ 176 static SkPathRef* CreateEmpty() { 177 if (!gEmptyPathRef) { 178 gEmptyPathRef = SkNEW(SkPathRef); // leak! 179 } 180 return SkRef(gEmptyPathRef); 181 } 182 183 /** 184 * Transforms a path ref by a matrix, allocating a new one only if necessary. 185 */ 186 static void CreateTransformedCopy(PR_CONTAINER* dst, 187 const SkPathRef& src, 188 const SkMatrix& matrix) { 189 src.validate(); 190 if (matrix.isIdentity()) { 191 if (dst->get() != &src) { 192 src.ref(); 193 dst->reset(const_cast<SkPathRef*>(&src)); 194 (*dst)->validate(); 195 } 196 return; 197 } 198 int32_t rcnt = dst->get()->getRefCnt(); 199 if (&src == dst->get() && 1 == rcnt) { 200 matrix.mapPoints((*dst)->fPoints, (*dst)->fPointCnt); 201 return; 202 } else if (rcnt > 1) { 203 dst->reset(SkNEW(SkPathRef)); 204 } 205 (*dst)->resetToSize(src.fVerbCnt, src.fPointCnt); 206 memcpy((*dst)->verbsMemWritable(), src.verbsMemBegin(), src.fVerbCnt * sizeof(uint8_t)); 207 matrix.mapPoints((*dst)->fPoints, src.points(), src.fPointCnt); 208 (*dst)->validate(); 209 } 210 211 #if NEW_PICTURE_FORMAT 212 static SkPathRef* CreateFromBuffer(SkRBuffer* buffer) { 213 SkPathRef* ref = SkNEW(SkPathRef); 214 ref->fGenerationID = buffer->readU32(); 215 int32_t verbCount = buffer->readS32(); 216 int32_t pointCount = buffer->readS32(); 217 ref->resetToSize(verbCount, pointCount); 218 219 SkASSERT(verbCount == ref->countVerbs()); 220 SkASSERT(pointCount == ref->countPoints()); 221 buffer->read(ref->verbsMemWritable(), verbCount * sizeof(uint8_t)); 222 buffer->read(ref->fPoints, pointCount * sizeof(SkPoint)); 223 return ref; 224 } 225 #else 226 static SkPathRef* CreateFromBuffer(int verbCount, int pointCount, SkRBuffer* buffer) { 227 SkPathRef* ref = SkNEW(SkPathRef); 228 229 ref->resetToSize(verbCount, pointCount); 230 SkASSERT(verbCount == ref->countVerbs()); 231 SkASSERT(pointCount == ref->countPoints()); 232 buffer->read(ref->fPoints, pointCount * sizeof(SkPoint)); 233 for (int i = 0; i < verbCount; ++i) { 234 ref->fVerbs[~i] = buffer->readU8(); 235 } 236 return ref; 237 } 238 #endif 239 240 /** 241 * Rollsback a path ref to zero verbs and points with the assumption that the path ref will be 242 * repopulated with approximately the same number of verbs and points. A new path ref is created 243 * only if necessary. 244 */ 245 static void Rewind(PR_CONTAINER* pathRef) { 246 if (1 == (*pathRef)->getRefCnt()) { 247 (*pathRef)->validate(); 248 (*pathRef)->fVerbCnt = 0; 249 (*pathRef)->fPointCnt = 0; 250 (*pathRef)->fFreeSpace = (*pathRef)->currSize(); 251 (*pathRef)->fGenerationID = 0; 252 (*pathRef)->validate(); 253 } else { 254 int oldVCnt = (*pathRef)->countVerbs(); 255 int oldPCnt = (*pathRef)->countPoints(); 256 pathRef->reset(SkNEW(SkPathRef)); 257 (*pathRef)->resetToSize(0, 0, oldVCnt, oldPCnt); 258 } 259 } 260 261 virtual ~SkPathRef() { 262 SkASSERT_X(this != gEmptyPathRef); 263 #if SK_DEBUG_PATH_REF 264 SkASSERT_X(!fOwners.count()); 265 #endif 266 267 this->validate(); 268 sk_free(fPoints); 269 270 SkDEBUGCODE_X(fPoints = NULL;) 271 SkDEBUGCODE_X(fVerbs = NULL;) 272 SkDEBUGCODE_X(fVerbCnt = 0x9999999;) 273 SkDEBUGCODE_X(fPointCnt = 0xAAAAAAA;) 274 SkDEBUGCODE_X(fPointCnt = 0xBBBBBBB;) 275 SkDEBUGCODE_X(fGenerationID = 0xEEEEEEEE;) 276 SkDEBUGCODE_X(fEditorsAttached = 0x7777777;) 277 } 278 279 int countPoints() const { this->validate(); return fPointCnt; } 280 int countVerbs() const { this->validate(); return fVerbCnt; } 281 282 /** 283 * Returns a pointer one beyond the first logical verb (last verb in memory order). 284 */ 285 const uint8_t* verbs() const { this->validate(); return fVerbs; } 286 287 /** 288 * Returns a const pointer to the first verb in memory (which is the last logical verb). 289 */ 290 const uint8_t* verbsMemBegin() const { return this->verbs() - fVerbCnt; } 291 292 /** 293 * Returns a const pointer to the first point. 294 */ 295 const SkPoint* points() const { this->validate(); return fPoints; } 296 297 /** 298 * Shortcut for this->points() + this->countPoints() 299 */ 300 const SkPoint* pointsEnd() const { return this->points() + this->countPoints(); } 301 302 /** 303 * Convenience methods for getting to a verb or point by index. 304 */ 305 uint8_t atVerb(int index) { 306 SkASSERT((unsigned) index < (unsigned) fVerbCnt); 307 return this->verbs()[~index]; 308 } 309 const SkPoint& atPoint(int index) const { 310 SkASSERT((unsigned) index < (unsigned) fPointCnt); 311 return this->points()[index]; 312 } 313 314 bool operator== (const SkPathRef& ref) const { 315 this->validate(); 316 ref.validate(); 317 bool genIDMatch = fGenerationID && fGenerationID == ref.fGenerationID; 318 #ifdef SK_RELEASE 319 if (genIDMatch) { 320 return true; 321 } 322 #endif 323 if (fPointCnt != ref.fPointCnt || 324 fVerbCnt != ref.fVerbCnt) { 325 SkASSERT(!genIDMatch); 326 return false; 327 } 328 if (0 != memcmp(this->verbsMemBegin(), 329 ref.verbsMemBegin(), 330 ref.fVerbCnt * sizeof(uint8_t))) { 331 SkASSERT(!genIDMatch); 332 return false; 333 } 334 if (0 != memcmp(this->points(), 335 ref.points(), 336 ref.fPointCnt * sizeof(SkPoint))) { 337 SkASSERT(!genIDMatch); 338 return false; 339 } 340 // We've done the work to determine that these are equal. If either has a zero genID, copy 341 // the other's. If both are 0 then genID() will compute the next ID. 342 if (0 == fGenerationID) { 343 fGenerationID = ref.genID(); 344 } else if (0 == ref.fGenerationID) { 345 ref.fGenerationID = this->genID(); 346 } 347 return true; 348 } 349 350 /** 351 * Writes the path points and verbs to a buffer. 352 */ 353 #if NEW_PICTURE_FORMAT 354 void writeToBuffer(SkWBuffer* buffer) { 355 this->validate(); 356 SkDEBUGCODE_X(size_t beforePos = buffer->pos();) 357 358 // TODO: write gen ID here. Problem: We don't know if we're cross process or not from 359 // SkWBuffer. Until this is fixed we write 0. 360 buffer->write32(0); 361 buffer->write32(this->fVerbCnt); 362 buffer->write32(this->fPointCnt); 363 buffer->write(this->verbsMemBegin(), fVerbCnt * sizeof(uint8_t)); 364 buffer->write(fPoints, fPointCnt * sizeof(SkPoint)); 365 366 SkASSERT(buffer->pos() - beforePos == (size_t) this->writeSize()); 367 } 368 369 /** 370 * Gets the number of bytes that would be written in writeBuffer() 371 */ 372 uint32_t writeSize() { 373 return 3 * sizeof(uint32_t) + fVerbCnt * sizeof(uint8_t) + fPointCnt * sizeof(SkPoint); 374 } 375 #else 376 void writeToBuffer(SkWBuffer* buffer) { 377 this->validate(); 378 buffer->write(fPoints, fPointCnt * sizeof(SkPoint)); 379 for (int i = 0; i < fVerbCnt; ++i) { 380 buffer->write8(fVerbs[~i]); 381 } 382 } 383 #endif 384 385 private: 386 SkPathRef() { 387 fPointCnt = 0; 388 fVerbCnt = 0; 389 fVerbs = NULL; 390 fPoints = NULL; 391 fFreeSpace = 0; 392 fGenerationID = kEmptyGenID; 393 SkDEBUGCODE_X(fEditorsAttached = 0;) 394 this->validate(); 395 } 396 397 void copy(const SkPathRef& ref, int additionalReserveVerbs, int additionalReservePoints) { 398 this->validate(); 399 this->resetToSize(ref.fVerbCnt, ref.fPointCnt, 400 additionalReserveVerbs, additionalReservePoints); 401 memcpy(this->verbsMemWritable(), ref.verbsMemBegin(), ref.fVerbCnt * sizeof(uint8_t)); 402 memcpy(this->fPoints, ref.fPoints, ref.fPointCnt * sizeof(SkPoint)); 403 // We could call genID() here to force a real ID (instead of 0). However, if we're making 404 // a copy then presumably we intend to make a modification immediately afterwards. 405 fGenerationID = ref.fGenerationID; 406 this->validate(); 407 } 408 409 /** Makes additional room but does not change the counts or change the genID */ 410 void incReserve(int additionalVerbs, int additionalPoints) { 411 this->validate(); 412 size_t space = additionalVerbs * sizeof(uint8_t) + additionalPoints * sizeof (SkPoint); 413 this->makeSpace(space); 414 this->validate(); 415 } 416 417 /** Resets the path ref with verbCount verbs and pointCount points, all unitialized. Also 418 * allocates space for reserveVerb additional verbs and reservePoints additional points.*/ 419 void resetToSize(int verbCount, int pointCount, int reserveVerbs = 0, int reservePoints = 0) { 420 this->validate(); 421 fGenerationID = 0; 422 423 size_t newSize = sizeof(uint8_t) * verbCount + sizeof(SkPoint) * pointCount; 424 size_t newReserve = sizeof(uint8_t) * reserveVerbs + sizeof(SkPoint) * reservePoints; 425 size_t minSize = newSize + newReserve; 426 427 ptrdiff_t sizeDelta = this->currSize() - minSize; 428 429 if (sizeDelta < 0 || static_cast<size_t>(sizeDelta) >= 3 * minSize) { 430 sk_free(fPoints); 431 fPoints = NULL; 432 fVerbs = NULL; 433 fFreeSpace = 0; 434 fVerbCnt = 0; 435 fPointCnt = 0; 436 this->makeSpace(minSize); 437 fVerbCnt = verbCount; 438 fPointCnt = pointCount; 439 fFreeSpace -= newSize; 440 } else { 441 fPointCnt = pointCount; 442 fVerbCnt = verbCount; 443 fFreeSpace = this->currSize() - minSize; 444 } 445 this->validate(); 446 } 447 448 /** 449 * Increases the verb count by newVerbs and the point count be newPoints. New verbs and points 450 * are uninitialized. 451 */ 452 void grow(int newVerbs, int newPoints) { 453 this->validate(); 454 size_t space = newVerbs * sizeof(uint8_t) + newPoints * sizeof (SkPoint); 455 this->makeSpace(space); 456 fVerbCnt += newVerbs; 457 fPointCnt += newPoints; 458 fFreeSpace -= space; 459 this->validate(); 460 } 461 462 /** 463 * Increases the verb count 1, records the new verb, and creates room for the requisite number 464 * of additional points. A pointer to the first point is returned. Any new points are 465 * uninitialized. 466 */ 467 SkPoint* growForVerb(SkPath::Verb verb) { 468 this->validate(); 469 int pCnt; 470 switch (verb) { 471 case SkPath::kMove_Verb: 472 pCnt = 1; 473 break; 474 case SkPath::kLine_Verb: 475 pCnt = 1; 476 break; 477 case SkPath::kQuad_Verb: 478 pCnt = 2; 479 break; 480 case SkPath::kCubic_Verb: 481 pCnt = 3; 482 break; 483 default: 484 pCnt = 0; 485 } 486 size_t space = sizeof(uint8_t) + pCnt * sizeof (SkPoint); 487 this->makeSpace(space); 488 this->fVerbs[~fVerbCnt] = verb; 489 SkPoint* ret = fPoints + fPointCnt; 490 fVerbCnt += 1; 491 fPointCnt += pCnt; 492 fFreeSpace -= space; 493 this->validate(); 494 return ret; 495 } 496 497 /** 498 * Ensures that the free space available in the path ref is >= size. The verb and point counts 499 * are not changed. 500 */ 501 void makeSpace(size_t size) { 502 this->validate(); 503 ptrdiff_t growSize = size - fFreeSpace; 504 if (growSize <= 0) { 505 return; 506 } 507 size_t oldSize = this->currSize(); 508 // round to next multiple of 8 bytes 509 growSize = (growSize + 7) & ~static_cast<size_t>(7); 510 // we always at least double the allocation 511 if (static_cast<size_t>(growSize) < oldSize) { 512 growSize = oldSize; 513 } 514 if (growSize < kMinSize) { 515 growSize = kMinSize; 516 } 517 size_t newSize = oldSize + growSize; 518 // Note that realloc could memcpy more than we need. It seems to be a win anyway. TODO: 519 // encapsulate this. 520 fPoints = reinterpret_cast<SkPoint*>(sk_realloc_throw(fPoints, newSize)); 521 size_t oldVerbSize = fVerbCnt * sizeof(uint8_t); 522 void* newVerbsDst = reinterpret_cast<void*>( 523 reinterpret_cast<intptr_t>(fPoints) + newSize - oldVerbSize); 524 void* oldVerbsSrc = reinterpret_cast<void*>( 525 reinterpret_cast<intptr_t>(fPoints) + oldSize - oldVerbSize); 526 memmove(newVerbsDst, oldVerbsSrc, oldVerbSize); 527 fVerbs = reinterpret_cast<uint8_t*>(reinterpret_cast<intptr_t>(fPoints) + newSize); 528 fFreeSpace += growSize; 529 this->validate(); 530 } 531 532 /** 533 * Private, non-const-ptr version of the public function verbsMemBegin(). 534 */ 535 uint8_t* verbsMemWritable() { 536 this->validate(); 537 return fVerbs - fVerbCnt; 538 } 539 540 /** 541 * Gets the total amount of space allocated for verbs, points, and reserve. 542 */ 543 size_t currSize() const { 544 return reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints); 545 } 546 547 /** 548 * Gets an ID that uniquely identifies the contents of the path ref. If two path refs have the 549 * same ID then they have the same verbs and points. However, two path refs may have the same 550 * contents but different genIDs. Zero is reserved and means an ID has not yet been determined 551 * for the path ref. 552 */ 553 int32_t genID() const { 554 SkASSERT_X(!fEditorsAttached); 555 if (!fGenerationID) { 556 if (0 == fPointCnt && 0 == fVerbCnt) { 557 fGenerationID = kEmptyGenID; 558 } else { 559 static int32_t gPathRefGenerationID; 560 // do a loop in case our global wraps around, as we never want to return a 0 or the 561 // empty ID 562 do { 563 fGenerationID = sk_atomic_inc(&gPathRefGenerationID) + 1; 564 } while (fGenerationID <= kEmptyGenID); 565 } 566 } 567 return fGenerationID; 568 } 569 570 void validate() const { 571 SkASSERT(static_cast<ptrdiff_t>(fFreeSpace) >= 0); 572 SkASSERT(reinterpret_cast<intptr_t>(fVerbs) - reinterpret_cast<intptr_t>(fPoints) >= 0); 573 SkASSERT((NULL == fPoints) == (NULL == fVerbs)); 574 SkASSERT(!(NULL == fPoints && 0 != fFreeSpace)); 575 SkASSERT(!(NULL == fPoints && 0 != fFreeSpace)); 576 SkASSERT(!(NULL == fPoints && fPointCnt)); 577 SkASSERT(!(NULL == fVerbs && fVerbCnt)); 578 SkASSERT(this->currSize() == 579 fFreeSpace + sizeof(SkPoint) * fPointCnt + sizeof(uint8_t) * fVerbCnt); 580 } 581 582 enum { 583 kMinSize = 256, 584 }; 585 586 SkPoint* fPoints; // points to begining of the allocation 587 uint8_t* fVerbs; // points just past the end of the allocation (verbs grow backwards) 588 int fVerbCnt; 589 int fPointCnt; 590 size_t fFreeSpace; // redundant but saves computation 591 enum { 592 kEmptyGenID = 1, // GenID reserved for path ref with zero points and zero verbs. 593 }; 594 mutable int32_t fGenerationID; 595 SkDEBUGCODE_X(int32_t fEditorsAttached;) // assert that only one editor in use at any time. 596 597 #if SK_DEBUG_PATH_REF 598 SkTDArray<SkPath*> fOwners; 599 #endif 600 601 typedef SkRefCnt INHERITED; 602 }; 603 604 SK_DEFINE_INST_COUNT(SkPathRef); 605 606 #endif 607
