Direct-BT v3.3.0-1-gc2d430c
Direct-BT - Direct Bluetooth Programming.
basic_algos.hpp
Go to the documentation of this file.
1/*
2 * Author: Sven Gothel <sgothel@jausoft.com>
3 * Copyright (c) 2020 Gothel Software e.K.
4 * Copyright (c) 2020 ZAFENA AB
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining
7 * a copy of this software and associated documentation files (the
8 * "Software"), to deal in the Software without restriction, including
9 * without limitation the rights to use, copy, modify, merge, publish,
10 * distribute, sublicense, and/or sell copies of the Software, and to
11 * permit persons to whom the Software is furnished to do so, subject to
12 * the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
24 */
25
26#ifndef JAU_BASIC_ALGOS_HPP_
27#define JAU_BASIC_ALGOS_HPP_
28
29#include <mutex>
30#include <type_traits>
31
32#include <jau/cow_iterator.hpp>
33
34namespace jau {
35 /** @defgroup Algorithms Basic Algorithms
36 * Basic algorithms.
37 *
38 * @{
39 */
40
41 /**
42 * Call on release allows the user to pass a function
43 * to be called at destruction of this instance.
44 * <p>
45 * One goal was to provide a thread exit cleanup facility,
46 * setting a 'is_running' flag to false when the thread exists
47 * normally or abnormally.
48 * <pre>
49 * jau::relaxed_atomic_bool is_running = true;
50 *
51 * void some_thread_func() {
52 * thread_local jau::call_on_release thread_cleanup([&]() {
53 * is_running = false;
54 * });
55 * ...
56 * do some work here, which might get cancelled
57 * ..
58 * thread_cleanup.set_released(); // mark orderly release
59 * }
60 * </pre>
61 * </p>
62 * @tparam UnaryFunction user provided function to be called @ dtor
63 * @see jau::service_runner
64 */
65 template <class UnaryFunction> class call_on_release {
66 private:
67 UnaryFunction f;
68 jau::sc_atomic_bool released;
69
70 public:
71 call_on_release(UnaryFunction release_func) noexcept
72 : f(release_func), released(false) {}
73 ~call_on_release() noexcept {
74 if( !released ) { f(); }
75 }
78 call_on_release& operator=(const call_on_release&) volatile = delete;
79
80 /** Mark the resource being orderly released, `release_func()` will not be called and *use after free* avoided. */
81 void set_released() noexcept { released = true; }
82 /** Query whethr the resource has been orderly released. */
83 bool is_released() const noexcept { return released; }
84 };
85
86 /****************************************************************************************
87 ****************************************************************************************/
88
89 /**
90 * Like std::find() of 'algorithm'
91 * <p>
92 * Only exists here as performance analysis over O(n*n) complexity
93 * exposes std::find() to be approximately 3x slower.<br>
94 * See test/test_cow_darray_perf01.cpp
95 * </p>
96 * @tparam InputIt the iterator type
97 * @tparam T the data type
98 * @param first range start of elements to examine
99 * @param last range end of elements to examine, exclusive
100 * @param value reference value for comparison
101 * @return Iterator to the first element satisfying the condition or last if no such element is found.
102 */
103 template<class InputIt, class T>
104 constexpr InputIt find(InputIt first, InputIt last, const T& value)
105 {
106 for (; first != last; ++first) {
107 if (*first == value) {
108 return first;
109 }
110 }
111 return last; // implicit move since C++11
112 }
113
114 /**
115 * Return true if `value` is contained in `array`.
116 * @tparam InputArray array type
117 * @tparam T value_type of value
118 * @param array the array to search
119 * @param value the value to search for
120 * @return true if contained, otherwise false
121 */
122 template<class InputArray, class T>
123 constexpr bool contains(InputArray &array, const T& value)
124 {
125 const typename InputArray::size_type size = array.size();
126 for (typename InputArray::size_type i = 0; i < size; ++i) {
127 if( value == array[i] ) {
128 return true;
129 }
130 }
131 return false;
132 }
133
134 /**
135 * Like std::find_if() of 'algorithm'
136 * <p>
137 * Only exists here as performance analysis over O(n*n) complexity
138 * exposes std::find_if() to be approximately 3x slower for 1000 x 1000.<br>
139 * See test/test_cow_darray_perf01.cpp
140 * </p>
141 * @tparam InputIt the iterator type
142 * @tparam UnaryPredicate
143 * @param first range start of elements to examine
144 * @param last range end of elements to examine, exclusive
145 * @param p unary predicate which returns ​true for the desired element.
146 * @return Iterator to the first element satisfying the condition or last if no such element is found.
147 */
148 template<class InputIt, class UnaryPredicate>
149 constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
150 {
151 for (; first != last; ++first) {
152 if (p(*first)) {
153 return first;
154 }
155 }
156 return last; // implicit move since C++11
157 }
158
159 /**
160 * Like std::find_if_not() of 'algorithm'
161 * <p>
162 * Only exists here as performance analysis over O(n*n) complexity
163 * exposes std::find_if_not() to be approximately 3x slower for 1000 x 1000.<br>
164 * See test/test_cow_darray_perf01.cpp
165 * </p>
166 * @tparam InputIt the iterator type
167 * @tparam UnaryPredicate
168 * @param first range start of elements to examine
169 * @param last range end of elements to examine, exclusive
170 * @param q unary predicate which returns ​false for the desired element.
171 * @return Iterator to the first element satisfying the condition or last if no such element is found.
172 */
173 template<class InputIt, class UnaryPredicate>
174 constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q)
175 {
176 for (; first != last; ++first) {
177 if (!q(*first)) {
178 return first;
179 }
180 }
181 return last; // implicit move since C++11
182 }
183
184 /**
185 * Identical to C++20 std::remove_if() of `algorithm`
186 *
187 * @tparam ForwardIt the iterator type
188 * @tparam UnaryPredicate
189 * @param first range start of elements to examine
190 * @param last range end of elements to examine, exclusive
191 * @param p unary predicate which returns true for the desired element to be removed
192 * @return past-the end iterator for the new range of values.
193 */
194 template<class ForwardIt, class UnaryPredicate>
195 ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
196 {
197 first = jau::find_if(first, last, p);
198 if (first != last) {
199 for(ForwardIt i = first; ++i != last; ) {
200 if (!p(*i)) {
201 *first++ = std::move(*i);
202 }
203 }
204 }
205 return first; // implicit move since C++11
206 }
207
208 /**
209 * Like std::for_each() of 'algorithm'
210 * <p>
211 * Only exists here as performance analysis over O(n*n) complexity
212 * exposes std::for_each() to be 'a little' slower for 1000 x 1000.<br>
213 * See test/test_cow_darray_perf01.cpp
214 * </p>
215 * @tparam InputIt the iterator type
216 * @tparam UnaryFunction
217 * @param first range start of elements to apply the function
218 * @param last range end of elements to apply the function
219 * @param f the function object, like <code>void fun(const Type &a)</code>
220 * @return the function
221 */
222 template<class InputIt, class UnaryFunction>
223 constexpr UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
224 {
225 for (; first != last; ++first) {
226 f(*first);
227 }
228 return f; // implicit move since C++11
229 }
230
231 /****************************************************************************************
232 ****************************************************************************************/
233
234 /**
235 * Like jau::for_each(), see above.
236 * <p>
237 * Additionally this template function removes
238 * the <code>const</code> qualifier
239 * of the <code>UnaryFunction</code> sole argument.<br>
240 * The latter is retrieved by dereferencing the iterator,
241 * which might expose the <code>const</code> qualifier if
242 * the iterator is a <code>const_iterator</code>.
243 * </p>
244 * <p>
245 * Implementation casts argument in the following fashion
246 * <code>const_cast<value_type*>(&arg)</code>,
247 * allowing to use <code>const_iterator</code> and subsequent
248 * non-const features of the argument, see below.
249 * </p>
250 * <p>
251 * Such situations may occur when preferring to use
252 * the <code>const_iterator</code> over non-const.<br>
253 * jau::cow_darray is such a scenario, where one might
254 * not mutate the elements of the container itself
255 * but needs to invoke non-const functions <i>in good faith</i>.<br>
256 * Here we can avoid costly side-effects of copying the CoW storage for later replacement.<br>
257 * See jau::cow_ro_iterator and jau::cow_rw_iterator
258 * in conjunction with jau::cow_darray.
259 * </p>
260 * <p>
261 * Requirements for the given IteratorIt type are to
262 * have typename <code>InputIt::value_type</code> available.
263 * </p>
264 * @tparam InputIt the iterator type, which might be a 'const_iterator' for non const types.
265 * @tparam UnaryFunction
266 * @param first range start of elements to apply the function
267 * @param last range end of elements to apply the function
268 * @param f the function object, like <code>void fun(const Type &a)</code>
269 * @return the function
270 * @see jau::cow_darray
271 * @see jau::cow_ro_iterator
272 * @see jau::cow_rw_iterator
273 */
274 template<class InputIt, class UnaryFunction>
275 constexpr UnaryFunction for_each_fidelity(InputIt first, InputIt last, UnaryFunction f)
276 {
277 typedef typename InputIt::value_type value_type;
278
279 for (; first != last; ++first) {
280 f( *const_cast<value_type*>( & (*first) ) );
281 }
282 return f; // implicit move since C++11
283 }
284
285 /****************************************************************************************
286 ****************************************************************************************/
287
288 /**
289 * Custom for_each template, same as jau::for_each but using a mutex.
290 * <p>
291 * Method performs UnaryFunction on all elements [first..last).
292 * </p>
293 * <p>
294 * This method also utilizes a given mutex to ensure thread-safety,
295 * by operating within an RAII-style std::lock_guard block.
296 * </p>
297 */
298 template<class Mutex, class InputIt, class UnaryFunction>
299 constexpr UnaryFunction for_each_mtx(Mutex &mtx, InputIt first, InputIt last, UnaryFunction f)
300 {
301 const std::lock_guard<Mutex> lock(mtx); // RAII-style acquire and relinquish via destructor
302
303 for (; first != last; ++first) {
304 f(*first);
305 }
306 return f; // implicit move since C++11
307 }
308
309 /**
310 * Custom for_each template, using indices instead of iterators,
311 * allowing container to be modified within lambda 'callback'.
312 * <p>
313 * Method performs UnaryFunction on all elements [0..n-1],
314 * where n is being retrieved once before the loop!
315 * </p>
316 */
317 template<class InputArray, class UnaryFunction>
318 constexpr UnaryFunction for_each_idx(InputArray &array, UnaryFunction f)
319 {
320 const typename InputArray::size_type size = array.size();
321 for (typename InputArray::size_type i = 0; i < size; ++i) {
322 f(array[i]);
323 }
324 return f; // implicit move since C++11
325 }
326
327 /**
328 * Custom for_each template,
329 * same as jau::for_each but using indices instead of iterators and a mutex.
330 * <p>
331 * Method performs UnaryFunction on all elements [0..n-1],
332 * where n is being retrieved once before the loop!
333 * </p>
334 * <p>
335 * This method also utilizes a given mutex to ensure thread-safety,
336 * by operating within an RAII-style std::lock_guard block.
337 * </p>
338 */
339 template<class Mutex, class InputArray, class UnaryFunction>
340 constexpr UnaryFunction for_each_idx_mtx(Mutex &mtx, InputArray &array, UnaryFunction f)
341 {
342 const std::lock_guard<Mutex> lock(mtx); // RAII-style acquire and relinquish via destructor
343
344 const typename InputArray::size_type size = array.size();
345 for (typename InputArray::size_type i = 0; i < size; ++i) {
346 f(array[i]);
347 }
348 return f; // implicit move since C++11
349 }
350
351 /****************************************************************************************
352 ****************************************************************************************/
353
354 template<class T>
355 const typename T::value_type * find_const(T& data, typename T::value_type const & elem,
356 std::enable_if_t< is_cow_type<T>::value, bool> = true ) noexcept
357 {
358 for (typename T::const_iterator first = data.cbegin(); !first.is_end(); ++first) {
359 if (*first == elem) {
360 return &(*first);
361 }
362 }
363 return nullptr;
364 }
365 template<class T>
366 const typename T::value_type * find_const(T& data, typename T::value_type const & elem,
367 std::enable_if_t< !is_cow_type<T>::value, bool> = true ) noexcept
368 {
369 typename T::const_iterator first = data.cbegin();
370 typename T::const_iterator last = data.cend();
371 for (; first != last; ++first) {
372 if (*first == elem) {
373 return &(*first);
374 }
375 }
376 return nullptr;
377 }
378
379 /****************************************************************************************
380 ****************************************************************************************/
381
382 template<class T, class UnaryFunction>
383 constexpr UnaryFunction for_each_const(T& data, UnaryFunction f,
384 std::enable_if_t< is_cow_type<T>::value, bool> = true ) noexcept
385 {
386 for (typename T::const_iterator first = data.cbegin(); !first.is_end(); ++first) {
387 f(*first);
388 }
389 return f; // implicit move since C++11
390 }
391 template<class T, class UnaryFunction>
392 constexpr UnaryFunction for_each_const(T& data, UnaryFunction f,
393 std::enable_if_t< !is_cow_type<T>::value, bool> = true ) noexcept
394 {
395 typename T::const_iterator first = data.cbegin();
396 typename T::const_iterator last = data.cend();
397 for (; first != last; ++first) {
398 f(*first);
399 }
400 return f; // implicit move since C++11
401 }
402
403 /****************************************************************************************
404 ****************************************************************************************/
405
406 /**
407 * See jau::for_each_fidelity()
408 */
409 template<class T, class UnaryFunction>
410 constexpr UnaryFunction for_each_fidelity(T& data, UnaryFunction f,
411 std::enable_if_t< is_cow_type<T>::value, bool> = true ) noexcept
412 {
413 for (typename T::const_iterator first = data.cbegin(); !first.is_end(); ++first) {
414 f( *const_cast<typename T::value_type*>( & (*first) ) );
415 }
416 return f; // implicit move since C++11
417 }
418 /**
419 * See jau::for_each_fidelity()
420 */
421 template<class T, class UnaryFunction>
422 constexpr UnaryFunction for_each_fidelity(T& data, UnaryFunction f,
423 std::enable_if_t< !is_cow_type<T>::value, bool> = true ) noexcept
424 {
425 typename T::const_iterator first = data.cbegin();
426 typename T::const_iterator last = data.cend();
427 for (; first != last; ++first) {
428 f( *const_cast<typename T::value_type*>( & (*first) ) );
429 }
430 return f; // implicit move since C++11
431 }
432
433 /**@}*/
434
435} // namespace jau
436
437#endif /* JAU_BASIC_ALGOS_HPP_ */
Call on release allows the user to pass a function to be called at destruction of this instance.
Definition: basic_algos.hpp:65
~call_on_release() noexcept
Definition: basic_algos.hpp:73
call_on_release(UnaryFunction release_func) noexcept
Definition: basic_algos.hpp:71
call_on_release & operator=(const call_on_release &)=delete
call_on_release & operator=(const call_on_release &) volatile=delete
call_on_release(const call_on_release &)=delete
void set_released() noexcept
Mark the resource being orderly released, release_func() will not be called and use after free avoide...
Definition: basic_algos.hpp:81
bool is_released() const noexcept
Query whethr the resource has been orderly released.
Definition: basic_algos.hpp:83
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
Identical to C++20 std::remove_if() of algorithm
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q)
Like std::find_if_not() of 'algorithm'.
constexpr bool contains(InputArray &array, const T &value)
Return true if value is contained in array.
const T::value_type * find_const(T &data, typename T::value_type const &elem, std::enable_if_t< is_cow_type< T >::value, bool >=true) noexcept
constexpr UnaryFunction for_each_idx_mtx(Mutex &mtx, InputArray &array, UnaryFunction f)
Custom for_each template, same as jau::for_each but using indices instead of iterators and a mutex.
constexpr UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
Like std::for_each() of 'algorithm'.
constexpr UnaryFunction for_each_mtx(Mutex &mtx, InputIt first, InputIt last, UnaryFunction f)
Custom for_each template, same as jau::for_each but using a mutex.
constexpr InputIt find(InputIt first, InputIt last, const T &value)
Like std::find() of 'algorithm'.
constexpr UnaryFunction for_each_fidelity(InputIt first, InputIt last, UnaryFunction f)
Like jau::for_each(), see above.
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
Like std::find_if() of 'algorithm'.
constexpr UnaryFunction for_each_const(T &data, UnaryFunction f, std::enable_if_t< is_cow_type< T >::value, bool >=true) noexcept
constexpr UnaryFunction for_each_idx(InputArray &array, UnaryFunction f)
Custom for_each template, using indices instead of iterators, allowing container to be modified withi...
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
Definition: backtrace.hpp:32
template< class T > is_cow_type<T>::value compile-time Type Trait, determining whether the given temp...