summaryrefslogtreecommitdiffstats
path: root/tests/auto/corelib/tools/qset/tst_qset.cpp
Commit message (Collapse)AuthorAgeFilesLines
* QHash: fix GrowthPolicy::bucketsForCapacityThiago Macieira2023-02-231-8/+20
| | | | | | | | | | | | | | | | | | | | | | | It was confusing entry capacity with the bucket capacity. The value maxNumBuckets() returned was the maximum number of entries. This issue was harmless: we would just fail to cap the maximum to an allocatable size. But the array new[] in the Data constructors would have capped the maximum anyway (by way of throwing std::bad_alloc). So instead of trying to calculate what the maximum bucket count is so we can cap at that, simplify the calculation of the next power of 2 while preventing it from overflowing in our calculations. We continue to rely on new[] throwing when we return count that is larger than the maximum allocatable. This commit changes the load factor for QHashes containing exactly a number of elements that is exactly a power of two. Previously, it would be loaded at 50%, now it's at 25%. For this reason, tst_QSet::squeeze needed to be fixed to depend less on the implementation details. Pick-to: 6.5 Change-Id: I9671dee8ceb64aa9b9cafffd17415f3856c358a0 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* tst_QSet: fix flakiness after we removed the fixed, non-zero seedThiago Macieira2022-10-181-11/+21
| | | | | | | | | | | | | | The "qhash" test relied on the fact that those four elements would produce a different order with a zero and a non-zero seed. But since commit b057e32dc455d81f9378d6bd0c58888a7eddd155 removed the setting of a deterministic non-zero seed, this test had a 1 in 4! chance of failing. Since 4! = 24, 128 retries should be more than enough to ensure we do find at least hash seed that provokes a different order. Fixes: QTBUG-107725 Change-Id: I3c79b7e08fa346988dfefffd171ee61b79ca5489 Reviewed-by: Marc Mutz <marc.mutz@qt.io> Reviewed-by: Ivan Solovev <ivan.solovev@qt.io>
* Port from container.count()/length() to size()Marc Mutz2022-10-041-10/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This is semantic patch using ClangTidyTransformator: auto QtContainerClass = expr(hasType(namedDecl(hasAnyName(<classes>)))).bind(o) makeRule(cxxMemberCallExpr(on(QtContainerClass), callee(cxxMethodDecl(hasAnyName({"count", "length"), parameterCountIs(0))))), changeTo(cat(access(o, cat("size"), "()"))), cat("use 'size()' instead of 'count()/length()'")) a.k.a qt-port-to-std-compatible-api with config Scope: 'Container'. <classes> are: // sequential: "QByteArray", "QList", "QQueue", "QStack", "QString", "QVarLengthArray", "QVector", // associative: "QHash", "QMultiHash", "QMap", "QMultiMap", "QSet", // Qt has no QMultiSet Change-Id: Ibe8837be96e8d30d1846881ecd65180c1bc459af Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* Port tests away from using q{Set}GlobalQHashSeedIvan Solovev2022-08-261-3/+3
| | | | | | | | These functions are marked as deprecated in future Qt releases. Task-number: QTBUG-104858 Change-Id: I25d2932455d8c9e3e2d722b1c48fc2cfa2d1e679 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Use SPDX license identifiersLucie Gérard2022-05-161-27/+2
| | | | | | | | | | | | | Replace the current license disclaimer in files by a SPDX-License-Identifier. Files that have to be modified by hand are modified. License files are organized under LICENSES directory. Task-number: QTBUG-67283 Change-Id: Id880c92784c40f3bbde861c0d93f58151c18b9f1 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Jörg Bornemann <joerg.bornemann@qt.io>
* Remove checks for features available in C++17Ievgenii Meshcheriakov2021-10-021-4/+0
| | | | | | | | | | This patch removes most of the checks that are made using C++20 __cpp_* macros for features available in C++17 and earlier. Library feature check macros (__cpp_lib_*) are unaffected. Change-Id: I557b2bd0d4ff09b13837555e9880eb28e0355f64 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash/QSet: fix squeeze() for default-constructed containerIvan Solovev2021-07-271-4/+4
| | | | | | | | | | | | | | | | | | | | | QHash::squeeze() was unconditionally calling reserve(0), which is always allocating memory (even for 0 size). This was leading to a confusing situation when calling squeeze() on a default-constructed container with 0 capacity() actually allocated memory. This is very misleading, as squeeze() is supposed to free unneeded memory, not to allocate more. This patch adds a check for non-zero capacity. As a result, nothing is done for default-constructed container. Note that this patch also affects the QSet::squeeze() behavior, because QSet uses QHash as its underlying data type. Task-number: QTBUG-91736 Pick-to: 6.2 6.1 Change-Id: Ib1c3c8b7b3de6ddeefea0e70b1ec71803e8fd3b3 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Andreas Buhr <andreas.buhr@qt.io>
* QSet: extend testsIvan Solovev2021-07-221-5/+172
| | | | | | | | | | | Extend tests to explicitly check the behavior of empty default-constructed container. Also add some missing tests to increase the code coverage. Task-number: QTBUG-91736 Pick-to: 6.2 6.1 Change-Id: Ie57b5d13fad9a846c29c87be4985c87e69bba305 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* Replace QtTest headers with QTestDavid Skoland2020-12-221-1/+1
| | | | | | | | | | | Complete search and replace of QtTest and QtTest/QtTest with QTest, as QtTest includes the whole module. Replace all such instances with correct header includes. See Jira task for more discussion. Fixes: QTBUG-88831 Change-Id: I981cfae18a1cabcabcabee376016b086d9d01f44 Pick-to: 6.0 Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* QSet: add insert(T&&)Mårten Nordheim2020-12-021-0/+79
| | | | | | | | | | | | | | We already have all we need in QHash to support this, so the addition is simple enough. Add test checking how many copies and/or moves are needed for a single insert. As a drive-by: remove some unneeded static_cast Change-Id: Iaf768657644afa45f78f5c81ffcf89ba9607be96 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Deprecate the static int based API in QMetaTypeLars Knoll2020-08-241-1/+1
| | | | | | | | | | | | | And remove one of the type id to name mapping that still existed in QMetaType. QMetaTypeInterface can provide that, so there's no need to have a second copy of the data. qMetaTypeTypeInternal() can still map all the names of all builtin types to ids. That functionality is for now still required by moc and can't be removed yet. Change-Id: Ib4f8e9c71e1e7d99d52da9e44477c9a1f1805e57 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Change qHash() to work with size_t instead of uintLars Knoll2020-04-091-1/+1
| | | | | | | | | | | This is required, so that QHash and QSet can hold more than 2^32 items on 64 bit platforms. The actual hashing functions for strings are still 32bit, this will be changed in a follow-up commit. Change-Id: I4372125252486075ff3a0b45ecfa818359fe103b Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* New QHash implementationLars Knoll2020-04-091-7/+10
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | A brand new QHash implementation using a faster and more memory efficient data structure than the old QHash. A new implementation for QHash. Instead of a node based approach as the old QHash, this implementation now uses a two stage lookup table. The total amount of buckets in the table are divided into spans of 128 entries. Inside each span, we use an array of chars to index into a storage area for the span. The storage area for each span is a simple array, that gets (re-)allocated with size increments of 16 items. This gives an average memory overhead of 8*sizeof(struct{ Key; Value; }) + 128*sizeof(char) + 16 for each span. To give good performance and avoid too many collisions, the array keeps its load factor between .25 and .5 (and grows and rehashes if the load factor goes above .5). This design allows us to keep the memory overhead of the Hash very small, while at the same time giving very good performance. The calculated overhead for a QHash<int, int> comes to 1.7-3.3 bytes per entry and to 2.2-4.3 bytes for a QHash<ptr, ptr>. The new implementation also completely splits the QHash and QMultiHash classes. One behavioral change to note is that the new QHash implementation will not provide stable references to nodes in the hash when the table needs to grow. Benchmarking using https://github.com/Tessil/hash-table-shootout shows very nice performance compared to many different hash table implementation. Numbers shown below are for a hash<int64, int64> with 1 million entries. These numbers scale nicely (mostly in a linear fashion with some variation due to varying load factors) to smaller and larger tables. All numbers are in seconds, measured with gcc on Linux: Hash table random random random random reads full insertion insertion full full after iteration (reserved) deletes reads deletes ------------------------------------------------------------------------------ std::unordered_map 0,3842 0,1969 0,4511 0,1300 0,1169 0,0708 google::dense_hash_map 0,1091 0,0846 0,0550 0,0452 0,0754 0,0160 google::sparse_hash_map 0,2888 0,1582 0,0948 0,1020 0,1348 0,0112 tsl::sparse_map 0,1487 0,1013 0,0735 0,0448 0,0505 0,0042 old QHash 0,2886 0,1798 0,5065 0,0840 0,0717 0,1387 new QHash 0,0940 0,0714 0,1494 0,0579 0,0449 0,0146 Numbers for hash<std::string, int64>, with the string having 15 characters: Hash table random random random random reads insertion insertion full full after (reserved) deletes reads deletes -------------------------------------------------------------------- std::unordered_map 0,4993 0,2563 0,5515 0,2950 0,2153 google::dense_hash_map 0,2691 0,1870 0,1547 0,1125 0,1622 google::sparse_hash_map 0,6979 0,3304 0,1884 0,1822 0,2122 tsl::sparse_map 0,4066 0,2586 0,1929 0,1146 0,1095 old QHash 0,3236 0,2064 0,5986 0,2115 0,1666 new QHash 0,2119 0,1652 0,2390 0,1378 0,0965 Memory usage numbers (in MB for a table with 1M entries) also look very nice: Hash table Key int64 std::string (15 chars) Value int64 int64 --------------------------------------------------------- std::unordered_map 44.63 75.35 google::dense_hash_map 32.32 80,60 google::sparse_hash_map 18.08 44.21 tsl::sparse_map 20.44 45,93 old QHash 53.95 69,16 new QHash 23.23 51,32 Fixes: QTBUG-80311 Change-Id: I5679734144bc9bca2102acbe725fcc2fa89f0dff Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Remove deprecated functionality from QSetLars Knoll2020-01-301-146/+1
| | | | | | | Remove support for reverse iteration over a QSet. Change-Id: I1e9c986a118aea4ebeb7fcdceb41e9ce6593cdb6 Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
* Get rid of QT_STRICT_ITERATORSLars Knoll2019-11-041-2/+0
| | | | | | | | | | | The concept was a nice idea to avoid accidental detach() calls in implicitly shared containers, but it conflicts with a C++11 compatible API for them, with signatures for modifying methods taking a const_iterator as argument and returning an iterator (e.g. iterator erase(const_iterator)). Change-Id: Ia33124bedbd260774a0a66f49aedd84e19c9971b Reviewed-by: Simon Hausmann <simon.hausmann@qt.io>
* QVector/QList/QLinkedList/QVarLengthArray/QSet: add missing deduction guidesMarc Mutz2019-08-071-0/+28
| | | | | | | | | | | Amends 2e1763d83a1dacfc5b747934fb77fa7cec7bfe47. The new range ctors need deduction guides, since the compiler can't deduce the value_type from a pair of iterators. Change-Id: I3ec1e5f91305b317c443b6a70246be416b55bad9 Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Remove handling of missing Q_COMPILER_INITIALIZER_LISTSAllan Sandfeld Jensen2019-05-021-12/+0
| | | | | | Change-Id: Id65b39c787235a051262544932e6717d076f1ea0 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Updated license headersJani Heikkinen2016-01-211-17/+12
| | | | | | | | | | | | | From Qt 5.7 -> tools & applications are lisenced under GPL v3 with some exceptions, see http://blog.qt.io/blog/2016/01/13/new-agreement-with-the-kde-free-qt-foundation/ Updated license headers to use new GPL-EXCEPT header instead of LGPL21 one (in those files which will be under GPL 3 with exceptions) Change-Id: I42a473ddc97101492a60b9287d90979d9eb35ae1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>
* Merge remote-tracking branch 'origin/5.6' into devLiang Qi2015-10-141-0/+16
|\ | | | | | | | | | | | | | | | | Conflicts: tests/auto/corelib/io/qfile/tst_qfile.cpp tests/auto/corelib/io/qprocess/tst_qprocess.cpp tests/auto/corelib/tools/qversionnumber/qversionnumber.pro Change-Id: Ia93ce500349d96a2fbf0b4a37b73f088cc505c6e
| * QLinkedList/QSet: add {const_,}reverse_iterator, {c,}r{begin,end}()Marc Mutz2015-10-131-0/+16
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Now all Qt sequential containers consistently provide reverse iterators. The associative ones, by way of not returning std::pair from op*, can't just use std::reverse_iterator. They would miss .key() and .value() methods. So that has to wait for 5.7. The reverse versions of the new key_iterators can also just use std::reverse_iterator, but I'm afraid that after bikeshedding over keyRBegin() vs. rKeyBegin() vs. reverseKeyBegin() vs. rkbegin() vs. krbegin() (<-- of course, what else?), it would anyway be too late for 5.6, so defer, too. [ChangeLog][QtCore][QLinkedList/QSet] Added rbegin(), crbegin(), rend(), crend(), and reverse_iterator and const_reverse_iterator typedefs. Task-number: QTBUG-25919 Change-Id: I58316fffade469e9a42c61d7aa1455ae3443fd94 Reviewed-by: Sérgio Martins <sergio.martins@kdab.com> Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* | Tests: Use QCOMPARE() with QLatin1String() for QString values.Friedemann Kleint2015-10-141-1/+1
|/ | | | | | | Prefer QCOMPARE over QVERIFY for equality and use QLatin1String(). Change-Id: If226a0fc7b25be3e6774c7e36ca1e6f99234e5dd Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@theqtcompany.com>
* Add getter and setter for qt_qhash_seedGabriel de Dietrich2015-09-221-21/+3
| | | | | | | | | | | | | | | | | | In some cases it's not possible to use QT_HASH_SEED, specially when we need to set the environment variable from inside the application, as dynamically loaded libraries or plugins may create static QHash instances. That would set qt_qhash_seed to a value different from -1 and skip the env var value. For those cases, and when we still want to set qt_qhash_seed, we provide a way to enforce its value. Auto-tests accessing qt_qhash_seed directly have been updated accordingly. Usage in qdoc, uic and rcc has been left as is for the time being. Change-Id: I3b35b4fa0223c83b1348a6508641905a2a63266f Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>
* QSet: Introduce intersects().Sérgio Martins2015-05-301-0/+27
| | | | | | | | | | | | The pattern "mySet.intersect(other).isEmpty()" has been spotted in the wild and in Qt codebase. intersects() is much cheaper because it bails out as soon as we find one common item and doesn't do any allocations. [ChangeLog][QtCore][QSet] Added intersects(). Change-Id: I44a350dc4cdb9deb835a23eee99fc99d6ca24c82 Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
* Update copyright headersJani Heikkinen2015-02-111-7/+7
| | | | | | | | | | | | | | | | | | Qt copyrights are now in The Qt Company, so we could update the source code headers accordingly. In the same go we should also fix the links to point to qt.io. Outdated header.LGPL removed (use header.LGPL21 instead) Old header.LGPL3 renamed to header.LGPL3-COMM to match actual licensing combination. New header.LGPL-COMM taken in the use file which were using old header.LGPL3 (src/plugins/platforms/android/extract.cpp) Added new header.LGPL3 containing Commercial + LGPLv3 + GPLv2 license combination Change-Id: I6f49b819a8a20cc4f88b794a8f6726d975e8ffbe Reviewed-by: Matti Paaso <matti.paaso@theqtcompany.com>
* tst_QSet: make qhash() test deterministicMarc Mutz2015-01-231-1/+18
| | | | | Change-Id: I857e66f21030da2210122c8c95c95f05a73da50a Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* Add qHash() overload for QSetMarc Mutz2015-01-181-0/+45
| | | | | | | | | ...using qHashRangeCommutative(). Also add a test. [ChangeLog][QtCore][QSet] Can now be used as the key in QSet, QHash. Change-Id: Ie7c81d257a3b324fc03d394fa7c9fcf0c6fb062a Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QSet: add a non-trivial test for op==Marc Mutz2015-01-051-0/+10
| | | | | Change-Id: Id42b2361e8741ee0d719fd52885a2d6dfdf6a634 Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Update license headers and add new license filesMatti Paaso2014-09-241-19/+11
| | | | | | | | | - Renamed LICENSE.LGPL to LICENSE.LGPLv21 - Added LICENSE.LGPLv3 - Removed LICENSE.GPL Change-Id: Iec3406e3eb3f133be549092015cefe33d259a3f2 Reviewed-by: Iikka Eklund <iikka.eklund@digia.com>
* tst_QSet: check which of several equal elements is insertedMarc Mutz2014-08-051-0/+26
| | | | | | | | | | | | Add a test that checks that QSet keeps the first of the elements that have equal value. This is documented, but inconsistent with values in a QHash, which keeps the last element with equal key. Document this as a test. That way, we'll be informed when the behavior changes (e.g. by a port to std::unordered_set). Change-Id: I4ca1718bb86599b925b3ccd13b0856917cd4ce67 Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* tst_QSet: verify that {}-style initialization drops duplicatesMarc Mutz2014-07-251-1/+1
| | | | | | | | No actual reason for this test, except my curiority. Then again, it's good to have this check, too. Change-Id: I815fce7e4dbe76e21cac29beb1dbfc1083191d24 Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Added initializer list constructors for Qt associative containers.Roman Pasechnik2013-01-241-0/+22
| | | | | | | | | Affected: QSet, QMap, QMultiMap, QHash, QMultiHash. Task-number: QTBUG-25679 Change-Id: I01f3ecfbca805f4c053a75232188bd2a77fdb1f2 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com>
* Update copyright year in Digia's license headersSergio Ahumada2013-01-181-1/+1
| | | | | Change-Id: Ic804938fc352291d011800d21e549c10acac66fb Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* Change copyrights from Nokia to DigiaIikka Eklund2012-09-221-24/+24
| | | | | | | | Change copyrights and license headers from Nokia to Digia Change-Id: If1cc974286d29fd01ec6c19dd4719a67f4c3f00e Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Sergio Ahumada <sergio.ahumada@digia.com>
* containers: add C++11-style c{begin,end}() as alias for const{Begin,End}()Marc Mutz2012-03-171-12/+12
| | | | | | | | | | | | | | | | | | C++11 adds cbegin()/cend() functions for the same reason Qt has constBegin()/constEnd(). This patch adds these functions to the Qt containers with the same implementation as constBegin()/constEnd(). It also fixes the return types in the documentation of existing constFind() functions (documentation only). C++11 only adds cbegin()/cend() (and crbegin()/crend(), which Qt doesn't have). In particular, it doesn't add cfind(), so I didn't supply these, even though Qt comes with constFind(). This is a forward-port of https://qt.gitorious.org/qt/qt/merge_requests/1365. Change-Id: Ida086b64246b24e25254eafbcb06c8e33388502b Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Remove "All rights reserved" line from license headers.Jason McDonald2012-01-301-1/+1
| | | | | | | | | | As in the past, to avoid rewriting various autotests that contain line-number information, an extra blank line has been inserted at the end of the license text to ensure that this commit does not change the total number of lines in the license header. Change-Id: I311e001373776812699d6efc045b5f742890c689 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Update contact information in license headers.Jason McDonald2012-01-231-1/+1
| | | | | | | Replace Nokia contact email address with Qt Project website. Change-Id: I431bbbf76d7c27d8b502f87947675c116994c415 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Update copyright year in license headers.Jason McDonald2012-01-051-1/+1
| | | | | Change-Id: I02f2c620296fcd91d4967d58767ea33fc4e1e7dc Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Remove empty functions from QSet autotest.Jason McDonald2011-12-251-4/+0
| | | | | Change-Id: Id6fac3a83e3f4385ee1978a19e6dc92605f4abdb Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Remove TESTED_CLASS/TESTED_FILES comments from tests.Jason McDonald2011-12-061-3/+0
| | | | | | | | | These comments were mostly empty or inaccurate. Appropriate naming of tests and appropriate placement of tests within the directory tree provide more reliable indicators of what is being tested. Change-Id: Ib6bf373d9e79917e4ab1417ee5c1264a2c2d7027 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Cleanup corelib autotestsJason McDonald2011-11-301-1/+0
| | | | | | | | Remove references to the old bug tracker. The data from the old bug tracker is no longer accessible, so these markers are meaningless. Change-Id: Ib9d029d52b70fd0a512b9532d65f03763eabfe57 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Moving relevant tests to corelib/toolsHolger Ihrig2011-09-011-0/+931
Task-number: QTBUG-21066 Change-Id: I650f8f7826b9feea7c1484f06e03e10c68ec2b65 Reviewed-on: http://codereview.qt.nokia.com/3712 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Sergio Ahumada <sergio.ahumada@nokia.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-10 15:06:29 +0000