include/llvm/ADT/Hashing.h

   1 //===-- llvm/ADT/Hashing.h - Utilities for hashing --------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines utilities for computing hash values for various data types.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_ADT_HASHING_H
  15 #define LLVM_ADT_HASHING_H
  16
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/Support/AlignOf.h"
  20 #include "llvm/Support/Compiler.h"
  21 #include "llvm/Support/DataTypes.h"
  22
  23 namespace llvm {
  24
  25 /// Class to compute a hash value from multiple data fields of arbitrary
  26 /// types. Note that if you are hashing a single data type, such as a
  27 /// string, it may be cheaper to use a hash algorithm that is tailored
  28 /// for that specific data type.
  29 /// Typical Usage:
  30 ///    GeneralHash Hash;
  31 ///    Hash.add(someValue);
  32 ///    Hash.add(someOtherValue);
  33 ///    return Hash.finish();
  34 /// Adapted from MurmurHash2 by Austin Appleby
  35 class GeneralHash {
  36 private:
  37   enum {
  38     M = 0x5bd1e995
  39   };
  40   unsigned Hash;
  41   unsigned Count;
  42 public:
  43   GeneralHash(unsigned Seed = 0) : Hash(Seed), Count(0) {}
  44
  45   /// Add a pointer value.
  46   /// Note: this adds pointers to the hash using sizes and endianness that
  47   /// depend on the host.  It doesn't matter however, because hashing on
  48   /// pointer values is inherently unstable.
  49   template<typename T>
  50   GeneralHash& add(const T *PtrVal) {
  51     addBits(&PtrVal, &PtrVal + 1);
  52     return *this;
  53   }
  54
  55   /// Add an ArrayRef of arbitrary data.
  56   template<typename T>
  57   GeneralHash& add(ArrayRef<T> ArrayVal) {
  58     addBits(ArrayVal.begin(), ArrayVal.end());
  59     return *this;
  60   }
  61
  62   /// Add a string
  63   GeneralHash& add(StringRef StrVal) {
  64     addBits(StrVal.begin(), StrVal.end());
  65     return *this;
  66   }
  67
  68   /// Add an signed 32-bit integer.
  69   GeneralHash& add(int32_t Data) {
  70     addInt(uint32_t(Data));
  71     return *this;
  72   }
  73
  74   /// Add an unsigned 32-bit integer.
  75   GeneralHash& add(uint32_t Data) {
  76     addInt(Data);
  77     return *this;
  78   }
  79
  80   /// Add an signed 64-bit integer.
  81   GeneralHash& add(int64_t Data) {
  82     addInt(uint64_t(Data));
  83     return *this;
  84   }
  85
  86   /// Add an unsigned 64-bit integer.
  87   GeneralHash& add(uint64_t Data) {
  88     addInt(Data);
  89     return *this;
  90   }
  91
  92   /// Add a float
  93   GeneralHash& add(float Data) {
  94     union {
  95       float D; uint32_t I;
  96     };
  97     D = Data;
  98     addInt(I);
  99     return *this;
 100   }
 101
 102   /// Add a double
 103   GeneralHash& add(double Data) {
 104     union {
 105       double D; uint64_t I;
 106     };
 107     D = Data;
 108     addInt(I);
 109     return *this;
 110   }
 111
 112   // Do a few final mixes of the hash to ensure the last few
 113   // bytes are well-incorporated.
 114   unsigned finish() {
 115     mix(Count);
 116     Hash ^= Hash >> 13;
 117     Hash *= M;
 118     Hash ^= Hash >> 15;
 119     return Hash;
 120   }
 121
 122 private:
 123   void mix(uint32_t Data) {
 124     ++Count;
 125     Data *= M;
 126     Data ^= Data >> 24;
 127     Data *= M;
 128     Hash *= M;
 129     Hash ^= Data;
 130   }
 131
 132   // Add a single uint32 value
 133   void addInt(uint32_t Val) {
 134     mix(Val);
 135   }
 136
 137   // Add a uint64 value
 138   void addInt(uint64_t Val) {
 139     mix(uint32_t(Val >> 32));
 140     mix(uint32_t(Val));
 141   }
 142
 143   template<typename T, bool isAligned>
 144   struct addBitsImpl {
 145     static void add(GeneralHash &Hash, const T *I, const T *E) {
 146       Hash.addUnaligned(
 147         reinterpret_cast<const uint8_t *>(I),
 148         reinterpret_cast<const uint8_t *>(E));
 149     }
 150   };
 151
 152   template<typename T>
 153   struct addBitsImpl<T, true> {
 154     static void add(GeneralHash &Hash, const T *I, const T *E) {
 155       Hash.addAligned(
 156         reinterpret_cast<const uint32_t *>(I),
 157         reinterpret_cast<const uint32_t *>(E));
 158     }
 159   };
 160
 161   // Add a range of bits from I to E.
 162   template<typename T>
 163   void addBits(const T *I, const T *E) {
 164     addBitsImpl<T, AlignOf<T>::Alignment_GreaterEqual_4Bytes>::add(*this, I, E);
 165   }
 166
 167   // Add a range of uint32s
 168   void addAligned(const uint32_t *I, const uint32_t *E) {
 169     while (I < E) {
 170       mix(*I++);
 171     }
 172   }
 173
 174   // Add a possibly unaligned sequence of bytes.
 175   void addUnaligned(const uint8_t *I, const uint8_t *E);
 176 };
 177
 178 } // end namespace llvm
 179
 180 #endif