1 2 /* 3 * Copyright 2011 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 10 #ifndef GrBinHashKey_DEFINED 11 #define GrBinHashKey_DEFINED 12 13 #include "GrTypes.h" 14 15 /** 16 * Hash function class that can take a data chunk of any predetermined length. The hash function 17 * used is the One-at-a-Time Hash (http://burtleburtle.net/bob/hash/doobs.html). 18 * 19 * Keys are computed from ENTRY objects. ENTRY must be fully ordered by a member: 20 * int compare(const GrTBinHashKey<ENTRY, ..>& k); 21 * which returns negative if the ENTRY < k, 0 if it equals k, and positive if k < the ENTRY. 22 * Additionally, ENTRY must be flattenable into the key using setKeyData. 23 * 24 * This class satisfies the requirements to be a key for a GrTHashTable. 25 */ 26 template<typename ENTRY, size_t KEY_SIZE> 27 class GrTBinHashKey { 28 public: 29 enum { kKeySize = KEY_SIZE }; 30 GrTBinHashKey()31 GrTBinHashKey() { 32 this->reset(); 33 } 34 GrTBinHashKey(const GrTBinHashKey<ENTRY,KEY_SIZE> & other)35 GrTBinHashKey(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) { 36 *this = other; 37 } 38 39 GrTBinHashKey<ENTRY, KEY_SIZE>& operator=(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) { 40 memcpy(this, &other, sizeof(*this)); 41 return *this; 42 } 43 ~GrTBinHashKey()44 ~GrTBinHashKey() { 45 } 46 reset()47 void reset() { 48 fHash = 0; 49 #if GR_DEBUG 50 fIsValid = false; 51 #endif 52 } 53 setKeyData(const uint32_t * SK_RESTRICT data)54 void setKeyData(const uint32_t* SK_RESTRICT data) { 55 GrAssert(GrIsALIGN4(KEY_SIZE)); 56 memcpy(&fData, data, KEY_SIZE); 57 58 uint32_t hash = 0; 59 size_t len = KEY_SIZE; 60 while (len >= 4) { 61 hash += *data++; 62 hash += (fHash << 10); 63 hash ^= (hash >> 6); 64 len -= 4; 65 } 66 hash += (fHash << 3); 67 hash ^= (fHash >> 11); 68 hash += (fHash << 15); 69 #if GR_DEBUG 70 fIsValid = true; 71 #endif 72 fHash = hash; 73 } 74 compare(const GrTBinHashKey<ENTRY,KEY_SIZE> & key)75 int compare(const GrTBinHashKey<ENTRY, KEY_SIZE>& key) const { 76 GrAssert(fIsValid && key.fIsValid); 77 return memcmp(fData, key.fData, KEY_SIZE); 78 } 79 EQ(const ENTRY & entry,const GrTBinHashKey<ENTRY,KEY_SIZE> & key)80 static bool EQ(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) { 81 GrAssert(key.fIsValid); 82 return 0 == entry.compare(key); 83 } 84 LT(const ENTRY & entry,const GrTBinHashKey<ENTRY,KEY_SIZE> & key)85 static bool LT(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) { 86 GrAssert(key.fIsValid); 87 return entry.compare(key) < 0; 88 } 89 getHash()90 uint32_t getHash() const { 91 GrAssert(fIsValid); 92 return fHash; 93 } 94 getData()95 const uint8_t* getData() const { 96 GrAssert(fIsValid); 97 return fData; 98 } 99 100 private: 101 uint32_t fHash; 102 uint8_t fData[KEY_SIZE]; // Buffer for key storage 103 104 #if GR_DEBUG 105 public: 106 bool fIsValid; 107 #endif 108 }; 109 110 #endif 111