src/util/hash.h

   1 /*********************                                                        */
   2 /*! \file hash.h
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Morgan Deters, Christopher L. Conway, Paul Meng
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2017 by the authors listed in the file AUTHORS
   8  ** in the top-level source directory) and their institutional affiliations.
   9  ** All rights reserved.  See the file COPYING in the top-level source
  10  ** directory for licensing information.\endverbatim
  11  **
  12  ** \brief [[ Add one-line brief description here ]]
  13  **
  14  ** [[ Add lengthier description here ]]
  15  ** \todo document this file
  16  **/
  17
  18 #include "cvc4_public.h"
  19
  20 #ifndef __CVC4__HASH_H
  21 #define __CVC4__HASH_H
  22
  23 #include <cstdint>
  24 #include <functional>
  25 #include <string>
  26
  27 namespace std {
  28
  29 #ifdef CVC4_NEED_HASH_UINT64_T
  30 // on some versions and architectures of GNU C++, we need a
  31 // specialization of hash for 64-bit values
  32 template <>
  33 struct hash<uint64_t> {
  34   size_t operator()(uint64_t v) const {
  35     return v;
  36   }
  37 };/* struct hash<uint64_t> */
  38 #endif /* CVC4_NEED_HASH_UINT64_T */
  39
  40 }/* std namespace */
  41
  42 namespace CVC4 {
  43
  44 namespace fnv1a {
  45
  46 /**
  47  * FNV-1a hash algorithm for 64-bit numbers.
  48  *
  49  * More details here: http://www.isthe.com/chongo/tech/comp/fnv/index.html
  50  */
  51 inline uint64_t fnv1a_64(uint64_t v, uint64_t hash = 14695981039346656037U) {
  52   hash ^= v;
  53   // Compute (hash * 1099511628211)
  54   return hash + (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
  55          (hash << 8) + (hash << 40);
  56 }
  57
  58 }  // namespace fnv1a
  59
  60 template <class T, class U, class HashT = std::hash<T>, class HashU = std::hash<U> >
  61 struct PairHashFunction {
  62   size_t operator()(const std::pair<T, U>& pr) const {
  63     uint64_t hash = fnv1a::fnv1a_64(HashT()(pr.first));
  64     return static_cast<size_t>(fnv1a::fnv1a_64(HashU()(pr.second), hash));
  65   }
  66 };/* struct PairHashFunction */
  67
  68 }/* CVC4 namespace */
  69
  70 #endif /* __CVC4__HASH_H */