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