diff options
Diffstat (limited to 'src/corelib/tools/qalgorithms.h')
| -rw-r--r-- | src/corelib/tools/qalgorithms.h | 72 |
1 files changed, 70 insertions, 2 deletions
diff --git a/src/corelib/tools/qalgorithms.h b/src/corelib/tools/qalgorithms.h index e3b76886f1..3bd3812e78 100644 --- a/src/corelib/tools/qalgorithms.h +++ b/src/corelib/tools/qalgorithms.h @@ -43,6 +43,7 @@ #define QALGORITHMS_H #include <QtCore/qglobal.h> +#include <algorithm> QT_BEGIN_NAMESPACE @@ -292,7 +293,7 @@ template <typename RandomAccessIterator, typename T> Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value) { // Implementation is duplicated from QAlgorithmsPrivate. - RandomAccessIterator it = qLowerBound(begin, end, value); + RandomAccessIterator it = std::lower_bound(begin, end, value); if (it == end || value < *it) return end; @@ -506,7 +507,7 @@ Q_OUTOFLINE_TEMPLATE RandomAccessIterator qUpperBoundHelper(RandomAccessIterator template <typename RandomAccessIterator, typename T, typename LessThan> Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) { - RandomAccessIterator it = qLowerBoundHelper(begin, end, value, lessThan); + RandomAccessIterator it = std::lower_bound(begin, end, value, lessThan); if (it == end || lessThan(value, *it)) return end; @@ -516,6 +517,73 @@ Q_OUTOFLINE_TEMPLATE RandomAccessIterator qBinaryFindHelper(RandomAccessIterator } //namespace QAlgorithmsPrivate + +// Use __builtin_popcount on gcc. Clang claims to be gcc +// but has a bug where __builtin_popcount is not marked as +// constexpr. +#if defined(Q_CC_GNU) && !defined(Q_CC_CLANG) +#define QALGORITHMS_USE_BUILTIN_POPCOUNT +#endif + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint32 v) +{ +#ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT + return __builtin_popcount(v); +#else + // See http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +#endif +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint8 v) +{ +#ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT + return __builtin_popcount(v); +#else + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +#endif +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint16 v) +{ +#ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT + return __builtin_popcount(v); +#else + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +#endif +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(quint64 v) +{ +#ifdef QALGORITHMS_USE_BUILTIN_POPCOUNT + return __builtin_popcountll(v); +#else + return + (((v ) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 12) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 24) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 36) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 48) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f + + (((v >> 60) & 0xfff) * Q_UINT64_C(0x1001001001001) & Q_UINT64_C(0x84210842108421)) % 0x1f; +#endif +} + +Q_DECL_CONSTEXPR inline uint qPopulationCount(long unsigned int v) +{ + return qPopulationCount(static_cast<quint64>(v)); +} + +#if defined(Q_CC_GNU) && !defined(Q_CC_CLANG) +#undef QALGORITHMS_USE_BUILTIN_POPCOUNT +#endif + + QT_END_NAMESPACE #endif // QALGORITHMS_H |