libcuckoo  0.3.1
cuckoohash_util.hh
Go to the documentation of this file.
1 
3 #ifndef _CUCKOOHASH_UTIL_HH
4 #define _CUCKOOHASH_UTIL_HH
5 
6 #include "cuckoohash_config.hh" // for LIBCUCKOO_DEBUG
7 #include <exception>
8 #include <thread>
9 #include <utility>
10 #include <vector>
11 
12 namespace libcuckoo {
13 
14 #if LIBCUCKOO_DEBUG
15 #define LIBCUCKOO_DBG(fmt, ...) \
18  fprintf(stderr, "\x1b[32m" \
19  "[libcuckoo:%s:%d:%lu] " fmt "" \
20  "\x1b[0m", \
21  __FILE__, __LINE__, \
22  std::hash<std::thread::id>()(std::this_thread::get_id()), \
23  __VA_ARGS__)
24 #else
25 #define LIBCUCKOO_DBG(fmt, ...) \
27  do { \
28  } while (0)
29 #endif
30 
35 #ifdef __GNUC__
36 #define LIBCUCKOO_ALIGNAS(x) __attribute__((aligned(x)))
37 #else
38 #define LIBCUCKOO_ALIGNAS(x) alignas(x)
39 #endif
40 
45 #ifdef _MSC_VER
46 #define LIBCUCKOO_SQUELCH_PADDING_WARNING __pragma(warning(suppress : 4324))
47 #else
48 #define LIBCUCKOO_SQUELCH_PADDING_WARNING
49 #endif
50 
56 #ifdef _MSC_VER
57 #define LIBCUCKOO_SQUELCH_DEADCODE_WARNING_BEGIN \
58  do { \
59  __pragma(warning(push)); \
60  __pragma(warning(disable : 4702)) \
61  } while (0)
62 #define LIBCUCKOO_SQUELCH_DEADCODE_WARNING_END __pragma(warning(pop))
63 #else
64 #define LIBCUCKOO_SQUELCH_DEADCODE_WARNING_BEGIN
65 #define LIBCUCKOO_SQUELCH_DEADCODE_WARNING_END
66 #endif
67 
75 class load_factor_too_low : public std::exception {
76 public:
82  load_factor_too_low(const double lf) noexcept : load_factor_(lf) {}
83 
87  virtual const char *what() const noexcept override {
88  return "Automatic expansion triggered when load factor was below "
89  "minimum threshold";
90  }
91 
95  double load_factor() const noexcept { return load_factor_; }
96 
97 private:
98  const double load_factor_;
99 };
100 
106 class maximum_hashpower_exceeded : public std::exception {
107 public:
113  maximum_hashpower_exceeded(const size_t hp) noexcept : hashpower_(hp) {}
114 
118  virtual const char *what() const noexcept override {
119  return "Expansion beyond maximum hashpower";
120  }
121 
125  size_t hashpower() const noexcept { return hashpower_; }
126 
127 private:
128  const size_t hashpower_;
129 };
130 
136 enum class UpsertContext {
137  NEWLY_INSERTED,
138  ALREADY_EXISTED,
139 };
140 
141 namespace internal {
142 
143 // Used to invoke the \ref uprase_fn functor with or without an \ref
144 // UpsertContext enum. Note that if we cannot pass an upsert context and the
145 // desired context is <tt>UpsertContext:::NEWLY_INSERTED</tt>, then we do not
146 // invoke the functor at all.
147 //
148 // We implement this utility using C++11-style SFINAE, for maximum
149 // compatibility.
150 template <typename F, typename MappedType>
152  private:
153  template <typename InnerF,
154  typename = decltype(std::declval<InnerF>()(
155  std::declval<MappedType&>(), std::declval<UpsertContext>()))>
156  static std::true_type test(int);
157 
158  // Note: The argument type needs to be less-preferable than the first
159  // overload so that it is picked only if the first overload cannot be
160  // instantiated.
161  template <typename InnerF>
162  static std::false_type test(float);
163 
164  public:
165  using type = decltype(test<F>(0));
166 };
167 
168 template <typename F, typename MappedType>
169 bool InvokeUpraseFn(F& f, MappedType& mapped, UpsertContext context,
170  std::true_type) {
171  return f(mapped, context);
172 }
173 
174 template <typename F, typename MappedType>
175 bool InvokeUpraseFn(F& f, MappedType& mapped, UpsertContext context,
176  std::false_type) {
177  if (context == UpsertContext::ALREADY_EXISTED) {
178  return f(mapped);
179  } else {
180  // Returning false indicates no deletion, making this a no-op.
181  return false;
182  }
183 }
184 
185 // Upgrades an upsert functor to an uprase functor, which always returns false,
186 // so that we never erase the element.
187 template <typename F, typename MappedType, bool kCanInvokeWithUpsertContext>
189 
190 template <typename F, typename MappedType>
191 struct UpsertToUpraseFn<F, MappedType, true> {
192  F& f;
193 
194  bool operator()(MappedType& mapped, UpsertContext context) const {
195  f(mapped, context);
196  return false;
197  }
198 };
199 
200 template <typename F, typename MappedType>
201 struct UpsertToUpraseFn<F, MappedType, false> {
202  F& f;
203 
204  bool operator()(MappedType& mapped) {
205  f(mapped);
206  return false;
207  }
208 };
209 
210 } // namespace internal
211 
212 } // namespace libcuckoo
213 
214 #endif // _CUCKOOHASH_UTIL_HH
libcuckoo::load_factor_too_low::load_factor
double load_factor() const noexcept
Definition: cuckoohash_util.hh:95
libcuckoo::maximum_hashpower_exceeded::maximum_hashpower_exceeded
maximum_hashpower_exceeded(const size_t hp) noexcept
Definition: cuckoohash_util.hh:113
libcuckoo::internal::UpsertToUpraseFn
Definition: cuckoohash_util.hh:188
libcuckoo::internal::CanInvokeWithUpsertContext
Definition: cuckoohash_util.hh:151
libcuckoo::maximum_hashpower_exceeded::what
virtual const char * what() const noexcept override
Definition: cuckoohash_util.hh:118
libcuckoo::load_factor_too_low
Definition: cuckoohash_util.hh:75
libcuckoo::UpsertContext
UpsertContext
Definition: cuckoohash_util.hh:136
cuckoohash_config.hh
libcuckoo::maximum_hashpower_exceeded::hashpower
size_t hashpower() const noexcept
Definition: cuckoohash_util.hh:125
libcuckoo::load_factor_too_low::what
virtual const char * what() const noexcept override
Definition: cuckoohash_util.hh:87
libcuckoo::maximum_hashpower_exceeded
Definition: cuckoohash_util.hh:106
libcuckoo::load_factor_too_low::load_factor_too_low
load_factor_too_low(const double lf) noexcept
Definition: cuckoohash_util.hh:82