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

Unified Diff: src/core/SkTDynamicHash.h

Issue 91453002: Speed up GrResourceCache add and lookup by using TDynamicHash (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Created 7 years, 1 month 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 | « src/core/SkScaledImageCache.cpp ('k') | src/gpu/GrResourceCache.h » ('j') | 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 4cb44204c85f61130354d25c78c7924249fe66f8..9b1dbf75fce3862eb46cd03188d0007c3f6c982d 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -11,6 +11,9 @@
#include "SkTypes.h"
#include "SkMath.h"
+/** SkTDynamicHash is a set of pointers of T. The elements can be looked up from the set by
+ * key Key. Duplicate keys are allowed.
+ */
template <typename T,
typename Key,
const Key& (GetKey)(const T&),
@@ -23,7 +26,6 @@ class SkTDynamicHash {
public:
SkTDynamicHash(int initialCapacity=64/sizeof(T*)) {
this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity));
- SkASSERT(this->validate());
mtklein 2013/11/27 14:21:54 Please put validate back to how it was. SkASSERT
Kimmo Kinnunen 2013/11/28 06:40:08 The commit msg actually said that when it is *run*
}
~SkTDynamicHash() {
@@ -32,78 +34,50 @@ public:
int count() const { return fCount; }
- // Return the entry with this key if we have it, otherwise NULL.
+ struct Any {
+ // Return the first entry that matches the key.
+ bool operator()(const T*) const { return true; }
mtklein 2013/11/27 14:21:54 I'm not a fan of this API. I know it's replicatin
Kimmo Kinnunen 2013/11/28 06:40:08 Yeah.. Though, in this stage of this usage, I don'
+ };
+
+ // Return an entry with passed key if the collection has it, otherwise NULL.
T* find(const Key& key) const {
+ return this->find(key, Any());
+ }
+
+ // Return an entry with the passed key if the collection has it and if filter returns true for
+ // the entry. Otherwise return NULL.
+ template <typename Filter>
+ T* find(const Key& key, Filter filter) const {
int index = this->firstIndex(key);
for (int round = 0; round < fCapacity; round++) {
T* candidate = fArray[index];
if (Empty() == candidate) {
return NULL;
}
- if (Deleted() != candidate && Equal(*candidate, key)) {
+ if (Deleted() != candidate && Equal(*candidate, key) && filter(fArray[index])) {
return candidate;
}
index = this->nextIndex(index, round);
}
- SkASSERT(0); // find: should be unreachable
return NULL;
}
- // Add an entry with this key. We require that no entry with newEntry's key is already present.
+ // Add an entry with this key.
void add(T* newEntry) {
- SkASSERT(NULL == this->find(GetKey(*newEntry)));
this->maybeGrow();
- SkASSERT(this->validate());
this->innerAdd(newEntry);
- SkASSERT(this->validate());
}
- // 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());
+ // Remove the entry with this key. We require that the entry has been added before.
+ void remove(const T* entry) {
mtklein 2013/11/27 14:21:54 Generally, these should be const T&. It's neither
Kimmo Kinnunen 2013/11/28 06:40:08 A) This is set that stores pointers B) Pointers ar
bsalomon 2013/12/02 14:18:16 If the function (or something it calls) will retai
reed1 2013/12/02 16:20:40 agreed -- passing a ptr is clearer (to me) that th
+ SkASSERT(NULL != this->find(GetKey(*entry)));
+ this->innerRemove(entry);
this->maybeShrink();
- SkASSERT(this->validate());
}
-protected:
- // These methods are used by tests only.
-
- int capacity() const { return fCapacity; }
-
- // How many collisions do we go through before finding where this entry should be inserted?
- int countCollisions(const Key& key) const {
- int index = this->firstIndex(key);
- for (int round = 0; round < fCapacity; round++) {
- const T* candidate = fArray[index];
- if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
- return round;
- }
- index = this->nextIndex(index, round);
- }
- SkASSERT(0); // countCollisions: should be unreachable
- return -1;
- }
-
-private:
- // We have two special values to indicate an empty or deleted entry.
- 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) {
- return (T**)sk_calloc_throw(sizeof(T*) * capacity); // All cells == Empty().
- }
-
- void reset(int capacity) {
- fCount = 0;
- fDeleted = 0;
- fCapacity = capacity;
- fArray = AllocArray(fCapacity);
- }
-
- bool validate() const {
- #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
+#ifdef SK_DEBUG
+ void validate() const {
+ #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return;
// Is capacity sane?
SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
@@ -145,12 +119,47 @@ private:
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
- return true;
+ }
+#else
+ void validate() const { }
+#endif
+
+protected:
+ // These methods are used by tests only.
+
+ int capacity() const { return fCapacity; }
+
+ // How many collisions do we go through before finding where this entry should be inseretd?
+ int countCollisions(const Key& key) const {
+ int index = this->firstIndex(key);
+ for (int round = 0; round < fCapacity; round++) {
+ const T* candidate = fArray[index];
+ if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
+ return round;
+ }
+ index = this->nextIndex(index, round);
+ }
+ SkASSERT(0); // countCollisions: should be unreachable
+ return -1;
+ }
+
+private:
+ // We have two special values to indicate an empty or deleted entry.
+ 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) {
+ return (T**)sk_calloc_throw(sizeof(T*) * capacity); // All cells == Empty().
+ }
+
+ void reset(int capacity) {
+ fCount = 0;
+ fDeleted = 0;
+ fCapacity = capacity;
+ fArray = AllocArray(fCapacity);
}
void innerAdd(T* newEntry) {
@@ -171,12 +180,13 @@ private:
SkASSERT(0); // add: should be unreachable
}
- void innerRemove(const Key& key) {
+ void innerRemove(const T* entry) {
+ const Key& key = GetKey(*entry);
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)) {
+ if (Deleted() != candidate && Equal(*candidate, key) && fArray[index] == entry) {
fDeleted++;
fCount--;
fArray[index] = Deleted();
« no previous file with comments | « src/core/SkScaledImageCache.cpp ('k') | src/gpu/GrResourceCache.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698