kblib  0.2.3
General utilities library for modern C++
hash.h
Go to the documentation of this file.
1 /* *****************************************************************************
2  * kblib is a general utility library for C++14 and C++17, intended to provide
3  * performant high-level abstractions and more expressive ways to do simple
4  * things.
5  *
6  * Copyright (c) 2021 killerbee
7  *
8  * This program is free software: you can redistribute it and/or modify
9  * it under the terms of the GNU General Public License as published by
10  * the Free Software Foundation, either version 3 of the License, or
11  * (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program. If not, see <https://www.gnu.org/licenses/>.
20  * ****************************************************************************/
21 
32 #ifndef HASH_H
33 #define HASH_H
34 
35 #include "iterators.h"
36 #include "tdecl.h"
37 #include "traits.h"
38 #include "variant.h"
39 
40 #include <climits>
41 #include <cstdint>
42 #include <numeric>
43 #include <string>
44 #include <unordered_map>
45 #include <unordered_set>
46 
47 #if KBLIB_USE_CXX17
48 # include <optional>
49 # include <string_view>
50 # include <variant>
51 #endif
52 
53 namespace kblib {
54 
55 template <typename Integral, typename CharT>
56 constexpr auto to_bytes_le(Integral ival,
57  CharT (&dest)[sizeof(Integral)]) noexcept -> void {
58  static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
59  and not std::is_same<CharT, bool>::value,
60  "CharT must be a char-like type.");
61  for (int byte = 0; byte != sizeof(Integral); ++byte) {
62  dest[byte] = static_cast<CharT>(to_unsigned(ival)
63  >> to_unsigned(CHAR_BIT * byte));
64  }
65 }
66 
67 template <typename Integral, typename CharT>
68 constexpr auto to_bytes_be(Integral ival,
69  CharT (&dest)[sizeof(Integral)]) noexcept -> void {
70  static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
71  and not std::is_same<CharT, bool>::value,
72  "CharT must be a char-like type.");
73  for (auto byte : range(sizeof(Integral))) {
74  dest[(sizeof(Integral) - 1) - byte]
75  = static_cast<CharT>(ival >> (CHAR_BIT * byte));
76  }
77 }
78 
79 template <typename Integral, typename CharT>
80 constexpr auto to_bytes(Integral val, CharT (&dest)[sizeof(Integral)]) noexcept
81  -> void {
82  static_assert(std::is_integral<CharT>::value and sizeof(CharT) == 1
83  and not std::is_same<CharT, bool>::value,
84  "CharT must be a char-like type.");
85  if (hash_order == endian::little) {
86  to_bytes_le(val, dest);
87  } else {
88  to_bytes_be(val, dest);
89  }
90 }
91 
92 namespace fnv {
93 
97  template <typename UInt>
98  struct fnv_prime;
99 
100  template <>
101  struct fnv_prime<std::uint32_t>
102  : std::integral_constant<std::uint32_t, 16777619ul> {};
103  template <>
104  struct fnv_prime<std::uint64_t>
105  : std::integral_constant<std::uint64_t, 1099511628211ull> {};
106 
107  template <typename UInt>
108  struct fnv_prime {
109  KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
112  };
113 
117  template <typename UInt>
118  struct fnv_offset;
119 
120  template <>
121  struct fnv_offset<std::uint32_t>
122  : std::integral_constant<std::uint32_t, 2166136261ul> {};
123  template <>
124  struct fnv_offset<std::uint64_t>
125  : std::integral_constant<std::uint64_t, 14695981039346656037ull> {};
126 
127  template <typename UInt>
128  struct fnv_offset {
129  KBLIB_CONSTANT_M UInt value = (sizeof(UInt) == sizeof(std::uint64_t)
132  };
133 
134 } // namespace fnv
135 
146 template <typename HashInt, typename Span>
147 KBLIB_NODISCARD constexpr auto FNVa(Span&& s,
148  HashInt hval
150  -> HashInt {
151  static_assert(sizeof(*std::begin(s)) == 1,
152  "Can only hash char-like objects.");
153  const HashInt prime = fnv::fnv_prime<HashInt>::value;
154  for (auto&& c : s) {
155  hval ^= static_cast<HashInt>(static_cast<unsigned char>(c));
156  hval *= prime;
157  }
158  return hval;
159 }
160 
172 template <typename HashInt, typename CharT, std::size_t N>
173 KBLIB_NODISCARD constexpr auto FNVa_a(
174  const CharT (&s)[N],
175  HashInt hval = fnv::fnv_offset<HashInt>::value) noexcept -> HashInt {
176  static_assert(sizeof(s[0]) == 1, "Can only hash char-like objects.");
177  const HashInt prime = fnv::fnv_prime<HashInt>::value;
178  for (auto&& c : s) {
179  hval ^= static_cast<HashInt>(static_cast<unsigned char>(c));
180  hval *= prime;
181  }
182  return hval;
183 }
184 
185 #if KBLIB_USE_CXX17
194 KBLIB_NODISCARD constexpr auto FNV32a(
195  std::string_view s,
196  std::uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
197  -> std::uint32_t {
198  const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
199  for (auto&& c : s) {
200  hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(c));
201  hval *= prime;
202  }
203  return hval;
204 }
205 #endif
206 
207 template <typename HashInt>
208 KBLIB_NODISCARD constexpr auto FNVa_s(
209  const char* begin, std::size_t length,
210  HashInt hval = fnv::fnv_offset<HashInt>::value) noexcept -> HashInt {
211  const HashInt prime = fnv::fnv_prime<HashInt>::value;
212  // for (const char* pos = begin; pos != begin + length; ++pos) {
213  // hval ^= static_cast<HashInt>(static_cast<unsigned char>(*pos));
214  // hval *= prime;
215  // }
216  for (const char* pos : range(begin, begin + length)) {
217  hval ^= static_cast<HashInt>(static_cast<unsigned char>(*pos));
218  hval *= prime;
219  }
220  return hval;
221 }
222 
232 template <std::size_t N>
233 KBLIB_NODISCARD constexpr auto FNV32a_a(
234  const char (&s)[N],
235  std::uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
236  -> std::uint32_t {
237  const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
238  for (auto&& c : s) {
239  hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(c));
240  hval *= prime;
241  }
242  return hval;
243 }
244 
245 KBLIB_NODISCARD constexpr auto FNV32a_s(
246  const char* begin, std::size_t length,
247  uint32_t hval = fnv::fnv_offset<std::uint32_t>::value) noexcept
248  -> std::uint32_t {
249  const std::uint32_t prime = fnv::fnv_prime<std::uint32_t>::value;
250  for (const char* pos = begin; pos != begin + length; ++pos) {
251  hval ^= static_cast<std::uint32_t>(static_cast<unsigned char>(*pos));
252  hval *= prime;
253  }
254  return hval;
255 }
256 
257 inline namespace literals {
261  KBLIB_NODISCARD constexpr auto operator""_fnv32(const char* str,
262  std::size_t length) noexcept
263  -> std::uint32_t {
264  return FNVa_s<std::uint32_t>(str, length);
265  }
266 
270  KBLIB_NODISCARD constexpr auto operator""_fnv64(const char* str,
271  std::size_t length) noexcept
272  -> std::uint64_t {
273  return FNVa_s<std::uint64_t>(str, length);
274  }
275 
276  // google-runtime-int not relevant here due to standard requirements
277  KBLIB_NODISCARD constexpr auto operator""_fnv32(unsigned long long val)
278  -> std::uint32_t {
279  unsigned char bytes[sizeof(unsigned long long)]{};
280  to_bytes(val, bytes);
281  return FNVa_a<std::uint32_t>(bytes);
282  }
283 
284  KBLIB_NODISCARD constexpr auto operator""_fnv64(unsigned long long val)
285  -> std::uint64_t {
286  unsigned char bytes[sizeof(unsigned long long)]{};
287  to_bytes(val, bytes);
288  return FNVa_a<std::uint64_t>(bytes);
289  }
290 
291 } // namespace literals
292 
297 template <typename T>
299  : std::integral_constant<int, CHAR_BIT * sizeof(T)
300  - std::numeric_limits<T>::digits
301  - std::numeric_limits<T>::is_signed> {};
302 
303 template <typename T>
305 
311 template <typename Key = void, typename HashInt = std::size_t, typename = void>
312 struct FNV_hash {
313  FNV_hash() = delete;
314  FNV_hash(const FNV_hash&) = delete;
315  FNV_hash(FNV_hash&&) = delete;
316  FNV_hash& operator=(const FNV_hash&) = delete;
318 };
319 
320 template <typename Key, typename = void>
321 struct is_hashable : std::false_type {};
322 
323 template <typename Key>
324 struct is_hashable<Key, void_if_t<std::is_constructible<FNV_hash<Key>>::value>>
325  : std::true_type {};
326 
327 template <typename Key>
329 
330 template <typename Key>
332 
337 template <typename HashInt>
338 struct FNV_hash<bool, HashInt, void> {
339  KBLIB_NODISCARD constexpr auto operator()(
340  bool key, HashInt offset
341  = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
342  char tmp[1] = {key};
343  return FNVa_a(tmp, offset);
344  }
345 };
346 
351 template <typename HashInt>
352 struct FNV_hash<char, HashInt, void> {
353  KBLIB_NODISCARD constexpr auto operator()(
354  char key, HashInt offset
355  = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
356  char tmp[1] = {key};
357  return FNVa_a(tmp, offset);
358  }
359 };
360 
365 template <typename HashInt>
366 struct FNV_hash<signed char, HashInt, void> {
367  KBLIB_NODISCARD constexpr auto operator()(
368  signed char key,
369  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
370  -> HashInt {
371  signed char tmp[1] = {key};
372  return FNVa_a(tmp, offset);
373  }
374 };
375 
380 template <typename HashInt>
381 struct FNV_hash<unsigned char, HashInt, void> {
382  KBLIB_NODISCARD constexpr auto operator()(
383  unsigned char key,
384  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
385  -> HashInt {
386  unsigned char tmp[1] = {key};
387  return FNVa_a(tmp, offset);
388  }
389 };
390 
394 template <typename T, typename HashInt>
395 struct FNV_hash<T, HashInt, void_if_t<std::is_empty<T>::value>> {
396  KBLIB_NODISCARD constexpr auto operator()(
397  const T&, HashInt offset
398  = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
399  return FNVa_a("", offset); // hashes the null terminator
400  }
401 };
402 
403 #if __cpp_lib_has_unique_object_representations
404 template <typename T>
406  = (std::is_trivially_copyable_v<
407  T> and std::has_unique_object_representations_v<T> and not std::is_empty<T>::value);
408 #else
409 template <typename T>
411  = (std::is_integral<T>::value and padding_bits<T>::value == 0)
412  or std::is_pointer<T>::value or std::is_member_object_pointer<T>::value
413  or std::is_member_function_pointer<T>::value;
414 #endif
415 template <typename T>
416 struct is_trivially_hashable : bool_constant<is_trivially_hashable_v<T>> {};
417 
422 template <typename T, typename HashInt>
423 struct FNV_hash<
424  T, HashInt,
425  void_if_t<std::is_integral<T>::value and is_trivially_hashable_v<T>>> {
426  KBLIB_NODISCARD constexpr auto operator()(
427  T key, HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
428  -> HashInt {
429  unsigned char tmp[sizeof(T)]{};
430  to_bytes(key, tmp);
431  return FNVa_a(tmp, offset);
432  }
433 };
434 
441 // uses std::is_pointer instead of just specializing on T* for cv pointers
442 template <typename T, typename HashInt>
443 struct FNV_hash<T, HashInt, void_if_t<std::is_pointer<T>::value>> {
445  T key_in, HashInt offset
446  = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
448  reinterpret_cast<std::uintptr_t>(key_in), offset);
449  }
450 };
451 
458 template <typename T, typename HashInt>
459 struct FNV_hash<T, HashInt,
460  void_if_t<(std::is_base_of<std::forward_iterator_tag,
461  typename std::iterator_traits<
462  T>::iterator_category>::value and
463  not std::is_pointer<T>::value and
464  not is_trivially_hashable_v<T> and
465  std::is_pointer<typename fakestd::invoke_result<
466  decltype(&T::operator->), T>::type>::value)>> {
468  T key_in, HashInt offset
469  = fnv::fnv_offset<HashInt>::value) const noexcept -> HashInt {
470  if (key_in
471  == T{}) { // avoid calling to_pointer on a value-initialized iterator
472  return FNV_hash<std::uintptr_t, HashInt>{}(0, offset);
473  } else {
475  reinterpret_cast<std::uintptr_t>(to_pointer(key_in)), offset);
476  }
477  }
478 };
479 
483 namespace asserts {
484 
485  template <typename Container>
488  and is_trivially_hashable_v<typename Container::value_type>);
489  static_assert(is_trivial_container<std::string>,
490  "kblib bug: std::string should be trivially hashable");
491 
492 } // namespace asserts
493 
498 template <typename Container, typename HashInt>
499 struct FNV_hash<
500  Container, HashInt,
501  void_if_t<(
503  Container> and is_trivially_hashable_v<typename Container::value_type>)>> {
504 
505  KBLIB_NODISCARD auto hash_fast(const Container& key,
506  HashInt offset) const noexcept -> HashInt {
507  return FNVa_s<HashInt>(reinterpret_cast<const char*>(key.data()),
508  key.size() * sizeof(*key.begin()), offset);
509  }
510 
512  const Container& key,
513  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
514  -> HashInt {
515 #if KBLIB_USE_CXX20
516  if (std::is_constant_evaluated()) {
517  using T = typename Container::value_type;
518  for (const auto& e : key) {
519  offset = FNV_hash<T>{}(e, offset);
520  }
521  } else {
522  return hash_fast(key, offset);
523  }
524 #else
525  return hash_fast(key, offset);
526 #endif
527  }
528 };
529 
538 template <typename T, typename HashInt>
539 struct FNV_hash<
540  T, HashInt,
541  void_if_t<not is_contiguous<T>::value and not std::is_integral<T>::value
542  and not std::is_pointer<T>::value
543  and is_trivially_hashable_v<T>>> {
545  T key, HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
546  -> HashInt {
547  char tmp[sizeof(T)];
548  std::memcpy(tmp, &key, sizeof(T));
549  return FNVa_a(tmp, offset);
550  }
551 };
552 
557 template <typename Container, typename HashInt>
558 struct FNV_hash<
559  Container, HashInt,
560  void_if_t<
561  value_detected<Container>::value
562  and is_hashable_v<
563  value_detected_t<Container>> and not hash_detected<Container>::value
564  and is_iterable<Container>::value
565  and not (is_contiguous<Container>::value
566  and is_trivially_hashable_v<typename Container::value_type>)
567  and not is_iterator_v<Container>>> {
568  KBLIB_NODISCARD constexpr auto operator()(
569  const Container& key,
570  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
571  -> HashInt {
572  using Elem = typename Container::value_type;
573  return std::accumulate(cbegin(key), cend(key), offset,
574  [](HashInt offset_, const Elem& elem) {
575  return FNV_hash<Elem, HashInt>{}(elem, offset_);
576  });
577  }
578 };
579 
584 namespace detail_hash {
585 
594  template <typename Tuple, typename HashInt, std::size_t I>
595  constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
596  std::index_sequence<I>) noexcept -> HashInt {
598  std::get<I>(tuple), offset);
599  }
600 
609  template <typename Tuple, typename HashInt, std::size_t I, std::size_t I2,
610  std::size_t... Is>
611  constexpr auto hash_tuple_impl(const Tuple& tuple, HashInt offset,
612  std::index_sequence<I, I2, Is...>) noexcept
613  -> HashInt {
614  HashInt first_hash
616  std::get<I>(tuple), offset);
617  return hash_tuple_impl(tuple, first_hash,
618  std::index_sequence<I2, Is...>{});
619  }
620 
621 #if KBLIB_USE_CXX17
622  template <typename Tuple, std::size_t... Is>
623  constexpr auto all_hashable_impl(std::index_sequence<Is...>) -> bool {
624  return (...
625  and is_hashable_v<typename std::tuple_element<Is, Tuple>::type>);
626  }
627 #else
628 
629  template <typename Tuple, typename IS>
630  struct all_hashable_impl_t;
631 
632  template <typename Tuple, std::size_t I, std::size_t... Is>
633  struct all_hashable_impl_t<Tuple, std::index_sequence<I, Is...>>
634  : bool_constant<(
635  is_hashable_v<
636  typename std::tuple_element<I, Tuple>::
637  type> and all_hashable_impl_t<Tuple, std::index_sequence<Is...>>::value)> {
638  };
639 
640  template <typename Tuple, std::size_t I>
641  struct all_hashable_impl_t<Tuple, std::index_sequence<I>>
642  : bool_constant<
643  is_hashable_v<typename std::tuple_element<I, Tuple>::type>> {};
644 
645  template <typename Tuple, std::size_t... Is>
646  constexpr auto all_hashable_impl(std::index_sequence<Is...>) -> bool {
647  return all_hashable_impl_t<Tuple, std::index_sequence<Is...>>::value;
648  }
649 #endif
650 
651  template <
652  typename Tuple,
653  typename std::enable_if<(std::tuple_size<Tuple>::value > 0u), int>::type
654  = 0>
655  constexpr auto all_hashable() -> bool {
656  return all_hashable_impl<Tuple>(
657  std::make_index_sequence<std::tuple_size<Tuple>::value>{});
658  }
659 
660 } // namespace detail_hash
661 
666 template <typename Tuple, typename HashInt>
667 struct FNV_hash<Tuple, HashInt,
669  and not is_trivially_hashable_v<
670  Tuple> and (std::tuple_size<Tuple>::value > 0u)
671  and not is_linear_container_v<Tuple>>> {
672  KBLIB_NODISCARD constexpr auto operator()(
673  const Tuple& key,
674  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
675  -> HashInt {
677  key, offset,
678  std::make_index_sequence<std::tuple_size<Tuple>::value>{});
679  }
680 };
681 
682 #if KBLIB_USE_CXX17
683 
684 template <typename T, typename HashInt>
685 struct FNV_hash<std::optional<T>, HashInt, void> {
686  KBLIB_NODISCARD constexpr auto operator()(
687  const std::optional<T>& key,
688  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
689  -> HashInt {
690  if (key) {
691  return FNV_hash<T, HashInt>{}(key.value(), offset);
692  } else {
693  return FNV_hash<std::nullopt_t, HashInt>{}(std::nullopt, offset);
694  }
695  }
696 };
697 
698 template <typename... Ts, typename HashInt>
699 struct FNV_hash<std::variant<Ts...>, HashInt,
700  void_if_t<detail_hash::all_hashable<std::tuple<Ts...>>()>> {
701  KBLIB_NODISCARD constexpr auto operator()(
702  const std::variant<Ts...>& key,
703  HashInt offset = fnv::fnv_offset<HashInt>::value) const noexcept
704  -> HashInt {
705  // Variant index is hashed alongside the value
706  offset = FNV_hash<HashInt>{}(key.index(), offset);
707  // visit2_nop does nothing when the variant is valueless_by_exception
708  kblib::visit2_nop(key, [&](auto& V) {
709  offset = FNV_hash<typename std::remove_reference<decltype(V)>::type,
710  HashInt>{}(V, offset);
711  });
712  return offset;
713  }
714 };
715 
716 #endif
717 
722 template <typename HashInt>
723 struct FNV_hash<void, HashInt, void> {
724  KBLIB_CONSTANT_MV is_transparent = true;
725 
726  template <typename T>
727  KBLIB_NODISCARD constexpr auto operator()(const T& key,
728  HashInt offset
730  -> enable_if_t<is_hashable_v<T>, HashInt> {
731  return FNV_hash<T>{}(key, offset);
732  }
733 };
734 
735 template <typename Key, typename Value>
736 using hash_map = std::unordered_map<Key, Value, FNV_hash<>, std::equal_to<>>;
737 template <typename Key, typename Value>
739  = std::unordered_multimap<Key, Value, FNV_hash<>, std::equal_to<>>;
740 template <typename T, typename HashInt>
741 using hash_set = std::unordered_set<T, FNV_hash<>, std::equal_to<>>;
742 template <typename T, typename HashInt>
743 using hash_multiset = std::unordered_set<T, FNV_hash<>, std::equal_to<>>;
744 
745 } // namespace kblib
746 
747 #endif // HASH_H
This file provides some iterators, ranges, iterator/range adapters, and operations that can be perfor...
KBLIB_CONSTANT_V is_trivial_container
Definition: hash.h:487
constexpr auto hash_tuple_impl(const Tuple &tuple, HashInt offset, std::index_sequence< I >) noexcept -> HashInt
Hash each element of a tuple. This overload is for tuples of a single type, or as the base case for t...
Definition: hash.h:595
constexpr auto all_hashable_impl(std::index_sequence< Is... >) -> bool
Definition: hash.h:623
constexpr auto all_hashable() -> bool
Definition: hash.h:655
The main namespace in which all entities from kblib are defined.
Definition: algorithm.h:44
KBLIB_CONSTANT_V is_hashable_v
Definition: hash.h:328
KBLIB_CONSTANT_V is_trivially_hashable_v
Definition: hash.h:411
constexpr auto to_pointer(P &&p) noexcept -> auto *
Gets a raw pointer out of any smart pointer or iterator you might pass in, without dereferencing it o...
Definition: iterators.h:71
std::unordered_multimap< Key, Value, FNV_hash<>, std::equal_to<> > hash_multimap
Definition: hash.h:739
typename std::enable_if< B, T >::type enable_if_t
Definition: fakestd.h:54
constexpr auto e() -> T
Definition: stats.h:465
constexpr auto to_bytes(Integral val, CharT(&dest)[sizeof(Integral)]) noexcept -> void
Definition: hash.h:80
constexpr auto FNV32a_s(const char *begin, std::size_t length, uint32_t hval=fnv::fnv_offset< std::uint32_t >::value) noexcept -> std::uint32_t
Definition: hash.h:245
constexpr auto range(Value min, Value max, Delta step=0) -> range_t< Value, Delta >
Constructs a range from beginning, end, and step amount. The range is half-open, that is min is in th...
Definition: iterators.h:620
constexpr auto FNVa(Span &&s, HashInt hval=fnv::fnv_offset< HashInt >::value) noexcept -> HashInt
A templatized generic FNVa hash function.
Definition: hash.h:147
constexpr auto visit2_nop(V &&v, F &&f, Fs &&... fs) -> void
Definition: variant.h:306
KBLIB_CONSTANT_V is_iterator_v
Definition: traits.h:424
constexpr auto FNV32a_a(const char(&s)[N], std::uint32_t hval=fnv::fnv_offset< std::uint32_t >::value) noexcept -> std::uint32_t
A standard FNV32a hash function, for raw character arrays, such as string literals.
Definition: hash.h:233
constexpr int padding_bits_v
Definition: hash.h:304
constexpr auto FNV32a(std::string_view s, std::uint32_t hval=fnv::fnv_offset< std::uint32_t >::value) noexcept -> std::uint32_t
A standard FNV32a hash function, for string_views.
Definition: hash.h:194
std::unordered_set< T, FNV_hash<>, std::equal_to<> > hash_multiset
Definition: hash.h:743
std::integral_constant< bool, v > bool_constant
Definition: fakestd.h:64
typename void_if< b >::type void_if_t
Definition: fakestd.h:512
constexpr auto FNVa_s(const char *begin, std::size_t length, HashInt hval=fnv::fnv_offset< HashInt >::value) noexcept -> HashInt
Definition: hash.h:208
std::unordered_set< T, FNV_hash<>, std::equal_to<> > hash_set
Definition: hash.h:741
constexpr auto to_bytes_be(Integral ival, CharT(&dest)[sizeof(Integral)]) noexcept -> void
Definition: hash.h:68
constexpr auto accumulate(InputIt first, InputIt last, T init) -> T
A constexpr version of std::accumulate.
Definition: algorithm.h:162
constexpr auto to_bytes_le(Integral ival, CharT(&dest)[sizeof(Integral)]) noexcept -> void
Definition: hash.h:56
constexpr auto FNVa_a(const CharT(&s)[N], HashInt hval=fnv::fnv_offset< HashInt >::value) noexcept -> HashInt
A templatized FNVa hash function, for raw character arrays, such as string literals.
Definition: hash.h:173
KBLIB_CONSTANT_V is_contiguous_v
Type trait to determine if a container is contiguous.
Definition: traits.h:261
constexpr endian hash_order
Definition: tdecl.h:197
std::unordered_map< Key, Value, FNV_hash<>, std::equal_to<> > hash_map
Definition: hash.h:736
constexpr auto to_unsigned(I x) -> std::make_unsigned_t< I >
Cast integral argument to corresponding unsigned type.
Definition: fakestd.h:585
Definition: bits.h:714
auto operator()(const Container &key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:511
constexpr auto operator()(const T &, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:396
constexpr auto operator()(T key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:426
auto operator()(T key_in, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:444
constexpr auto operator()(bool key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:339
constexpr auto operator()(char key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:353
constexpr auto operator()(signed char key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:367
constexpr auto operator()(const std::optional< T > &key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:686
constexpr auto operator()(const std::variant< Ts... > &key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:701
constexpr auto operator()(unsigned char key, HashInt offset=fnv::fnv_offset< HashInt >::value) const noexcept -> HashInt
Definition: hash.h:382
constexpr auto operator()(const T &key, HashInt offset=fnv::fnv_offset< HashInt >::value) -> enable_if_t< is_hashable_v< T >, HashInt >
Definition: hash.h:727
The primary template has to exist, but not be constructible, in order to be compatible with std::hash...
Definition: hash.h:312
FNV_hash(FNV_hash &&)=delete
FNV_hash()=delete
FNV_hash & operator=(FNV_hash &&)=delete
FNV_hash(const FNV_hash &)=delete
FNV_hash & operator=(const FNV_hash &)=delete
The starting value for the FNVa hash algorithm, as a type trait.
Definition: hash.h:128
KBLIB_CONSTANT_M UInt value
Definition: hash.h:129
The prime to use for the FNVa hash algorithm, as a type trait.
Definition: hash.h:108
KBLIB_CONSTANT_M UInt value
Definition: hash.h:109
Get the number of padding bits in an integral type.
Definition: hash.h:301
Provides macros and basic templates used by the rest of kblib.
#define KBLIB_NODISCARD
This internal macro is used to provide a fallback for [[nodiscard]] in C++14.
Definition: tdecl.h:81
#define KBLIB_CONSTANT_V
Definition: tdecl.h:99
#define KBLIB_CXX20(args)
This internal macro is used to selectively use C++20 features.
Definition: tdecl.h:116
#define KBLIB_CONSTANT_M
Definition: tdecl.h:100
#define KBLIB_CONSTANT_MV
Definition: tdecl.h:101
Contains some type traits not in the standard library that are useful in the implementation of kblib.
Provides utilities for working with std::variant more expressively and more efficiently.