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