From 046f3254838715079b853ab4e15eed4ef464fb30 Mon Sep 17 00:00:00 2001 From: Glen Mabey Date: Sat, 7 Feb 2015 21:11:22 -0600 Subject: Adds qFindFirstSetBit() and qFindLastSetBit(). Two new function families have been added: qFindFirstSetBit() and qFindLastSetBit() for a variety of integer sizes. Fast implementations are included for most platforms. [ChangeLog][QtCore][QtAlgorithms] Added qFindFirstSetBit() and qFindLastSetBit(). Change-Id: I89d9d1637ea26070aee5a60be95be1b51bfc84dc Reviewed-by: Thiago Macieira --- .../corelib/tools/qalgorithms/tst_qalgorithms.cpp | 107 +++++++++++++++++++++ 1 file changed, 107 insertions(+) mode change 100644 => 100755 tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp (limited to 'tests/auto/corelib/tools/qalgorithms') diff --git a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp old mode 100644 new mode 100755 index 9bce948140..99e5c4c85d --- a/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp +++ b/tests/auto/corelib/tools/qalgorithms/tst_qalgorithms.cpp @@ -31,6 +31,7 @@ ** ****************************************************************************/ +#include "../../../../../src/corelib/tools/qalgorithms.h" #include #include @@ -80,6 +81,24 @@ private slots: void popCount32() { popCount_impl(); } void popCount64() { popCount_impl(); } + void countTrailing08_data() { countTrailing_data_impl(sizeof(quint8 )); } + void countTrailing16_data() { countTrailing_data_impl(sizeof(quint16)); } + void countTrailing32_data() { countTrailing_data_impl(sizeof(quint32)); } + void countTrailing64_data() { countTrailing_data_impl(sizeof(quint64)); } + void countTrailing08() { countTrailing_impl(); } + void countTrailing16() { countTrailing_impl(); } + void countTrailing32() { countTrailing_impl(); } + void countTrailing64() { countTrailing_impl(); } + + void countLeading08_data() { countLeading_data_impl(sizeof(quint8 )); } + void countLeading16_data() { countLeading_data_impl(sizeof(quint16)); } + void countLeading32_data() { countLeading_data_impl(sizeof(quint32)); } + void countLeading64_data() { countLeading_data_impl(sizeof(quint64)); } + void countLeading08() { countLeading_impl(); } + void countLeading16() { countLeading_impl(); } + void countLeading32() { countLeading_impl(); } + void countLeading64() { countLeading_impl(); } + private: #if Q_TEST_PERFORMANCE void performance(); @@ -87,6 +106,14 @@ private: void popCount_data_impl(size_t sizeof_T_Int); template void popCount_impl(); + + void countTrailing_data_impl(size_t sizeof_T_Int); + template + void countTrailing_impl(); + + void countLeading_data_impl(size_t sizeof_T_Int); + template + void countLeading_impl(); }; class TestInt @@ -1084,6 +1111,86 @@ void tst_QAlgorithms::popCount_impl() QCOMPARE(qPopulationCount(value), expected); } +void tst_QAlgorithms::countTrailing_data_impl(size_t sizeof_T_Int) +{ + using namespace QTest; + addColumn("input"); + addColumn("expected"); + + int nibs = sizeof_T_Int*2; + + newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + const quint64 input = Q_UINT64_C(1) << i; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; + } + + quint64 type_mask; + if (sizeof_T_Int>=8) + type_mask = ~Q_UINT64_C(0); + else + type_mask = (Q_UINT64_C(1) << (sizeof_T_Int*8))-1; + + // and some random ones: + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary + const quint64 r = quint64(qrand()) << 32 | quint32(qrand()); + const quint64 b = Q_UINT64_C(1) << i; + const quint64 mask = ((~(b-1)) ^ b) & type_mask; + const quint64 input = (r&mask) | b; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << i; + } + } +} + +template +void tst_QAlgorithms::countTrailing_impl() +{ + QFETCH(quint64, input); + QFETCH(uint, expected); + + const T_Int value = static_cast(input); + + QCOMPARE(qCountTrailingZeroBits(value), expected); +} + +void tst_QAlgorithms::countLeading_data_impl(size_t sizeof_T_Int) +{ + using namespace QTest; + addColumn("input"); + addColumn("expected"); + + int nibs = sizeof_T_Int*2; + + newRow(("0x"+QByteArray::number(0,16).rightJustified(nibs,'0')).constData()) << Q_UINT64_C(0) << uint(sizeof_T_Int*8); + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + const quint64 input = Q_UINT64_C(1) << i; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); + } + + // and some random ones: + for (uint i = 0; i < sizeof_T_Int*8; ++i) { + for (uint j = 0; j < sizeof_T_Int*3; ++j) { // 3 is arbitrary + const quint64 r = quint64(qrand()) << 32 | quint32(qrand()); + const quint64 b = Q_UINT64_C(1) << i; + const quint64 mask = b-1; + const quint64 input = (r&mask) | b; + newRow(("0x"+QByteArray::number(input,16).rightJustified(nibs,'0')).constData()) << input << uint(sizeof_T_Int*8-i-1); + } + } +} + +template +void tst_QAlgorithms::countLeading_impl() +{ + QFETCH(quint64, input); + QFETCH(uint, expected); + + const T_Int value = static_cast(input); + + QCOMPARE(qCountLeadingZeroBits(value), expected); +} + QTEST_APPLESS_MAIN(tst_QAlgorithms) #include "tst_qalgorithms.moc" -- cgit v1.2.3