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