blob: 7d4aa0fbe8de9af48289a3b32c2cc9574bfafdb0 [file] [log] [blame]
epoger@google.comec3ed6a2011-07-28 14:26:00 +00001
junov@google.comf93e7172011-03-31 21:26:24 +00002/*
epoger@google.comec3ed6a2011-07-28 14:26:00 +00003 * 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.comf93e7172011-03-31 21:26:24 +00007 */
8
epoger@google.comec3ed6a2011-07-28 14:26:00 +00009
junov@google.comf93e7172011-03-31 21:26:24 +000010#ifndef GrBinHashKey_DEFINED
11#define GrBinHashKey_DEFINED
12
13#include "GrTypes.h"
14
15/**
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000016 * 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.com0797c2c2012-12-20 15:13:01 +000019 * 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.com9ba4fa62012-07-16 17:36:28 +000023 *
24 * This class satisfies the requirements to be a key for a GrTHashTable.
junov@google.comf93e7172011-03-31 21:26:24 +000025 */
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000026template<typename ENTRY, size_t KEY_SIZE>
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000027class GrTBinHashKey {
junov@google.comf93e7172011-03-31 21:26:24 +000028public:
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000029 enum { kKeySize = KEY_SIZE };
30
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000031 GrTBinHashKey() {
32 this->reset();
33 }
junov@google.comf93e7172011-03-31 21:26:24 +000034
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000035 GrTBinHashKey(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) {
junov@google.comf7c00f62011-08-18 18:15:16 +000036 *this = other;
junov@google.comf93e7172011-03-31 21:26:24 +000037 }
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000038
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000039 GrTBinHashKey<ENTRY, KEY_SIZE>& operator=(const GrTBinHashKey<ENTRY, KEY_SIZE>& other) {
junov@google.comf7c00f62011-08-18 18:15:16 +000040 memcpy(this, &other, sizeof(*this));
41 return *this;
junov@google.comf93e7172011-03-31 21:26:24 +000042 }
43
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000044 ~GrTBinHashKey() {
45 }
46
47 void reset() {
48 fHash = 0;
commit-bot@chromium.org515dcd32013-08-28 14:17:03 +000049#ifdef SK_DEBUG
bsalomon@google.com9ba4fa62012-07-16 17:36:28 +000050 fIsValid = false;
51#endif
junov@google.comf93e7172011-03-31 21:26:24 +000052 }
53
bsalomon@google.com6b5fdc12011-12-12 22:35:18 +000054 void setKeyData(const uint32_t* SK_RESTRICT data) {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000055 SkASSERT(GrIsALIGN4(KEY_SIZE));
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000056 memcpy(&fData, data, KEY_SIZE);
junov@google.comf7c00f62011-08-18 18:15:16 +000057
bsalomon@google.com6b5fdc12011-12-12 22:35:18 +000058 uint32_t hash = 0;
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000059 size_t len = KEY_SIZE;
junov@google.comf7c00f62011-08-18 18:15:16 +000060 while (len >= 4) {
bsalomon@google.com6b5fdc12011-12-12 22:35:18 +000061 hash += *data++;
62 hash += (fHash << 10);
63 hash ^= (hash >> 6);
junov@google.comf7c00f62011-08-18 18:15:16 +000064 len -= 4;
junov@google.comf93e7172011-03-31 21:26:24 +000065 }
bsalomon@google.com6b5fdc12011-12-12 22:35:18 +000066 hash += (fHash << 3);
67 hash ^= (fHash >> 11);
68 hash += (fHash << 15);
commit-bot@chromium.org515dcd32013-08-28 14:17:03 +000069#ifdef SK_DEBUG
junov@google.comf7c00f62011-08-18 18:15:16 +000070 fIsValid = true;
71#endif
bsalomon@google.com6b5fdc12011-12-12 22:35:18 +000072 fHash = hash;
junov@google.comf93e7172011-03-31 21:26:24 +000073 }
74
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000075 int compare(const GrTBinHashKey<ENTRY, KEY_SIZE>& key) const {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000076 SkASSERT(fIsValid && key.fIsValid);
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000077 return memcmp(fData, key.fData, KEY_SIZE);
junov@google.comf93e7172011-03-31 21:26:24 +000078 }
79
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000080 static bool EQ(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000081 SkASSERT(key.fIsValid);
junov@google.comf93e7172011-03-31 21:26:24 +000082 return 0 == entry.compare(key);
83 }
tomhudson@google.com0d3f1fb2011-06-01 19:27:31 +000084
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000085 static bool LT(const ENTRY& entry, const GrTBinHashKey<ENTRY, KEY_SIZE>& key) {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000086 SkASSERT(key.fIsValid);
tomhudson@google.com0d3f1fb2011-06-01 19:27:31 +000087 return entry.compare(key) < 0;
junov@google.comf93e7172011-03-31 21:26:24 +000088 }
89
90 uint32_t getHash() const {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000091 SkASSERT(fIsValid);
junov@google.comf7c00f62011-08-18 18:15:16 +000092 return fHash;
junov@google.comf93e7172011-03-31 21:26:24 +000093 }
94
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000095 const uint8_t* getData() const {
tfarina@chromium.orgf6de4752013-08-17 00:02:59 +000096 SkASSERT(fIsValid);
bsalomon@google.com0797c2c2012-12-20 15:13:01 +000097 return fData;
98 }
99
junov@google.comf93e7172011-03-31 21:26:24 +0000100private:
junov@google.comf7c00f62011-08-18 18:15:16 +0000101 uint32_t fHash;
bsalomon@google.com0797c2c2012-12-20 15:13:01 +0000102 uint8_t fData[KEY_SIZE]; // Buffer for key storage
junov@google.comf93e7172011-03-31 21:26:24 +0000103
commit-bot@chromium.org515dcd32013-08-28 14:17:03 +0000104#ifdef SK_DEBUG
junov@google.comf93e7172011-03-31 21:26:24 +0000105public:
106 bool fIsValid;
107#endif
108};
109
110#endif