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 */ 27 class GrBinHashKeyBuilder { 28 public: GrBinHashKeyBuilder()29 GrBinHashKeyBuilder() {} ~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 */ 58 template<typename Entry, size_t StackSize> 59 class GrBinHashKey : public GrBinHashKeyBuilder { 60 public: GrBinHashKey()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 73 private: 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. GrBinHashKey(const GrBinHashKey<Entry,StackSize> &)79 GrBinHashKey(const GrBinHashKey<Entry, StackSize>&) {} 80 GrBinHashKey<Entry, StackSize>& operator=(const GrBinHashKey<Entry, 81 StackSize>&) { 82 return this; 83 } 84 85 public: copyAndTakeOwnership(GrBinHashKey<Entry,StackSize> & key)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 deepCopyFrom(const GrBinHashKey<Entry,StackSize> & key)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 ~GrBinHashKey()109 virtual ~GrBinHashKey() { 110 if (fUseHeap) { 111 GrFree(fHeapData); 112 } 113 } 114 doPass()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 keyData(const uint32_t * dataToAdd,size_t len)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 compare(const GrBinHashKey<Entry,StackSize> & key)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 EQ(const Entry & entry,const GrBinHashKey<Entry,StackSize> & key)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 LT(const Entry & entry,const GrBinHashKey<Entry,StackSize> & key)195 LT(const Entry& entry, const GrBinHashKey<Entry, StackSize>& key) { 196 GrAssert(key.fIsValid); 197 return entry.compare(key) < 0; 198 } 199 getHash()200 uint32_t getHash() const { 201 GrAssert(fIsValid); 202 return fA; 203 } 204 205 private: copyFields(const GrBinHashKey<Entry,StackSize> & src)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 232 public: 233 bool fIsValid; 234 #endif 235 }; 236 237 #endif 238