Home | History | Annotate | Download | only in gpu 
      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 
     31     GrTBinHashKey() {
     32         this->reset();
     33     }
     34 
     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 
     44     ~GrTBinHashKey() {
     45     }
     46 
     47     void reset() {
     48         fHash = 0;
     49 #if GR_DEBUG
     50         fIsValid = false;
     51 #endif
     52     }
     53 
     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 
     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 
     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 
     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 
     90     uint32_t getHash() const {
     91         GrAssert(fIsValid);
     92         return fHash;
     93     }
     94 
     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