diff options
author | Android Chromium Automerger <chromium-automerger@android> | 2013-08-12 17:13:24 +0000 |
---|---|---|
committer | Android Chromium Automerger <chromium-automerger@android> | 2013-08-12 17:13:24 +0000 |
commit | 14fbddabd0a29826804e0c0c62065018555e52f0 (patch) | |
tree | 7862f373cee75a01fef741982eeacc6266759012 | |
parent | df9ea50094e0e2ab294631c6fb659ed4220810da (diff) | |
parent | 1f1c0d428453bea56d6092a89906fb668a7900f9 (diff) | |
download | src-14fbddabd0a29826804e0c0c62065018555e52f0.tar.gz |
Merge third_party/skia/src from https://chromium.googlesource.com/external/skia/src.git at 1f1c0d428453bea56d6092a89906fb668a7900f9
This commit was generated by merge_from_chromium.py.
Change-Id: I13955a5baad575afeec3cb756f09bc2cd629347c
-rw-r--r-- | core/SkBBoxRecord.cpp | 8 | ||||
-rw-r--r-- | core/SkBBoxRecord.h | 3 | ||||
-rw-r--r-- | core/SkCanvas.cpp | 6 | ||||
-rw-r--r-- | core/SkTDynamicHash.h | 159 |
4 files changed, 115 insertions, 61 deletions
diff --git a/core/SkBBoxRecord.cpp b/core/SkBBoxRecord.cpp index 666e4409..52d599f5 100644 --- a/core/SkBBoxRecord.cpp +++ b/core/SkBBoxRecord.cpp @@ -176,14 +176,6 @@ void SkBBoxRecord::drawPosText(const void* text, size_t byteLength, } } -void SkBBoxRecord::drawPosTextBounded(const void* text, size_t byteLength, - const SkPoint pos[], const SkRect& bbox, - const SkPaint& paint) { - if (this->transformBounds(bbox, &paint)) { - INHERITED::drawPosText(text, byteLength, pos, paint); - } -} - void SkBBoxRecord::drawPosTextH(const void* text, size_t byteLength, const SkScalar xpos[], SkScalar constY, const SkPaint& paint) { SkRect bbox; diff --git a/core/SkBBoxRecord.h b/core/SkBBoxRecord.h index 16dd8fff..9f796717 100644 --- a/core/SkBBoxRecord.h +++ b/core/SkBBoxRecord.h @@ -49,9 +49,6 @@ public: const SkRect& dst, const SkPaint* paint) SK_OVERRIDE; virtual void drawPosText(const void* text, size_t byteLength, const SkPoint pos[], const SkPaint& paint) SK_OVERRIDE; - virtual void drawPosTextBounded(const void* text, size_t byteLength, - const SkPoint pos[], const SkRect& bbox, - const SkPaint& paint) SK_OVERRIDE; virtual void drawPosTextH(const void* text, size_t byteLength, const SkScalar xpos[], SkScalar constY, const SkPaint& paint) SK_OVERRIDE; diff --git a/core/SkCanvas.cpp b/core/SkCanvas.cpp index 232bee33..5a9a56b2 100644 --- a/core/SkCanvas.cpp +++ b/core/SkCanvas.cpp @@ -1990,12 +1990,6 @@ void SkCanvas::drawPosText(const void* text, size_t byteLength, LOOPER_END } -void SkCanvas::drawPosTextBounded(const void* text, size_t byteLength, - const SkPoint pos[], const SkRect& bbox, - const SkPaint& paint) { - this->drawPosText(text, byteLength, pos, paint); -} - void SkCanvas::drawPosTextH(const void* text, size_t byteLength, const SkScalar xpos[], SkScalar constY, const SkPaint& paint) { diff --git a/core/SkTDynamicHash.h b/core/SkTDynamicHash.h index 21aca07b..a4087019 100644 --- a/core/SkTDynamicHash.h +++ b/core/SkTDynamicHash.h @@ -15,13 +15,16 @@ template <typename T, typename Key, const Key& (GetKey)(const T&), uint32_t (Hash)(const Key&), - bool (Equal)(const T&, const Key&)> + bool (Equal)(const T&, const Key&), + int kGrowPercent = 75, // Larger -> more memory efficient, but slower. + int kShrinkPercent = 25> class SkTDynamicHash { + static const int kMinCapacity = 4; // Smallest capacity we allow. public: - SkTDynamicHash(int initialCapacity=64/sizeof(T*)) - : fCount(0) - , fCapacity(SkNextPow2(initialCapacity > 0 ? initialCapacity : 1)) - , fArray(AllocArray(fCapacity)) {} + SkTDynamicHash(int initialCapacity=64/sizeof(T*)) { + this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity)); + SkASSERT(this->validate()); + } ~SkTDynamicHash() { sk_free(fArray); @@ -34,10 +37,10 @@ public: int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { T* candidate = fArray[index]; - if (candidate == Empty()) { + if (Empty() == candidate) { return NULL; } - if (candidate != Deleted() && Equal(*candidate, key)) { + if (Deleted() != candidate && Equal(*candidate, key)) { return candidate; } index = this->nextIndex(index, round); @@ -46,32 +49,22 @@ public: return NULL; } - // Add an entry with this key. + // Add an entry with this key. We require that no entry with newEntry's key is already present. void add(T* newEntry) { + SkASSERT(NULL == this->find(GetKey(*newEntry))); this->maybeGrow(); - - const Key& key = GetKey(*newEntry); - int index = this->firstIndex(key); - for (int round = 0; round < fCapacity; round++) { - T* candidate = fArray[index]; - if (candidate == Empty() || candidate == Deleted()) { - fArray[index] = newEntry; - fCount++; - return; - } - if (Equal(*candidate, key)) { - fArray[index] = newEntry; - return; - } - index = this->nextIndex(index, round); - } - SkASSERT(!"add: should be unreachable"); + SkASSERT(this->validate()); + this->innerAdd(newEntry); + SkASSERT(this->validate()); } - // Remove entry with this key, if we have it. + // Remove the entry with this key. We reqire that an entry with this key is present. void remove(const Key& key) { + SkASSERT(NULL != this->find(key)); this->innerRemove(key); + SkASSERT(this->validate()); this->maybeShrink(); + SkASSERT(this->validate()); } protected: @@ -84,7 +77,7 @@ protected: int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { const T* candidate = fArray[index]; - if (candidate == Empty() || candidate == Deleted() || Equal(*candidate, key)) { + if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) { return round; } index = this->nextIndex(index, round); @@ -95,8 +88,8 @@ protected: private: // We have two special values to indicate an empty or deleted entry. - static const T* Empty() { return reinterpret_cast<const T*>(0); } // i.e. NULL - static const T* Deleted() { return reinterpret_cast<const T*>(1); } // Also an invalid pointer. + static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. NULL + static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer. static T** AllocArray(int capacity) { T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity); @@ -104,16 +97,91 @@ private: return array; } - void innerRemove(const Key& key) { + void reset(int capacity) { + fCount = 0; + fDeleted = 0; + fCapacity = capacity; + fArray = AllocArray(fCapacity); + } + + bool validate() const { + #define CHECK(x) SkASSERT((x)); if (!(x)) return false + + // Is capacity sane? + CHECK(SkIsPow2(fCapacity)); + CHECK(fCapacity >= kMinCapacity); + + // Is fCount correct? + int count = 0; + for (int i = 0; i < fCapacity; i++) { + if (Empty() != fArray[i] && Deleted() != fArray[i]) { + count++; + } + } + CHECK(count == fCount); + + // Is fDeleted correct? + int deleted = 0; + for (int i = 0; i < fCapacity; i++) { + if (Deleted() == fArray[i]) { + deleted++; + } + } + CHECK(deleted == fDeleted); + + // Are all entries findable? + for (int i = 0; i < fCapacity; i++) { + if (Empty() == fArray[i] || Deleted() == fArray[i]) { + continue; + } + CHECK(NULL != this->find(GetKey(*fArray[i]))); + } + + // Are all entries unique? + for (int i = 0; i < fCapacity; i++) { + if (Empty() == fArray[i] || Deleted() == fArray[i]) { + continue; + } + for (int j = i+1; j < fCapacity; j++) { + if (Empty() == fArray[j] || Deleted() == fArray[j]) { + continue; + } + CHECK(fArray[i] != fArray[j]); + CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); + CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); + } + } + #undef CHECK + return true; + } + + void innerAdd(T* newEntry) { + const Key& key = GetKey(*newEntry); int index = this->firstIndex(key); for (int round = 0; round < fCapacity; round++) { const T* candidate = fArray[index]; - if (candidate == Empty()) { + if (Empty() == candidate || Deleted() == candidate) { + if (Deleted() == candidate) { + fDeleted--; + } + fCount++; + fArray[index] = newEntry; return; } - if (candidate != Deleted() && Equal(*candidate, key)) { - fArray[index] = const_cast<T*>(Deleted()); + index = this->nextIndex(index, round); + } + SkASSERT(!"add: should be unreachable"); + } + + void innerRemove(const Key& key) { + const int firstIndex = this->firstIndex(key); + int index = firstIndex; + for (int round = 0; round < fCapacity; round++) { + const T* candidate = fArray[index]; + if (Deleted() != candidate && Equal(*candidate, key)) { + fDeleted++; fCount--; + fArray[index] = Deleted(); return; } index = this->nextIndex(index, round); @@ -122,21 +190,27 @@ private: } void maybeGrow() { - if (fCount < fCapacity / 2) { - return; + if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) { + resize(fCapacity * 2); + } + } + + void maybeShrink() { + if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) { + resize(fCapacity / 2); } + } + void resize(int newCapacity) { SkDEBUGCODE(int oldCount = fCount;) int oldCapacity = fCapacity; T** oldArray = fArray; - fCount = 0; - fCapacity *= 2; - fArray = AllocArray(fCapacity); + reset(newCapacity); for (int i = 0; i < oldCapacity; i++) { T* entry = oldArray[i]; - if (entry != Empty() && entry != Deleted()) { + if (Empty() != entry && Deleted() != entry) { this->add(entry); } } @@ -145,10 +219,6 @@ private: sk_free(oldArray); } - void maybeShrink() { - // TODO - } - // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash. uint32_t hashMask() const { return fCapacity - 1; } @@ -162,7 +232,8 @@ private: return (index + round + 1) & this->hashMask(); } - int fCount; // Number of non-empty, non-deleted entries in fArray. + int fCount; // Number of non Empty(), non Deleted() entries in fArray. + int fDeleted; // Number of Deleted() entries in fArray. int fCapacity; // Number of entries in fArray. Always a power of 2. T** fArray; }; |