summaryrefslogtreecommitdiffstats
path: root/tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp
Commit message (Collapse)AuthorAgeFilesLines
* qHash: make hashing of QLatin1StringView be the same as QStringThiago Macieira2024-03-121-1/+1
| | | | | | | Everywhere, except for ARM. Change-Id: I50e2158aeade4256ad1dfffd17b11ca2d57ad1fb Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* qHash: implement an AES hasher for QLatin1StringViewThiago Macieira2024-03-121-3/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | It's the same aeshash() as before, except we're passing a template parameter to indicate whether to read half and then zero-extend the data. That is, it will perform a conversion from Latin1 on the fly. When running in zero-extending mode, the length parameters are actually doubled (counting the number of UTF-16 code units) and we then divide again by 2 when advancing. The implementation should have the following performance characteristics: * QLatin1StringView now will be roughly half as fast as Qt 6.7 * QLatin1StringView now will be roughly as fast as QStringView For the aeshash128() in default builds of QtCore (will use SSE4.1), the long loop (32 characters or more) is: QStringView QLatin1StringView movdqu -0x20(%rax),%xmm4 | pmovzxbw -0x10(%rdx),%xmm2 movdqu -0x10(%rax),%xmm5 | pmovzxbw -0x8(%rdx),%xmm3 add $0x20,%rax | add $0x10,%rdx pxor %xmm4,%xmm0 | pxor %xmm2,%xmm0 pxor %xmm5,%xmm1 | pxor %xmm3,%xmm1 aesenc %xmm0,%xmm0 aesenc %xmm0,%xmm0 aesenc %xmm1,%xmm1 aesenc %xmm1,%xmm1 aesenc %xmm0,%xmm0 aesenc %xmm0,%xmm0 aesenc %xmm1,%xmm1 aesenc %xmm1,%xmm1 The number of instructions is identical, but there are actually 2 more uops per iteration. LLVM-MCA simulation shows this should execute in the same number of cycles on older CPUs that do not have support for VAES (see <https://analysis.godbolt.org/z/x95Mrfrf7>). For the VAES version in aeshash256() and the AVX10 version in aeshash256_256(): QStringView QLatin1StringView vpxor -0x40(%rax),%ymm1,%ym | vpmovzxbw -0x20(%rax),%ymm3 vpxor -0x20(%rax),%ymm0,%ym | vpmovzxbw -0x10(%rax),%ymm2 add $0x40,%rax | add $0x20,%rax | vpxor %ymm3,%ymm0,%ymm0 | vpxor %ymm2,%ymm1,%ymm1 vaesenc %ymm1,%ymm1,%ymm1 < vaesenc %ymm0,%ymm0,%ymm0 vaesenc %ymm0,%ymm0,%ymm0 vaesenc %ymm1,%ymm1,%ymm1 vaesenc %ymm1,%ymm1,%ymm1 vaesenc %ymm0,%ymm0,%ymm0 vaesenc %ymm0,%ymm0,%ymm0 > vaesenc %ymm1,%ymm1,%ymm1 In this case, the increase in number of instructions matches the increase in number of uops. The LLVM-MCA simulation says that the QLatin1StringView version is faster at 11 cycles/iteration vs 14 cyc/it (see <https://analysis.godbolt.org/z/1Gv1coz13>), but that can't be right. Measured performance of CPU cycles, on an Intel Core i9-7940X (Skylake, no VAES support), normalized on the QString performance (QByteArray is used as a stand-in for the performance in Qt 6.7): aeshash | siphash QByteArray QL1SV QString QByteArray QString dictionary 94.5% 79.7% 100.0% 150.5%* 159.8% paths-small 90.2% 93.2% 100.0% 202.8% 290.3% uuids 81.8% 100.7% 100.0% 215.2% 350.7% longstrings 42.5% 100.8% 100.0% 185.7% 353.2% numbers 95.5% 77.9% 100.0% 155.3%* 164.5% On an Intel Core i7-1165G7 (Tiger Lake, capable of VAES and AVX512VL): aeshash | siphash QByteArray QL1SV QString QByteArray QString dictionary 90.0% 91.1% 100.0% 103.3%* 157.1% paths-small 99.4% 104.8% 100.0% 237.5% 358.0% uuids 88.5% 117.6% 100.0% 274.5% 461.7% longstrings 57.4% 111.2% 100.0% 503.0% 974.3% numbers 90.6% 89.7% 100.0% 98.7%* 149.9% On an Intel 4th Generation Xeon Scalable Platinum (Sapphire Rapids, same Golden Cove core as Alder Lake): aeshash | siphash QByteArray QL1SV QString QByteArray QString dictionary 89.9% 102.1% 100.0% 158.1%* 172.7% paths-small 78.0% 89.4% 100.0% 159.4% 258.0% uuids 109.1% 107.9% 100.0% 279.0% 496.3% longstrings 52.1% 112.4% 100.0% 564.4% 1078.3% numbers 85.8% 98.9% 100.0% 152.6%* 190.4% * dictionary contains very short entries (6 characters) * paths-small contains strings of varying length, but very few over 32 * uuids-list contains fixed-length strings (38 characters) * longstrings is the same but 304 characters * numbers also a lot contains very short strings (1 to 6 chars) What this shows: * For short strings, the performance difference is negligible between all three * For longer strings, QLatin1StringView now costs between 7 and 17% more than QString on the tested machines instead of up to ~50% less, except on the older machine (where I think the main QString hashing is suffering from memory bandwidth limitations) * The AES hash implementation is anywhere from 1.6 to 11x faster than Siphash * Murmurhash (marked with asterisk) is much faster than Siphash, but it only managed to beat the AES hash in one test Change-Id: I664b9f014ffc48cbb49bfffd17b045c1811ac0ed Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* qHash: implement chunked hashing of QLatin1StringViewThiago Macieira2024-03-121-0/+13
| | | | | | | | | | | So that it hashes to the same value as QString{,View}. In order to test this, you must either run on a CPU other than ARM and x86, or disable the AES hasher. I did that and can confirm siphash and murmurhash do work with on-the-fly conversion from Latin-1. Change-Id: I664b9f014ffc48cbb49bfffd17b03e5e62ec4e89 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* qHash: backport the q(u)int128-to-quint64 reduction trick to 32-bitThiago Macieira2024-02-121-1/+1
| | | | | | | | | | I didn't do it in a template because the 32-bit code requires a compatibility hack for Qt 6 and it's using an XOR of the high and low parts. Fixes: QTBUG-116080 Change-Id: I5dd50a1a7ca5424d9e7afffd17ae0ba5b9ff52f6 Reviewed-by: Ivan Solovev <ivan.solovev@qt.io>
* Add missing qHash(qu/int128) overloadsMarc Mutz2024-02-121-0/+25
| | | | | | | | | | | | | | | | | | | | | | If we add the typedefs, we also need to add the qHash() overloads. See code comments for the explanation of how it works. I chose to use an addition to merge the upper and lower parts because of the comment in QHashCombineCommutative's operator(), introduced by commit 91b44afdcba3f4cb2ddc7a80c0cff723b408b447. Found in 6.6 API-review, but didn't make the cut and then was forgotten. Drive-by fix long line nearby. [ChangeLog][QtCore] Added qHash() overloads for quint128 and qint128. Fixes: QTBUG-116054 Task-number: QTBUG-116080 Change-Id: If484aed08ba476e0eace800b719f435203100f3e Reviewed-by: Ivan Solovev <ivan.solovev@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Allan Sandfeld Jensen <allan.jensen@qt.io>
* tst_QHashFunctions: make the consistency check table-drivenThiago Macieira2024-02-121-72/+214
| | | | | | | | | | | So we can test more values. Because we are testing more values, we can't use QEXPECT_FAIL, because we can't guarantee a mismatch. Pick-to: 6.7 Task-number: QTBUG-116077 Task-number: QTBUG-116080 Change-Id: I664b9f014ffc48cbb49bfffd17b021719e6d612f Reviewed-by: Ivan Solovev <ivan.solovev@qt.io>
* Change license for tests filesLucie Gérard2024-02-041-1/+1
| | | | | | | | | | | | According to QUIP-18 [1], all tests file should be LicenseRef-Qt-Commercial OR GPL-3.0-only [1]: https://contribute.qt-project.org/quips/18 Pick-to: 6.7 Task-number: QTBUG-121787 Change-Id: I9657df5d660820e56c96d511ea49d321c54682e8 Reviewed-by: Christian Ehrlicher <ch.ehrlicher@gmx.de>
* qHash: provide the long double overload on Darwin systemsThiago Macieira2024-02-031-2/+0
| | | | | | | | | | | | Commit c0791ac76ec7cfdc3945efa67a6f72ee3623413c didn't explain why it was #ifdef'ed out. It's just an alias for double. Maybe compilers at the time used to complain if you used it, but I can't make Apple's clang produce a warning now. Pick-to: 6.7 Change-Id: I664b9f014ffc48cbb49bfffd17b02293403e9571 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* tst_QHashFunctions: extend the consistency() test with mixed-signedness int ↵Marc Mutz2024-01-091-0/+19
| | | | | | | | | | | types Looking good, because all signed integral qHash overloads are implemented by casting to the unsigned type before hashing. Pick-to: 6.7 6.6 6.5 Change-Id: I8372eb6d4a57b40c2371db58d1b5aeabe9a3951a Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QHashFunctions: suppress warning about casting from float to _Float16Thiago Macieira2023-10-241-1/+1
| | | | | | | | | | Amends c86cf385d6d66d8fd3de1666205aaf4b8fcec747. tst_qhashfunctions.cpp:109:59: warning: converting to ‘qfloat16::NativeType’ {aka ‘_Float16’} from ‘float’ with greater conversion rank Pick-to: 6.6 6.5 Change-Id: I79e700614d034281bf55fffd178f91775966658f Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* Fix qHash(qfloat16) to match Qt 6.4 behaviorMarc Mutz2023-09-121-6/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | There were two problems: - On platforms where QFLOAT16_IS_NATIVE == true, a qHash(qfloat16{}) call has become ambiguous between the three FP qHash() overloads (float, double, long double), where it was unambiguously calling the float one in Qt 6.4. This SiC was caused by the replacement of operator float() by operator __fp16() in 99c7f0419e66692260be56c0385badeacb3f6760, which is in Qt 6.5. - On platforms where QFLOAT16_IS_NATIVE == false, qHash(qfloat16{}) would produce a different value from qHash(float{}), and therefore Qt 6.4, when the seed was != 0, because the former would go via the one-arg-to-two-arg qHash adapter while the latter one would not. Since participating functions are inline, this causes old and new code to produce different hash values for the same qfloat16, leading to a BiC possibly corrupting QHash etc. Fix both by adding an explicit qHash(qfloat16). This function is inline, so it doesn't add a new symbol to 6.5.x. [ChangeLog][QtCore] Fixed qHash(qfloat16) which was broken from 6.5.0 to 6.5.3, inclusive. If you compiled against one of the affected Qt versions, you need to recompile against either Qt 6.4 or earlier or 6.5.4 or later, because the problematic code is inline. Pick-to: 6.6 6.5 Fixes: QTBUG-116064 Fixes: QTBUG-116076 Change-Id: Id02bc29a6c3ec463352f4bef314c040369081e9b Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QHashFunctions: fix std::pair test to use QFETCH_GLOBAL seedsMarc Mutz2023-09-081-6/+0
| | | | | | | | | | | | | | | | Because the local `seed` variable shadowed the member one, this test was run for each QFETCH_GLOBAL with the same data and seed. That doesn't make sense, so make the test use the member variable `seed`, as all other tests already do. Since zero is one of the seeds coming from QFETCH_GLOBAL, drop the seedless calls to qHash(), too. Amends 64bfc927b09b46bb7fc0dc6caf1bf1a4d4133ab4. Pick-to: 6.6 6.5 6.2 Change-Id: I1e22ec0b38341264bcf2d5c26146cbbcab6e0749 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QHashFunctions: test with actual 64-bit seedsMarc Mutz2023-09-081-12/+18
| | | | | | | | | | | | | | | | | | | The old code only tested with seed = 0 and seed = 1045982819, the latter being a "random number", which, however, fits into 32-bits. Since Qt 6.0 increased the seed from uint to size_t, amend the test to actually test a seed value with some of the upper half of bits set, too, also in 64-bit mode. While we're at it, also test with each seed's bits flipped for extra coverage. Remove a static assertion that prevented testing seeds with the MSB set. Pick-to: 6.6 6.5 6.2 Change-Id: I5ed6ffb5cabaaead0eb9c01f994d15dcbc622509 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Ivan Solovev <ivan.solovev@qt.io>
* tst_QHashFunctions: extend the consistency() test with int/FP typesMarc Mutz2023-08-161-0/+55
| | | | | | | | | | | | | | | It's ... broken. Found and filed lots of bugs. Add #ifdef'ery and QEXPECTED_FAIL() to document the state of affairs, hopefully reminding us to fix these things come Qt 7. Task-number: QTBUG-116064 Task-number: QTBUG-116076 Task-number: QTBUG-116077 Task-number: QTBUG-116079 Task-number: QTBUG-116080 Pick-to: 6.6 6.5 Change-Id: I29e89fdf995ddf60ef1e03c7af009e80980c9817 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QHashFunctions: use actual seed in consistent() test functionMarc Mutz2023-08-161-1/+1
| | | | | | | | | | | | | We were only ever testing with a 0 seed, even though the function was called for all QFETCH_GLOBAL seeds. Add the seed. Amends 5e93361888e3d2b03e7b6da19517b44e0239fb47. Pick-to: 6.6 6.5 6.2 5.15 Change-Id: I3c78714ad6fb3f94233789dd2c8884d9b157fa76 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: tame HasQHashSingleArgOverload ODR violationsGiuseppe D'Angelo2022-11-011-0/+13
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | qhashfunctions.h defines a catch-all 2-arguments qHash(T, seed) in order to support datatypes that implement a 1-argument overload of qHash (i.e. qHash(Type)). The catch-all calls the 1-argument overload and XORs the result with the seed. The catch-all is constrained on the existence of such a 1-argument overload. This is done in order to make the catch-all SFINAE-friendly; otherwise merely instantiating the catch-all would trigger a hard error. Such an error would make it impossible to build a type trait that detects if one can call qHash(T, size_t) for a given type T. The constraint itself is called HasQHashSingleArgOverload and lives in a private namespace. It has been observed that HasQHashSingleArgOverload misbehaves for some datatypes. For instance, HasQHashSingleArgOverload<int> is actually false, despite qHash(123) being perfectly callable. (The second argument of qHash(int, size_t) is defaulted, so the call *is* possible.) -- Why is HasQHashSingleArgOverload<int> false? This has to do with how HasQHashSingleArgOverload<T> is implemented: as a detection trait that checks if qHash(declval<T>()) is callable. The detection itself is not a problem. Consider this code: template <typename T> constexpr bool HasQHashSingleArgOverload = /* magic */; class MyClass {}; size_t qHash(MyClass); static_assert(HasQHashSingleArgOverload<MyClass>); // OK Here, the static_assert passes, even if qHash(MyClass) (and MyClass itself) were not defined at all when HasQHashSingleArgOverload was defined. This is nothing but 2-phase lookup at work ([temp.dep.res]): the detection inside HasQHashSingleArgOverload takes into account the qHash overloads available when HasQHashSingleArgOverload was declared, as well as any other overload declared before the "point of instantiation". This means that qHash(MyClass) will be visible and detected. Let's try something slightly different: template <typename T> constexpr bool HasQHashSingleArgOverload = /* magic */; size_t qHash(int); static_assert(HasQHashSingleArgOverload<int>); // ERROR This one *does not work*. How is it possible? The answer is that 2-phase name lookup combines the names found at definition time with the names _found at instantiation time using argument-dependent lookup only_. `int` is a fundamental type and does not participate in ADL. In the example, HasQHashSingleArgOverload has actually no qHash overloads to even consider, and therefore its detection fails. You can restore detection by moving the declaration of the qHash(int) overload *before* the definition of HasQHashSingleArgOverload, so it's captured at definition time: size_t qHash(int); template <typename T> constexpr bool HasQHashSingleArgOverload = /* magic */; static_assert(HasQHashSingleArgOverload<int>); // OK! This is why HasQHashSingleArgOverload<int> is currently returning `false`: because HasQHashSingleArgOverload is defined *before* all the qHash(fundamental_type) overloads in qhashfunctions.h. -- Now consider this variation of the above, where we keep the qHash(int) overload after the detector (so, it's not found), but also prepend an Evil class implicitly convertible from int: struct Evil { Evil(int); }; size_t qHash(Evil); template <typename T> constexpr bool HasQHashSingleArgOverload = /* magic */; size_t qHash(int); static_assert(HasQHashSingleArgOverload<int>); // OK Now the static_assert passes. HasQHashSingleArgOverload is still not considering qHash(int) (it's declared after), but it's considering qHash(Evil). Can you call *that* one with an int? Yes, after a conversion to Evil. This is extremely fragile and likely an ODR violation (if not ODR, then likely falls into [temp.dep.candidate/1]). -- Does this "really matter" for a type like `int`? The answer is no. If HasQHashSingleArgOverload<int> is true, then a call like qHash(42, 123uz); will have two overloads in its overloads set: 1) qHash(int, size_t) 2) qHash(T, size_t), i.e. the catch-all template. To be pedantic, qHash<int>(const int &, size_t), that is, the instantiation of the catch-all after template type deduction for T (= int) ([over.match.funcs.general/8]). Although it may look like this is ambiguous as both calls have perfect matches for the arguments, 1) is actually a better match than 2) because it is not a template specialization ([over.match.best/2.4]). In other words: qHash(int, size_t) is *always* called when the argument is `int`, no matter the value of HasQHashSingleArgOverload<int>. The catch-all template may be added or not to the overload set, but it's a worse match anyways. -- Now, let's consider this code: enum MyEnum { E1, E2, E3 }; qHash(E1, 42uz); This code compiles, although we do not define any qHash overload specifically for enumeration types (nor one is defined by MyEnum's author). Which qHash overload gets called? Again there are two possible overloads available: 1) qHash(int, size_t). E1 can be converted to `int` ([conv.prom/3]), and this overload selected. 2) qHash(T, size_t), which after instantiation, is qHash<MyEnum>(const MyEnum &, size_t). In this case, 2) is a better match than 1), because it does not require any conversion for the arguments. Is 2) a viable overload? Unfortunately the answer here is "it depends", because it's subject to what we've learned before: since the catch-all is constrained by the HasQHashSingleArgOverload trait, names introduced before the trait may exclude or include the overload. This code: #include <qhashfunctions.h> enum MyEnum { E1, E2, E3 }; qHash(E1, 42uz); static_assert(HasQHashSingleArgOverload<MyEnum>); // ERROR will fail the static_assert. This means that only qHash(int, size_t) is in the overload set. However, this code: struct Evil { Evil(int); }; size_t qHash(Evil); #include <qhashfunctions.h> enum MyEnum { E1, E2, E3 }; qHash(E1, 42uz); static_assert(HasQHashSingleArgOverload<MyEnum>); // OK will pass the static_assert. qHash(Evil) can be called with an object of type MyEnum after an user-defined conversion sequence ([over.best.ics.general], [over.ics.user]: a standard conversion sequence, made of a lvalue-to-rvalue conversion + a integral promotion, followed by a conversion by constructor [class.conv.ctor]). Therefore, HasQHashSingleArgOverload<MyEnum> is true here; the catch-all template is added to the overload set; and it's a best match for the qHash(E1, 42uz) call. -- Is this a problem? **Yes**, and a huge one: the catch-all template does not yield the same value as the qHash(int, size_t) overload. This means that calculating hash values (e.g. QHash, QSet) will have different results depending on include ordering! A translation unit TU1 may have #include <QSet> #include <Evil> QSet<MyEnum> calculateSet { /* ... */ } And another translation unit TU2 may have #include <Evil> #include <QSet> // different order void use() { QSet<MyEnum> set = calculateSet(); } And now the two TUs cannot exchange QHash/QSet objects as they would hash the contents differently. -- `Evil` actually exists in Qt. The bug report specifies QKeySequence, which has an implicit constructor from int, but one can concoct infinite other examples. -- Congratulations if you've read so far. ========================= === PROPOSED SOLUTION === ========================= 1) Move the HasQHashSingleArgOverload detection after declaring the overloads for all the fundamental types (which we already do anyways). This means that HasQHashSingleArgOverload<fundamental_type> will now be true. It also means that the catch-all becomes available for all fundamental types, but as discussed before, for all of them we have better matches anyways. 2) For unscoped enumeration types, this means however an ABI break: the catch-all template becomes always the best match. Code compiled before this change would call qHash(int, size_t), and code compiled after this change would call the catch-all qHash<Enum>(Enum, size_t); as discussed before, the two don't yield the same results, so mixing old code and new code will break. In order to restore the old behavior, add a qHash overload for enumeration types that forwards the implementation to the integer overloads (using qToUnderlying¹). (Here I'm considering the "old", correct behavior the one that one gets by simply including QHash/QSet, declaring an enumeration and calling qHash on it. In other words, without having Evil around before including QHash.) This avoids an ABI break for most enumeration types, for which one does not explicitly define a qHash overload. It however *introduces* an ABI break for enumeration types for which there is a single-argument qHash(E) overload. This is because - before this change, the catch-all template was called, and that in turn called qHash(E) and XOR'ed the result with the seed; - after this change, the newly introduced qHash overload for enumerations gets called. It's very likely that it would not give the same result as before. I don't have a solution for this, so we'll have to accept the ABI break. Note that if one defines a two-arguments overload for an enum type, then nothing changes there (the overload is still the best match). 3) Make plans to kill the catch-all template, for Qt 7.0 at the latest. We've asked users to provide a two-args qHash overload for a very long time, it's time to stop working around that. 4) Make plans to switch from overloading qHash to specializing std::hash (or equivalent). Specializations don't overload, and we'd get rid of all these troubles with implicit conversions. -- ¹ To nitpick, qToUnderlying may select a *different* overload than the one selected by an implicit conversion. That's because an unscoped enumeration without a fixed underlying type is allowed to have an underlying type U, and implicitly convert to V, with U and V being two different types (!). U is "an integral type that can represent all the enumerator values" ([dcl.enum/7]). V is selected in a specific list in a specific order ([conv.prom]/3). This means that in theory a compiler can take enum E { E1, E2 }, give it `unsigned long long` as underlying type, and still allow for a conversion to `int`. As far as I know, no compiler we use does something as crazy as that, but if it's a concern, it needs to be fixed. [ChangeLog][Deprecation Notice] Support for overloads of qHash with only one argument is going to be removed in Qt 7. Users are encouraged to upgrade to the two-arguments overload. Please refer to the QHash documentation for more information. [ChangeLog][Potentially Binary-Incompatible Changes] If an enumeration type for which a single-argument qHash overload has been declared is being used as a key type in QHash, QMultiHash or QSet, then objects of these types are no longer binary compatible with code compiled against an earlier version of Qt. It is very unlikely that such qHash overloads exist, because enumeration types work out of the box as keys Qt unordered associative containers; users do not need to define qHash overloads for their custom enumerations. Note that there is no binary incompatibity if a *two* arguments qHash overload has been declared instead. Fixes: QTBUG-108032 Fixes: QTBUG-107033 Pick-to: 6.2 6.4 Change-Id: I2ebffb2820c553e5fdc3a341019433793a58e3ab Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Port tests away from using q{Set}GlobalQHashSeedIvan Solovev2022-08-261-0/+6
| | | | | | | | 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>
* Tests: Do not depend on transitive includesFabian Kosmale2022-03-171-0/+1
| | | | | Change-Id: Ibc6a948480a904913a5427e6408d4d296784fb4f Reviewed-by: Sona Kurazyan <sona.kurazyan@qt.io>
* QT_SPECIALIZE_STD_HASH_TO_CALL_QHASH: use unqualified qHash() lookupMarc Mutz2021-11-291-0/+26
| | | | | | | | | | | ... instead of QT_PREPEND_NAMESPACE(qHash), which is qualified (prepends at least '::'), and therefore disables ADL. This is not a problem as long as we wrote our qHash() overloads as free functions (incl. non-hidden friends), but it should™ fail for hidden friends, so use the old using-std::swap() trick to bring QT_PREPEND_NAMESPACE(qHash) into scope, proceeding with an unqualified lookup. Pick-to: 6.2 Change-Id: I00860b2313699849f86bfe3dd9f41db4ce993cd3 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* tst_qhashfunctions: check qHashRange{,Commutative}() find hidden friend qHash()Marc Mutz2021-11-261-9/+27
| | | | | | | | | ... extending the existing check for ADL-found qHash() implementations. Pick-to: 6.2 5.15 Change-Id: Iac6ed2721db9e95ee921bd1d5170fa8c8d43475d Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QHash: fix qHash(std::pair)Thiago Macieira2021-05-231-0/+40
| | | | | | | | | | | | | | There were two problems here: first, qHash(std::pair) must be declared before qHashMulti that might call back to qHash(std::pair) (i.e., a pair with one element that is also a pair). But moving the declaration above causes the second problem: the noexcept expression can't refer to qHash functions that aren't declared yet. So we forward-declare a constexpr function for that result, but implement it far below. Fixes: QTBUG-92910 Change-Id: Ia8e48103a54446509e3bfffd16767ed2e29b026c Reviewed-by: Christian Kandeler <christian.kandeler@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* 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>
* Move QStringRef and remains to Qt5CompatKarsten Heimrich2020-08-201-10/+2
| | | | | | | | | Export some private functions from QUtf8 to resolve undefined symbols in Qt5Compat after moving QStringRef. Task-number: QTBUG-84437 Change-Id: I9046dcb14ed520d8868a511d79da6e721e26f72b Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Port Q_STATIC_ASSERT(_X) to static_assertGiuseppe D'Angelo2020-06-191-2/+2
| | | | | | | | | | | | | | | | | There is no reason for keep using our macro now that we have C++17. The macro itself is left in for the moment being, as well as its detection logic, because it's needed for C code (not everything supports C11 yet). A few more cleanups will arrive in the next few patches. Note that this is a mere search/replace; some places were using double braces to work around the presence of commas in a macro, no attempt has been done to fix those. tst_qglobal had just some minor changes to keep testing the macro. Change-Id: I1c1c397d9f3e63db3338842bf350c9069ea57639 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QChar: make std::hash'ableMarc Mutz2020-05-051-0/+7
| | | | | Change-Id: I2164df19cd17ab96a39020de66a3fe9fec838a36 Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* Change qHashBits to use MurmurHash2Lars Knoll2020-04-091-11/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The old implementation was either using CRC32 on modern processors or a trivial, but rather slow implementation. We can't continue with CRC32, as that implementation can only give us 32bit hashes, where we now need to support 64bit in Qt 6. Change the implementation to use MurmurHash, as public domain implementation that is both very fast and leads to well distributed hashes. This hash function is about as fast as the SSE optimized CRC32 implementation but works everywhere and gives us 64 bit hash values. Here are some numbers (time for 10M hashes): 14 char 16 char QByteArray QString float old qHash (non CRC32) 127ms 134ms 48ms old qHash (using SSE CRC32 instructions 60ms 62ms 46ms new qHash 52ms 43ms 46ms Unfortunately MurmurHash is not safe against hash table DoS attacks, as potential hash collisions are indepenent of the seed. This will get addressed in followup commit, where we use SipHash or an SSE optimized AES based hashing algorithm that does not have those issues. Change-Id: I4fbc0ac299215b6db78c7a0a2a1d7689b0ea848b Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Change qHash() to work with size_t instead of uintLars Knoll2020-04-091-5/+5
| | | | | | | | | | | 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>
* qhashfunctions.h: add specializations of std::hash for some Qt typesMarc Mutz2019-05-291-0/+36
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | We have a problem. Our types don't play well with the std unordered containers, because they do not specialize std::hash. We therefore force our users to come up with an implementation, hindering interoperability, since any two developers are unlikely to come up with compatible implementations. So combining libraries written by different developers will result in ODR violations. Now that we depend on C++11, and thus the presence of std::hash, we still face the problem that the standard does not provide us with a means to compose new hash functions out of old ones. In particular, we cannot, yet, depend on C++17's std::hash<std::string_view> to implement std::hash<QByteArray>, say. There's also no std::hash for std::tuple, which would allow easy composition by using std::tie(). So piggy-back on the work we have done over the years on qHash() functions, and implement the std::hash specializations for Qt types using the existing qHash() functions, with a twist: The standard allows implementations to provide means against predictable hash values. Qt has this, too, but the seed is managed by the container and passed to the qHash() function as a separate argument. The standard does not have this explicit seed, so any protection must be implicit in the normal use of std::hash. To reap whatever protection that std library has on offer, if any, we calculate a seed value by hashing int(0). This will be subject to constant folding if there's no actual seed, but will produce a value dependent on the seed if there is one. Add some tests. A question that remains is how to document the specialization. Can we have a \stdhashable QDoc macro that does everything for us? Task-number: QTBUG-33428 Change-Id: Idfe775f1661f8489587353c4b148d76611ac76f3 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
* QHash: make it so a zero seed selects a constant algorithmThiago Macieira2017-04-261-4/+4
| | | | | | | | | | | | That's the only value for which we will guarantee a stable result across Qt versions and across invocations of the same application on different architectures is zero. For any other value, we reserve the right to change the algorithm. We'll now print a warning when we detect that. Task-number: QTBUG-47566 Change-Id: I27b55fdf514247549455fffd14b1135e10d24ab4 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: David Faure <david.faure@kdab.com>
* Merge remote-tracking branch 'origin/5.9' into devLiang Qi2017-04-201-46/+72
|\ | | | | | | | | | | | | | | | | | | | | | | Conflicts: src/corelib/tools/qbytearray.h src/corelib/tools/qdatetime.h src/corelib/tools/qstring.h src/corelib/tools/qversionnumber.h src/plugins/platforms/android/qandroidplatformintegration.cpp tests/auto/corelib/tools/qhashfunctions/tst_qhashfunctions.cpp Change-Id: Iefd92a435e687a76cd593099e40d9a9620a1454d
| * tst_qhashfunctions: Test non-zero seeds tooThiago Macieira2017-04-111-44/+70
| | | | | | | | | | Change-Id: Ib0e40a7a3ebc44329f23fffd14b2e927021a1a2e Reviewed-by: David Faure <david.faure@kdab.com>
* | Add a test for consistency of hash values between QString{,Ref,View}Marc Mutz2017-04-071-0/+12
| | | | | | | | | | | | Change-Id: I64a169fd6c8e2444bfe67e3ecd5375ea7b6a81ee Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* | Extend the check for null and empty QString hashing to QString{Ref,View}Marc Mutz2017-04-061-0/+8
|/ | | | | Change-Id: I5c41287991f6dd2eeb3d54699da0f653bfac59be Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* Replace custom type traits with std one'sKai Koehne2016-11-081-2/+1
| | | | | | | | | | | | | | | | | | Remove most type traits from qtypetraits.h, but keep the custom implementation of is_signed/is_unsigned. This gets rid of BSD-3 licensed code from Google in a public header (hugh!). The custom implementations for is_signed/is_unsigned are kept because the implementations in gcc's standard headers do not work as we expect for enums - both is_signed and is_unsigned always returns false there - see also https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59027 [ChangeLog][QtCore][General] Qt now relies on type traits from the C++ standard library. Change-Id: I3f2188b46949f04ca4482a6ac9afd3482103f0e1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Merge remote-tracking branch 'origin/5.6' into 5.7Edward Welbourne2016-07-151-0/+16
|\ | | | | | | | | | | | | | | | | | | | | Conflicts: qmake/library/qmakeevaluator.cpp One side changed the iterator to use ranged-for, the other changed its body; they only conflicted because the latter had to add braces around the body, intruding on the for-line. Trivial resolution. Change-Id: Ib487bc3bd6e3c5225db15f94b9a8f6caaa33456b
| * QHashFunctions: test for hash equality of null and empty string typesMarc Mutz2016-07-111-0/+16
| | | | | | | | | | | | | | | | | | | | In Qt, null QStrings compare equal to empty ones, so add an explicit check that the corresponding hash values are identical, too. Ditto for QByteArray. Change-Id: I190fc95a765305928d9b6b0e4955433865b6b247 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>
* | Add qHash(std::pair)Marc Mutz2015-12-301-0/+16
|/ | | | | | | | | | | We already include <utility> in <qglobal.h>, so we might as well provide a qHash() overload for std::pair. [ChangeLog][QtCore] Added qHash(std::pair), defined in <QHashFunctions>. Change-Id: I0f61c513e82e05ce9d2e56bcf18f3be9e2da4da9 Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>
* Add getter and setter for qt_qhash_seedGabriel de Dietrich2015-09-221-0/+18
| | | | | | | | | | | | | | | | | | 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>
* Fixed license headersJani Heikkinen2015-02-171-1/+1
| | | | | Change-Id: Ibebe1318d1c2de97601aa07269705c87737083ee Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@theqtcompany.com>
* Update copyright headersJani Heikkinen2015-02-111-22/+14
| | | | | | | | | | | | | | | | | | 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>
* Add qHashRange and qHashRangeCommutativeMarc Mutz2015-01-091-0/+66
| | | | | | | | | | | | | | | | | | | qHashRange() takes an (input iterator) range and hashes each element, combining the hash values using the hash combiner from Boost/N1837 with the magic number 0x9e3779b9, as described here: http://stackoverflow.com/questions/4948780/magic-number-in-boosthash-combine qHashRangeCommutative() does the same but with a cummutative combiner (unsigned addition) to create hash values that are order-independent, e.g. for hashed containers. The obvious combiner, XOR, is a bad one because it eliminates duplicate elements. Signed addition cannot be used, since signed overflow leads to undefined behavior. [ChangeLog][QtCore] Added qHashRange() and qHashRangeCommutative() functions to aid implementing qHash() overloads for custom types. Change-Id: I3c2bbc9ce4bd0455262a70e0cf248486525e534f Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* tst_QHash: Factor qHash()-related test cases into a separate testMarc Mutz2015-01-051-0/+153
This is in preparation of adding more qHash()-related tests. Change-Id: Iae65bf8b123e1d6ac6d1eb34d74ba4eb9df8173c Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-26 11:34:29 +0000