From cd0bf0adaa7adc24f79834e1b36884b72e64dbcc Mon Sep 17 00:00:00 2001 From: "commit-bot@chromium.org" Date: Fri, 17 Jan 2014 17:55:14 +0000 Subject: 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 --- src/core/SkTDynamicHash.h | 62 +++++++++++++++++++++-------------------------- 1 file changed, 28 insertions(+), 34 deletions(-) (limited to 'src/core') 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 -- cgit v1.2.3