src/third_party/skia/src/gpu/GrBinHashKey.h

   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 "SkChecksum.h"
  14 #include "GrTypes.h"
  15
  16 /**
  17  *  GrMurmur3HashKey is a hash key class that can take a data chunk of any predetermined
  18  *  length. It uses the Murmur3 hash function. It is intended to be used with
  19  *  SkTDynamicHash (where GrBinHashKey is for GrTHashTable).
  20  */
  21 template<size_t KEY_SIZE_IN_BYTES>
  22 class GrMurmur3HashKey {
  23 public:
  24     GrMurmur3HashKey() {
  25         this->reset();
  26     }
  27
  28     void reset() {
  29         fHash = 0;
  30 #ifdef SK_DEBUG
  31         fIsValid = false;
  32 #endif
  33     }
  34
  35     void setKeyData(const uint32_t* data) {
  36         SK_COMPILE_ASSERT(KEY_SIZE_IN_BYTES % 4 == 0, key_size_mismatch);
  37         memcpy(fData, data, KEY_SIZE_IN_BYTES);
  38
  39         fHash = SkChecksum::Murmur3(fData, KEY_SIZE_IN_BYTES);
  40 #ifdef SK_DEBUG
  41         fIsValid = true;
  42 #endif
  43     }
  44
  45     bool operator==(const GrMurmur3HashKey& other) const {
  46         if (fHash != other.fHash) {
  47             return false;
  48         }
  49
  50         return !memcmp(fData, other.fData, KEY_SIZE_IN_BYTES);
  51     }
  52
  53     uint32_t getHash() const {
  54         SkASSERT(fIsValid);
  55         return fHash;
  56     }
  57
  58     const uint8_t* getData() const {
  59         SkASSERT(fIsValid);
  60         return reinterpret_cast<const uint8_t*>(fData);
  61     }
  62
  63 private:
  64     uint32_t fHash;
  65     uint32_t fData[KEY_SIZE_IN_BYTES / sizeof(uint32_t)];  // Buffer for key storage.
  66
  67 #ifdef SK_DEBUG
  68 public:
  69     bool                fIsValid;
  70 #endif
  71 };
  72
  73 /**
  74  *  GrBinHashKey is a hash key class that can take a data chunk of any predetermined
  75  *  length. The hash function used is the One-at-a-Time Hash
  76  *  (http://burtleburtle.net/bob/hash/doobs.html).
  77  */
  78 template<size_t KEY_SIZE>
  79 class GrBinHashKey {
  80 public:
  81     enum { kKeySize = KEY_SIZE };
  82
  83     GrBinHashKey() {
  84         this->reset();
  85     }
  86
  87     void reset() {
  88         fHash = 0;
  89 #ifdef SK_DEBUG
  90         fIsValid = false;
  91 #endif
  92     }
  93
  94     void setKeyData(const uint32_t* SK_RESTRICT data) {
  95         SK_COMPILE_ASSERT(KEY_SIZE % 4 == 0, key_size_mismatch);
  96         memcpy(&fData, data, KEY_SIZE);
  97
  98         uint32_t hash = 0;
  99         size_t len = KEY_SIZE;
 100         while (len >= 4) {
 101             hash += *data++;
 102             hash += (hash << 10);
 103             hash ^= (hash >> 6);
 104             len -= 4;
 105         }
 106         hash += (hash << 3);
 107         hash ^= (hash >> 11);
 108         hash += (hash << 15);
 109 #ifdef SK_DEBUG
 110         fIsValid = true;
 111 #endif
 112         fHash = hash;
 113     }
 114
 115     bool operator==(const GrBinHashKey<KEY_SIZE>& key) const {
 116         SkASSERT(fIsValid && key.fIsValid);
 117         if (fHash != key.fHash) {
 118             return false;
 119         }
 120         for (size_t i = 0; i < SK_ARRAY_COUNT(fData); ++i) {
 121             if (fData[i] != key.fData[i]) {
 122                 return false;
 123             }
 124         }
 125         return true;
 126     }
 127
 128     bool operator<(const GrBinHashKey<KEY_SIZE>& key) const {
 129         SkASSERT(fIsValid && key.fIsValid);
 130         for (size_t i = 0; i < SK_ARRAY_COUNT(fData); ++i) {
 131             if (fData[i] < key.fData[i]) {
 132                 return true;
 133             } else if (fData[i] > key.fData[i]) {
 134                 return false;
 135             }
 136         }
 137         return false;
 138     }
 139
 140     uint32_t getHash() const {
 141         SkASSERT(fIsValid);
 142         return fHash;
 143     }
 144
 145     const uint8_t* getData() const {
 146         SkASSERT(fIsValid);
 147         return reinterpret_cast<const uint8_t*>(fData);
 148     }
 149
 150 private:
 151     uint32_t            fHash;
 152     uint32_t            fData[KEY_SIZE / sizeof(uint32_t)];  // Buffer for key storage.
 153
 154 #ifdef SK_DEBUG
 155 public:
 156     bool                fIsValid;
 157 #endif
 158 };
 159
 160 #endif