1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of the QtCore module of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see https://www.qt.io/terms-conditions. For further
15 ** information use the contact form at https://www.qt.io/contact-us.
16 **
17 ** GNU Lesser General Public License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Lesser
19 ** General Public License version 3 as published by the Free Software
20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the
21 ** packaging of this file. Please review the following information to
22 ** ensure the GNU Lesser General Public License version 3 requirements
23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24 **
25 ** GNU General Public License Usage
26 ** Alternatively, this file may be used under the terms of the GNU
27 ** General Public License version 2.0 or (at your option) the GNU General
28 ** Public license version 3 or any later version approved by the KDE Free
29 ** Qt Foundation. The licenses are as published by the Free Software
30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31 ** included in the packaging of this file. Please review the following
32 ** information to ensure the GNU General Public License requirements will
33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34 ** https://www.gnu.org/licenses/gpl-3.0.html.
35 **
36 ** $QT_END_LICENSE$
37 **
38 ****************************************************************************/
39
40 #ifndef QALGORITHMS_H
41 #define QALGORITHMS_H
42
43 #include <QtCore/qglobal.h>
44
45 #ifdef Q_CC_MSVC
46 #include <intrin.h>
47 #endif
48
49 QT_BEGIN_NAMESPACE
50 QT_WARNING_PUSH
51 QT_WARNING_DISABLE_DEPRECATED
52
53 /*
54 Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
55 and may be changed from version to version or even be completely removed.
56 */
57 namespace QAlgorithmsPrivate {
58
59 #if QT_DEPRECATED_SINCE(5, 2)
60 template <typename RandomAccessIterator, typename T, typename LessThan>
61 QT_DEPRECATED_X("Use std::sort") Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
62 template <typename RandomAccessIterator, typename T>
63 QT_DEPRECATED_X("Use std::sort") inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);
64
65 template <typename RandomAccessIterator, typename T, typename LessThan>
66 QT_DEPRECATED_X("Use std::stable_sort") Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
67 template <typename RandomAccessIterator, typename T>
68 QT_DEPRECATED_X("Use std::stable_sort") inline void qStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);
69
70 template <typename RandomAccessIterator, typename T, typename LessThan>
71 QT_DEPRECATED_X("Use std::lower_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
72 template <typename RandomAccessIterator, typename T, typename LessThan>
73 QT_DEPRECATED_X("Use std::upper_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
74 template <typename RandomAccessIterator, typename T, typename LessThan>
75 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
76 #endif // QT_DEPRECATED_SINCE(5, 2)
77
78 }
79
80 #if QT_DEPRECATED_SINCE(5, 2)
81 template <typename InputIterator, typename OutputIterator>
qCopy(InputIterator begin,InputIterator end,OutputIterator dest)82 QT_DEPRECATED_X("Use std::copy") inline OutputIterator qCopy(InputIterator begin, InputIterator end, OutputIterator dest)
83 {
84 while (begin != end)
85 *dest++ = *begin++;
86 return dest;
87 }
88
89 template <typename BiIterator1, typename BiIterator2>
qCopyBackward(BiIterator1 begin,BiIterator1 end,BiIterator2 dest)90 QT_DEPRECATED_X("Use std::copy_backward") inline BiIterator2 qCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
91 {
92 while (begin != end)
93 *--dest = *--end;
94 return dest;
95 }
96
97 template <typename InputIterator1, typename InputIterator2>
qEqual(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2)98 QT_DEPRECATED_X("Use std::equal") inline bool qEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
99 {
100 for (; first1 != last1; ++first1, ++first2)
101 if (!(*first1 == *first2))
102 return false;
103 return true;
104 }
105
106 template <typename ForwardIterator, typename T>
qFill(ForwardIterator first,ForwardIterator last,const T & val)107 QT_DEPRECATED_X("Use std::fill") inline void qFill(ForwardIterator first, ForwardIterator last, const T &val)
108 {
109 for (; first != last; ++first)
110 *first = val;
111 }
112
113 template <typename Container, typename T>
qFill(Container & container,const T & val)114 QT_DEPRECATED_X("Use std::fill") inline void qFill(Container &container, const T &val)
115 {
116 qFill(container.begin(), container.end(), val);
117 }
118
119 template <typename InputIterator, typename T>
qFind(InputIterator first,InputIterator last,const T & val)120 QT_DEPRECATED_X("Use std::find") inline InputIterator qFind(InputIterator first, InputIterator last, const T &val)
121 {
122 while (first != last && !(*first == val))
123 ++first;
124 return first;
125 }
126
127 template <typename Container, typename T>
qFind(const Container & container,const T & val)128 QT_DEPRECATED_X("Use std::find") inline typename Container::const_iterator qFind(const Container &container, const T &val)
129 {
130 return qFind(container.constBegin(), container.constEnd(), val);
131 }
132
133 template <typename InputIterator, typename T, typename Size>
qCount(InputIterator first,InputIterator last,const T & value,Size & n)134 QT_DEPRECATED_X("Use std::count") inline void qCount(InputIterator first, InputIterator last, const T &value, Size &n)
135 {
136 for (; first != last; ++first)
137 if (*first == value)
138 ++n;
139 }
140
141 template <typename Container, typename T, typename Size>
qCount(const Container & container,const T & value,Size & n)142 QT_DEPRECATED_X("Use std::count") inline void qCount(const Container &container, const T &value, Size &n)
143 {
144 qCount(container.constBegin(), container.constEnd(), value, n);
145 }
146
147 #ifdef Q_QDOC
148 typedef void* LessThan;
149 template <typename T> LessThan qLess();
150 template <typename T> LessThan qGreater();
151 #else
152 template <typename T>
153 class QT_DEPRECATED_X("Use std::less") qLess
154 {
155 public:
operator()156 inline bool operator()(const T &t1, const T &t2) const
157 {
158 return (t1 < t2);
159 }
160 };
161
162 template <typename T>
163 class QT_DEPRECATED_X("Use std::greater") qGreater
164 {
165 public:
operator()166 inline bool operator()(const T &t1, const T &t2) const
167 {
168 return (t2 < t1);
169 }
170 };
171 #endif
172
173 template <typename RandomAccessIterator>
qSort(RandomAccessIterator start,RandomAccessIterator end)174 QT_DEPRECATED_X("Use std::sort") inline void qSort(RandomAccessIterator start, RandomAccessIterator end)
175 {
176 if (start != end)
177 QAlgorithmsPrivate::qSortHelper(start, end, *start);
178 }
179
180 template <typename RandomAccessIterator, typename LessThan>
qSort(RandomAccessIterator start,RandomAccessIterator end,LessThan lessThan)181 QT_DEPRECATED_X("Use std::sort") inline void qSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
182 {
183 if (start != end)
184 QAlgorithmsPrivate::qSortHelper(start, end, *start, lessThan);
185 }
186
187 template<typename Container>
qSort(Container & c)188 QT_DEPRECATED_X("Use std::sort") inline void qSort(Container &c)
189 {
190 #ifdef Q_CC_BOR
191 // Work around Borland 5.5 optimizer bug
192 c.detach();
193 #endif
194 if (!c.empty())
195 QAlgorithmsPrivate::qSortHelper(c.begin(), c.end(), *c.begin());
196 }
197
198 template <typename RandomAccessIterator>
qStableSort(RandomAccessIterator start,RandomAccessIterator end)199 QT_DEPRECATED_X("Use std::stable_sort") inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end)
200 {
201 if (start != end)
202 QAlgorithmsPrivate::qStableSortHelper(start, end, *start);
203 }
204
205 template <typename RandomAccessIterator, typename LessThan>
qStableSort(RandomAccessIterator start,RandomAccessIterator end,LessThan lessThan)206 QT_DEPRECATED_X("Use std::stable_sort") inline void qStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
207 {
208 if (start != end)
209 QAlgorithmsPrivate::qStableSortHelper(start, end, *start, lessThan);
210 }
211
212 template<typename Container>
qStableSort(Container & c)213 QT_DEPRECATED_X("Use std::stable_sort") inline void qStableSort(Container &c)
214 {
215 #ifdef Q_CC_BOR
216 // Work around Borland 5.5 optimizer bug
217 c.detach();
218 #endif
219 if (!c.empty())
220 QAlgorithmsPrivate::qStableSortHelper(c.begin(), c.end(), *c.begin());
221 }
222
223 template <typename RandomAccessIterator, typename T>
qLowerBound(RandomAccessIterator begin,RandomAccessIterator end,const T & value)224 QT_DEPRECATED_X("Use std::lower_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
225 {
226 // Implementation is duplicated from QAlgorithmsPrivate to keep existing code
227 // compiling. We have to allow using *begin and value with different types,
228 // and then implementing operator< for those types.
229 RandomAccessIterator middle;
230 int n = end - begin;
231 int half;
232
233 while (n > 0) {
234 half = n >> 1;
235 middle = begin + half;
236 if (*middle < value) {
237 begin = middle + 1;
238 n -= half + 1;
239 } else {
240 n = half;
241 }
242 }
243 return begin;
244 }
245
246 template <typename RandomAccessIterator, typename T, typename LessThan>
qLowerBound(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)247 QT_DEPRECATED_X("Use std::lower_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
248 {
249 return QAlgorithmsPrivate::qLowerBoundHelper(begin, end, value, lessThan);
250 }
251
252 template <typename Container, typename T>
qLowerBound(const Container & container,const T & value)253 QT_DEPRECATED_X("Use std::lower_bound") Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qLowerBound(const Container &container, const T &value)
254 {
255 return QAlgorithmsPrivate::qLowerBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
256 }
257
258 template <typename RandomAccessIterator, typename T>
qUpperBound(RandomAccessIterator begin,RandomAccessIterator end,const T & value)259 QT_DEPRECATED_X("Use std::upper_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
260 {
261 // Implementation is duplicated from QAlgorithmsPrivate.
262 RandomAccessIterator middle;
263 int n = end - begin;
264 int half;
265
266 while (n > 0) {
267 half = n >> 1;
268 middle = begin + half;
269 if (value < *middle) {
270 n = half;
271 } else {
272 begin = middle + 1;
273 n -= half + 1;
274 }
275 }
276 return begin;
277 }
278
279 template <typename RandomAccessIterator, typename T, typename LessThan>
qUpperBound(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)280 QT_DEPRECATED_X("Use std::upper_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
281 {
282 return QAlgorithmsPrivate::qUpperBoundHelper(begin, end, value, lessThan);
283 }
284
285 template <typename Container, typename T>
qUpperBound(const Container & container,const T & value)286 QT_DEPRECATED_X("Use std::upper_bound") Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qUpperBound(const Container &container, const T &value)
287 {
288 return QAlgorithmsPrivate::qUpperBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
289 }
290
291 template <typename RandomAccessIterator, typename T>
qBinaryFind(RandomAccessIterator begin,RandomAccessIterator end,const T & value)292 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
293 {
294 // Implementation is duplicated from QAlgorithmsPrivate.
295 RandomAccessIterator it = qLowerBound(begin, end, value);
296
297 if (it == end || value < *it)
298 return end;
299
300 return it;
301 }
302
303 template <typename RandomAccessIterator, typename T, typename LessThan>
qBinaryFind(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)304 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
305 {
306 return QAlgorithmsPrivate::qBinaryFindHelper(begin, end, value, lessThan);
307 }
308
309 template <typename Container, typename T>
qBinaryFind(const Container & container,const T & value)310 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE typename Container::const_iterator qBinaryFind(const Container &container, const T &value)
311 {
312 return QAlgorithmsPrivate::qBinaryFindHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
313 }
314 #endif // QT_DEPRECATED_SINCE(5, 2)
315
316 template <typename ForwardIterator>
qDeleteAll(ForwardIterator begin,ForwardIterator end)317 Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
318 {
319 while (begin != end) {
320 delete *begin;
321 ++begin;
322 }
323 }
324
325 template <typename Container>
qDeleteAll(const Container & c)326 inline void qDeleteAll(const Container &c)
327 {
328 qDeleteAll(c.begin(), c.end());
329 }
330
331 /*
332 Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
333 and may be changed from version to version or even be completely removed.
334 */
335 namespace QAlgorithmsPrivate {
336
337 #if QT_DEPRECATED_SINCE(5, 2)
338
339 template <typename RandomAccessIterator, typename T, typename LessThan>
qSortHelper(RandomAccessIterator start,RandomAccessIterator end,const T & t,LessThan lessThan)340 QT_DEPRECATED_X("Use std::sort") Q_OUTOFLINE_TEMPLATE void qSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
341 {
342 top:
343 int span = int(end - start);
344 if (span < 2)
345 return;
346
347 --end;
348 RandomAccessIterator low = start, high = end - 1;
349 RandomAccessIterator pivot = start + span / 2;
350
351 if (lessThan(*end, *start))
352 qSwap(*end, *start);
353 if (span == 2)
354 return;
355
356 if (lessThan(*pivot, *start))
357 qSwap(*pivot, *start);
358 if (lessThan(*end, *pivot))
359 qSwap(*end, *pivot);
360 if (span == 3)
361 return;
362
363 qSwap(*pivot, *end);
364
365 while (low < high) {
366 while (low < high && lessThan(*low, *end))
367 ++low;
368
369 while (high > low && lessThan(*end, *high))
370 --high;
371
372 if (low < high) {
373 qSwap(*low, *high);
374 ++low;
375 --high;
376 } else {
377 break;
378 }
379 }
380
381 if (lessThan(*low, *end))
382 ++low;
383
384 qSwap(*end, *low);
385 qSortHelper(start, low, t, lessThan);
386
387 start = low + 1;
388 ++end;
389 goto top;
390 }
391
392 template <typename RandomAccessIterator, typename T>
qSortHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & dummy)393 QT_DEPRECATED_X("Use std::sort") inline void qSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
394 {
395 qSortHelper(begin, end, dummy, qLess<T>());
396 }
397
398 template <typename RandomAccessIterator>
qReverse(RandomAccessIterator begin,RandomAccessIterator end)399 QT_DEPRECATED_X("Use std::reverse") Q_OUTOFLINE_TEMPLATE void qReverse(RandomAccessIterator begin, RandomAccessIterator end)
400 {
401 --end;
402 while (begin < end)
403 qSwap(*begin++, *end--);
404 }
405
406 template <typename RandomAccessIterator>
qRotate(RandomAccessIterator begin,RandomAccessIterator middle,RandomAccessIterator end)407 QT_DEPRECATED_X("Use std::rotate") Q_OUTOFLINE_TEMPLATE void qRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
408 {
409 qReverse(begin, middle);
410 qReverse(middle, end);
411 qReverse(begin, end);
412 }
413
414 template <typename RandomAccessIterator, typename T, typename LessThan>
qMerge(RandomAccessIterator begin,RandomAccessIterator pivot,RandomAccessIterator end,T & t,LessThan lessThan)415 QT_DEPRECATED_X("Use std::merge") Q_OUTOFLINE_TEMPLATE void qMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
416 {
417 const int len1 = pivot - begin;
418 const int len2 = end - pivot;
419
420 if (len1 == 0 || len2 == 0)
421 return;
422
423 if (len1 + len2 == 2) {
424 if (lessThan(*(begin + 1), *(begin)))
425 qSwap(*begin, *(begin + 1));
426 return;
427 }
428
429 RandomAccessIterator firstCut;
430 RandomAccessIterator secondCut;
431 int len2Half;
432 if (len1 > len2) {
433 const int len1Half = len1 / 2;
434 firstCut = begin + len1Half;
435 secondCut = qLowerBound(pivot, end, *firstCut, lessThan);
436 len2Half = secondCut - pivot;
437 } else {
438 len2Half = len2 / 2;
439 secondCut = pivot + len2Half;
440 firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
441 }
442
443 qRotate(firstCut, pivot, secondCut);
444 const RandomAccessIterator newPivot = firstCut + len2Half;
445 qMerge(begin, firstCut, newPivot, t, lessThan);
446 qMerge(newPivot, secondCut, end, t, lessThan);
447 }
448
449 template <typename RandomAccessIterator, typename T, typename LessThan>
qStableSortHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & t,LessThan lessThan)450 QT_DEPRECATED_X("Use std::stable_sort") Q_OUTOFLINE_TEMPLATE void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &t, LessThan lessThan)
451 {
452 const int span = end - begin;
453 if (span < 2)
454 return;
455
456 const RandomAccessIterator middle = begin + span / 2;
457 qStableSortHelper(begin, middle, t, lessThan);
458 qStableSortHelper(middle, end, t, lessThan);
459 qMerge(begin, middle, end, t, lessThan);
460 }
461
462 template <typename RandomAccessIterator, typename T>
qStableSortHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & dummy)463 QT_DEPRECATED_X("Use std::stable_sort") inline void qStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
464 {
465 qStableSortHelper(begin, end, dummy, qLess<T>());
466 }
467
468 template <typename RandomAccessIterator, typename T, typename LessThan>
qLowerBoundHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)469 QT_DEPRECATED_X("Use std::lower_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
470 {
471 RandomAccessIterator middle;
472 int n = int(end - begin);
473 int half;
474
475 while (n > 0) {
476 half = n >> 1;
477 middle = begin + half;
478 if (lessThan(*middle, value)) {
479 begin = middle + 1;
480 n -= half + 1;
481 } else {
482 n = half;
483 }
484 }
485 return begin;
486 }
487
488
489 template <typename RandomAccessIterator, typename T, typename LessThan>
qUpperBoundHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)490 QT_DEPRECATED_X("Use std::upper_bound") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
491 {
492 RandomAccessIterator middle;
493 int n = end - begin;
494 int half;
495
496 while (n > 0) {
497 half = n >> 1;
498 middle = begin + half;
499 if (lessThan(value, *middle)) {
500 n = half;
501 } else {
502 begin = middle + 1;
503 n -= half + 1;
504 }
505 }
506 return begin;
507 }
508
509 template <typename RandomAccessIterator, typename T, typename LessThan>
qBinaryFindHelper(RandomAccessIterator begin,RandomAccessIterator end,const T & value,LessThan lessThan)510 QT_DEPRECATED_X("Use std::binary_search") Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
511 {
512 RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan);
513
514 if (it == end || lessThan(value, *it))
515 return end;
516
517 return it;
518 }
519
520 #endif // QT_DEPRECATED_SINCE(5, 2)
521
522 #ifdef Q_CC_CLANG
523 // Clang had a bug where __builtin_ctz/clz/popcount were not marked as constexpr.
524 # if (defined __apple_build_version__ && __clang_major__ >= 7) || (Q_CC_CLANG >= 307)
525 # define QT_HAS_CONSTEXPR_BUILTINS
526 # endif
527 #elif defined(Q_CC_MSVC) && !defined(Q_CC_INTEL) && !defined(Q_PROCESSOR_ARM)
528 # define QT_HAS_CONSTEXPR_BUILTINS
529 #elif defined(Q_CC_GNU)
530 # define QT_HAS_CONSTEXPR_BUILTINS
531 #endif
532
533 #if defined QT_HAS_CONSTEXPR_BUILTINS
534 #if defined(Q_CC_GNU) || defined(Q_CC_CLANG)
535 # define QT_HAS_BUILTIN_CTZS
qt_builtin_ctzs(quint16 v)536 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
537 {
538 # if __has_builtin(__builtin_ctzs)
539 return __builtin_ctzs(v);
540 # else
541 return __builtin_ctz(v);
542 # endif
543 }
544 #define QT_HAS_BUILTIN_CLZS
qt_builtin_clzs(quint16 v)545 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
546 {
547 # if __has_builtin(__builtin_clzs)
548 return __builtin_clzs(v);
549 # else
550 return __builtin_clz(v) - 16U;
551 # endif
552 }
553 #define QT_HAS_BUILTIN_CTZ
qt_builtin_ctz(quint32 v)554 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_ctz(quint32 v) noexcept
555 {
556 return __builtin_ctz(v);
557 }
558 #define QT_HAS_BUILTIN_CLZ
qt_builtin_clz(quint32 v)559 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_clz(quint32 v) noexcept
560 {
561 return __builtin_clz(v);
562 }
563 #define QT_HAS_BUILTIN_CTZLL
qt_builtin_ctzll(quint64 v)564 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_ctzll(quint64 v) noexcept
565 {
566 return __builtin_ctzll(v);
567 }
568 #define QT_HAS_BUILTIN_CLZLL
qt_builtin_clzll(quint64 v)569 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_clzll(quint64 v) noexcept
570 {
571 return __builtin_clzll(v);
572 }
573 #define QALGORITHMS_USE_BUILTIN_POPCOUNT
qt_builtin_popcount(quint32 v)574 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
575 {
576 return __builtin_popcount(v);
577 }
qt_builtin_popcount(quint8 v)578 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
579 {
580 return __builtin_popcount(v);
581 }
qt_builtin_popcount(quint16 v)582 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
583 {
584 return __builtin_popcount(v);
585 }
586 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
qt_builtin_popcountll(quint64 v)587 Q_DECL_CONSTEXPR Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
588 {
589 return __builtin_popcountll(v);
590 }
591 #elif defined(Q_CC_MSVC) && !defined(Q_PROCESSOR_ARM)
592 #define QT_POPCOUNT_CONSTEXPR
593 #define QT_POPCOUNT_RELAXED_CONSTEXPR
594 #define QT_HAS_BUILTIN_CTZ
qt_builtin_ctz(quint32 val)595 Q_ALWAYS_INLINE unsigned long qt_builtin_ctz(quint32 val)
596 {
597 unsigned long result;
598 _BitScanForward(&result, val);
599 return result;
600 }
601 #define QT_HAS_BUILTIN_CLZ
qt_builtin_clz(quint32 val)602 Q_ALWAYS_INLINE unsigned long qt_builtin_clz(quint32 val)
603 {
604 unsigned long result;
605 _BitScanReverse(&result, val);
606 // Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31
607 // and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it
608 // starts there), and the lsb index is 31.
609 result ^= sizeof(quint32) * 8 - 1;
610 return result;
611 }
612 #if Q_PROCESSOR_WORDSIZE == 8
613 // These are only defined for 64bit builds.
614 #define QT_HAS_BUILTIN_CTZLL
qt_builtin_ctzll(quint64 val)615 Q_ALWAYS_INLINE unsigned long qt_builtin_ctzll(quint64 val)
616 {
617 unsigned long result;
618 _BitScanForward64(&result, val);
619 return result;
620 }
621 // MSVC calls it _BitScanReverse and returns the carry flag, which we don't need
622 #define QT_HAS_BUILTIN_CLZLL
qt_builtin_clzll(quint64 val)623 Q_ALWAYS_INLINE unsigned long qt_builtin_clzll(quint64 val)
624 {
625 unsigned long result;
626 _BitScanReverse64(&result, val);
627 // see qt_builtin_clz
628 result ^= sizeof(quint64) * 8 - 1;
629 return result;
630 }
631 #endif // MSVC 64bit
632 # define QT_HAS_BUILTIN_CTZS
qt_builtin_ctzs(quint16 v)633 Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
634 {
635 return qt_builtin_ctz(v);
636 }
637 #define QT_HAS_BUILTIN_CLZS
qt_builtin_clzs(quint16 v)638 Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
639 {
640 return qt_builtin_clz(v) - 16U;
641 }
642
643 // Neither MSVC nor the Intel compiler define a macro for the POPCNT processor
644 // feature, so we're using either the SSE4.2 or the AVX macro as a proxy (Clang
645 // does define the macro). It's incorrect for two reasons:
646 // 1. It's a separate bit in CPUID, so a processor could implement SSE4.2 and
647 // not POPCNT, but that's unlikely to happen.
648 // 2. There are processors that support POPCNT but not AVX (Intel Nehalem
649 // architecture), but unlike the other compilers, MSVC has no option
650 // to generate code for those processors.
651 // So it's an acceptable compromise.
652 #if defined(__AVX__) || defined(__SSE4_2__) || defined(__POPCNT__)
653 #define QALGORITHMS_USE_BUILTIN_POPCOUNT
654 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
qt_builtin_popcount(quint32 v)655 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
656 {
657 return __popcnt(v);
658 }
qt_builtin_popcount(quint8 v)659 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
660 {
661 return __popcnt16(v);
662 }
qt_builtin_popcount(quint16 v)663 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
664 {
665 return __popcnt16(v);
666 }
qt_builtin_popcountll(quint64 v)667 Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
668 {
669 #if Q_PROCESSOR_WORDSIZE == 8
670 return __popcnt64(v);
671 #else
672 return __popcnt(quint32(v)) + __popcnt(quint32(v >> 32));
673 #endif // MSVC 64bit
674 }
675
676 #endif // __AVX__ || __SSE4_2__ || __POPCNT__
677
678 #endif // MSVC
679 #endif // QT_HAS_CONSTEXPR_BUILTINS
680
681 #ifndef QT_POPCOUNT_CONSTEXPR
682 #define QT_POPCOUNT_CONSTEXPR Q_DECL_CONSTEXPR
683 #define QT_POPCOUNT_RELAXED_CONSTEXPR Q_DECL_RELAXED_CONSTEXPR
684 #endif
685
686 } //namespace QAlgorithmsPrivate
687
qPopulationCount(quint32 v)688 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint32 v) noexcept
689 {
690 #ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT
691 return QAlgorithmsPrivate::qt_builtin_popcount(v);
692 #else
693 // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
694 return
695 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
696 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
697 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
698 #endif
699 }
700
qPopulationCount(quint8 v)701 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint8 v) noexcept
702 {
703 #ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT
704 return QAlgorithmsPrivate::qt_builtin_popcount(v);
705 #else
706 return
707 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
708 #endif
709 }
710
qPopulationCount(quint16 v)711 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint16 v) noexcept
712 {
713 #ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT
714 return QAlgorithmsPrivate::qt_builtin_popcount(v);
715 #else
716 return
717 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
718 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
719 #endif
720 }
721
qPopulationCount(quint64 v)722 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint64 v) noexcept
723 {
724 #ifdef QALGORITHMS_USE_BUILTIN_POPCOUNTLL
725 return QAlgorithmsPrivate::qt_builtin_popcountll(v);
726 #else
727 return
728 (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
729 (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
730 (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
731 (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
732 (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
733 (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
734 #endif
735 }
736
qPopulationCount(long unsigned int v)737 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(long unsigned int v) noexcept
738 {
739 return qPopulationCount(static_cast<quint64>(v));
740 }
741
742 #if defined(Q_CC_GNU) && !defined(Q_CC_CLANG)
743 #undef QALGORITHMS_USE_BUILTIN_POPCOUNT
744 #endif
745 #undef QT_POPCOUNT_CONSTEXPR
746
qCountTrailingZeroBits(quint32 v)747 Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint32 v) noexcept
748 {
749 #if defined(QT_HAS_BUILTIN_CTZ)
750 return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 32U;
751 #else
752 // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
753 unsigned int c = 32; // c will be the number of zero bits on the right
754 v &= -signed(v);
755 if (v) c--;
756 if (v & 0x0000FFFF) c -= 16;
757 if (v & 0x00FF00FF) c -= 8;
758 if (v & 0x0F0F0F0F) c -= 4;
759 if (v & 0x33333333) c -= 2;
760 if (v & 0x55555555) c -= 1;
761 return c;
762 #endif
763 }
764
qCountTrailingZeroBits(quint8 v)765 Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint8 v) noexcept
766 {
767 #if defined(QT_HAS_BUILTIN_CTZ)
768 return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 8U;
769 #else
770 unsigned int c = 8; // c will be the number of zero bits on the right
771 v &= -signed(v);
772 if (v) c--;
773 if (v & 0x0000000F) c -= 4;
774 if (v & 0x00000033) c -= 2;
775 if (v & 0x00000055) c -= 1;
776 return c;
777 #endif
778 }
779
qCountTrailingZeroBits(quint16 v)780 Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint16 v) noexcept
781 {
782 #if defined(QT_HAS_BUILTIN_CTZS)
783 return v ? QAlgorithmsPrivate::qt_builtin_ctzs(v) : 16U;
784 #else
785 unsigned int c = 16; // c will be the number of zero bits on the right
786 v &= -signed(v);
787 if (v) c--;
788 if (v & 0x000000FF) c -= 8;
789 if (v & 0x00000F0F) c -= 4;
790 if (v & 0x00003333) c -= 2;
791 if (v & 0x00005555) c -= 1;
792 return c;
793 #endif
794 }
795
qCountTrailingZeroBits(quint64 v)796 Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(quint64 v) noexcept
797 {
798 #if defined(QT_HAS_BUILTIN_CTZLL)
799 return v ? QAlgorithmsPrivate::qt_builtin_ctzll(v) : 64;
800 #else
801 quint32 x = static_cast<quint32>(v);
802 return x ? qCountTrailingZeroBits(x)
803 : 32 + qCountTrailingZeroBits(static_cast<quint32>(v >> 32));
804 #endif
805 }
806
qCountTrailingZeroBits(unsigned long v)807 Q_DECL_RELAXED_CONSTEXPR inline uint qCountTrailingZeroBits(unsigned long v) noexcept
808 {
809 return qCountTrailingZeroBits(QIntegerForSizeof<long>::Unsigned(v));
810 }
811
qCountLeadingZeroBits(quint32 v)812 Q_DECL_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint32 v) noexcept
813 {
814 #if defined(QT_HAS_BUILTIN_CLZ)
815 return v ? QAlgorithmsPrivate::qt_builtin_clz(v) : 32U;
816 #else
817 // Hacker's Delight, 2nd ed. Fig 5-16, p. 102
818 v = v | (v >> 1);
819 v = v | (v >> 2);
820 v = v | (v >> 4);
821 v = v | (v >> 8);
822 v = v | (v >> 16);
823 return qPopulationCount(~v);
824 #endif
825 }
826
qCountLeadingZeroBits(quint8 v)827 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint8 v) noexcept
828 {
829 #if defined(QT_HAS_BUILTIN_CLZ)
830 return v ? QAlgorithmsPrivate::qt_builtin_clz(v)-24U : 8U;
831 #else
832 v = v | (v >> 1);
833 v = v | (v >> 2);
834 v = v | (v >> 4);
835 return qPopulationCount(static_cast<quint8>(~v));
836 #endif
837 }
838
qCountLeadingZeroBits(quint16 v)839 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint16 v) noexcept
840 {
841 #if defined(QT_HAS_BUILTIN_CLZS)
842 return v ? QAlgorithmsPrivate::qt_builtin_clzs(v) : 16U;
843 #else
844 v = v | (v >> 1);
845 v = v | (v >> 2);
846 v = v | (v >> 4);
847 v = v | (v >> 8);
848 return qPopulationCount(static_cast<quint16>(~v));
849 #endif
850 }
851
qCountLeadingZeroBits(quint64 v)852 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint64 v) noexcept
853 {
854 #if defined(QT_HAS_BUILTIN_CLZLL)
855 return v ? QAlgorithmsPrivate::qt_builtin_clzll(v) : 64U;
856 #else
857 v = v | (v >> 1);
858 v = v | (v >> 2);
859 v = v | (v >> 4);
860 v = v | (v >> 8);
861 v = v | (v >> 16);
862 v = v | (v >> 32);
863 return qPopulationCount(~v);
864 #endif
865 }
866
qCountLeadingZeroBits(unsigned long v)867 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(unsigned long v) noexcept
868 {
869 return qCountLeadingZeroBits(QIntegerForSizeof<long>::Unsigned(v));
870 }
871
872 QT_WARNING_POP
873 QT_END_NAMESPACE
874
875 #endif // QALGORITHMS_H
876