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 GrTHashCache_DEFINED
12#define GrTHashCache_DEFINED
13
14#include "GrTypes.h"
15#include "SkTDArray.h"
16
17// GrTDefaultFindFunctor implements the default find behavior for
18// GrTHashTable (i.e., return the first resource that matches the
19// provided key)
20template <typename T> class GrTDefaultFindFunctor {
21public:
22    // always accept the first element examined
23    bool operator()(const T* elem) const { return true; }
24};
25
26/**
27 *  Key needs
28 *      static bool EQ(const Entry&, const HashKey&);
29 *      static bool LT(const Entry&, const HashKey&);
30 *      uint32_t getHash() const;
31 *
32 *  Allows duplicate key entries but on find you may get
33 *  any of the duplicate entries returned.
34 */
35template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
36public:
37    GrTHashTable() { Gr_bzero(fHash, sizeof(fHash)); }
38    ~GrTHashTable() {}
39
40    int count() const { return fSorted.count(); }
41    T*  find(const Key&) const;
42    template <typename FindFuncType> T*  find(const Key&, const FindFuncType&) const;
43    // return true if key was unique when inserted.
44    bool insert(const Key&, T*);
45    void remove(const Key&, const T*);
46    T* removeAt(int index, uint32_t hash);
47    void removeAll();
48    void deleteAll();
49    void unrefAll();
50
51    /**
52     *  Return the index for the element, using a linear search.
53     */
54    int slowFindIndex(T* elem) const { return fSorted.find(elem); }
55
56#if GR_DEBUG
57    void validate() const;
58    bool contains(T*) const;
59#endif
60
61    // testing
62    const SkTDArray<T*>& getArray() const { return fSorted; }
63private:
64    enum {
65        kHashCount = 1 << kHashBits,
66        kHashMask  = kHashCount - 1
67    };
68    static unsigned hash2Index(uint32_t hash) {
69        hash ^= hash >> 16;
70        if (kHashBits <= 8) {
71            hash ^= hash >> 8;
72        }
73        return hash & kHashMask;
74    }
75
76    mutable T* fHash[kHashCount];
77    SkTDArray<T*> fSorted;
78
79    // search fSorted, and return the found index, or ~index of where it
80    // should be inserted
81    int searchArray(const Key&) const;
82};
83
84///////////////////////////////////////////////////////////////////////////////
85
86template <typename T, typename Key, size_t kHashBits>
87int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
88    int count = fSorted.count();
89    if (0 == count) {
90        // we should insert it at 0
91        return ~0;
92    }
93
94    const T* const* array = fSorted.begin();
95    int high = count - 1;
96    int low = 0;
97    while (high > low) {
98        int index = (low + high) >> 1;
99        if (Key::LT(*array[index], key)) {
100            low = index + 1;
101        } else {
102            high = index;
103        }
104    }
105
106    // check if we found it
107    if (Key::EQ(*array[high], key)) {
108        // above search should have found the first occurrence if there
109        // are multiple.
110        GrAssert(0 == high || Key::LT(*array[high - 1], key));
111        return high;
112    }
113
114    // now return the ~ of where we should insert it
115    if (Key::LT(*array[high], key)) {
116        high += 1;
117    }
118    return ~high;
119}
120
121template <typename T, typename Key, size_t kHashBits>
122T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const {
123    GrTDefaultFindFunctor<T> find;
124
125    return this->find(key, find);
126}
127
128template <typename T, typename Key, size_t kHashBits>
129template <typename FindFuncType>
130T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const {
131
132    int hashIndex = hash2Index(key.getHash());
133    T* elem = fHash[hashIndex];
134
135    if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) {
136        return elem;
137    }
138
139    // bsearch for the key in our sorted array
140    int index = this->searchArray(key);
141    if (index < 0) {
142        return NULL;
143    }
144
145    const T* const* array = fSorted.begin();
146
147    // above search should have found the first occurrence if there
148    // are multiple.
149    GrAssert(0 == index || Key::LT(*array[index - 1], key));
150
151    for ( ; index < count() && Key::EQ(*array[index], key); ++index) {
152        if (findFunc(fSorted[index])) {
153            // update the hash
154            fHash[hashIndex] = fSorted[index];
155            return fSorted[index];
156        }
157    }
158
159    return NULL;
160}
161
162template <typename T, typename Key, size_t kHashBits>
163bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
164    int index = this->searchArray(key);
165    bool first = index < 0;
166    if (first) {
167        // turn it into the actual index
168        index = ~index;
169    }
170    // add it to our array
171    *fSorted.insert(index) = elem;
172    // update our hash table (overwrites any dupe's position in the hash)
173    fHash[hash2Index(key.getHash())] = elem;
174    return first;
175}
176
177template <typename T, typename Key, size_t kHashBits>
178void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
179    int index = hash2Index(key.getHash());
180    if (fHash[index] == elem) {
181        fHash[index] = NULL;
182    }
183
184    // remove from our sorted array
185    index = this->searchArray(key);
186    GrAssert(index >= 0);
187    // if there are multiple matches searchArray will give us the first match
188    // march forward until we find elem.
189    while (elem != fSorted[index]) {
190        ++index;
191        GrAssert(index < fSorted.count());
192    }
193    GrAssert(elem == fSorted[index]);
194    fSorted.remove(index);
195}
196
197template <typename T, typename Key, size_t kHashBits>
198T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) {
199    int hashIndex = hash2Index(hash);
200    if (fHash[hashIndex] == fSorted[elemIndex]) {
201        fHash[hashIndex] = NULL;
202    }
203    // remove from our sorted array
204    T* elem = fSorted[elemIndex];
205    fSorted.remove(elemIndex);
206    return elem;
207}
208
209template <typename T, typename Key, size_t kHashBits>
210void GrTHashTable<T, Key, kHashBits>::removeAll() {
211    fSorted.reset();
212    Gr_bzero(fHash, sizeof(fHash));
213}
214
215template <typename T, typename Key, size_t kHashBits>
216void GrTHashTable<T, Key, kHashBits>::deleteAll() {
217    fSorted.deleteAll();
218    Gr_bzero(fHash, sizeof(fHash));
219}
220
221template <typename T, typename Key, size_t kHashBits>
222void GrTHashTable<T, Key, kHashBits>::unrefAll() {
223    fSorted.unrefAll();
224    Gr_bzero(fHash, sizeof(fHash));
225}
226
227#if GR_DEBUG
228template <typename T, typename Key, size_t kHashBits>
229void GrTHashTable<T, Key, kHashBits>::validate() const {
230    int count = fSorted.count();
231    for (int i = 1; i < count; i++) {
232        GrAssert(Key::LT(*fSorted[i - 1], *fSorted[i]) ||
233                 Key::EQ(*fSorted[i - 1], *fSorted[i]));
234    }
235}
236
237template <typename T, typename Key, size_t kHashBits>
238bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
239    int index = fSorted.find(elem);
240    return index >= 0;
241}
242
243#endif
244
245#endif
246