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 #include <cstring>
  23
  24 namespace llvm {
  25
  26 /// Class to compute a hash value from multiple data fields of arbitrary
  27 /// types. Note that if you are hashing a single data type, such as a
  28 /// string, it may be cheaper to use a hash algorithm that is tailored
  29 /// for that specific data type.
  30 /// Typical Usage:
  31 ///    GeneralHash Hash;
  32 ///    Hash.add(someValue);
  33 ///    Hash.add(someOtherValue);
  34 ///    return Hash.finish();
  35 /// Adapted from MurmurHash2 by Austin Appleby
  36 class GeneralHash {
  37 private:
  38   enum {
  39     M = 0x5bd1e995
  40   };
  41   unsigned Hash;
  42   unsigned Count;
  43 public:
  44   GeneralHash(unsigned Seed = 0) : Hash(Seed), Count(0) {}
  45
  46   /// Add a pointer value.
  47   /// Note: this adds pointers to the hash using sizes and endianness that
  48   /// depend on the host.  It doesn't matter however, because hashing on
  49   /// pointer values is inherently unstable.
  50   template<typename T>
  51   GeneralHash& add(const T *PtrVal) {
  52     addBits(&PtrVal, &PtrVal + 1);
  53     return *this;
  54   }
  55
  56   /// Add an ArrayRef of arbitrary data.
  57   template<typename T>
  58   GeneralHash& add(ArrayRef<T> ArrayVal) {
  59     addBits(ArrayVal.begin(), ArrayVal.end());
  60     return *this;
  61   }
  62
  63   /// Add a string
  64   GeneralHash& add(StringRef StrVal) {
  65     addBits(StrVal.begin(), StrVal.end());
  66     return *this;
  67   }
  68
  69   /// Add an signed 32-bit integer.
  70   GeneralHash& add(int32_t Data) {
  71     addInt(uint32_t(Data));
  72     return *this;
  73   }
  74
  75   /// Add an unsigned 32-bit integer.
  76   GeneralHash& add(uint32_t Data) {
  77     addInt(Data);
  78     return *this;
  79   }
  80
  81   /// Add an signed 64-bit integer.
  82   GeneralHash& add(int64_t Data) {
  83     addInt(uint64_t(Data));
  84     return *this;
  85   }
  86
  87   /// Add an unsigned 64-bit integer.
  88   GeneralHash& add(uint64_t Data) {
  89     addInt(Data);
  90     return *this;
  91   }
  92
  93   /// Add a float
  94   GeneralHash& add(float Data) {
  95     union {
  96       float D; uint32_t I;
  97     };
  98     D = Data;
  99     addInt(I);
 100     return *this;
 101   }
 102
 103   /// Add a double
 104   GeneralHash& add(double Data) {
 105     union {
 106       double D; uint64_t I;
 107     };
 108     D = Data;
 109     addInt(I);
 110     return *this;
 111   }
 112
 113   // Do a few final mixes of the hash to ensure the last few
 114   // bytes are well-incorporated.
 115   unsigned finish() {
 116     mix(Count);
 117     Hash ^= Hash >> 13;
 118     Hash *= M;
 119     Hash ^= Hash >> 15;
 120     return Hash;
 121   }
 122
 123 private:
 124   void mix(uint32_t Data) {
 125     ++Count;
 126     Data *= M;
 127     Data ^= Data >> 24;
 128     Data *= M;
 129     Hash *= M;
 130     Hash ^= Data;
 131   }
 132
 133   // Add a single uint32 value
 134   void addInt(uint32_t Val) {
 135     mix(Val);
 136   }
 137
 138   // Add a uint64 value
 139   void addInt(uint64_t Val) {
 140     mix(uint32_t(Val >> 32));
 141     mix(uint32_t(Val));
 142   }
 143
 144   // Add a range of bytes from I to E.
 145   template<bool ElementsHaveEvenLength>
 146   void addBytes(const char *I, const char *E) {
 147     uint32_t Data;
 148     // Note that aliasing rules forbid us from dereferencing
 149     // reinterpret_cast<uint32_t *>(I) even if I happens to be suitably
 150     // aligned, so we use memcpy instead.
 151     for (; E - I >= ptrdiff_t(sizeof Data); I += sizeof Data) {
 152       // A clever compiler should be able to turn this memcpy into a single
 153       // aligned or unaligned load (depending on the alignment of the type T
 154       // that was used in the call to addBits).
 155       std::memcpy(&Data, I, sizeof Data);
 156       mix(Data);
 157     }
 158     if (!ElementsHaveEvenLength && I != E) {
 159       Data = 0;
 160       std::memcpy(&Data, I, E - I);
 161       mix(Data);
 162     }
 163   }
 164
 165   // Add a range of bits from I to E.
 166   template<typename T>
 167   void addBits(const T *I, const T *E) {
 168     addBytes<sizeof (T) % sizeof (uint32_t) == 0>(
 169       reinterpret_cast<const char *>(I),
 170       reinterpret_cast<const char *>(E));
 171   }
 172 };
 173
 174 } // end namespace llvm
 175
 176 #endif