Debian Codegraph @

src/mpt/base/algorithm.hpp

raw
1 /* SPDX-License-Identifier: BSL-1.0 OR BSD-3-Clause */
2
3 #ifndef MPT_BASE_ALGORITHM_HPP
4 #define MPT_BASE_ALGORITHM_HPP
5
6
7
8 #include "mpt/base/detect_compiler.hpp"
9 #include "mpt/base/macros.hpp"
10 #include "mpt/base/namespace.hpp"
11 #include "mpt/base/saturate_cast.hpp"
12
13 #include <algorithm>
14 #include <iterator>
15 #include <limits>
16 #include <type_traits>
17
18
19
20 namespace mpt {
21 inline namespace MPT_INLINE_NS {
22
23
24 // Grows x with an exponential factor suitable for increasing buffer sizes.
25 // Clamps the result at limit.
26 // And avoids integer overflows while doing its business.
27 // The growth factor is 1.5, rounding down, execpt for the initial x==1 case.
28 template <typename T, typename Tlimit>
29 inline T exponential_grow(const T & x, const Tlimit & limit) {
30 if (x <= 1) {
31 return 2;
32 }
33 T add = std::min(x >> 1, std::numeric_limits<T>::max() - x);
34 return std::min(x + add, mpt::saturate_cast<T>(limit));
35 }
36
37 template <typename T>
38 inline T exponential_grow(const T & x) {
39 return mpt::exponential_grow(x, std::numeric_limits<T>::max());
40 }
41
42
43 // Check if val is in [lo,hi] without causing compiler warnings
44 // if theses checks are always true due to the domain of T.
45 // GCC does not warn if the type is templated.
46 template <typename T, typename C>
47 constexpr bool is_in_range(const T & val, const C & lo, const C & hi) {
48 return lo <= val && val <= hi;
49 }
50
51
52 namespace detail {
53 namespace contains {
54
55 template <typename Container, typename Signature>
56 struct has_find : std::false_type {
57 };
58
59 template <typename Container, typename Ret, typename... Args>
60 struct has_find<Container, Ret(Args...)> {
61 private:
62 template <typename T>
63 static constexpr inline auto check(T *) -> typename std::is_same<decltype(std::declval<T>().find(std::declval<Args>()...)), Ret>::type {
64 return {};
65 }
66 template <typename T>
67 static constexpr inline std::false_type check(...) {
68 return {};
69 }
70 public:
71 typedef decltype(check<Container>(nullptr)) type;
72 static constexpr inline bool value = type::value;
73 };
74
75 template <typename Tcontainer, typename Tval>
76 MPT_CONSTEXPR20_FUN bool contains_class_find_impl(const Tcontainer & container, const Tval & value, std::true_type) noexcept(noexcept(container.find(value) != container.end())) {
77 return container.find(value) != container.end();
78 }
79
80 template <typename Tcontainer, typename Tval>
81 MPT_CONSTEXPR20_FUN bool contains_class_find_impl(const Tcontainer & container, const Tval & value, std::false_type) noexcept(noexcept(std::find(std::begin(container), std::end(container), value))) {
82 return std::find(std::begin(container), std::end(container), value) != std::end(container);
83 }
84
85 template <typename Tcontainer, typename Tval>
86 MPT_CONSTEXPR20_FUN bool contains_class_impl(const Tcontainer & container, const Tval & value, std::true_type) noexcept(noexcept(mpt::detail::contains::contains_class_find_impl<Tcontainer, Tval>(container, value, typename mpt::detail::contains::has_find<Tcontainer, typename Tcontainer::iterator(Tval)>::type{}))) {
87 return mpt::detail::contains::contains_class_find_impl<Tcontainer, Tval>(container, value, typename mpt::detail::contains::has_find<Tcontainer, typename Tcontainer::iterator(Tval)>::type{});
88 }
89
90 template <typename Tcontainer, typename Tval>
91 MPT_CONSTEXPR20_FUN bool contains_class_impl(const Tcontainer & container, const Tval & value, std::false_type) noexcept(noexcept(std::find(std::begin(container), std::end(container), value))) {
92 return std::find(std::begin(container), std::end(container), value) != std::end(container);
93 }
94
95 } // namespace contains
96 } // namespace detail
97
98 template <typename Tcontainer, typename Tval>
99 MPT_CONSTEXPR20_FUN bool contains(const Tcontainer & container, const Tval & value) noexcept(noexcept(mpt::detail::contains::contains_class_impl<Tcontainer, Tval>(container, value, typename std::is_class<Tcontainer>::type{}))) {
100 return mpt::detail::contains::contains_class_impl<Tcontainer, Tval>(container, value, typename std::is_class<Tcontainer>::type{});
101 }
102
103
104 } // namespace MPT_INLINE_NS
105 } // namespace mpt
106
107
108
109 #endif // MPT_BASE_ALGORITHM_HPP