1/*
2    Copyright 2011 Google Inc.
3
4    Licensed under the Apache License, Version 2.0 (the "License");
5    you may not use this file except in compliance with the License.
6    You may obtain a copy of the License at
7
8         http://www.apache.org/licenses/LICENSE-2.0
9
10    Unless required by applicable law or agreed to in writing, software
11    distributed under the License is distributed on an "AS IS" BASIS,
12    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13    See the License for the specific language governing permissions and
14    limitations under the License.
15 */
16
17#ifndef GrBinHashKey_DEFINED
18#define GrBinHashKey_DEFINED
19
20#include "GrTypes.h"
21
22/**
23 * Abstract base class that presents the building interface of GrBinHashKey.
24 * This base class allows builder methods to not know the exact template
25 * parameters of GrBinHashKey
26 */
27class GrBinHashKeyBuilder {
28public:
29    GrBinHashKeyBuilder() {}
30    virtual ~GrBinHashKeyBuilder() {}
31    virtual void keyData(const uint32_t *dataToAdd, size_t len) = 0;
32};
33
34/**
35 *  Hash function class than can take a data stream of indeterminate length.
36 *  It also has the ability to recieve data in several chunks (steamed). The
37 *  hash function used is the One-at-a-Time Hash
38 *  (http://burtleburtle.net/bob/hash/doobs.html).
39 *
40 *  Keys are built in two passes the first pass builds the key until the
41 *  allocated storage for the key runs out, raw data accumulation stops, but
42 *  the calculation of the 32-bit hash value and total key length continue.
43 *  The second pass is only necessary if storage ran-out during the first pass.
44 *  If that is the case, the heap storage portion of the key will be
45 *  re-allocated so that the entire key can be stored in the second pass.
46 *
47 *  Code for building a key:
48 *
49 *      GrBinHashKey<MyEntryStruct, MyStackSize> MyKey;
50 *      while( MyKey->doPass() )
51 *      {
52 *          MyObject->buildKey(&MyKey); //invoke a builder method
53 *      }
54 *
55 *  All the builder method needs to do is make calls to the keyData method to
56 *  append binary data to the key.
57 */
58template<typename Entry, size_t StackSize>
59class GrBinHashKey : public GrBinHashKeyBuilder {
60public:
61    GrBinHashKey()
62        : fA(0)
63        , fLength(0)
64        , fHeapData(NULL)
65        , fPhysicalSize(StackSize)
66        , fUseHeap(false)
67        , fPass(0)
68#if GR_DEBUG
69        , fIsValid(true)
70#endif
71    {}
72
73private:
74    // Illegal: must choose explicitly between copyAndTakeOwnership
75    // and deepCopyFrom.
76    // Not inheriting GrNoncopyable, because it causes very obscure compiler
77    // errors with template classes, which are hard to trace back to the use
78    // of assignment.
79    GrBinHashKey(const GrBinHashKey<Entry, StackSize>&) {}
80    GrBinHashKey<Entry, StackSize>& operator=(const GrBinHashKey<Entry,
81        StackSize>&) {
82        return this;
83    }
84
85public:
86    void copyAndTakeOwnership(GrBinHashKey<Entry, StackSize>& key) {
87        GrAssert(key.fIsValid);
88        copyFields(key);
89        if (fUseHeap) {
90            key.fHeapData = NULL;  // ownership transfer
91        }
92        // Consistency Checking
93        // To avoid the overhead of copying or ref-counting the dynamically
94        // allocated portion of the key, we use ownership transfer
95        // Key usability is only tracked in debug builds.
96        GR_DEBUGCODE(key.fIsValid = false;)
97    }
98
99    void deepCopyFrom(const GrBinHashKey<Entry, StackSize>& key) {
100        GrAssert(key.fIsValid);
101        copyFields(key);
102        if (fUseHeap) {
103            fHeapData = reinterpret_cast<uint8_t*>(
104                GrMalloc(sizeof(uint8_t) * fPhysicalSize));
105            memcpy(fHeapData, key.fHeapData, fLength);
106        }
107    }
108
109    virtual ~GrBinHashKey() {
110        if (fUseHeap) {
111            GrFree(fHeapData);
112        }
113    }
114
115    bool doPass() {
116        GrAssert(fIsValid);
117        if (0 == fPass) {
118            fPass++;
119            return true;
120        }
121        if (1 == fPass) {
122            bool passNeeded = false;
123            if (fLength > fPhysicalSize) {
124                // If the first pass ran out of space the we need to
125                // re-allocate and perform a second pass
126                GrFree(fHeapData);
127                fHeapData = reinterpret_cast<uint8_t*>(
128                    GrMalloc(sizeof(uint8_t) * fLength));
129                fPhysicalSize = fLength;
130                fUseHeap = true;
131                passNeeded = true;
132                fLength = 0;
133            }
134            fPass++;
135            return passNeeded;
136        }
137        return false;
138    }
139
140    void keyData(const uint32_t *dataToAdd, size_t len) {
141        GrAssert(fIsValid);
142        GrAssert(fPass);
143        GrAssert(GrIsALIGN4(len));
144        if (fUseHeap) {
145            GrAssert(fHeapData);
146            GrAssert(fLength + len <= fPhysicalSize);
147            memcpy(&fHeapData[fLength], dataToAdd, len );
148        } else {
149            if (fLength + len <= StackSize) {
150                memcpy(&fStackData[fLength], dataToAdd, len);
151            } else {
152                GrAssert(1 == fPass);
153            }
154        }
155
156        fLength += len;
157
158        if (1 == fPass) {
159            uint32_t a = fA;
160            while (len >= 4) {
161                a += *dataToAdd++;
162                a += (a << 10);
163                a ^= (a >> 6);
164                len -= 4;
165            }
166            a += (a << 3);
167            a ^= (a >> 11);
168            a += (a << 15);
169
170            fA = a;
171        }
172    }
173
174    int compare(const GrBinHashKey<Entry, StackSize>& key) const {
175        GrAssert(fIsValid);
176        if (fLength == key.fLength) {
177            GrAssert(fUseHeap == key.fUseHeap);
178            if(fUseHeap) {
179                return memcmp(fHeapData, key.fHeapData, fLength);
180            } else {
181                return memcmp(fStackData, key.fStackData, fLength);
182            }
183        }
184
185        return (fLength - key.fLength);
186    }
187
188    static bool
189    EQ(const Entry& entry, const GrBinHashKey<Entry, StackSize>& key) {
190        GrAssert(key.fIsValid);
191        return 0 == entry.compare(key);
192    }
193
194    static bool
195    LT(const Entry& entry, const GrBinHashKey<Entry, StackSize>& key) {
196        GrAssert(key.fIsValid);
197        return entry.compare(key) < 0;
198    }
199
200    uint32_t getHash() const {
201        GrAssert(fIsValid);
202        return fA;
203    }
204
205private:
206    void copyFields(const GrBinHashKey<Entry, StackSize>& src) {
207        if (fUseHeap) {
208            GrFree(fHeapData);
209        }
210        // We do a field-by-field copy because this is a non-POD
211        // class, and therefore memcpy would be bad
212        fA = src.fA;
213        fLength = src.fLength;
214        memcpy(fStackData, src.fStackData, StackSize);
215        fHeapData = src.fHeapData;
216        fPhysicalSize = src.fPhysicalSize;
217        fUseHeap = src.fUseHeap;
218        fPass = src.fPass;
219    }
220
221    uint32_t                fA;
222
223    // For accumulating the variable length binary key
224    size_t              fLength;                // length of data accumulated so far
225    uint8_t             fStackData[StackSize];  //Buffer for key storage
226    uint8_t*            fHeapData;              //Dynamically allocated extended key storage
227    size_t              fPhysicalSize;          //Total size available for key storage
228    bool                fUseHeap;               //Using a dynamically allocated key storage
229    int                 fPass;                  //Key generation pass counter
230
231#if GR_DEBUG
232public:
233    bool                fIsValid;
234#endif
235};
236
237#endif
238