/* * 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(uint32_t hash) { 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