1/*
2 * Copyright 2013 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#ifndef SkTDynamicHash_DEFINED
9#define SkTDynamicHash_DEFINED
10
11#include "SkMath.h"
12#include "SkTemplates.h"
13#include "SkTypes.h"
14
15// Traits requires:
16//   static const Key& GetKey(const T&) { ... }
17//   static uint32_t Hash(const Key&) { ... }
18// We'll look on T for these by default, or you can pass a custom Traits type.
19template <typename T,
20          typename Key,
21          typename Traits = T,
22          int kGrowPercent = 75>  // Larger -> more memory efficient, but slower.
23class SkTDynamicHash {
24public:
25    SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
26        SkASSERT(this->validate());
27    }
28
29    ~SkTDynamicHash() {
30        sk_free(fArray);
31    }
32
33    class Iter {
34    public:
35        explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
36            SkASSERT(hash);
37            ++(*this);
38        }
39        bool done() const {
40            SkASSERT(fCurrentIndex <= fHash->fCapacity);
41            return fCurrentIndex == fHash->fCapacity;
42        }
43        T& operator*() const {
44            SkASSERT(!this->done());
45            return *this->current();
46        }
47        void operator++() {
48            do {
49                fCurrentIndex++;
50            } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
51        }
52
53    private:
54        T* current() const { return fHash->fArray[fCurrentIndex]; }
55
56        SkTDynamicHash* fHash;
57        int fCurrentIndex;
58    };
59
60    class ConstIter {
61    public:
62        explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
63            SkASSERT(hash);
64            ++(*this);
65        }
66        bool done() const {
67            SkASSERT(fCurrentIndex <= fHash->fCapacity);
68            return fCurrentIndex == fHash->fCapacity;
69        }
70        const T& operator*() const {
71            SkASSERT(!this->done());
72            return *this->current();
73        }
74        void operator++() {
75            do {
76                fCurrentIndex++;
77            } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
78        }
79
80    private:
81        const T* current() const { return fHash->fArray[fCurrentIndex]; }
82
83        const SkTDynamicHash* fHash;
84        int fCurrentIndex;
85    };
86
87    int count() const { return fCount; }
88
89    // Return the entry with this key if we have it, otherwise nullptr.
90    T* find(const Key& key) const {
91        int index = this->firstIndex(key);
92        for (int round = 0; round < fCapacity; round++) {
93            SkASSERT(index >= 0 && index < fCapacity);
94            T* candidate = fArray[index];
95            if (Empty() == candidate) {
96                return nullptr;
97            }
98            if (Deleted() != candidate && GetKey(*candidate) == key) {
99                return candidate;
100            }
101            index = this->nextIndex(index, round);
102        }
103        SkASSERT(fCapacity == 0);
104        return nullptr;
105    }
106
107    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
108    void add(T* newEntry) {
109        SkASSERT(nullptr == this->find(GetKey(*newEntry)));
110        this->maybeGrow();
111        this->innerAdd(newEntry);
112        SkASSERT(this->validate());
113    }
114
115    // Remove the entry with this key.  We require that an entry with this key is present.
116    void remove(const Key& key) {
117        SkASSERT(this->find(key));
118        this->innerRemove(key);
119        SkASSERT(this->validate());
120    }
121
122    void rewind() {
123        if (fArray) {
124            sk_bzero(fArray, sizeof(T*)* fCapacity);
125        }
126        fCount = 0;
127        fDeleted = 0;
128    }
129
130    void reset() {
131        fCount = 0;
132        fDeleted = 0;
133        fCapacity = 0;
134        sk_free(fArray);
135        fArray = nullptr;
136    }
137
138protected:
139    // These methods are used by tests only.
140
141    int capacity() const { return fCapacity; }
142
143    // How many collisions do we go through before finding where this entry should be inserted?
144    int countCollisions(const Key& key) const {
145        int index = this->firstIndex(key);
146        for (int round = 0; round < fCapacity; round++) {
147            SkASSERT(index >= 0 && index < fCapacity);
148            const T* candidate = fArray[index];
149            if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
150                return round;
151            }
152            index = this->nextIndex(index, round);
153        }
154        SkASSERT(fCapacity == 0);
155        return 0;
156    }
157
158private:
159    // We have two special values to indicate an empty or deleted entry.
160    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. nullptr
161    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
162
163    bool validate() const {
164        #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false
165        static const int kLarge = 50;  // Arbitrary, tweak to suit your patience.
166
167        // O(1) checks, always done.
168        // Is capacity sane?
169        SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
170
171        // O(N) checks, skipped when very large.
172        if (fCount < kLarge * kLarge) {
173            // Are fCount and fDeleted correct, and are all elements findable?
174            int count = 0, deleted = 0;
175            for (int i = 0; i < fCapacity; i++) {
176                if (Deleted() == fArray[i]) {
177                    deleted++;
178                } else if (Empty() != fArray[i]) {
179                    count++;
180                    SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
181                }
182            }
183            SKTDYNAMICHASH_CHECK(count == fCount);
184            SKTDYNAMICHASH_CHECK(deleted == fDeleted);
185        }
186
187        // O(N^2) checks, skipped when large.
188        if (fCount < kLarge) {
189            // Are all entries unique?
190            for (int i = 0; i < fCapacity; i++) {
191                if (Empty() == fArray[i] || Deleted() == fArray[i]) {
192                    continue;
193                }
194                for (int j = i+1; j < fCapacity; j++) {
195                    if (Empty() == fArray[j] || Deleted() == fArray[j]) {
196                        continue;
197                    }
198                    SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
199                    SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
200                }
201            }
202        }
203        #undef SKTDYNAMICHASH_CHECK
204        return true;
205    }
206
207    void innerAdd(T* newEntry) {
208        const Key& key = GetKey(*newEntry);
209        int index = this->firstIndex(key);
210        for (int round = 0; round < fCapacity; round++) {
211            SkASSERT(index >= 0 && index < fCapacity);
212            const T* candidate = fArray[index];
213            if (Empty() == candidate || Deleted() == candidate) {
214                if (Deleted() == candidate) {
215                    fDeleted--;
216                }
217                fCount++;
218                fArray[index] = newEntry;
219                return;
220            }
221            index = this->nextIndex(index, round);
222        }
223        SkASSERT(fCapacity == 0);
224    }
225
226    void innerRemove(const Key& key) {
227        const int firstIndex = this->firstIndex(key);
228        int index = firstIndex;
229        for (int round = 0; round < fCapacity; round++) {
230            SkASSERT(index >= 0 && index < fCapacity);
231            const T* candidate = fArray[index];
232            if (Deleted() != candidate && GetKey(*candidate) == key) {
233                fDeleted++;
234                fCount--;
235                fArray[index] = Deleted();
236                return;
237            }
238            index = this->nextIndex(index, round);
239        }
240        SkASSERT(fCapacity == 0);
241    }
242
243    void maybeGrow() {
244        if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
245            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
246        }
247    }
248
249    void resize(int newCapacity) {
250        SkDEBUGCODE(int oldCount = fCount;)
251        int oldCapacity = fCapacity;
252        SkAutoTMalloc<T*> oldArray(fArray);
253
254        fCount = fDeleted = 0;
255        fCapacity = newCapacity;
256        fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
257
258        for (int i = 0; i < oldCapacity; i++) {
259            T* entry = oldArray[i];
260            if (Empty() != entry && Deleted() != entry) {
261                this->innerAdd(entry);
262            }
263        }
264        SkASSERT(oldCount == fCount);
265    }
266
267    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
268    uint32_t hashMask() const { return fCapacity - 1; }
269
270    int firstIndex(const Key& key) const {
271        return Hash(key) & this->hashMask();
272    }
273
274    // Given index at round N, what is the index to check at N+1?  round should start at 0.
275    int nextIndex(int index, int round) const {
276        // This will search a power-of-two array fully without repeating an index.
277        return (index + round + 1) & this->hashMask();
278    }
279
280    static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
281    static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
282
283    int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
284    int fDeleted;   // Number of Deleted() entries in fArray.
285    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
286    T** fArray;
287};
288
289#endif
290