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 */
28template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
29public:
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; }
57private:
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
87template <typename T, typename Key, size_t kHashBits>
88int 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
122template <typename T, typename Key, size_t kHashBits>
123template <typename Filter>
124T* 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
156template <typename T, typename Key, size_t kHashBits>
157bool 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
171template <typename T, typename Key, size_t kHashBits>
172void 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
191template <typename T, typename Key, size_t kHashBits>
192void GrTHashTable<T, Key, kHashBits>::deleteAll() {
193    fSorted.deleteAll();
194    this->clearHash();
195}
196
197#ifdef SK_DEBUG
198template <typename T, typename Key, size_t kHashBits>
199void 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
207template <typename T, typename Key, size_t kHashBits>
208bool 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
216