qt.core.algorithms source code

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