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