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(NULL) {
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    int count() const { return fCount; }
61
62    // Return the entry with this key if we have it, otherwise NULL.
63    T* find(const Key& key) const {
64        int index = this->firstIndex(key);
65        for (int round = 0; round < fCapacity; round++) {
66            T* candidate = fArray[index];
67            if (Empty() == candidate) {
68                return NULL;
69            }
70            if (Deleted() != candidate && GetKey(*candidate) == key) {
71                return candidate;
72            }
73            index = this->nextIndex(index, round);
74        }
75        SkASSERT(fCapacity == 0);
76        return NULL;
77    }
78
79    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
80    void add(T* newEntry) {
81        SkASSERT(NULL == this->find(GetKey(*newEntry)));
82        this->maybeGrow();
83        this->innerAdd(newEntry);
84        SkASSERT(this->validate());
85    }
86
87    // Remove the entry with this key.  We reqire that an entry with this key is present.
88    void remove(const Key& key) {
89        SkASSERT(NULL != this->find(key));
90        this->innerRemove(key);
91        SkASSERT(this->validate());
92    }
93
94protected:
95    // These methods are used by tests only.
96
97    int capacity() const { return fCapacity; }
98
99    // How many collisions do we go through before finding where this entry should be inserted?
100    int countCollisions(const Key& key) const {
101        int index = this->firstIndex(key);
102        for (int round = 0; round < fCapacity; round++) {
103            const T* candidate = fArray[index];
104            if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
105                return round;
106            }
107            index = this->nextIndex(index, round);
108        }
109        SkASSERT(fCapacity == 0);
110        return 0;
111    }
112
113private:
114    // We have two special values to indicate an empty or deleted entry.
115    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
116    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
117
118    bool validate() const {
119        #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
120        static const int kLarge = 50;  // Arbitrary, tweak to suit your patience.
121
122        // O(1) checks, always done.
123        // Is capacity sane?
124        SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
125
126        // O(N) checks, skipped when very large.
127        if (fCount < kLarge * kLarge) {
128            // Are fCount and fDeleted correct, and are all elements findable?
129            int count = 0, deleted = 0;
130            for (int i = 0; i < fCapacity; i++) {
131                if (Deleted() == fArray[i]) {
132                    deleted++;
133                } else if (Empty() != fArray[i]) {
134                    count++;
135                    SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])));
136                }
137            }
138            SKTDYNAMICHASH_CHECK(count == fCount);
139            SKTDYNAMICHASH_CHECK(deleted == fDeleted);
140        }
141
142        // O(N^2) checks, skipped when large.
143        if (fCount < kLarge) {
144            // Are all entries unique?
145            for (int i = 0; i < fCapacity; i++) {
146                if (Empty() == fArray[i] || Deleted() == fArray[i]) {
147                    continue;
148                }
149                for (int j = i+1; j < fCapacity; j++) {
150                    if (Empty() == fArray[j] || Deleted() == fArray[j]) {
151                        continue;
152                    }
153                    SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
154                    SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
155                }
156            }
157        }
158        #undef SKTDYNAMICHASH_CHECK
159        return true;
160    }
161
162    void innerAdd(T* newEntry) {
163        const Key& key = GetKey(*newEntry);
164        int index = this->firstIndex(key);
165        for (int round = 0; round < fCapacity; round++) {
166            const T* candidate = fArray[index];
167            if (Empty() == candidate || Deleted() == candidate) {
168                if (Deleted() == candidate) {
169                    fDeleted--;
170                }
171                fCount++;
172                fArray[index] = newEntry;
173                return;
174            }
175            index = this->nextIndex(index, round);
176        }
177        SkASSERT(fCapacity == 0);
178    }
179
180    void innerRemove(const Key& key) {
181        const int firstIndex = this->firstIndex(key);
182        int index = firstIndex;
183        for (int round = 0; round < fCapacity; round++) {
184            const T* candidate = fArray[index];
185            if (Deleted() != candidate && GetKey(*candidate) == key) {
186                fDeleted++;
187                fCount--;
188                fArray[index] = Deleted();
189                return;
190            }
191            index = this->nextIndex(index, round);
192        }
193        SkASSERT(fCapacity == 0);
194    }
195
196    void maybeGrow() {
197        if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
198            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
199        }
200    }
201
202    void resize(int newCapacity) {
203        SkDEBUGCODE(int oldCount = fCount;)
204        int oldCapacity = fCapacity;
205        SkAutoTMalloc<T*> oldArray(fArray);
206
207        fCount = fDeleted = 0;
208        fCapacity = newCapacity;
209        fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
210
211        for (int i = 0; i < oldCapacity; i++) {
212            T* entry = oldArray[i];
213            if (Empty() != entry && Deleted() != entry) {
214                this->innerAdd(entry);
215            }
216        }
217        SkASSERT(oldCount == fCount);
218    }
219
220    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
221    uint32_t hashMask() const { return fCapacity - 1; }
222
223    int firstIndex(const Key& key) const {
224        return Hash(key) & this->hashMask();
225    }
226
227    // Given index at round N, what is the index to check at N+1?  round should start at 0.
228    int nextIndex(int index, int round) const {
229        // This will search a power-of-two array fully without repeating an index.
230        return (index + round + 1) & this->hashMask();
231    }
232
233    static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
234    static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
235
236    int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
237    int fDeleted;   // Number of Deleted() entries in fArray.
238    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
239    T** fArray;
240};
241
242#endif
243