michael@0: 
michael@0: /*
michael@0:  * Copyright 2010 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: 
michael@0: #ifndef GrTHashTable_DEFINED
michael@0: #define GrTHashTable_DEFINED
michael@0: 
michael@0: #include "GrTypes.h"
michael@0: #include "SkTDArray.h"
michael@0: 
michael@0: /**
michael@0:  *  Key needs
michael@0:  *      static bool Equals(const Entry&, const Key&);
michael@0:  *      static bool LessThan(const Entry&, const Key&);
michael@0:  *      static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
michael@0:  *      static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
michael@0:  *      uint32_t getHash() const;
michael@0:  *
michael@0:  *  Allows duplicate key entries but on find you may get
michael@0:  *  any of the duplicate entries returned.
michael@0:  */
michael@0: template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
michael@0: public:
michael@0:     GrTHashTable() { this->clearHash(); }
michael@0:     ~GrTHashTable() {}
michael@0: 
michael@0:     int count() const { return fSorted.count(); }
michael@0: 
michael@0:     struct Any {
michael@0:         // Return the first resource that matches the key.
michael@0:         bool operator()(const T*) const { return true; }
michael@0:     };
michael@0: 
michael@0:     T* find(const Key& key) const { return this->find(key, Any()); }
michael@0:     template <typename Filter> T* find(const Key&, Filter filter) const;
michael@0: 
michael@0:     // return true if key was unique when inserted.
michael@0:     bool insert(const Key&, T*);
michael@0:     void remove(const Key&, const T*);
michael@0: 
michael@0:     void deleteAll();
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     void validate() const;
michael@0:     bool contains(T*) const;
michael@0: #endif
michael@0: 
michael@0:     // testing
michael@0:     const SkTDArray<T*>& getArray() const { return fSorted; }
michael@0:     SkTDArray<T*>& getArray() { return fSorted; }
michael@0: private:
michael@0:     void clearHash() { sk_bzero(fHash, sizeof(fHash)); }
michael@0: 
michael@0:     enum {
michael@0:         kHashCount = 1 << kHashBits,
michael@0:         kHashMask  = kHashCount - 1
michael@0:     };
michael@0:     static unsigned hash2Index(uint32_t hash) {
michael@0:         hash ^= hash >> 16;
michael@0:         if (kHashBits <= 8) {
michael@0:             hash ^= hash >> 8;
michael@0:         }
michael@0:         return hash & kHashMask;
michael@0:     }
michael@0: 
michael@0:     mutable T* fHash[kHashCount];
michael@0:     SkTDArray<T*> fSorted;
michael@0: 
michael@0:     // search fSorted, and return the found index, or ~index of where it
michael@0:     // should be inserted
michael@0:     int searchArray(const Key&) const;
michael@0: };
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
michael@0:     int count = fSorted.count();
michael@0:     if (0 == count) {
michael@0:         // we should insert it at 0
michael@0:         return ~0;
michael@0:     }
michael@0: 
michael@0:     const T* const* array = fSorted.begin();
michael@0:     int high = count - 1;
michael@0:     int low = 0;
michael@0:     while (high > low) {
michael@0:         int index = (low + high) >> 1;
michael@0:         if (Key::LessThan(*array[index], key)) {
michael@0:             low = index + 1;
michael@0:         } else {
michael@0:             high = index;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // check if we found it
michael@0:     if (Key::Equals(*array[high], key)) {
michael@0:         // above search should have found the first occurrence if there
michael@0:         // are multiple.
michael@0:         SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
michael@0:         return high;
michael@0:     }
michael@0: 
michael@0:     // now return the ~ of where we should insert it
michael@0:     if (Key::LessThan(*array[high], key)) {
michael@0:         high += 1;
michael@0:     }
michael@0:     return ~high;
michael@0: }
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: template <typename Filter>
michael@0: T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const {
michael@0: 
michael@0:     int hashIndex = hash2Index(key.getHash());
michael@0:     T* elem = fHash[hashIndex];
michael@0: 
michael@0:     if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
michael@0:         return elem;
michael@0:     }
michael@0: 
michael@0:     // bsearch for the key in our sorted array
michael@0:     int index = this->searchArray(key);
michael@0:     if (index < 0) {
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     const T* const* array = fSorted.begin();
michael@0: 
michael@0:     // above search should have found the first occurrence if there
michael@0:     // are multiple.
michael@0:     SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
michael@0: 
michael@0:     for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
michael@0:         if (filter(fSorted[index])) {
michael@0:             // update the hash
michael@0:             fHash[hashIndex] = fSorted[index];
michael@0:             return fSorted[index];
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
michael@0:     int index = this->searchArray(key);
michael@0:     bool first = index < 0;
michael@0:     if (first) {
michael@0:         // turn it into the actual index
michael@0:         index = ~index;
michael@0:     }
michael@0:     // add it to our array
michael@0:     *fSorted.insert(index) = elem;
michael@0:     // update our hash table (overwrites any dupe's position in the hash)
michael@0:     fHash[hash2Index(key.getHash())] = elem;
michael@0:     return first;
michael@0: }
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
michael@0:     int index = hash2Index(key.getHash());
michael@0:     if (fHash[index] == elem) {
michael@0:         fHash[index] = NULL;
michael@0:     }
michael@0: 
michael@0:     // remove from our sorted array
michael@0:     index = this->searchArray(key);
michael@0:     SkASSERT(index >= 0);
michael@0:     // if there are multiple matches searchArray will give us the first match
michael@0:     // march forward until we find elem.
michael@0:     while (elem != fSorted[index]) {
michael@0:         ++index;
michael@0:         SkASSERT(index < fSorted.count());
michael@0:     }
michael@0:     SkASSERT(elem == fSorted[index]);
michael@0:     fSorted.remove(index);
michael@0: }
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: void GrTHashTable<T, Key, kHashBits>::deleteAll() {
michael@0:     fSorted.deleteAll();
michael@0:     this->clearHash();
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: void GrTHashTable<T, Key, kHashBits>::validate() const {
michael@0:     int count = fSorted.count();
michael@0:     for (int i = 1; i < count; i++) {
michael@0:         SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
michael@0:                  Key::Equals(*fSorted[i - 1], *fSorted[i]));
michael@0:     }
michael@0: }
michael@0: 
michael@0: template <typename T, typename Key, size_t kHashBits>
michael@0: bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
michael@0:     int index = fSorted.find(elem);
michael@0:     return index >= 0;
michael@0: }
michael@0: 
michael@0: #endif
michael@0: 
michael@0: #endif