include/QtCore/qalgorithms.h

0001 // Copyright (C) 2020 The Qt Company Ltd.
0002 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0003
0004 #ifndef QALGORITHMS_H
0005 #define QALGORITHMS_H
0006
0007 #if 0
0008 #pragma qt_class(QtAlgorithms)
0009 #endif
0010
0011 #include <QtCore/qglobal.h>
0012 #include <QtCore/q20functional.h>
0013
0014 #if __has_include(<bit>) && __cplusplus > 201703L
0015 #include <bit>
0016 #endif
0017 #include <type_traits>
0018
0019 #ifdef Q_CC_MSVC
0020 #include <intrin.h>
0021 #endif
0022
0023 QT_BEGIN_NAMESPACE
0024
0025 template <typename ForwardIterator>
0026 Q_OUTOFLINE_TEMPLATE void qDeleteAll(ForwardIterator begin, ForwardIterator end)
0027 {
0028     while (begin != end) {
0029         delete *begin;
0030         ++begin;
0031     }
0032 }
0033
0034 template <typename Container>
0035 inline void qDeleteAll(const Container &c)
0036 {
0037     qDeleteAll(c.begin(), c.end());
0038 }
0039
0040 /*
0041     Warning: The contents of QAlgorithmsPrivate is not a part of the public Qt API
0042     and may be changed from version to version or even be completely removed.
0043 */
0044 namespace QAlgorithmsPrivate {
0045
0046 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0047 // We use C++20 <bit> operations instead which ensures constexpr bit ops
0048 #  define QT_HAS_CONSTEXPR_BITOPS
0049 #elif defined(Q_CC_GNU)
0050 #  define QT_HAS_CONSTEXPR_BITOPS
0051 #  define QT_HAS_BUILTIN_CTZS
0052 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
0053 {
0054 #  if __has_builtin(__builtin_ctzs)
0055     return __builtin_ctzs(v);
0056 #  else
0057     return __builtin_ctz(v);
0058 #  endif
0059 }
0060 #define QT_HAS_BUILTIN_CLZS
0061 constexpr Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
0062 {
0063 #  if __has_builtin(__builtin_clzs)
0064     return __builtin_clzs(v);
0065 #  else
0066     return __builtin_clz(v) - 16U;
0067 #  endif
0068 }
0069 #define QT_HAS_BUILTIN_CTZ
0070 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctz(quint32 v) noexcept
0071 {
0072     return __builtin_ctz(v);
0073 }
0074 #define QT_HAS_BUILTIN_CLZ
0075 constexpr Q_ALWAYS_INLINE uint qt_builtin_clz(quint32 v) noexcept
0076 {
0077     return __builtin_clz(v);
0078 }
0079 #define QT_HAS_BUILTIN_CTZLL
0080 constexpr Q_ALWAYS_INLINE uint qt_builtin_ctzll(quint64 v) noexcept
0081 {
0082     return __builtin_ctzll(v);
0083 }
0084 #define QT_HAS_BUILTIN_CLZLL
0085 constexpr Q_ALWAYS_INLINE uint qt_builtin_clzll(quint64 v) noexcept
0086 {
0087     return __builtin_clzll(v);
0088 }
0089 #define QALGORITHMS_USE_BUILTIN_POPCOUNT
0090 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
0091 {
0092     return __builtin_popcount(v);
0093 }
0094 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
0095 {
0096     return __builtin_popcount(v);
0097 }
0098 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
0099 {
0100     return __builtin_popcount(v);
0101 }
0102 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
0103 constexpr Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
0104 {
0105     return __builtin_popcountll(v);
0106 }
0107 #elif defined(Q_CC_MSVC) && !defined(Q_PROCESSOR_ARM)
0108 #define QT_HAS_BUILTIN_CTZ
0109 Q_ALWAYS_INLINE unsigned long qt_builtin_ctz(quint32 val)
0110 {
0111     unsigned long result;
0112     _BitScanForward(&result, val);
0113     return result;
0114 }
0115 #define QT_HAS_BUILTIN_CLZ
0116 Q_ALWAYS_INLINE unsigned long qt_builtin_clz(quint32 val)
0117 {
0118     unsigned long result;
0119     _BitScanReverse(&result, val);
0120     // Now Invert the result: clz will count *down* from the msb to the lsb, so the msb index is 31
0121     // and the lsb index is 0. The result for the index when counting up: msb index is 0 (because it
0122     // starts there), and the lsb index is 31.
0123     result ^= sizeof(quint32) * 8 - 1;
0124     return result;
0125 }
0126 #if Q_PROCESSOR_WORDSIZE == 8
0127 // These are only defined for 64bit builds.
0128 #define QT_HAS_BUILTIN_CTZLL
0129 Q_ALWAYS_INLINE unsigned long qt_builtin_ctzll(quint64 val)
0130 {
0131     unsigned long result;
0132     _BitScanForward64(&result, val);
0133     return result;
0134 }
0135 // MSVC calls it _BitScanReverse and returns the carry flag, which we don't need
0136 #define QT_HAS_BUILTIN_CLZLL
0137 Q_ALWAYS_INLINE unsigned long qt_builtin_clzll(quint64 val)
0138 {
0139     unsigned long result;
0140     _BitScanReverse64(&result, val);
0141     // see qt_builtin_clz
0142     result ^= sizeof(quint64) * 8 - 1;
0143     return result;
0144 }
0145 #endif // MSVC 64bit
0146 #  define QT_HAS_BUILTIN_CTZS
0147 Q_ALWAYS_INLINE uint qt_builtin_ctzs(quint16 v) noexcept
0148 {
0149     return qt_builtin_ctz(v);
0150 }
0151 #define QT_HAS_BUILTIN_CLZS
0152 Q_ALWAYS_INLINE uint qt_builtin_clzs(quint16 v) noexcept
0153 {
0154     return qt_builtin_clz(v) - 16U;
0155 }
0156
0157 // Neither MSVC nor the Intel compiler define a macro for the POPCNT processor
0158 // feature, so we're using either the SSE4.2 or the AVX macro as a proxy (Clang
0159 // does define the macro). It's incorrect for two reasons:
0160 // 1. It's a separate bit in CPUID, so a processor could implement SSE4.2 and
0161 //    not POPCNT, but that's unlikely to happen.
0162 // 2. There are processors that support POPCNT but not AVX (Intel Nehalem
0163 //    architecture), but unlike the other compilers, MSVC has no option
0164 //    to generate code for those processors.
0165 // So it's an acceptable compromise.
0166 #if defined(__AVX__) || defined(__SSE4_2__) || defined(__POPCNT__)
0167 #define QT_POPCOUNT_CONSTEXPR
0168 #define QT_POPCOUNT_RELAXED_CONSTEXPR
0169 #define QALGORITHMS_USE_BUILTIN_POPCOUNT
0170 #define QALGORITHMS_USE_BUILTIN_POPCOUNTLL
0171 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint32 v) noexcept
0172 {
0173     return __popcnt(v);
0174 }
0175 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint8 v) noexcept
0176 {
0177     return __popcnt16(v);
0178 }
0179 Q_ALWAYS_INLINE uint qt_builtin_popcount(quint16 v) noexcept
0180 {
0181     return __popcnt16(v);
0182 }
0183 Q_ALWAYS_INLINE uint qt_builtin_popcountll(quint64 v) noexcept
0184 {
0185 #if Q_PROCESSOR_WORDSIZE == 8
0186     return __popcnt64(v);
0187 #else
0188     return __popcnt(quint32(v)) + __popcnt(quint32(v >> 32));
0189 #endif // MSVC 64bit
0190 }
0191
0192 #endif // __AVX__ || __SSE4_2__ || __POPCNT__
0193
0194 #endif // MSVC
0195
0196 #ifndef QT_POPCOUNT_CONSTEXPR
0197 #define QT_POPCOUNT_CONSTEXPR constexpr
0198 #define QT_POPCOUNT_RELAXED_CONSTEXPR constexpr
0199 #endif
0200
0201 } //namespace QAlgorithmsPrivate
0202
0203 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint32 v) noexcept
0204 {
0205 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0206     return std::popcount(v);
0207 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
0208     return QAlgorithmsPrivate::qt_builtin_popcount(v);
0209 #else
0210     // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
0211     return
0212         (((v      ) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0213         (((v >> 12) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0214         (((v >> 24) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0215 #endif
0216 }
0217
0218 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint8 v) noexcept
0219 {
0220 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0221     return std::popcount(v);
0222 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
0223     return QAlgorithmsPrivate::qt_builtin_popcount(v);
0224 #else
0225     return
0226         (((v      ) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0227 #endif
0228 }
0229
0230 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint16 v) noexcept
0231 {
0232 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0233     return std::popcount(v);
0234 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNT
0235     return QAlgorithmsPrivate::qt_builtin_popcount(v);
0236 #else
0237     return
0238         (((v      ) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0239         (((v >> 12) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0240 #endif
0241 }
0242
0243 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(quint64 v) noexcept
0244 {
0245 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0246     return std::popcount(v);
0247 #elif defined QALGORITHMS_USE_BUILTIN_POPCOUNTLL
0248     return QAlgorithmsPrivate::qt_builtin_popcountll(v);
0249 #else
0250     return
0251         (((v      ) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0252         (((v >> 12) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0253         (((v >> 24) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0254         (((v >> 36) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0255         (((v >> 48) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f +
0256         (((v >> 60) & 0xfff)    * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f;
0257 #endif
0258 }
0259
0260 Q_DECL_CONST_FUNCTION QT_POPCOUNT_CONSTEXPR inline uint qPopulationCount(long unsigned int v) noexcept
0261 {
0262     return qPopulationCount(static_cast<quint64>(v));
0263 }
0264
0265 #if defined(QALGORITHMS_USE_BUILTIN_POPCOUNT)
0266 #undef QALGORITHMS_USE_BUILTIN_POPCOUNT
0267 #endif
0268 #undef QT_POPCOUNT_CONSTEXPR
0269
0270 namespace QtPrivate {
0271 constexpr inline uint qConstexprCountTrailingZeroBits(quint32 v) noexcept
0272 {
0273     // see http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
0274     unsigned int c = 32; // c will be the number of zero bits on the right
0275     v &= -signed(v);
0276     if (v) c--;
0277     if (v & 0x0000FFFF) c -= 16;
0278     if (v & 0x00FF00FF) c -= 8;
0279     if (v & 0x0F0F0F0F) c -= 4;
0280     if (v & 0x33333333) c -= 2;
0281     if (v & 0x55555555) c -= 1;
0282     return c;
0283 }
0284
0285 constexpr inline uint qConstexprCountTrailingZeroBits(quint64 v) noexcept
0286 {
0287     quint32 x = static_cast<quint32>(v);
0288     return x ? qConstexprCountTrailingZeroBits(x)
0289              : 32 + qConstexprCountTrailingZeroBits(static_cast<quint32>(v >> 32));
0290 }
0291
0292 constexpr inline uint qConstexprCountTrailingZeroBits(quint8 v) noexcept
0293 {
0294     unsigned int c = 8; // c will be the number of zero bits on the right
0295     v &= quint8(-signed(v));
0296     if (v) c--;
0297     if (v & 0x0000000F) c -= 4;
0298     if (v & 0x00000033) c -= 2;
0299     if (v & 0x00000055) c -= 1;
0300     return c;
0301 }
0302
0303 constexpr inline uint qConstexprCountTrailingZeroBits(quint16 v) noexcept
0304 {
0305     unsigned int c = 16; // c will be the number of zero bits on the right
0306     v &= quint16(-signed(v));
0307     if (v) c--;
0308     if (v & 0x000000FF) c -= 8;
0309     if (v & 0x00000F0F) c -= 4;
0310     if (v & 0x00003333) c -= 2;
0311     if (v & 0x00005555) c -= 1;
0312     return c;
0313 }
0314
0315 constexpr inline uint qConstexprCountTrailingZeroBits(unsigned long v) noexcept
0316 {
0317     return qConstexprCountTrailingZeroBits(QIntegerForSizeof<long>::Unsigned(v));
0318 }
0319 }
0320
0321 constexpr inline uint qCountTrailingZeroBits(quint32 v) noexcept
0322 {
0323 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0324     return std::countr_zero(v);
0325 #elif defined(QT_HAS_BUILTIN_CTZ)
0326     return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 32U;
0327 #else
0328     return QtPrivate::qConstexprCountTrailingZeroBits(v);
0329 #endif
0330 }
0331
0332 constexpr inline uint qCountTrailingZeroBits(quint8 v) noexcept
0333 {
0334 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0335     return std::countr_zero(v);
0336 #elif defined(QT_HAS_BUILTIN_CTZ)
0337     return v ? QAlgorithmsPrivate::qt_builtin_ctz(v) : 8U;
0338 #else
0339     return QtPrivate::qConstexprCountTrailingZeroBits(v);
0340 #endif
0341 }
0342
0343 constexpr inline uint qCountTrailingZeroBits(quint16 v) noexcept
0344 {
0345 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0346     return std::countr_zero(v);
0347 #elif defined(QT_HAS_BUILTIN_CTZS)
0348     return v ? QAlgorithmsPrivate::qt_builtin_ctzs(v) : 16U;
0349 #else
0350     return QtPrivate::qConstexprCountTrailingZeroBits(v);
0351 #endif
0352 }
0353
0354 constexpr inline uint qCountTrailingZeroBits(quint64 v) noexcept
0355 {
0356 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0357     return std::countr_zero(v);
0358 #elif defined(QT_HAS_BUILTIN_CTZLL)
0359     return v ? QAlgorithmsPrivate::qt_builtin_ctzll(v) : 64;
0360 #else
0361     return QtPrivate::qConstexprCountTrailingZeroBits(v);
0362 #endif
0363 }
0364
0365 constexpr inline uint qCountTrailingZeroBits(unsigned long v) noexcept
0366 {
0367     return qCountTrailingZeroBits(QIntegerForSizeof<long>::Unsigned(v));
0368 }
0369
0370 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint32 v) noexcept
0371 {
0372 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0373     return std::countl_zero(v);
0374 #elif defined(QT_HAS_BUILTIN_CLZ)
0375     return v ? QAlgorithmsPrivate::qt_builtin_clz(v) : 32U;
0376 #else
0377     // Hacker's Delight, 2nd ed. Fig 5-16, p. 102
0378     v = v | (v >> 1);
0379     v = v | (v >> 2);
0380     v = v | (v >> 4);
0381     v = v | (v >> 8);
0382     v = v | (v >> 16);
0383     return qPopulationCount(~v);
0384 #endif
0385 }
0386
0387 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint8 v) noexcept
0388 {
0389 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0390     return std::countl_zero(v);
0391 #elif defined(QT_HAS_BUILTIN_CLZ)
0392     return v ? QAlgorithmsPrivate::qt_builtin_clz(v)-24U : 8U;
0393 #else
0394     v = v | (v >> 1);
0395     v = v | (v >> 2);
0396     v = v | (v >> 4);
0397     return qPopulationCount(static_cast<quint8>(~v));
0398 #endif
0399 }
0400
0401 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint16 v) noexcept
0402 {
0403 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0404     return std::countl_zero(v);
0405 #elif defined(QT_HAS_BUILTIN_CLZS)
0406     return v ? QAlgorithmsPrivate::qt_builtin_clzs(v) : 16U;
0407 #else
0408     v = v | (v >> 1);
0409     v = v | (v >> 2);
0410     v = v | (v >> 4);
0411     v = v | (v >> 8);
0412     return qPopulationCount(static_cast<quint16>(~v));
0413 #endif
0414 }
0415
0416 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(quint64 v) noexcept
0417 {
0418 #if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
0419     return std::countl_zero(v);
0420 #elif defined(QT_HAS_BUILTIN_CLZLL)
0421     return v ? QAlgorithmsPrivate::qt_builtin_clzll(v) : 64U;
0422 #else
0423     v = v | (v >> 1);
0424     v = v | (v >> 2);
0425     v = v | (v >> 4);
0426     v = v | (v >> 8);
0427     v = v | (v >> 16);
0428     v = v | (v >> 32);
0429     return qPopulationCount(~v);
0430 #endif
0431 }
0432
0433 QT_POPCOUNT_RELAXED_CONSTEXPR inline uint qCountLeadingZeroBits(unsigned long v) noexcept
0434 {
0435     return qCountLeadingZeroBits(QIntegerForSizeof<long>::Unsigned(v));
0436 }
0437
0438 #undef QT_POPCOUNT_RELAXED_CONSTEXPR
0439
0440 template <typename InputIterator, typename Result, typename Separator = Result,
0441           typename Projection = q20::identity>
0442 Result qJoin(InputIterator first, InputIterator last, Result init, const Separator &separator = {},
0443              Projection p = {})
0444 {
0445     if (first != last) {
0446         init += std::invoke(p, *first);
0447         ++first;
0448     }
0449
0450     while (first != last) {
0451         init += separator;
0452         init += std::invoke(p, *first);
0453         ++first;
0454     }
0455
0456     return init;
0457 }
0458
0459 namespace QtPrivate {
0460
0461 template <typename T>
0462 constexpr
0463 std::enable_if_t<std::conjunction_v<std::is_integral<T>, std::is_unsigned<T>>, int>
0464 log2i(T x)
0465 {
0466     // Integral -> int version of std::log2():
0467     Q_ASSERT(x > 0); // Q_PRE
0468     // C++20: return std::bit_width(x) - 1
0469     return int(sizeof(T) * 8 - 1 - qCountLeadingZeroBits(x));
0470 }
0471
0472 } // namespace QtPrivate
0473
0474 QT_END_NAMESPACE
0475
0476 #endif // QALGORITHMS_H