src/util/hash.h

   1 /*********************                                                        */
   2 /*! \file hash.h
   3  ** \verbatim
   4  ** Top contributors (to current version):
   5  **   Morgan Deters, Andres Noetzli, Mathias Preiner
   6  ** This file is part of the CVC4 project.
   7  ** Copyright (c) 2009-2021 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 <functional>
  24 #include <string>
  25
  26 namespace std {
  27
  28 #ifdef CVC4_NEED_HASH_UINT64_T
  29 // on some versions and architectures of GNU C++, we need a
  30 // specialization of hash for 64-bit values
  31 template <>
  32 struct hash<uint64_t> {
  33   size_t operator()(uint64_t v) const {
  34     return v;
  35   }
  36 };/* struct hash<uint64_t> */
  37 #endif /* CVC4_NEED_HASH_UINT64_T */
  38
  39 }/* std namespace */
  40
  41 namespace cvc5 {
  42
  43 namespace fnv1a {
  44
  45 /**
  46  * FNV-1a hash algorithm for 64-bit numbers.
  47  *
  48  * More details here: http://www.isthe.com/chongo/tech/comp/fnv/index.html
  49  */
  50 inline uint64_t fnv1a_64(uint64_t v, uint64_t hash = 14695981039346656037U) {
  51   hash ^= v;
  52   // Compute (hash * 1099511628211)
  53   return hash + (hash << 1) + (hash << 4) + (hash << 5) + (hash << 7) +
  54          (hash << 8) + (hash << 40);
  55 }
  56
  57 }  // namespace fnv1a
  58
  59 template <class T, class U, class HashT = std::hash<T>, class HashU = std::hash<U> >
  60 struct PairHashFunction {
  61   size_t operator()(const std::pair<T, U>& pr) const {
  62     uint64_t hash = fnv1a::fnv1a_64(HashT()(pr.first));
  63     return static_cast<size_t>(fnv1a::fnv1a_64(HashU()(pr.second), hash));
  64   }
  65 };/* struct PairHashFunction */
  66
  67 }  // namespace cvc5
  68
  69 #endif /* CVC4__HASH_H */