SkTDynamicHash.h revision f916f9e7cf4403846c413acf8fec403e38cd8451 
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&)>
19class SkTDynamicHash {
20public:
21    SkTDynamicHash(int initialCapacity=64/sizeof(T*))
22    : fCount(0)
23    , fCapacity(SkNextPow2(initialCapacity > 0 ? initialCapacity : 1))
24    , fArray(AllocArray(fCapacity)) {}
25
26    ~SkTDynamicHash() {
27        sk_free(fArray);
28    }
29
30    int count() const { return fCount; }
31
32    // Return the entry with this key if we have it, otherwise NULL.
33    T* find(const Key& key) const {
34        int index = this->firstIndex(key);
35        for (int round = 0; round < fCapacity; round++) {
36            T* candidate = fArray[index];
37            if (candidate == Empty()) {
38                return NULL;
39            }
40            if (candidate != Deleted() && Equal(*candidate, key)) {
41                return candidate;
42            }
43            index = this->nextIndex(index, round);
44        }
45        SkASSERT(!"find: should be unreachable");
46        return NULL;
47    }
48
49    // Add an entry with this key.
50    void add(T* newEntry) {
51        this->maybeGrow();
52
53        const Key& key = GetKey(*newEntry);
54        int index = this->firstIndex(key);
55        for (int round = 0; round < fCapacity; round++) {
56            T* candidate = fArray[index];
57            if (candidate == Empty() || candidate == Deleted()) {
58                fArray[index] = newEntry;
59                fCount++;
60                return;
61            }
62            if (Equal(*candidate, key)) {
63                fArray[index] = newEntry;
64                return;
65            }
66            index = this->nextIndex(index, round);
67        }
68        SkASSERT(!"add: should be unreachable");
69    }
70
71    // Remove entry with this key, if we have it.
72    void remove(const Key& key) {
73        this->innerRemove(key);
74        this->maybeShrink();
75    }
76
77protected:
78    // These methods are used by tests only.
79
80    int capacity() const { return fCapacity; }
81
82    // How many collisions do we go through before finding where this entry should be inserted?
83    int countCollisions(const Key& key) const {
84        int index = this->firstIndex(key);
85        for (int round = 0; round < fCapacity; round++) {
86            const T* candidate = fArray[index];
87            if (candidate == Empty() || candidate == Deleted() || Equal(*candidate, key)) {
88                return round;
89            }
90            index = this->nextIndex(index, round);
91        }
92        SkASSERT(!"countCollisions: should be unreachable");
93        return -1;
94    }
95
96private:
97    // We have two special values to indicate an empty or deleted entry.
98    static const T* Empty()   { return reinterpret_cast<const T*>(0); }  // i.e. NULL
99    static const T* Deleted() { return reinterpret_cast<const T*>(1); }  // Also an invalid pointer.
100
101    static T** AllocArray(int capacity) {
102        T** array = (T**)sk_malloc_throw(sizeof(T*) * capacity);
103        sk_bzero(array, sizeof(T*) * capacity);  // All cells == Empty().
104        return array;
105    }
106
107    void innerRemove(const Key& key) {
108        int index = this->firstIndex(key);
109        for (int round = 0; round < fCapacity; round++) {
110            const T* candidate = fArray[index];
111            if (candidate == Empty()) {
112                return;
113            }
114            if (candidate != Deleted() && Equal(*candidate, key)) {
115                fArray[index] = const_cast<T*>(Deleted());
116                fCount--;
117                return;
118            }
119            index = this->nextIndex(index, round);
120        }
121        SkASSERT(!"innerRemove: should be unreachable");
122    }
123
124    void maybeGrow() {
125        if (fCount < fCapacity / 2) {
126            return;
127        }
128
129        SkDEBUGCODE(int oldCount = fCount;)
130        int oldCapacity = fCapacity;
131        T** oldArray = fArray;
132
133        fCount = 0;
134        fCapacity *= 2;
135        fArray = AllocArray(fCapacity);
136
137        for (int i = 0; i < oldCapacity; i++) {
138            T* entry = oldArray[i];
139            if (entry != Empty() && entry != Deleted()) {
140                this->add(entry);
141            }
142        }
143        SkASSERT(oldCount == fCount);
144
145        sk_free(oldArray);
146    }
147
148    void maybeShrink() {
149        // TODO
150    }
151
152    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
153    uint32_t hashMask() const { return fCapacity - 1; }
154
155    int firstIndex(const Key& key) const {
156        return Hash(key) & this->hashMask();
157    }
158
159    // Given index at round N, what is the index to check at N+1?  round should start at 0.
160    int nextIndex(int index, int round) const {
161        // This will search a power-of-two array fully without repeating an index.
162        return (index + round + 1) & this->hashMask();
163    }
164
165    int fCount;     // Number of non-empty, non-deleted entries in fArray.
166    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
167    T** fArray;
168};
169
170#endif
171