Home | History | Annotate | Download | only in include 
      1 /*
      2     Copyright 2010 Google Inc.
      3 
      4     Licensed under the Apache License, Version 2.0 (the "License");
      5     you may not use this file except in compliance with the License.
      6     You may obtain a copy of the License at
      7 
      8          http://www.apache.org/licenses/LICENSE-2.0
      9 
     10     Unless required by applicable law or agreed to in writing, software
     11     distributed under the License is distributed on an "AS IS" BASIS,
     12     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13     See the License for the specific language governing permissions and
     14     limitations under the License.
     15  */
     16 
     17 
     18 #ifndef GrTHashCache_DEFINED
     19 #define GrTHashCache_DEFINED
     20 
     21 #include "GrTDArray.h"
     22 
     23 /**
     24  *  Key needs
     25  *      static bool EQ(const Entry&, const HashKey&);
     26  *      static bool LT(const Entry&, const HashKey&);
     27  *      uint32_t getHash() const;
     28  *
     29  *  Allows duplicate key entries but on find you may get
     30  *  any of the duplicate entries returned.
     31  */
     32 template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
     33 public:
     34     GrTHashTable() { Gr_bzero(fHash, sizeof(fHash)); }
     35     ~GrTHashTable() {}
     36 
     37     int count() const { return fSorted.count(); }
     38     T*  find(const Key&) const;
     39     // return true if key was unique when inserted.
     40     bool insert(const Key&, T*);
     41     void remove(const Key&, const T*);
     42     T* removeAt(int index, uint32_t hash);
     43     void removeAll();
     44     void deleteAll();
     45     void unrefAll();
     46 
     47     /**
     48      *  Return the index for the element, using a linear search.
     49      */
     50     int slowFindIndex(T* elem) const { return fSorted.find(elem); }
     51 
     52 #if GR_DEBUG
     53     void validate() const;
     54     bool contains(T*) const;
     55 #endif
     56 
     57     // testing
     58     const GrTDArray<T*>& getArray() const { return fSorted; }
     59 private:
     60     enum {
     61         kHashCount = 1 << kHashBits,
     62         kHashMask  = kHashCount - 1
     63     };
     64     static unsigned hash2Index(uint32_t hash) {
     65         hash ^= hash >> 16;
     66         if (kHashBits <= 8) {
     67             hash ^= hash >> 8;
     68         }
     69         return hash & kHashMask;
     70     }
     71 
     72     mutable T* fHash[kHashCount];
     73     GrTDArray<T*> fSorted;
     74 
     75     // search fSorted, and return the found index, or ~index of where it
     76     // should be inserted
     77     int searchArray(const Key&) const;
     78 };
     79 
     80 ///////////////////////////////////////////////////////////////////////////////
     81 
     82 template <typename T, typename Key, size_t kHashBits>
     83 int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
     84     int count = fSorted.count();
     85     if (0 == count) {
     86         // we should insert it at 0
     87         return ~0;
     88     }
     89 
     90     const T* const* array = fSorted.begin();
     91     int high = count - 1;
     92     int low = 0;
     93     while (high > low) {
     94         int index = (low + high) >> 1;
     95         if (Key::LT(*array[index], key)) {
     96             low = index + 1;
     97         } else {
     98             high = index;
     99         }
    100     }
    101 
    102     // check if we found it
    103     if (Key::EQ(*array[high], key)) {
    104         // above search should have found the first occurrence if there
    105         // are multiple.
    106         GrAssert(0 == high || Key::LT(*array[high - 1], key));
    107         return high;
    108     }
    109 
    110     // now return the ~ of where we should insert it
    111     if (Key::LT(*array[high], key)) {
    112         high += 1;
    113     }
    114     return ~high;
    115 }
    116 
    117 template <typename T, typename Key, size_t kHashBits>
    118 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const {
    119     int hashIndex = hash2Index(key.getHash());
    120     T* elem = fHash[hashIndex];
    121 
    122     if (NULL == elem || !Key::EQ(*elem, key)) {
    123         // bsearch for the key in our sorted array
    124         int index = this->searchArray(key);
    125         if (index < 0) {
    126             return NULL;
    127         }
    128         elem = fSorted[index];
    129         // update the hash
    130         fHash[hashIndex] = elem;
    131     }
    132     return elem;
    133 }
    134 
    135 template <typename T, typename Key, size_t kHashBits>
    136 bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
    137     int index = this->searchArray(key);
    138     bool first = index < 0;
    139     if (first) {
    140         // turn it into the actual index
    141         index = ~index;
    142     }
    143     // add it to our array
    144     *fSorted.insert(index) = elem;
    145     // update our hash table (overwrites any dupe's position in the hash)
    146     fHash[hash2Index(key.getHash())] = elem;
    147     return first;
    148 }
    149 
    150 template <typename T, typename Key, size_t kHashBits>
    151 void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
    152     int index = hash2Index(key.getHash());
    153     if (fHash[index] == elem) {
    154         fHash[index] = NULL;
    155     }
    156 
    157     // remove from our sorted array
    158     index = this->searchArray(key);
    159     GrAssert(index >= 0);
    160     // if there are multiple matches searchArray will give us the first match
    161     // march forward until we find elem.
    162     while (elem != fSorted[index]) {
    163         ++index;
    164         GrAssert(index < fSorted.count());
    165     }
    166     GrAssert(elem == fSorted[index]);
    167     fSorted.remove(index);
    168 }
    169 
    170 template <typename T, typename Key, size_t kHashBits>
    171 T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) {
    172     int hashIndex = hash2Index(hash);
    173     if (fHash[hashIndex] == fSorted[elemIndex]) {
    174         fHash[hashIndex] = NULL;
    175     }
    176     // remove from our sorted array
    177     T* elem = fSorted[elemIndex];
    178     fSorted.remove(elemIndex);
    179     return elem;
    180 }
    181 
    182 template <typename T, typename Key, size_t kHashBits>
    183 void GrTHashTable<T, Key, kHashBits>::removeAll() {
    184     fSorted.reset();
    185     Gr_bzero(fHash, sizeof(fHash));
    186 }
    187 
    188 template <typename T, typename Key, size_t kHashBits>
    189 void GrTHashTable<T, Key, kHashBits>::deleteAll() {
    190     fSorted.deleteAll();
    191     Gr_bzero(fHash, sizeof(fHash));
    192 }
    193 
    194 template <typename T, typename Key, size_t kHashBits>
    195 void GrTHashTable<T, Key, kHashBits>::unrefAll() {
    196     fSorted.unrefAll();
    197     Gr_bzero(fHash, sizeof(fHash));
    198 }
    199 
    200 #if GR_DEBUG
    201 template <typename T, typename Key, size_t kHashBits>
    202 void GrTHashTable<T, Key, kHashBits>::validate() const {
    203     for (size_t i = 0; i < GR_ARRAY_COUNT(fHash); i++) {
    204         if (fHash[i]) {
    205             unsigned hashIndex = hash2Index(Key::GetHash(*fHash[i]));
    206             GrAssert(hashIndex == i);
    207         }
    208     }
    209 
    210     int count = fSorted.count();
    211     for (int i = 1; i < count; i++) {
    212         GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) ||
    213                  Key::EQ(*fSorted[i - 1], *fSorted[i]));
    214     }
    215 }
    216 
    217 template <typename T, typename Key, size_t kHashBits>
    218 bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
    219     int index = fSorted.find(elem);
    220     return index >= 0;
    221 }
    222 
    223 #endif
    224 
    225 #endif
    226 
    227