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