1 | // Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com> |
2 | // Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> |
3 | // Copyright (C) 2020 The Qt Company Ltd. |
4 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
5 | |
6 | #if 0 |
7 | #pragma qt_sync_skip_header_check |
8 | #pragma qt_sync_stop_processing |
9 | #endif |
10 | |
11 | #ifndef QCONTAINERTOOLS_IMPL_H |
12 | #define QCONTAINERTOOLS_IMPL_H |
13 | |
14 | #include <QtCore/qglobal.h> |
15 | #include <QtCore/qtypeinfo.h> |
16 | |
17 | #include <QtCore/qxptype_traits.h> |
18 | |
19 | #include <cstring> |
20 | #include <iterator> |
21 | #include <memory> |
22 | #include <algorithm> |
23 | |
24 | QT_BEGIN_NAMESPACE |
25 | |
26 | namespace QtPrivate |
27 | { |
28 | |
29 | /*! |
30 | \internal |
31 | |
32 | Returns whether \a p is within a range [b, e). In simplest form equivalent to: |
33 | b <= p < e. |
34 | */ |
35 | template<typename T, typename Cmp = std::less<>> |
36 | static constexpr bool q_points_into_range(const T *p, const T *b, const T *e, |
37 | Cmp less = {}) noexcept |
38 | { |
39 | return !less(p, b) && less(p, e); |
40 | } |
41 | |
42 | /*! |
43 | \internal |
44 | |
45 | Returns whether \a p is within container \a c. In its simplest form equivalent to: |
46 | c.data() <= p < c.data() + c.size() |
47 | */ |
48 | template <typename C, typename T> |
49 | static constexpr bool q_points_into_range(const T &p, const C &c) noexcept |
50 | { |
51 | static_assert(std::is_same_v<decltype(std::data(c)), T>); |
52 | |
53 | // std::distance because QArrayDataPointer has a "qsizetype size" |
54 | // member but no size() function |
55 | return q_points_into_range(p, std::data(c), |
56 | std::data(c) + std::distance(std::begin(c), std::end(c))); |
57 | } |
58 | |
59 | QT_WARNING_PUSH |
60 | QT_WARNING_DISABLE_GCC("-Wmaybe-uninitialized" ) |
61 | |
62 | template <typename T, typename N> |
63 | void q_uninitialized_move_if_noexcept_n(T* first, N n, T* out) |
64 | { |
65 | if constexpr (std::is_nothrow_move_constructible_v<T> || !std::is_copy_constructible_v<T>) |
66 | std::uninitialized_move_n(first, n, out); |
67 | else |
68 | std::uninitialized_copy_n(first, n, out); |
69 | } |
70 | |
71 | template <typename T, typename N> |
72 | void q_uninitialized_relocate_n(T* first, N n, T* out) |
73 | { |
74 | if constexpr (QTypeInfo<T>::isRelocatable) { |
75 | static_assert(std::is_copy_constructible_v<T> || std::is_move_constructible_v<T>, |
76 | "Refusing to relocate this non-copy/non-move-constructible type." ); |
77 | if (n != N(0)) { // even if N == 0, out == nullptr or first == nullptr are UB for memcpy() |
78 | std::memcpy(dest: static_cast<void *>(out), |
79 | src: static_cast<const void *>(first), |
80 | n: n * sizeof(T)); |
81 | } |
82 | } else { |
83 | q_uninitialized_move_if_noexcept_n(first, n, out); |
84 | if constexpr (QTypeInfo<T>::isComplex) |
85 | std::destroy_n(first, n); |
86 | } |
87 | } |
88 | |
89 | QT_WARNING_POP |
90 | |
91 | /*! |
92 | \internal |
93 | |
94 | A wrapper around std::rotate(), with an optimization for |
95 | Q_RELOCATABLE_TYPEs. We omit the return value, as it would be more work to |
96 | compute in the Q_RELOCATABLE_TYPE case and, unlike std::rotate on |
97 | ForwardIterators, callers can compute the result in constant time |
98 | themselves. |
99 | */ |
100 | template <typename T> |
101 | void q_rotate(T *first, T *mid, T *last) |
102 | { |
103 | if constexpr (QTypeInfo<T>::isRelocatable) { |
104 | const auto cast = [](T *p) { return reinterpret_cast<uchar*>(p); }; |
105 | std::rotate(cast(first), cast(mid), cast(last)); |
106 | } else { |
107 | std::rotate(first, mid, last); |
108 | } |
109 | } |
110 | |
111 | /*! |
112 | \internal |
113 | Copies all elements, except the ones for which \a pred returns \c true, from |
114 | range [first, last), to the uninitialized memory buffer starting at \a out. |
115 | |
116 | It's undefined behavior if \a out points into [first, last). |
117 | |
118 | Returns a pointer one past the last copied element. |
119 | |
120 | If an exception is thrown, all the already copied elements in the destination |
121 | buffer are destroyed. |
122 | */ |
123 | template <typename T, typename Predicate> |
124 | T *q_uninitialized_remove_copy_if(T *first, T *last, T *out, Predicate &pred) |
125 | { |
126 | static_assert(std::is_nothrow_destructible_v<T>, |
127 | "This algorithm requires that T has a non-throwing destructor" ); |
128 | Q_ASSERT(!q_points_into_range(out, first, last)); |
129 | |
130 | T *dest_begin = out; |
131 | QT_TRY { |
132 | while (first != last) { |
133 | if (!pred(*first)) { |
134 | new (std::addressof(*out)) T(*first); |
135 | ++out; |
136 | } |
137 | ++first; |
138 | } |
139 | } QT_CATCH (...) { |
140 | std::destroy(std::reverse_iterator(out), std::reverse_iterator(dest_begin)); |
141 | QT_RETHROW; |
142 | } |
143 | return out; |
144 | } |
145 | |
146 | template<typename iterator, typename N> |
147 | void q_relocate_overlap_n_left_move(iterator first, N n, iterator d_first) |
148 | { |
149 | // requires: [first, n) is a valid range |
150 | // requires: d_first + n is reachable from d_first |
151 | // requires: iterator is at least a random access iterator |
152 | // requires: value_type(iterator) has a non-throwing destructor |
153 | |
154 | Q_ASSERT(n); |
155 | Q_ASSERT(d_first < first); // only allow moves to the "left" |
156 | using T = typename std::iterator_traits<iterator>::value_type; |
157 | |
158 | // Watches passed iterator. Unless commit() is called, all the elements that |
159 | // the watched iterator passes through are deleted at the end of object |
160 | // lifetime. freeze() could be used to stop watching the passed iterator and |
161 | // remain at current place. |
162 | // |
163 | // requires: the iterator is expected to always point to an invalid object |
164 | // (to uninitialized memory) |
165 | struct Destructor |
166 | { |
167 | iterator *iter; |
168 | iterator end; |
169 | iterator intermediate; |
170 | |
171 | Destructor(iterator &it) noexcept : iter(std::addressof(it)), end(it) { } |
172 | void commit() noexcept { iter = std::addressof(end); } |
173 | void freeze() noexcept |
174 | { |
175 | intermediate = *iter; |
176 | iter = std::addressof(intermediate); |
177 | } |
178 | ~Destructor() noexcept |
179 | { |
180 | for (const int step = *iter < end ? 1 : -1; *iter != end;) { |
181 | std::advance(*iter, step); |
182 | (*iter)->~T(); |
183 | } |
184 | } |
185 | } destroyer(d_first); |
186 | |
187 | const iterator d_last = d_first + n; |
188 | // Note: use pair and explicitly copy iterators from it to prevent |
189 | // accidental reference semantics instead of copy. equivalent to: |
190 | // |
191 | // auto [overlapBegin, overlapEnd] = std::minmax(d_last, first); |
192 | auto pair = std::minmax(d_last, first); |
193 | |
194 | // overlap area between [d_first, d_first + n) and [first, first + n) or an |
195 | // uninitialized memory area between the two ranges |
196 | iterator overlapBegin = pair.first; |
197 | iterator overlapEnd = pair.second; |
198 | |
199 | // move construct elements in uninitialized region |
200 | while (d_first != overlapBegin) { |
201 | // account for std::reverse_iterator, cannot use new(d_first) directly |
202 | new (std::addressof(*d_first)) T(std::move_if_noexcept(*first)); |
203 | ++d_first; |
204 | ++first; |
205 | } |
206 | |
207 | // cannot commit but have to stop - there might be an overlap region |
208 | // which we don't want to delete (because it's part of existing data) |
209 | destroyer.freeze(); |
210 | |
211 | // move assign elements in overlap region |
212 | while (d_first != d_last) { |
213 | *d_first = std::move_if_noexcept(*first); |
214 | ++d_first; |
215 | ++first; |
216 | } |
217 | |
218 | Q_ASSERT(d_first == destroyer.end + n); |
219 | destroyer.commit(); // can commit here as ~T() below does not throw |
220 | |
221 | while (first != overlapEnd) |
222 | (--first)->~T(); |
223 | } |
224 | |
225 | /*! |
226 | \internal |
227 | |
228 | Relocates a range [first, n) to [d_first, n) taking care of potential memory |
229 | overlaps. This is a generic equivalent of memmove. |
230 | |
231 | If an exception is thrown during the relocation, all the relocated elements |
232 | are destroyed and [first, n) may contain valid but unspecified values, |
233 | including moved-from values (basic exception safety). |
234 | */ |
235 | template<typename T, typename N> |
236 | void q_relocate_overlap_n(T *first, N n, T *d_first) |
237 | { |
238 | static_assert(std::is_nothrow_destructible_v<T>, |
239 | "This algorithm requires that T has a non-throwing destructor" ); |
240 | |
241 | if (n == N(0) || first == d_first || first == nullptr || d_first == nullptr) |
242 | return; |
243 | |
244 | if constexpr (QTypeInfo<T>::isRelocatable) { |
245 | std::memmove(dest: static_cast<void *>(d_first), src: static_cast<const void *>(first), n: n * sizeof(T)); |
246 | } else { // generic version has to be used |
247 | if (d_first < first) { |
248 | q_relocate_overlap_n_left_move(first, n, d_first); |
249 | } else { // first < d_first |
250 | auto rfirst = std::make_reverse_iterator(first + n); |
251 | auto rd_first = std::make_reverse_iterator(d_first + n); |
252 | q_relocate_overlap_n_left_move(rfirst, n, rd_first); |
253 | } |
254 | } |
255 | } |
256 | |
257 | template <typename Iterator> |
258 | using IfIsInputIterator = typename std::enable_if< |
259 | std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::input_iterator_tag>::value, |
260 | bool>::type; |
261 | |
262 | template <typename Iterator> |
263 | using IfIsForwardIterator = typename std::enable_if< |
264 | std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value, |
265 | bool>::type; |
266 | |
267 | template <typename Iterator> |
268 | using IfIsNotForwardIterator = typename std::enable_if< |
269 | !std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value, |
270 | bool>::type; |
271 | |
272 | template <typename Container, |
273 | typename InputIterator, |
274 | IfIsNotForwardIterator<InputIterator> = true> |
275 | void reserveIfForwardIterator(Container *, InputIterator, InputIterator) |
276 | { |
277 | } |
278 | |
279 | template <typename Container, |
280 | typename ForwardIterator, |
281 | IfIsForwardIterator<ForwardIterator> = true> |
282 | void reserveIfForwardIterator(Container *c, ForwardIterator f, ForwardIterator l) |
283 | { |
284 | c->reserve(static_cast<typename Container::size_type>(std::distance(f, l))); |
285 | } |
286 | |
287 | template <typename Iterator> |
288 | using KeyAndValueTest = decltype( |
289 | std::declval<Iterator &>().key(), |
290 | std::declval<Iterator &>().value() |
291 | ); |
292 | |
293 | template <typename Iterator> |
294 | using FirstAndSecondTest = decltype( |
295 | std::declval<Iterator &>()->first, |
296 | std::declval<Iterator &>()->second |
297 | ); |
298 | |
299 | template <typename Iterator> |
300 | using IfAssociativeIteratorHasKeyAndValue = |
301 | std::enable_if_t<qxp::is_detected_v<KeyAndValueTest, Iterator>, bool>; |
302 | |
303 | template <typename Iterator> |
304 | using IfAssociativeIteratorHasFirstAndSecond = |
305 | std::enable_if_t< |
306 | std::conjunction_v< |
307 | std::negation<qxp::is_detected<KeyAndValueTest, Iterator>>, |
308 | qxp::is_detected<FirstAndSecondTest, Iterator> |
309 | >, bool>; |
310 | |
311 | template <typename Iterator> |
312 | using MoveBackwardsTest = decltype( |
313 | std::declval<Iterator &>().operator--() |
314 | ); |
315 | |
316 | template <typename Iterator> |
317 | using IfIteratorCanMoveBackwards = |
318 | std::enable_if_t<qxp::is_detected_v<MoveBackwardsTest, Iterator>, bool>; |
319 | |
320 | template <typename T, typename U> |
321 | using IfIsNotSame = |
322 | typename std::enable_if<!std::is_same<T, U>::value, bool>::type; |
323 | |
324 | template<typename T, typename U> |
325 | using IfIsNotConvertible = typename std::enable_if<!std::is_convertible<T, U>::value, bool>::type; |
326 | |
327 | template <typename Container, typename Predicate> |
328 | auto sequential_erase_if(Container &c, Predicate &pred) |
329 | { |
330 | // This is remove_if() modified to perform the find_if step on |
331 | // const_iterators to avoid shared container detaches if nothing needs to |
332 | // be removed. We cannot run remove_if after find_if: doing so would apply |
333 | // the predicate to the first matching element twice! |
334 | |
335 | const auto cbegin = c.cbegin(); |
336 | const auto cend = c.cend(); |
337 | const auto t_it = std::find_if(cbegin, cend, pred); |
338 | auto result = std::distance(cbegin, t_it); |
339 | if (result == c.size()) |
340 | return result - result; // `0` of the right type |
341 | |
342 | // now detach: |
343 | const auto e = c.end(); |
344 | |
345 | auto it = std::next(c.begin(), result); |
346 | auto dest = it; |
347 | |
348 | // Loop Invariants: |
349 | // - it != e |
350 | // - [next(it), e[ still to be checked |
351 | // - [c.begin(), dest[ are result |
352 | while (++it != e) { |
353 | if (!pred(*it)) { |
354 | *dest = std::move(*it); |
355 | ++dest; |
356 | } |
357 | } |
358 | |
359 | result = std::distance(dest, e); |
360 | c.erase(dest, e); |
361 | return result; |
362 | } |
363 | |
364 | template <typename Container, typename T> |
365 | auto sequential_erase(Container &c, const T &t) |
366 | { |
367 | // use the equivalence relation from http://eel.is/c++draft/list.erasure#1 |
368 | auto cmp = [&](auto &e) { return e == t; }; |
369 | return sequential_erase_if(c, cmp); // can't pass rvalues! |
370 | } |
371 | |
372 | template <typename Container, typename T> |
373 | auto sequential_erase_with_copy(Container &c, const T &t) |
374 | { |
375 | using CopyProxy = std::conditional_t<std::is_copy_constructible_v<T>, T, const T &>; |
376 | return sequential_erase(c, CopyProxy(t)); |
377 | } |
378 | |
379 | template <typename Container, typename T> |
380 | auto sequential_erase_one(Container &c, const T &t) |
381 | { |
382 | const auto cend = c.cend(); |
383 | const auto it = std::find(c.cbegin(), cend, t); |
384 | if (it == cend) |
385 | return false; |
386 | c.erase(it); |
387 | return true; |
388 | } |
389 | |
390 | template <typename T, typename Predicate> |
391 | qsizetype qset_erase_if(QSet<T> &set, Predicate &pred) |
392 | { |
393 | qsizetype result = 0; |
394 | auto it = set.begin(); |
395 | const auto e = set.end(); |
396 | while (it != e) { |
397 | if (pred(*it)) { |
398 | ++result; |
399 | it = set.erase(it); |
400 | } else { |
401 | ++it; |
402 | } |
403 | } |
404 | return result; |
405 | } |
406 | |
407 | |
408 | // Prerequisite: F is invocable on ArgTypes |
409 | template <typename R, typename F, typename ... ArgTypes> |
410 | struct is_invoke_result_explicitly_convertible : std::is_constructible<R, std::invoke_result_t<F, ArgTypes...>> |
411 | {}; |
412 | |
413 | // is_invocable_r checks for implicit conversions, but we need to check |
414 | // for explicit conversions in remove_if. So, roll our own trait. |
415 | template <typename R, typename F, typename ... ArgTypes> |
416 | constexpr bool is_invocable_explicit_r_v = std::conjunction_v< |
417 | std::is_invocable<F, ArgTypes...>, |
418 | is_invoke_result_explicitly_convertible<R, F, ArgTypes...> |
419 | >; |
420 | |
421 | template <typename Container, typename Predicate> |
422 | auto associative_erase_if(Container &c, Predicate &pred) |
423 | { |
424 | // we support predicates callable with either Container::iterator |
425 | // or with std::pair<const Key &, Value &> |
426 | using Iterator = typename Container::iterator; |
427 | using Key = typename Container::key_type; |
428 | using Value = typename Container::mapped_type; |
429 | using KeyValuePair = std::pair<const Key &, Value &>; |
430 | |
431 | typename Container::size_type result = 0; |
432 | |
433 | auto it = c.begin(); |
434 | const auto e = c.end(); |
435 | while (it != e) { |
436 | if constexpr (is_invocable_explicit_r_v<bool, Predicate &, Iterator &>) { |
437 | if (pred(it)) { |
438 | it = c.erase(it); |
439 | ++result; |
440 | } else { |
441 | ++it; |
442 | } |
443 | } else if constexpr (is_invocable_explicit_r_v<bool, Predicate &, KeyValuePair &&>) { |
444 | KeyValuePair p(it.key(), it.value()); |
445 | if (pred(std::move(p))) { |
446 | it = c.erase(it); |
447 | ++result; |
448 | } else { |
449 | ++it; |
450 | } |
451 | } else { |
452 | static_assert(sizeof(Container) == 0, "Predicate has an incompatible signature" ); |
453 | } |
454 | } |
455 | |
456 | return result; |
457 | } |
458 | |
459 | } // namespace QtPrivate |
460 | |
461 | QT_END_NAMESPACE |
462 | |
463 | #endif // QCONTAINERTOOLS_IMPL_H |
464 | |