Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(379)

Unified Diff: src/core/SkTDynamicHash.h

Issue 140753003: Tweak validate() to check less as the size of the hash grows. (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: int is fine Created 6 years, 11 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/core/SkTDynamicHash.h
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index 4893fb384ff7e6b13a3fea8a814cb523fb2ae33d..9c82a04737bbd5ffdb4d9229646cb223376a4691 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -50,7 +50,6 @@ public:
void add(T* newEntry) {
SkASSERT(NULL == this->find(GetKey(*newEntry)));
this->maybeGrow();
- SkASSERT(this->validate());
this->innerAdd(newEntry);
SkASSERT(this->validate());
}
@@ -88,48 +87,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
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698