src/third_party/skia/src/gpu/GrTHashTable.h

   1
   2 /*
   3  * Copyright 2010 Google Inc.
   4  *
   5  * Use of this source code is governed by a BSD-style license that can be
   6  * found in the LICENSE file.
   7  */
   8
   9
  10
  11 #ifndef GrTHashTable_DEFINED
  12 #define GrTHashTable_DEFINED
  13
  14 #include "GrTypes.h"
  15 #include "SkTDArray.h"
  16
  17 /**
  18  *  Key needs
  19  *      static bool Equals(const Entry&, const Key&);
  20  *      static bool LessThan(const Entry&, const Key&);
  21  *      static bool Equals(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
  22  *      static bool LessThan(const Entry&, const Entry&); for SK_DEBUG if GrTHashTable::validate() is called
  23  *      uint32_t getHash() const;
  24  *
  25  *  Allows duplicate key entries but on find you may get
  26  *  any of the duplicate entries returned.
  27  */
  28 template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
  29 public:
  30     GrTHashTable() { this->clearHash(); }
  31     ~GrTHashTable() {}
  32
  33     int count() const { return fSorted.count(); }
  34
  35     struct Any {
  36         // Return the first resource that matches the key.
  37         bool operator()(const T*) const { return true; }
  38     };
  39
  40     T* find(const Key& key) const { return this->find(key, Any()); }
  41     template <typename Filter> T* find(const Key&, Filter filter) const;
  42
  43     // return true if key was unique when inserted.
  44     bool insert(const Key&, T*);
  45     void remove(const Key&, const T*);
  46
  47     void deleteAll();
  48
  49 #ifdef SK_DEBUG
  50     void validate() const;
  51     bool contains(T*) const;
  52 #endif
  53
  54     // testing
  55     const SkTDArray<T*>& getArray() const { return fSorted; }
  56     SkTDArray<T*>& getArray() { return fSorted; }
  57 private:
  58     void clearHash() { sk_bzero(fHash, sizeof(fHash)); }
  59
  60     enum {
  61         kHashCount = 1 << kHashBits,
  62         kHashMask  = kHashCount - 1
  63     };
  64     static unsigned hash2Index(intptr_t hash) {
  65 #if 0
  66         if (sizeof(hash) == 8) {
  67             hash ^= hash >> 32;
  68         }
  69 #endif
  70         hash ^= hash >> 16;
  71         if (kHashBits <= 8) {
  72             hash ^= hash >> 8;
  73         }
  74         return hash & kHashMask;
  75     }
  76
  77     mutable T* fHash[kHashCount];
  78     SkTDArray<T*> fSorted;
  79
  80     // search fSorted, and return the found index, or ~index of where it
  81     // should be inserted
  82     int searchArray(const Key&) const;
  83 };
  84
  85 ///////////////////////////////////////////////////////////////////////////////
  86
  87 template <typename T, typename Key, size_t kHashBits>
  88 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
  89     int count = fSorted.count();
  90     if (0 == count) {
  91         // we should insert it at 0
  92         return ~0;
  93     }
  94
  95     const T* const* array = fSorted.begin();
  96     int high = count - 1;
  97     int low = 0;
  98     while (high > low) {
  99         int index = (low + high) >> 1;
 100         if (Key::LessThan(*array[index], key)) {
 101             low = index + 1;
 102         } else {
 103             high = index;
 104         }
 105     }
 106
 107     // check if we found it
 108     if (Key::Equals(*array[high], key)) {
 109         // above search should have found the first occurrence if there
 110         // are multiple.
 111         SkASSERT(0 == high || Key::LessThan(*array[high - 1], key));
 112         return high;
 113     }
 114
 115     // now return the ~ of where we should insert it
 116     if (Key::LessThan(*array[high], key)) {
 117         high += 1;
 118     }
 119     return ~high;
 120 }
 121
 122 template <typename T, typename Key, size_t kHashBits>
 123 template <typename Filter>
 124 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, Filter filter) const {
 125
 126     int hashIndex = hash2Index(key.getHash());
 127     T* elem = fHash[hashIndex];
 128
 129     if (NULL != elem && Key::Equals(*elem, key) && filter(elem)) {
 130         return elem;
 131     }
 132
 133     // bsearch for the key in our sorted array
 134     int index = this->searchArray(key);
 135     if (index < 0) {
 136         return NULL;
 137     }
 138
 139     const T* const* array = fSorted.begin();
 140
 141     // above search should have found the first occurrence if there
 142     // are multiple.
 143     SkASSERT(0 == index || Key::LessThan(*array[index - 1], key));
 144
 145     for ( ; index < count() && Key::Equals(*array[index], key); ++index) {
 146         if (filter(fSorted[index])) {
 147             // update the hash
 148             fHash[hashIndex] = fSorted[index];
 149             return fSorted[index];
 150         }
 151     }
 152
 153     return NULL;
 154 }
 155
 156 template <typename T, typename Key, size_t kHashBits>
 157 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
 158     int index = this->searchArray(key);
 159     bool first = index < 0;
 160     if (first) {
 161         // turn it into the actual index
 162         index = ~index;
 163     }
 164     // add it to our array
 165     *fSorted.insert(index) = elem;
 166     // update our hash table (overwrites any dupe's position in the hash)
 167     fHash[hash2Index(key.getHash())] = elem;
 168     return first;
 169 }
 170
 171 template <typename T, typename Key, size_t kHashBits>
 172 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
 173     int index = hash2Index(key.getHash());
 174     if (fHash[index] == elem) {
 175         fHash[index] = NULL;
 176     }
 177
 178     // remove from our sorted array
 179     index = this->searchArray(key);
 180     SkASSERT(index >= 0);
 181     // if there are multiple matches searchArray will give us the first match
 182     // march forward until we find elem.
 183     while (elem != fSorted[index]) {
 184         ++index;
 185         SkASSERT(index < fSorted.count());
 186     }
 187     SkASSERT(elem == fSorted[index]);
 188     fSorted.remove(index);
 189 }
 190
 191 template <typename T, typename Key, size_t kHashBits>
 192 void GrTHashTable<T, Key, kHashBits>::deleteAll() {
 193     fSorted.deleteAll();
 194     this->clearHash();
 195 }
 196
 197 #ifdef SK_DEBUG
 198 template <typename T, typename Key, size_t kHashBits>
 199 void GrTHashTable<T, Key, kHashBits>::validate() const {
 200     int count = fSorted.count();
 201     for (int i = 1; i < count; i++) {
 202         SkASSERT(Key::LessThan(*fSorted[i - 1], *fSorted[i]) ||
 203                  Key::Equals(*fSorted[i - 1], *fSorted[i]));
 204     }
 205 }
 206
 207 template <typename T, typename Key, size_t kHashBits>
 208 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
 209     int index = fSorted.find(elem);
 210     return index >= 0;
 211 }
 212
 213 #endif
 214
 215 #endif