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

Unified Diff: src/gpu/GrTHashTable.h

Issue 421253003: Finish removing GrTHashTable (Closed) Base URL: https://skia.googlesource.com/skia.git@master
Patch Set: Created 6 years, 5 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 | « gyp/tests.gypi ('k') | src/gpu/gl/GrGLProgram.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/gpu/GrTHashTable.h
diff --git a/src/gpu/GrTHashTable.h b/src/gpu/GrTHashTable.h
deleted file mode 100644
index 9da4b06debe926f9f49896c49dc9c911cecb7463..0000000000000000000000000000000000000000
--- a/src/gpu/GrTHashTable.h
+++ /dev/null
@@ -1,215 +0,0 @@
-
-/*
- * Copyright 2010 Google Inc.
- *
- * Use of this source code is governed by a BSD-style license that can be
- * found in the LICENSE file.
- */
-
-
-
-#ifndef GrTHashTable_DEFINED
-#define GrTHashTable_DEFINED
-
-#include "GrTypes.h"
-#include "SkTDArray.h"
-
-/**
- * Key needs
- * static bool Equals(const Entry&, const Key&);
- * static bool LessThan(const Entry&, const Key&);
- * static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
- * static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
- * uint32_t getHash() const;
- *
- * Allows duplicate key entries but on find you may get
- * any of the duplicate entries returned.
- */
-template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
-public:
- GrTHashTable() { this->clearHash(); }
- ~GrTHashTable() {}
-
- int count() const { return fSorted.count(); }
-
- struct Any {
- // Return the first resource that matches the key.
- bool operator()(const T*) const { return true; }
- };
-
- T* find(const Key& key) const { return this->find(key, Any()); }
- template <typename Filter> T* find(const Key&, Filter filter) const;
-
- // return true if key was unique when inserted.
- bool insert(const Key&, T*);
- void remove(const Key&, const T*);
-
- void deleteAll();
-
-#ifdef SK_DEBUG
- void validate() const;
- bool contains(T*) const;
-#endif
-
- // testing
- const SkTDArray<T*>& getArray() const { return fSorted; }
- SkTDArray<T*>& getArray() { return fSorted; }
-private:
- void clearHash() { sk_bzero(fHash, sizeof(fHash)); }
-
- enum {
- kHashCount = 1 << kHashBits,
- kHashMask = kHashCount - 1
- };
- static unsigned hash2Index(intptr_t hash) {
-#if 0
- if (sizeof(hash) == 8) {
- hash ^= hash >> 32;
- }
-#endif
- hash ^= hash >> 16;
- if (kHashBits <= 8) {
- hash ^= hash >> 8;
- }
- return hash & kHashMask;
- }
-
- mutable T* fHash[kHashCount];
- SkTDArray<T*> fSorted;
-
- // search fSorted, and return the found index, or ~index of where it
- // should be inserted
- int searchArray(const Key&) const;
-};
-
-///////////////////////////////////////////////////////////////////////////////
-
-template <typename T, typename Key, size_t kHashBits>
-int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
- int count = fSorted.count();
- if (0 == count) {
- // we should insert it at 0
- return ~0;
- }
-
- const T* const* array = fSorted.begin();
- int high = count - 1;
- int low = 0;
- while (high > low) {
- int index = (low + high) >> 1;
- if (Key::LessThan(*array[index], key)) {
- low = index + 1;
- } else {
- high = index;
- }
- }
-
- // check if we found it
- if (Key::Equals(*array[high], key)) {
- // above search should have found the first occurrence if there
- // are multiple.
- SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
- return high;
- }
-
- // now return the ~ of where we should insert it
- if (Key::LessThan(*array[high], key)) {
- high += 1;
- }
- return ~high;
-}
-
-template <typename T, typename Key, size_t kHashBits>
-template <typename Filter>
-T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const {
-
- int hashIndex = hash2Index(key.getHash());
- T* elem = fHash[hashIndex];
-
- if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
- return elem;
- }
-
- // bsearch for the key in our sorted array
- int index = this->searchArray(key);
- if (index < 0) {
- return NULL;
- }
-
- const T* const* array = fSorted.begin();
-
- // above search should have found the first occurrence if there
- // are multiple.
- SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
-
- for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
- if (filter(fSorted[index])) {
- // update the hash
- fHash[hashIndex] = fSorted[index];
- return fSorted[index];
- }
- }
-
- return NULL;
-}
-
-template <typename T, typename Key, size_t kHashBits>
-bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
- int index = this->searchArray(key);
- bool first = index < 0;
- if (first) {
- // turn it into the actual index
- index = ~index;
- }
- // add it to our array
- *fSorted.insert(index) = elem;
- // update our hash table (overwrites any dupe's position in the hash)
- fHash[hash2Index(key.getHash())] = elem;
- return first;
-}
-
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
- int index = hash2Index(key.getHash());
- if (fHash[index] == elem) {
- fHash[index] = NULL;
- }
-
- // remove from our sorted array
- index = this->searchArray(key);
- SkASSERT(index >= 0);
- // if there are multiple matches searchArray will give us the first match
- // march forward until we find elem.
- while (elem != fSorted[index]) {
- ++index;
- SkASSERT(index < fSorted.count());
- }
- SkASSERT(elem == fSorted[index]);
- fSorted.remove(index);
-}
-
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::deleteAll() {
- fSorted.deleteAll();
- this->clearHash();
-}
-
-#ifdef SK_DEBUG
-template <typename T, typename Key, size_t kHashBits>
-void GrTHashTable<T, Key, kHashBits>::validate() const {
- int count = fSorted.count();
- for (int i = 1; i < count; i++) {
- SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
- Key::Equals(*fSorted[i - 1], *fSorted[i]));
- }
-}
-
-template <typename T, typename Key, size_t kHashBits>
-bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
- int index = fSorted.find(elem);
- return index >= 0;
-}
-
-#endif
-
-#endif
« no previous file with comments | « gyp/tests.gypi ('k') | src/gpu/gl/GrGLProgram.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698