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 "SkTypes.h"
12#include "SkMath.h"
13
14template <typename T,
15          typename Key,
16          const Key& (GetKey)(const T&),
17          uint32_t (Hash)(const Key&),
18          bool (Equal)(const T&, const Key&),
19          int kGrowPercent   = 75,  // Larger -> more memory efficient, but slower.
20          int kShrinkPercent = 25>
21class SkTDynamicHash {
22    static const int kMinCapacity = 4;  // Smallest capacity we allow.
23public:
24    SkTDynamicHash(int initialCapacity=64/sizeof(T*)) {
25        this->reset(SkNextPow2(initialCapacity > kMinCapacity ? initialCapacity : kMinCapacity));
26        SkASSERT(this->validate());
27    }
28
29    ~SkTDynamicHash() {
30        sk_free(fArray);
31    }
32
33    int count() const { return fCount; }
34
35    // Return the entry with this key if we have it, otherwise NULL.
36    T* find(const Key& key) const {
37        int index = this->firstIndex(key);
38        for (int round = 0; round < fCapacity; round++) {
39            T* candidate = fArray[index];
40            if (Empty() == candidate) {
41                return NULL;
42            }
43            if (Deleted() != candidate && Equal(*candidate, key)) {
44                return candidate;
45            }
46            index = this->nextIndex(index, round);
47        }
48        SkASSERT(!"find: should be unreachable");
49        return NULL;
50    }
51
52    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
53    void add(T* newEntry) {
54        SkASSERT(NULL == this->find(GetKey(*newEntry)));
55        this->maybeGrow();
56        SkASSERT(this->validate());
57        this->innerAdd(newEntry);
58        SkASSERT(this->validate());
59    }
60
61    // Remove the entry with this key.  We reqire that an entry with this key is present.
62    void remove(const Key& key) {
63        SkASSERT(NULL != this->find(key));
64        this->innerRemove(key);
65        SkASSERT(this->validate());
66        this->maybeShrink();
67        SkASSERT(this->validate());
68    }
69
70protected:
71    // These methods are used by tests only.
72
73    int capacity() const { return fCapacity; }
74
75    // How many collisions do we go through before finding where this entry should be inserted?
76    int countCollisions(const Key& key) const {
77        int index = this->firstIndex(key);
78        for (int round = 0; round < fCapacity; round++) {
79            const T* candidate = fArray[index];
80            if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
81                return round;
82            }
83            index = this->nextIndex(index, round);
84        }
85        SkASSERT(!"countCollisions: should be unreachable");
86        return -1;
87    }
88
89private:
90    // We have two special values to indicate an empty or deleted entry.
91    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
92    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
93
94    static T** AllocArray(int capacity) {
95        T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity);
96        sk_bzero(array, sizeof(T*) * capacity);  // All cells == Empty().
97        return array;
98    }
99
100    void reset(int capacity) {
101        fCount = 0;
102        fDeleted = 0;
103        fCapacity = capacity;
104        fArray = AllocArray(fCapacity);
105    }
106
107    bool validate() const {
108        #define CHECK(x) SkASSERT((x)); if (!(x)) return false
109
110        // Is capacity sane?
111        CHECK(SkIsPow2(fCapacity));
112        CHECK(fCapacity >= kMinCapacity);
113
114        // Is fCount correct?
115        int count = 0;
116        for (int i = 0; i < fCapacity; i++) {
117            if (Empty() != fArray[i] && Deleted() != fArray[i]) {
118                count++;
119            }
120        }
121        CHECK(count == fCount);
122
123        // Is fDeleted correct?
124        int deleted = 0;
125        for (int i = 0; i < fCapacity; i++) {
126            if (Deleted() == fArray[i]) {
127                deleted++;
128            }
129        }
130        CHECK(deleted == fDeleted);
131
132        // Are all entries findable?
133        for (int i = 0; i < fCapacity; i++) {
134            if (Empty() == fArray[i] || Deleted() == fArray[i]) {
135                continue;
136            }
137            CHECK(NULL != this->find(GetKey(*fArray[i])));
138        }
139
140        // Are all entries unique?
141        for (int i = 0; i < fCapacity; i++) {
142            if (Empty() == fArray[i] || Deleted() == fArray[i]) {
143                continue;
144            }
145            for (int j = i+1; j < fCapacity; j++) {
146                if (Empty() == fArray[j] || Deleted() == fArray[j]) {
147                    continue;
148                }
149                CHECK(fArray[i] != fArray[j]);
150                CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
151                CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
152            }
153        }
154        #undef CHECK
155        return true;
156    }
157
158    void innerAdd(T* newEntry) {
159        const Key& key = GetKey(*newEntry);
160        int index = this->firstIndex(key);
161        for (int round = 0; round < fCapacity; round++) {
162            const T* candidate = fArray[index];
163            if (Empty() == candidate || Deleted() == candidate) {
164                if (Deleted() == candidate) {
165                    fDeleted--;
166                }
167                fCount++;
168                fArray[index] = newEntry;
169                return;
170            }
171            index = this->nextIndex(index, round);
172        }
173        SkASSERT(!"add: should be unreachable");
174    }
175
176    void innerRemove(const Key& key) {
177        const int firstIndex = this->firstIndex(key);
178        int index = firstIndex;
179        for (int round = 0; round < fCapacity; round++) {
180            const T* candidate = fArray[index];
181            if (Deleted() != candidate && Equal(*candidate, key)) {
182                fDeleted++;
183                fCount--;
184                fArray[index] = Deleted();
185                return;
186            }
187            index = this->nextIndex(index, round);
188        }
189        SkASSERT(!"innerRemove: should be unreachable");
190    }
191
192    void maybeGrow() {
193        if (fCount + fDeleted + 1 > (fCapacity * kGrowPercent) / 100) {
194            resize(fCapacity * 2);
195        }
196    }
197
198    void maybeShrink() {
199        if (fCount < (fCapacity * kShrinkPercent) / 100 && fCapacity / 2 > kMinCapacity) {
200            resize(fCapacity / 2);
201        }
202    }
203
204    void resize(int newCapacity) {
205        SkDEBUGCODE(int oldCount = fCount;)
206        int oldCapacity = fCapacity;
207        T** oldArray = fArray;
208
209        reset(newCapacity);
210
211        for (int i = 0; i < oldCapacity; i++) {
212            T* entry = oldArray[i];
213            if (Empty() != entry && Deleted() != entry) {
214                this->add(entry);
215            }
216        }
217        SkASSERT(oldCount == fCount);
218
219        sk_free(oldArray);
220    }
221
222    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
223    uint32_t hashMask() const { return fCapacity - 1; }
224
225    int firstIndex(const Key& key) const {
226        return Hash(key) & this->hashMask();
227    }
228
229    // Given index at round N, what is the index to check at N+1?  round should start at 0.
230    int nextIndex(int index, int round) const {
231        // This will search a power-of-two array fully without repeating an index.
232        return (index + round + 1) & this->hashMask();
233    }
234
235    int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
236    int fDeleted;   // Number of Deleted() entries in fArray.
237    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
238    T** fArray;
239};
240
241#endif
242