diff options
| author |  commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-01-17 17:55:14 +0000 |
|---|---|---|
| committer | commit-bot@chromium.org <commit-bot@chromium.org@2bbb7eff-a529-9590-31e7-b0007b416f81> | 2014-01-17 17:55:14 +0000 |
| commit | cd0bf0adaa7adc24f79834e1b36884b72e64dbcc (patch) | |
| tree | ac08b93f6c7e0a33a8bc4c339766bf01352de15b /src | |
| parent | 2ab1ba055536825552d6b49f0210c4e1531f02f0 (diff) | |
Tweak validate() to check less as the size of the hash grows.
This makes working with a non-trivial SkTDynamicHash less painful in Debug
builds. validate() is skipped in Release, so this has no effect there.
BUG=
R=kkinnunen@nvidia.com, bsalomon@google.com
Author: mtklein@google.com
Review URL: https://codereview.chromium.org/140753003
git-svn-id: http://skia.googlecode.com/svn/trunk@13121 2bbb7eff-a529-9590-31e7-b0007b416f81
Diffstat (limited to 'src')
| -rw-r--r-- | src/core/SkTDynamicHash.h | 62 |
1 files changed, 28 insertions, 34 deletions
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h index cae32b3417..8f66c86d90 100644 --- a/src/core/SkTDynamicHash.h +++ b/src/core/SkTDynamicHash.h @@ -51,7 +51,6 @@ public: void add(T* newEntry) { SkASSERT(NULL == this->find(GetKey(*newEntry))); this->maybeGrow(); - SkASSERT(this->validate()); this->innerAdd(newEntry); SkASSERT(this->validate()); } @@ -89,48 +88,43 @@ private: bool validate() const { #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false + static const int kLarge = 50; // Arbitrary, tweak to suit your patience. + // O(1) checks, always done. // Is capacity sane? SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity)); - // Is fCount correct? - int count = 0; - for (int i = 0; i < fCapacity; i++) { - if (Empty() != fArray[i] && Deleted() != fArray[i]) { - count++; - } - } - SKTDYNAMICHASH_CHECK(count == fCount); - - // Is fDeleted correct? - int deleted = 0; - for (int i = 0; i < fCapacity; i++) { - if (Deleted() == fArray[i]) { - deleted++; - } - } - SKTDYNAMICHASH_CHECK(deleted == fDeleted); - - // Are all entries findable? - for (int i = 0; i < fCapacity; i++) { - if (Empty() == fArray[i] || Deleted() == fArray[i]) { - continue; + // O(N) checks, skipped when very large. + if (fCount < kLarge * kLarge) { + // Are fCount and fDeleted correct, and are all elements findable? + int count = 0, deleted = 0; + for (int i = 0; i < fCapacity; i++) { + if (Deleted() == fArray[i]) { + deleted++; + } else if (Empty() != fArray[i]) { + count++; + SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i]))); + } } - SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i]))); + SKTDYNAMICHASH_CHECK(count == fCount); + SKTDYNAMICHASH_CHECK(deleted == fDeleted); } - // 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]) { + // O(N^2) checks, skipped when large. + if (fCount < kLarge) { + // Are all entries unique? + for (int i = 0; i < fCapacity; i++) { + if (Empty() == fArray[i] || Deleted() == fArray[i]) { continue; } - SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); - SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); - SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); + for (int j = i+1; j < fCapacity; j++) { + if (Empty() == fArray[j] || Deleted() == fArray[j]) { + continue; + } + SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]); + SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j]))); + SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i]))); + } } } #undef SKTDYNAMICHASH_CHECK |