functional.h 8.38 KB
Newer Older
1 2 3 4 5 6 7
// Copyright 2014 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_BASE_FUNCTIONAL_H_
#define V8_BASE_FUNCTIONAL_H_

8 9 10
#include <stddef.h>
#include <stdint.h>

11
#include <cstddef>
12
#include <cstring>
13 14 15
#include <functional>
#include <utility>

16
#include "src/base/base-export.h"
17 18 19 20 21 22 23 24 25 26 27
#include "src/base/macros.h"

namespace v8 {
namespace base {

// base::hash is an implementation of the hash function object specified by
// C++11. It was designed to be compatible with std::hash (in C++11) and
// boost:hash (which in turn is based on the hash function object specified by
// the Draft Technical Report on C++ Library Extensions (TR1)).
//
// base::hash is implemented by calling the hash_value function. The namespace
28
// isn't specified so that it can detect overloads via argument dependent
29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
// lookup. So if there is a free function hash_value in the same namespace as a
// custom type, it will get called.
//
// If users are asked to implement a hash function for their own types with no
// guidance, they generally write bad hash functions. Instead, we provide  a
// simple function base::hash_combine to pass hash-relevant member variables
// into, in order to define a decent hash function. base::hash_combine is
// declared as:
//
//   template<typename T, typename... Ts>
//   size_t hash_combine(const T& v, const Ts& ...vs);
//
// Consider the following example:
//
//   namespace v8 {
//   namespace bar {
//     struct Point { int x; int y; };
//     size_t hash_value(Point const& p) {
//       return base::hash_combine(p.x, p.y);
//     }
//   }
//
//   namespace foo {
//     void DoSomeWork(bar::Point const& p) {
//       base::hash<bar::Point> h;
//       ...
//       size_t hash_code = h(p);  // calls bar::hash_value(Point const&)
//       ...
//     }
//   }
//   }
//
// Based on the "Hashing User-Defined Types in C++1y" proposal from Jeffrey
// Yasskin and Chandler Carruth, see
// http://www.open-std.org/Jtc1/sc22/wg21/docs/papers/2012/n3333.html.

template <typename>
struct hash;


69 70
V8_INLINE size_t hash_combine() { return 0u; }
V8_INLINE size_t hash_combine(size_t seed) { return seed; }
71
V8_BASE_EXPORT size_t hash_combine(size_t seed, size_t value);
72
template <typename T, typename... Ts>
73
V8_INLINE size_t hash_combine(T const& v, Ts const&... vs) {
74 75 76 77 78 79 80 81 82 83 84
  return hash_combine(hash_combine(vs...), hash<T>()(v));
}


template <typename Iterator>
V8_INLINE size_t hash_range(Iterator first, Iterator last) {
  size_t seed = 0;
  for (; first != last; ++first) {
    seed = hash_combine(seed, *first);
  }
  return seed;
85 86 87 88
}


#define V8_BASE_HASH_VALUE_TRIVIAL(type) \
89
  V8_INLINE size_t hash_value(type v) { return static_cast<size_t>(v); }
90 91 92 93 94
V8_BASE_HASH_VALUE_TRIVIAL(bool)
V8_BASE_HASH_VALUE_TRIVIAL(unsigned char)
V8_BASE_HASH_VALUE_TRIVIAL(unsigned short)  // NOLINT(runtime/int)
#undef V8_BASE_HASH_VALUE_TRIVIAL

95 96 97
V8_BASE_EXPORT size_t hash_value(unsigned int);
V8_BASE_EXPORT size_t hash_value(unsigned long);       // NOLINT(runtime/int)
V8_BASE_EXPORT size_t hash_value(unsigned long long);  // NOLINT(runtime/int)
98 99

#define V8_BASE_HASH_VALUE_SIGNED(type)            \
100
  V8_INLINE size_t hash_value(signed type v) {     \
101 102 103 104 105 106 107 108 109
    return hash_value(bit_cast<unsigned type>(v)); \
  }
V8_BASE_HASH_VALUE_SIGNED(char)
V8_BASE_HASH_VALUE_SIGNED(short)      // NOLINT(runtime/int)
V8_BASE_HASH_VALUE_SIGNED(int)        // NOLINT(runtime/int)
V8_BASE_HASH_VALUE_SIGNED(long)       // NOLINT(runtime/int)
V8_BASE_HASH_VALUE_SIGNED(long long)  // NOLINT(runtime/int)
#undef V8_BASE_HASH_VALUE_SIGNED

110 111 112 113 114 115 116 117 118
V8_INLINE size_t hash_value(float v) {
  // 0 and -0 both hash to zero.
  return v != 0.0f ? hash_value(bit_cast<uint32_t>(v)) : 0;
}

V8_INLINE size_t hash_value(double v) {
  // 0 and -0 both hash to zero.
  return v != 0.0 ? hash_value(bit_cast<uint64_t>(v)) : 0;
}
119

120 121 122 123 124 125 126 127 128 129
template <typename T, size_t N>
V8_INLINE size_t hash_value(const T (&v)[N]) {
  return hash_range(v, v + N);
}

template <typename T, size_t N>
V8_INLINE size_t hash_value(T (&v)[N]) {
  return hash_range(v, v + N);
}

130
template <typename T>
131 132
V8_INLINE size_t hash_value(T* const& v) {
  return hash_value(bit_cast<uintptr_t>(v));
133 134 135
}

template <typename T1, typename T2>
136
V8_INLINE size_t hash_value(std::pair<T1, T2> const& v) {
137 138 139 140 141 142
  return hash_combine(v.first, v.second);
}


template <typename T>
struct hash : public std::unary_function<T, size_t> {
143
  V8_INLINE size_t operator()(T const& v) const { return hash_value(v); }
144 145 146 147 148
};

#define V8_BASE_HASH_SPECIALIZE(type)                            \
  template <>                                                    \
  struct hash<type> : public std::unary_function<type, size_t> { \
149
    V8_INLINE size_t operator()(type const v) const {            \
150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169
      return ::v8::base::hash_value(v);                          \
    }                                                            \
  };
V8_BASE_HASH_SPECIALIZE(bool)
V8_BASE_HASH_SPECIALIZE(signed char)
V8_BASE_HASH_SPECIALIZE(unsigned char)
V8_BASE_HASH_SPECIALIZE(short)           // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(unsigned short)  // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(int)
V8_BASE_HASH_SPECIALIZE(unsigned int)
V8_BASE_HASH_SPECIALIZE(long)                // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(unsigned long)       // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(long long)           // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(unsigned long long)  // NOLINT(runtime/int)
V8_BASE_HASH_SPECIALIZE(float)
V8_BASE_HASH_SPECIALIZE(double)
#undef V8_BASE_HASH_SPECIALIZE

template <typename T>
struct hash<T*> : public std::unary_function<T*, size_t> {
170 171 172
  V8_INLINE size_t operator()(T* const v) const {
    return ::v8::base::hash_value(v);
  }
173 174
};

175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
// base::bit_equal_to is a function object class for bitwise equality
// comparison, similar to std::equal_to, except that the comparison is performed
// on the bit representation of the operands.
//
// base::bit_hash is a function object class for bitwise hashing, similar to
// base::hash. It can be used together with base::bit_equal_to to implement a
// hash data structure based on the bitwise representation of types.

template <typename T>
struct bit_equal_to : public std::binary_function<T, T, bool> {};

template <typename T>
struct bit_hash : public std::unary_function<T, size_t> {};

#define V8_BASE_BIT_SPECIALIZE_TRIVIAL(type)                 \
  template <>                                                \
  struct bit_equal_to<type> : public std::equal_to<type> {}; \
  template <>                                                \
  struct bit_hash<type> : public hash<type> {};
V8_BASE_BIT_SPECIALIZE_TRIVIAL(signed char)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned char)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(short)           // NOLINT(runtime/int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned short)  // NOLINT(runtime/int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(long)                // NOLINT(runtime/int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long)       // NOLINT(runtime/int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(long long)           // NOLINT(runtime/int)
V8_BASE_BIT_SPECIALIZE_TRIVIAL(unsigned long long)  // NOLINT(runtime/int)
#undef V8_BASE_BIT_SPECIALIZE_TRIVIAL

#define V8_BASE_BIT_SPECIALIZE_BIT_CAST(type, btype)                          \
  template <>                                                                 \
  struct bit_equal_to<type> : public std::binary_function<type, type, bool> { \
    V8_INLINE bool operator()(type lhs, type rhs) const {                     \
      return bit_cast<btype>(lhs) == bit_cast<btype>(rhs);                    \
    }                                                                         \
  };                                                                          \
  template <>                                                                 \
  struct bit_hash<type> : public std::unary_function<type, size_t> {          \
    V8_INLINE size_t operator()(type v) const {                               \
      hash<btype> h;                                                          \
      return h(bit_cast<btype>(v));                                           \
    }                                                                         \
  };
V8_BASE_BIT_SPECIALIZE_BIT_CAST(float, uint32_t)
V8_BASE_BIT_SPECIALIZE_BIT_CAST(double, uint64_t)
#undef V8_BASE_BIT_SPECIALIZE_BIT_CAST
223 224 225 226 227

}  // namespace base
}  // namespace v8

#endif  // V8_BASE_FUNCTIONAL_H_