1/****************************************************************************
2**
3** Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
4** Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
5** Copyright (C) 2020 The Qt Company Ltd.
6** Contact: https://www.qt.io/licensing/
7**
8** This file is part of the QtCore module of the Qt Toolkit.
9**
10** $QT_BEGIN_LICENSE:LGPL$
11** Commercial License Usage
12** Licensees holding valid commercial Qt licenses may use this file in
13** accordance with the commercial license agreement provided with the
14** Software or, alternatively, in accordance with the terms contained in
15** a written agreement between you and The Qt Company. For licensing terms
16** and conditions see https://www.qt.io/terms-conditions. For further
17** information use the contact form at https://www.qt.io/contact-us.
18**
19** GNU Lesser General Public License Usage
20** Alternatively, this file may be used under the terms of the GNU Lesser
21** General Public License version 3 as published by the Free Software
22** Foundation and appearing in the file LICENSE.LGPL3 included in the
23** packaging of this file. Please review the following information to
24** ensure the GNU Lesser General Public License version 3 requirements
25** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
26**
27** GNU General Public License Usage
28** Alternatively, this file may be used under the terms of the GNU
29** General Public License version 2.0 or (at your option) the GNU General
30** Public license version 3 or any later version approved by the KDE Free
31** Qt Foundation. The licenses are as published by the Free Software
32** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
33** included in the packaging of this file. Please review the following
34** information to ensure the GNU General Public License requirements will
35** be met: https://www.gnu.org/licenses/gpl-2.0.html and
36** https://www.gnu.org/licenses/gpl-3.0.html.
37**
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#if 0
43#pragma qt_sync_skip_header_check
44#pragma qt_sync_stop_processing
45#endif
46
47#ifndef QCONTAINERTOOLS_IMPL_H
48#define QCONTAINERTOOLS_IMPL_H
49
50#include <QtCore/qglobal.h>
51#include <QtCore/qtypeinfo.h>
52
53#include <cstring>
54#include <iterator>
55#include <memory>
56
57QT_BEGIN_NAMESPACE
58
59namespace QtPrivate
60{
61
62template <typename T, typename N>
63void q_uninitialized_relocate_n(T* first, N n, T* out)
64{
65 if constexpr (QTypeInfo<T>::isRelocatable) {
66 if (n != N(0)) { // even if N == 0, out == nullptr or first == nullptr are UB for memmove()
67 std::memmove(static_cast<void*>(out),
68 static_cast<const void*>(first),
69 n * sizeof(T));
70 }
71 } else {
72 std::uninitialized_move_n(first, n, out);
73 if constexpr (QTypeInfo<T>::isComplex)
74 std::destroy_n(first, n);
75 }
76}
77
78
79template <typename Iterator>
80using IfIsInputIterator = typename std::enable_if<
81 std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::input_iterator_tag>::value,
82 bool>::type;
83
84template <typename Iterator>
85using IfIsForwardIterator = typename std::enable_if<
86 std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value,
87 bool>::type;
88
89template <typename Iterator>
90using IfIsNotForwardIterator = typename std::enable_if<
91 !std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value,
92 bool>::type;
93
94template <typename Container,
95 typename InputIterator,
96 IfIsNotForwardIterator<InputIterator> = true>
97void reserveIfForwardIterator(Container *, InputIterator, InputIterator)
98{
99}
100
101template <typename Container,
102 typename ForwardIterator,
103 IfIsForwardIterator<ForwardIterator> = true>
104void reserveIfForwardIterator(Container *c, ForwardIterator f, ForwardIterator l)
105{
106 c->reserve(static_cast<typename Container::size_type>(std::distance(f, l)));
107}
108
109template <typename Iterator, typename = std::void_t<>>
110struct AssociativeIteratorHasKeyAndValue : std::false_type
111{
112};
113
114template <typename Iterator>
115struct AssociativeIteratorHasKeyAndValue<
116 Iterator,
117 std::void_t<decltype(std::declval<Iterator &>().key()),
118 decltype(std::declval<Iterator &>().value())>
119 >
120 : std::true_type
121{
122};
123
124template <typename Iterator, typename = std::void_t<>, typename = std::void_t<>>
125struct AssociativeIteratorHasFirstAndSecond : std::false_type
126{
127};
128
129template <typename Iterator>
130struct AssociativeIteratorHasFirstAndSecond<
131 Iterator,
132 std::void_t<decltype(std::declval<Iterator &>()->first),
133 decltype(std::declval<Iterator &>()->second)>
134 >
135 : std::true_type
136{
137};
138
139template <typename Iterator>
140using IfAssociativeIteratorHasKeyAndValue =
141 typename std::enable_if<AssociativeIteratorHasKeyAndValue<Iterator>::value, bool>::type;
142
143template <typename Iterator>
144using IfAssociativeIteratorHasFirstAndSecond =
145 typename std::enable_if<AssociativeIteratorHasFirstAndSecond<Iterator>::value, bool>::type;
146
147template <typename T, typename U>
148using IfIsNotSame =
149 typename std::enable_if<!std::is_same<T, U>::value, bool>::type;
150
151template<typename T, typename U>
152using IfIsNotConvertible = typename std::enable_if<!std::is_convertible<T, U>::value, bool>::type;
153
154template <typename Container, typename T>
155auto sequential_erase(Container &c, const T &t)
156{
157 // avoid a detach in case there is nothing to remove
158 const auto cbegin = c.cbegin();
159 const auto cend = c.cend();
160 const auto t_it = std::find(cbegin, cend, t);
161 auto result = std::distance(cbegin, t_it);
162 if (result == c.size())
163 return result - result; // `0` of the right type
164
165 const auto e = c.end();
166 const auto it = std::remove(std::next(c.begin(), result), e, t);
167 result = std::distance(it, e);
168 c.erase(it, e);
169 return result;
170}
171
172template <typename Container, typename T>
173auto sequential_erase_with_copy(Container &c, const T &t)
174{
175 using CopyProxy = std::conditional_t<std::is_copy_constructible_v<T>, T, const T &>;
176 const T &tCopy = CopyProxy(t);
177 return sequential_erase(c, tCopy);
178}
179
180template <typename Container, typename T>
181auto sequential_erase_one(Container &c, const T &t)
182{
183 const auto cend = c.cend();
184 const auto it = std::find(c.cbegin(), cend, t);
185 if (it == cend)
186 return false;
187 c.erase(it);
188 return true;
189}
190
191template <typename Container, typename Predicate>
192auto sequential_erase_if(Container &c, Predicate &pred)
193{
194 // avoid a detach in case there is nothing to remove
195 const auto cbegin = c.cbegin();
196 const auto cend = c.cend();
197 const auto t_it = std::find_if(cbegin, cend, pred);
198 auto result = std::distance(cbegin, t_it);
199 if (result == c.size())
200 return result - result; // `0` of the right type
201
202 const auto e = c.end();
203 const auto it = std::remove_if(std::next(c.begin(), result), e, pred);
204 result = std::distance(it, e);
205 c.erase(it, e);
206 return result;
207}
208
209template <typename T, typename Predicate>
210qsizetype qset_erase_if(QSet<T> &set, Predicate &pred)
211{
212 qsizetype result = 0;
213 auto it = set.begin();
214 const auto e = set.end();
215 while (it != e) {
216 if (pred(*it)) {
217 ++result;
218 it = set.erase(it);
219 } else {
220 ++it;
221 }
222 }
223 return result;
224}
225
226
227// Prerequisite: F is invocable on ArgTypes
228template <typename R, typename F, typename ... ArgTypes>
229struct is_invoke_result_explicitly_convertible : std::is_constructible<R, std::invoke_result_t<F, ArgTypes...>>
230{};
231
232// is_invocable_r checks for implicit conversions, but we need to check
233// for explicit conversions in remove_if. So, roll our own trait.
234template <typename R, typename F, typename ... ArgTypes>
235constexpr bool is_invocable_explicit_r_v = std::conjunction_v<
236 std::is_invocable<F, ArgTypes...>,
237 is_invoke_result_explicitly_convertible<R, F, ArgTypes...>
238>;
239
240template <typename Container, typename Predicate>
241auto associative_erase_if(Container &c, Predicate &pred)
242{
243 // we support predicates callable with either Container::iterator
244 // or with std::pair<const Key &, Value &>
245 using Iterator = typename Container::iterator;
246 using Key = typename Container::key_type;
247 using Value = typename Container::mapped_type;
248 using KeyValuePair = std::pair<const Key &, Value &>;
249
250 typename Container::size_type result = 0;
251
252 auto it = c.begin();
253 const auto e = c.end();
254 while (it != e) {
255 if constexpr (is_invocable_explicit_r_v<bool, Predicate &, Iterator &>) {
256 if (pred(it)) {
257 it = c.erase(it);
258 ++result;
259 } else {
260 ++it;
261 }
262 } else if constexpr (is_invocable_explicit_r_v<bool, Predicate &, KeyValuePair &&>) {
263 KeyValuePair p(it.key(), it.value());
264 if (pred(std::move(p))) {
265 it = c.erase(it);
266 ++result;
267 } else {
268 ++it;
269 }
270 } else {
271 static_assert(sizeof(Container) == 0, "Predicate has an incompatible signature");
272 }
273 }
274
275 return result;
276}
277
278} // namespace QtPrivate
279
280QT_END_NAMESPACE
281
282#endif // QCONTAINERTOOLS_IMPL_H
283