epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 2 | /* |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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. |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 7 | */ |
| 8 | |
epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 9 | |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 10 | #ifndef GrBinHashKey_DEFINED |
| 11 | #define GrBinHashKey_DEFINED |
| 12 | |
| 13 | #include "GrTypes.h" |
| 14 | |
| 15 | /** |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 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 | * |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 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. |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 23 | * |
| 24 | * This class satisfies the requirements to be a key for a GrTHashTable. |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 25 | */ |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 26 | template<typename ENTRY, size_t KEY_SIZE> |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 27 | class GrTBinHashKey { |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 28 | public: |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 29 | enum { kKeySize = KEY_SIZE }; |
| 30 | |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 31 | GrTBinHashKey() { |
| 32 | this->reset(); |
| 33 | } |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 34 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 35 | GrTBinHashKey(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) { |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 36 | *this = other; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 37 | } |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 38 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 39 | GrTBinHashKey<ENTRY, KEY_SIZE>& operator=(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) { |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 40 | memcpy(this, &other, sizeof(*this)); |
| 41 | return *this; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 42 | } |
| 43 | |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 44 | ~GrTBinHashKey() { |
| 45 | } |
| 46 | |
| 47 | void reset() { |
| 48 | fHash = 0; |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 49 | #ifdef SK_DEBUG |
bsalomon@google.com | 9ba4fa6 | 2012-07-16 17:36:28 +0000 | [diff] [blame] | 50 | fIsValid = false; |
| 51 | #endif |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 52 | } |
| 53 | |
bsalomon@google.com | 6b5fdc1 | 2011-12-12 22:35:18 +0000 | [diff] [blame] | 54 | void setKeyData(const uint32_t* SK_RESTRICT data) { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 55 | SkASSERT(GrIsALIGN4(KEY_SIZE)); |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 56 | memcpy(&fData, data, KEY_SIZE); |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 57 | |
bsalomon@google.com | 6b5fdc1 | 2011-12-12 22:35:18 +0000 | [diff] [blame] | 58 | uint32_t hash = 0; |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 59 | size_t len = KEY_SIZE; |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 60 | while (len >= 4) { |
bsalomon@google.com | 6b5fdc1 | 2011-12-12 22:35:18 +0000 | [diff] [blame] | 61 | hash += *data++; |
| 62 | hash += (fHash << 10); |
| 63 | hash ^= (hash >> 6); |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 64 | len -= 4; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 65 | } |
bsalomon@google.com | 6b5fdc1 | 2011-12-12 22:35:18 +0000 | [diff] [blame] | 66 | hash += (fHash << 3); |
| 67 | hash ^= (fHash >> 11); |
| 68 | hash += (fHash << 15); |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 69 | #ifdef SK_DEBUG |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 70 | fIsValid = true; |
| 71 | #endif |
bsalomon@google.com | 6b5fdc1 | 2011-12-12 22:35:18 +0000 | [diff] [blame] | 72 | fHash = hash; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 73 | } |
| 74 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 75 | int compare(const GrTBinHashKey<ENTRY, KEY_SIZE>& key) const { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 76 | SkASSERT(fIsValid && key.fIsValid); |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 77 | return memcmp(fData, key.fData, KEY_SIZE); |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 78 | } |
| 79 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 80 | static bool EQ(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 81 | SkASSERT(key.fIsValid); |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 82 | return 0 == entry.compare(key); |
| 83 | } |
tomhudson@google.com | 0d3f1fb | 2011-06-01 19:27:31 +0000 | [diff] [blame] | 84 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 85 | static bool LT(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 86 | SkASSERT(key.fIsValid); |
tomhudson@google.com | 0d3f1fb | 2011-06-01 19:27:31 +0000 | [diff] [blame] | 87 | return entry.compare(key) < 0; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 88 | } |
| 89 | |
| 90 | uint32_t getHash() const { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 91 | SkASSERT(fIsValid); |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 92 | return fHash; |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 93 | } |
| 94 | |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 95 | const uint8_t* getData() const { |
tfarina@chromium.org | f6de475 | 2013-08-17 00:02:59 +0000 | [diff] [blame] | 96 | SkASSERT(fIsValid); |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 97 | return fData; |
| 98 | } |
| 99 | |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 100 | private: |
junov@google.com | f7c00f6 | 2011-08-18 18:15:16 +0000 | [diff] [blame] | 101 | uint32_t fHash; |
bsalomon@google.com | 0797c2c | 2012-12-20 15:13:01 +0000 | [diff] [blame] | 102 | uint8_t fData[KEY_SIZE]; // Buffer for key storage |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 103 | |
commit-bot@chromium.org | 515dcd3 | 2013-08-28 14:17:03 +0000 | [diff] [blame] | 104 | #ifdef SK_DEBUG |
junov@google.com | f93e717 | 2011-03-31 21:26:24 +0000 | [diff] [blame] | 105 | public: |
| 106 | bool fIsValid; |
| 107 | #endif |
| 108 | }; |
| 109 | |
| 110 | #endif |