summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
Commit message (Collapse)AuthorAgeFilesLines
* QHash: implement the heterogeneous non-const operator[]Thiago Macieira2024-03-121-3/+23
| | | | | | | | | | This complements the previous commit by adding the heterogeneous lookup in operator[]. Unlike the members of the previous commit, this one may insert into the hash, in which case it needs a way to cast from the heterogeneous type K to the actual Key type. Change-Id: I664b9f014ffc48cbb49bfffd17b037c1063dfb91 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QHash: add support for heterogeneous key lookupsThiago Macieira2024-03-121-24/+263
| | | | | | | | | | | | | | | | | | | | | | | This implements support in QHash and QMultiHash for lookups of heterogeneous key types that produce the same hash value. This is implemented by duplicating each of the following functions into an overload on Key and one a template that is enable_if-constrained to a key type that meets the requirement: * contains * count * equals_range * find * operator[] (const only) * remove * take * value * values (QMultiHash) The non-const operator[] may insert into the hash, so it's not part of this commit. Change-Id: I664b9f014ffc48cbb49bfffd17b037852f0fd192 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QHash: merge the two equal_range() overloadsThiago Macieira2024-03-121-9/+10
| | | | | | | | | | | | They were literally identical (as in, they used exactly the same letters in the exact same order), but changed on whether *this was const or not. So pass *this as a parameter so we can have just one implementation. QMultiHash doesn't need this change because its non-const equal_range() calls the const version after making a copy. Change-Id: I6818d78a57394e37857bfffd17ba06aee2e7db0b Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QHash/QMultiHash: further simplify the key() and value() overloadsThiago Macieira2024-03-121-44/+20
| | | | | | | | | | Complements commit 7fe5611365aa9d5065fe8ba62fed9a07c722ea1c by moving the default value selection into a lambda that is passed to the Impl function. This makes the two pairs of overloads in each of the classes be a single line. Change-Id: I6818d78a57394e37857bfffd17ba067beb3a42fa Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QHash: improve perf when detaching with potential growthMårten Nordheim2024-01-311-1/+1
| | | | | | | | | By not assuming we will have resized. reserve(size() + 1) will have suffered a bit from this, but that is probably not very common. Change-Id: I8750d430f532a72729ed06e67c0f315707a916d6 Reviewed-by: Lars Knoll <lars@knoll.priv.no>
* QMap/QHash: s/QPair/std::pair/Marc Mutz2023-12-131-10/+10
| | | | | | | | | Also port from qMakePair to just braced initialization using CTAD. Task-number: QTBUG-115841 Pick-to: 6.7 Change-Id: Ib0ad55d7110521e34004dc9050022f9c0046722e Reviewed-by: Ahmad Samir <a.samirh78@gmail.com>
* QHash: reduce duplication between two lookupsMårten Nordheim2023-06-011-16/+4
| | | | | | | | | findNode and findBucket are virtually the same Change-Id: I9ba8534d66f0feaa2dea7c2b9beacf8d5faddb52 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Lars Knoll <lars@knoll.priv.no> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: suppress GCC 12 & 13 warning that QHash could overflowThiago Macieira2023-05-151-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | It can't unless you really have so many elements that it should overflow. When growing, we call bucketsForCapacity(), which won't overflow; when copying/detaching, we allocate the exact same amount of memory that we've previously allocated, so that has to be good too. There was nothing wrong with the previous code. The warning was showing how the compiler had detected a possible overflow and caused a call to operator new(-1) to force std::bad_alloc to be thrown. Disabling the warning did not work in LTO mode. So we mimic it: Q_CHECK_PTR will call qBadAlloc() for us if exceptions are enabled, or qt_check_pointer() if not but assertions are (if neither are, then we have no means of reporting the error, so let's just assume that it can't happen). In function ‘allocateSpans’, inlined from ‘__ct ’ at qhash.h:581:48, inlined from ‘detached’ at qhash.h:596:20, [...] qhash.h:551:19: warning: argument 1 value ‘18446744073709551615’ exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=] Commit 1d167b515ef81ba71f3f47863e66d36ed6d06c1c is the likely source of this warning. Fixes: QTBUG-113335 Pick-to: 6.5 Change-Id: Ieab617d69f3b4b54ab30fffd175bb8d36228209c Reviewed-by: Lars Knoll <lars@knoll.priv.no>
* QHash: centralize the span allocationThiago Macieira2023-05-151-9/+17
| | | | | | | | | Deduplicates code and will allow me to insert some magic. Pick-to: 6.5 Task-number: QTBUG-113335 Change-Id: Ieab617d69f3b4b54ab30fffd175bb4a2af610ff8 Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QMultiHash: fix missing update to m_sizeThiago Macieira2023-04-041-1/+3
| | | | | | | | | | | | | | | | | | | | | QMultiHash has access to two sizes: one of them is shared with QHash, stored in QHashPrivate::Data::size, which counts keys; the other, which is what our public size() function returns, is stored in QMultiHash::m_size and counts plain (key,value) entries. We forgot to update it in the non-const operator[] that created a node. I've reviewed the rest of the code and can't find any more places where the item count may be changed and m_size isn't updated. [ChangeLog][QtCore][QMultiHash] Fixed a bug that caused an element that was created by operator[] to not be counted, resulting in a hash map with an incorrect element count and which could cause an assertion failure depending on how the hash was later mutated. Fixes: QTBUG-112534 Pick-to: 6.2 6.4 6.5 Change-Id: Idd5e1bb52be047d7b4fffffd17527ec274e1d99e Reviewed-by: Lars Knoll <lars@knoll.priv.no>
* QHash: fix GrowthPolicy::bucketsForCapacityThiago Macieira2023-02-231-19/+21
| | | | | | | | | | | | | | | | | | | | | | | 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>
* qmath: add qNextPowerOfTwo(unsigned long) - for size_tThiago Macieira2023-02-221-1/+1
| | | | | | | | | | | This completes the triad uint/ulong/qulonglong, ensuring that one of them will be size_t and one of them will be uintptr_t (size_t and uintptr_t don't have to be the same type). The signeds ensure one of them will be ptrdiff_t too. Pick-to: 6.5 Change-Id: I9671dee8ceb64aa9b9cafffd17415a0bfcbd68b7 Reviewed-by: Lars Knoll <lars@knoll.priv.no>
* Replace usages of Q_CLANG_QDOC with Q_QDOCLuca Di Sera2022-10-211-4/+4
| | | | | | | | | | | | | | | | | | | | | | | To allow the user to customize the C++ code that QDoc sees, so as to be able to work-around some limitations on QDoc itself, QDoc defines two symbols: Q_QDOC and Q_CLANG_QDOC, both of which are "true" during an entire execution of QDoc. At a certain point in time, QDoc allowed the user the choice between a custom C++ parser and a Clang based one. The Q_QDOC symbol would always be defined while the Q_CLANG_QDOC symbol would be defined only when the Clang based parser was chosen. In more recent times, QDoc always uses a Clang based parser, such that both Q_CLANG_QDOC and Q_QDOC are always defined, making them equivalent. To avoid using different symbols, and the possible confusion and fragmentation that derives from it, all usages of Q_CLANG_QDOC are now replaced by the equivalent usages of Q_QDOC. Change-Id: I5810abb9ad1016a4c5bbea99acd03381b8514b3f Reviewed-by: Kai Koehne <kai.koehne@qt.io>
* Port from qAsConst() to std::as_const()Marc Mutz2022-10-111-1/+1
| | | | | | | | | | | | | | | | We've been requiring C++17 since Qt 6.0, and our qAsConst use finally starts to bother us (QTBUG-99313), so time to port away from it now. Since qAsConst has exactly the same semantics as std::as_const (down to rvalue treatment, constexpr'ness and noexcept'ness), there's really nothing more to it than a global search-and-replace, with manual unstaging of the actual definition and documentation in dist/, src/corelib/doc/ and src/corelib/global/. Task-number: QTBUG-99313 Change-Id: I4c7114444a325ad4e62d0fcbfd347d2bbfb21541 Reviewed-by: Ivan Solovev <ivan.solovev@qt.io>
* Replace qExchange calls with std::exchangeFabian Kosmale2022-09-281-4/+4
| | | | | | | | | | | | | | | | | | | | | qExchange is one of the few remaining functionalities that have not been moved out of qglobal. Given that std::exchange exists in the standard, we can simply move to it everywhere... ...if it weren't for the fact that std::exchange is only constexpr in C++20, and only has its noexceptness specified in (most likely) C++23. Still, we want to move to the existing std functionality where possible, to allow the removal of qglobal includes in lieu of something more fine-grained in the future. So leave any constexpr calls[1] alone for now (and observe that none of our current usages cares about the conditional noexceptness), but replace everything else. [1] QScopedValueRollback' ctor and QExplicitlySharedDataPointerV2::take Task-number: QTBUG-99313 Change-Id: I599cb9846cf319c7ffd3457130938347a75aad25 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Use SPDX license identifiersLucie Gérard2022-05-161-39/+3
| | | | | | | | | | | | | 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>
* QHash: port away from std::aligned_storageMarc Mutz2022-05-071-1/+1
| | | | | | | | | | | It's deprecated in C++23. Just use an explicitly-aligned char array directly, wrapped in a struct to avoid decays to char*. Task-number: QTBUG-99122 Pick-to: 6.3 6.2 Change-Id: I802761c1af62efa6ffc006b07837a7deed1ea4cc Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Q[Multi]Hash: fix squeeze()Ivan Solovev2022-04-061-15/+29
| | | | | | | | | | | | | | | | | | | When calling QHash::reserve(), or when creating the internal QHashPrivate::Data structure, the value 0 for the size parameter is reserved for performing the squeeze operation. However commit 8a984ab772dd194e39094e728b869e65912912a7 broke it, by using the 0 value in QHashPrivate::Data constructors as a mark that no resizing needs to be done. This patch reverts the problematic commit (also applying some later fixes to the code), and adds the missing tests for Q[Multi]Hash::squeeze(). Pick-to: 6.3 6.2 Change-Id: Id644df7b2beb008e6a37b2c89b709adfbd893e25 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Q[Multi]Hash::reserve(): do nothing if desired size is less than currentIvan Solovev2022-04-061-0/+6
| | | | | | | | | | | | | | | | Calling Q[Multi]Hash::reserve(n) when n is much smaller than the current amount of elements in the hash, could result in an infinite loop, because at some point the algorithm could not find a free bucket for the element. Fixing it by returning early if the new desired capacity is less than current. Fixes: QTBUG-102067 Pick-to: 6.3 6.2 Change-Id: I38ef0b2168c4e2a317eedf91b2155b1fdffb1c27 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Associative containers: add a way to obtain a key/value rangeGiuseppe D'Angelo2022-03-041-0/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Our associative containers' iterator's value_type isn't a destructurable type (yielding key/value). This means that something like for (auto [k, v] : map) doesn't even compile -- one can only "directly" iterate on the values. For quite some time we've had QKeyValueIterator to allow key/value iteration, but then one had to resort to a "traditional" for loop: for (auto i = map.keyValueBegin(), e = keyValueEnd(); i!=e; ++i) This can be easily packaged in an adaptor class, which is what this commmit does, thereby offering a C++17-compatible way to obtain key/value iteration over associative containers. Something possibly peculiar is the fact that the range so obtained is a range of pairs of references -- not a range of references to pairs. But that's easily explained by the fact that we have no pairs to build references to; hence, for (auto &[k, v] : map.asKeyValueRange()) doesn't compile (lvalue reference doesn't bind to prvalue pair). Instead, both of these compile: for (auto [k, v] : map.asKeyValueRange()) for (auto &&[k, v] : map.asKeyValueRange()) and in *both* cases one gets references to the keys/values in the map. If the map is non-const, the reference to the value is mutable. Last but not least, implement pinning for rvalue containers. [ChangeLog][QtCore][QMap] Added asKeyValueRange(). [ChangeLog][QtCore][QMultiMap] Added asKeyValueRange(). [ChangeLog][QtCore][QHash] Added asKeyValueRange(). [ChangeLog][QtCore][QMultiHash] Added asKeyValueRange(). Task-number: QTBUG-4615 Change-Id: Ic8506bff38b2f753494b21ab76f52e05c06ffc8b Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* QHash: fix off-by-one in assertionsMårten Nordheim2022-02-161-6/+6
| | | | | | | | | | | | | Coverity-Id: 378365 Coverity-Id: 378366 Coverity-Id: 378399 Coverity-Id: 378427 Coverity-Id: 378468 Coverity-Id: 378472 Pick-to: 6.3 6.2 Change-Id: Ib1efeacb59030b9d004320e56f560367f564d207 Reviewed-by: Marc Mutz <marc.mutz@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QtCore: replace qSwap with std::swap/member-swap where possibleMarc Mutz2022-01-201-2/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | qSwap() is a monster that looks for ADL overloads of swap() and also detects the noexcept of the wrapped swap() function, so it should only be used when the argument type is unknown. In the vast majority of cases, the type is known to be efficiently std::swap()able or to have a member-swap. Call either of these. For the common case of pointer types, circumvent the expensive trait checks on std::swap() by providing a hand-rolled qt_ptr_swap() template, the advantage being that it can be unconditionally noexcept, removing all type traits instantiations. Don't document it, otherwise we'd be unable to pick it to 6.2. Effects on Clang -ftime-trace of a PCH'ed libQt6Gui.so build: before: **** Template sets that took longest to instantiate: [...] 27766 ms: qSwap<$> (9073 times, avg 3 ms) [...] 2806 ms: std::swap<$> (1229 times, avg 2 ms) (30572ms) after: **** Template sets that took longest to instantiate: [...] 5047 ms: qSwap<$> (641 times, avg 7 ms) [...] 3371 ms: std::swap<$> (1376 times, avg 2 ms) [qt_ptr_swap<$> does not appear in the top 400, so < 905ms] (< 9323ms) As a drive-by, remove superfluous inline keywords and template ornaments. Task-number: QTBUG-97601 Pick-to: 6.3 6.2 Change-Id: I88f9b4e3cbece268c4a1238b6d50e5712a1bab5a Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Joerg Bornemann <joerg.bornemann@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* QHash: Return void from QHashPrivate::Data::erase()Lars Knoll2021-12-171-9/+11
| | | | | | | | | | | | | | | | | This removes some calculations that are not required in 80% of the cases where d->erase() is being called (as the return value is ignored). When removing lots of elements from the hash, the ++it could loop quite a bit until it found the next valid item in the hash. This chain of changes combined improve the overall performance of QHash by 10-50% depending on the operation. Deletes are twice as fast, reads around 20% faster, inserts around 10% faster. Task-number: QTBUG-91739 Fixes: QTBUG-98436 Change-Id: I2d82a7c9dd1dd0a4da8402e6d95bfd620caeff3a Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QHash: Add and use a Bucket helper classLars Knoll2021-12-171-96/+172
| | | | | | | | | | | | | | | | Introduces a QHashPrivate::Data::Bucket class. This class helps avoid repeated bitshift and masking operations when locating bucket entries in the hash. Change signature of some internal methods to use Bucket instead of the private iterator, so we can avoid repeated encoding/decoding steps for the bucket index. Task-number: QTBUG-91739 Task-number: QTBUG-98436 Change-Id: I9ed2205bf886f9c20a5be109fd88456eec4d1540 Reviewed-by: Marc Mutz <marc.mutz@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix hash lookup using the value of a key iteratorLars Knoll2021-12-161-7/+13
| | | | | | | | | | | | | | | QHash::operator[] could grow the hash even if the key being looked up already existed. This in turn invalidated all iterators. Avoid this by refactoring findOrInsert() to not grow if the key already exists. Added advantage is that this should make lookups of existing keys slightly faster. Fixes: QTBUG-97752 Pick-to: 6.3 6.2 Change-Id: I9df30459797b42c434ba0ee299fd1d55af8d2313 Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QHash: Improve memory-allocation strategyLars Knoll2021-12-131-6/+19
| | | | | | | | | | | | | | | Be smarter when allocating memory for the real data in addStorage(). As the amount of entries in there follow a binominal distribution, we know pretty well, how many there will be at least and at most. This avoids most of the reallocations of the storage when not rehashing, while Tessil's tests show that the total memory consumption has not changed. Task-number: QTBUG-91739 Task-number: QTBUG-98436 Change-Id: I98854bfbde8b2a16e788bfa1890c694d38fd09b5 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: increase minimum buckets to a full spanLars Knoll2021-12-131-2/+4
| | | | | | | | | | | | | | Change the minimum amount of buckets to be at least 128, ie. one full Span. This will simplify some assumptions in the code. Regeneration of rcc test-data needed because the extra buckets causes the order of the keys to change. Task-number: QTBUG-91739 Task-number: QTBUG-98436 Change-Id: Ic0c7da03570cc4c4e6aacc9645e536aec3667a98 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: Move span constants to its own structMårten Nordheim2021-12-131-52/+51
| | | | | | | | | To avoid needing a templated Span to access them Task-number: QTBUG-98436 Change-Id: I5c3b16f9a806986b14ed794a3818990aa3ead0f7 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QMultiHash: fix erase returning the wrong iteratorMårten Nordheim2021-12-071-2/+3
| | | | | | | | | | | | When deleting the last item in a chain, without it being the last item in the chain, then we re-use the iterator which was passed in as an argument. This is wrong if we detached earlier in the function, and means we return an iterator to the previously shared data. Pick-to: 6.2 Change-Id: I7da6309e23a32073da59e7da0cbfd1d16734f1ca Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QHash: fix thread race around references and detachingMårten Nordheim2021-11-251-31/+80
| | | | | | | | | | | If we detach from a shared hash while holding a reference to a key from said shared hash then there is no guarantee for how long the reference is valid (given a multi-thread environment). Pick-to: 6.2 Change-Id: Ifb610753d24faca63e2c0eb8836c78d55a229001 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QHash: optimize value(key) and key(value) callersMarc Mutz2021-11-191-12/+81
| | | | | | | | | | | | | | | | | | | | | | | | | | ... by not injecting potentially-expensive temporary objects into the caller's stack frame. Default arguments are a convenient way to avoid overloads, but if the defaulted argument isn't a Trivial Type, and the common use case is not to pass the extra argument explicitly, the construction of the temporary can dominate the call's runtime. Since QHash is generic code, we don't know whether T or Key are expensive or cheap to construct, so use overloading instead of default arguments to avoid injecting needless code into call sites. [ChangeLog][QtCore][Potentially Source-Incompatible Changes][QHash/QMultiHash] The value(key) and key(value) functions are now overloaded on presence of the defaultValue (was: defaulted argument) to avoid injecting temporary objects into the caller's stack frame. Task-number: QTBUG-98117 Change-Id: I80fdd5436f3de3e4bbe20242fe45916aef62ff0c Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Fix QMultiHash::operator== crashAndreas Buhr2021-11-111-3/+3
| | | | | | | | | | QMultiHash::operator== crashes when comparing two unequal objects. This patch fixes it. Pick-to: 6.2 Fixes: QTBUG-98265 Change-Id: Ibf9fef3372a2b4581843be5f25e65cc9a55ef64d Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QHash: avoid crashing when reserving on a shared hashMårten Nordheim2021-10-261-1/+2
| | | | | | | | Pick-to: 6.2 Change-Id: I21ad13fa223bd5a2c61112e790965093a2750268 Reviewed-by: Timur Pocheptsov <timur.pocheptsov@qt.io> Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix metatype declaration for QHash/QMultiHash with no operator==Sona Kurazyan2021-10-201-6/+14
| | | | | | | | | | | | | | | | | | | | | | | When declaring metatypes, the metatype system tries to detect if the comparison operators for the given type exist and automatically register them. In case of QHash, the equality operator was enabled if the value type provides one. But the implementation needs equality operator of the key type as well. As a result, when the key type has no equality operator, the metatype system detects that the equality operator is available for the QHash itself, but the compilation for metatype registration fails when trying to instantiate the code that uses equality operator for the key. This is fixed by enabling equality operators for the QHash only when both the key and value types provide one. The same issue existed also for QMultiHash, with the difference, that QMultiHash didn't have the constraints even on the value type. So added checks for both. Fixes: QTBUG-96256 Pick-to: 6.2 Change-Id: Ib8b6d365223f2b3515cbcb1843524cd6f867a6ac Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix docs for comparison/debug/data stream operators of Qt containersSona Kurazyan2021-10-181-0/+5
| | | | | | | | | | | | | | Because of the constraints on comparison, debug and data stream operators, the return types for them look weird in docs. Conditionally use the actual return types, in case if Q_CLANG_QDOC is defined. Also add the docs of debug stream operators for types for which they were misssing. Task-number: QTBUG-97247 Pick-to: 6.2 Change-Id: I57f2c52bd3af805c7eeebb602c47de1e95ee09bd Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QHash: suppress annoying GCC warning about allocation size too bigThiago Macieira2021-10-041-20/+31
| | | | | | | | | | | GCC is right, the maximum memory allocation is half the VM size, not the full VM size or multiple times that. QHashPrivate::Span is big. qhash.h:552:17: warning: argument 1 value ‘18446744073709551615’ exceeds maximum object size 9223372036854775807 [-Walloc-size-larger-than=] Change-Id: Ie72b0dd0fbe84d2caae0fffd16a071ffb5d0c70f Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Fix compilation for recursive Qt containersSona Kurazyan2021-09-071-2/+2
| | | | | | | | | | | | | | | | | | | | The operator checks cause compilation errors when trying to check for their existence for recursive containers. This happens because of trying to check for the operators on the template parameter type(s), that inherit from the container itself, which leads to compilation errors. Introduced alternative versions of the operator checks (with _container suffix), that first check if the container is recursive, i.e. any of its template parameter types inherits from the given container, and skips the operator check, if that's the case. The fix is done for all Qt container types that had the problem, except for QVarLengthArray and QContiguousCache, which don't compile with recursive parameter types for unrelated reasons. Fixes: QTBUG-91707 Pick-to: 6.2 6.1 Change-Id: Ia1e7240b4ce240c1c44f00ca680717d182df7550 Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QHash/QSet: fix squeeze() for default-constructed containerIvan Solovev2021-07-271-1/+5
| | | | | | | | | | | | | | | | | | | | | 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>
* Fix QMultiHash::keys(const T&) overloadIvan Solovev2021-07-081-1/+1
| | | | | | | | | | | | The method was never tested, but it failed to compile after QMultiHash was introduced as a separate class in 6.0. This patch fixes it and adds some unit-tests to cover the case. Task-number: QTBUG-91736 Pick-to: 6.2 6.1 Change-Id: I5dd989d4775efc6a9bb13c5ed1d892e499d95dc2 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* QMultiHash::find - prevent detaching shared nullIvan Solovev2021-07-081-1/+3
| | | | | | | | | | | | | Do not detach when find(key, value) is called on an empty QMultiHash. As a drive-by: fix return value for QMultiHash::remove() in case of empty QMultiHash. Task-number: QTBUG-91736 Pick-to: 6.2 6.1 Change-Id: I1e32f359e7ee9ce8403dae79d02e0b88a20ec4a5 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QHash: Fix erase() edge-caseMårten Nordheim2021-06-181-1/+4
| | | | | | | | | | | | | | | | | | | | | When the element you want to erase is the last element AND the next element (element 0), when rehashed, would be relocated to the last element, this leads to the state below. Which is similar to a test in tst_qhash for some seeds. auto it = hash.begin + (hash.size - 1) it = hash.erase(it) it != hash.end By forcing the iterator to increment if we were erasing the last element we always end up with a pointer which is equal to hash.end Befriend the tst_qhash class so we can set the seed to a known-bad one Pick-to: 6.2 6.1 Change-Id: Ie0b175003a2acb175ef5e3ab5a984e010f65d986 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Deprecate qGlobalQHashSeed and qSetGlobalQHashSeed in Qt 6.6Thiago Macieira2021-05-231-1/+1
| | | | | | | That's two years from when the replacements were added (6.2). Change-Id: Id2983978ad544ff79911fffd1671f7dd38fede02 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Fix QMultiHash::count(key) crashAndrei Golubev2021-03-121-0/+4
| | | | | | | | | | | As QMultiHash uses a pointer for the data, nullptr dereference is a thing, so check for valid d before doing anything in count() Fixes: QTBUG-91704 Pick-to: 6.0 6.1 Change-Id: Ia20440cd7bdc03cb09c77f796fb9c5b52765eac5 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix QMultiHash::equal_range crashesZhang Yu2021-01-061-0/+3
| | | | | | | | | | | | QMultiHash::equal_range crashes when called in a const member function. The Data `d` is a NULL pointer when calling equal_range() before inserting data into an empty QMultiHash. Then calling`d->find` crashes. Fixes: QTBUG-89687 Pick-to: 6.0 Change-Id: I10c3d196cbc72aed8c8c922ef16534bba51037b7 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Add a qHashEquals() method and use it to compare keys in QHashLars Knoll2020-12-041-1/+1
| | | | | | | | | | | | | | | In some cases, the default equality operator for a class is not suitable for using in hashing (for example because it uses fuzzy comparisons). Add a qHashEquals() method that by default uses the equality operator, but allows to tailor the operations that should be used when using the class as a key in QHash. Task-number: QTBUG-88966 Change-Id: I346cf0e6e923277a8b42a79e50342a1c2511fd80 Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io> (cherry picked from commit 5d8b586e73e37070b0303bee24372550854637eb) Reviewed-by: Qt Cherry-pick Bot <cherrypick_bot@qt-project.org>
* QHash: default the argument for the hash calculator helperGiuseppe D'Angelo2020-12-031-1/+1
| | | | | | | Just to be consistent with everything else. Change-Id: I48ceb4bbc1cbf65b03caee77b7405cb585793248 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Associative containers: add erase_ifGiuseppe D'Angelo2020-12-021-0/+22
| | | | | | | | | | | | | | | | | | | | Use a trick similar to the one we use for their ranged constructors: support predicates that either take a container's iterator, or that take a std::pair (for STL compatibility). [ChangeLog][QtCore][QMap] Added removeIf() and erase_if(). [ChangeLog][QtCore][QMultiMap] Added removeIf() and erase_if(). [ChangeLog][QtCore][QHash] Added removeIf() and erase_if(). [ChangeLog][QtCore][QMultiHash] Added removeIf() and erase_if(). Change-Id: Ie40aadf6217d7a4126a626c390d530812ebcf020 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: support std::hash as hashing functionGiuseppe D'Angelo2020-11-301-2/+44
| | | | | | | | | | | | | | | | | | | | In addition (and as a fallback) from requiring qHash, add support for std::hash specializations. This catches two birds with one stone: 1) users of Qt can simply specialize std::hash for their datatypes, and use them in both QHash and stdlib unordered associative containers; 2) we get QHash support for any (stdlib) datatype that is hashable without having to overload qHash for them. [ChangeLog][QtCore][QHash] QHash, QMultiHash and QSet now support for key types anything that can be hashed via std::hash, instead of always requiring a qHash() overload. Change-Id: Ib5ecba86e4b376d318389500bd24883ac6534c5f Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Don't allow storing types that throw in the destructor in our containersLars Knoll2020-11-171-0/+6
| | | | | | | | | | | | | | | | | | | | | | Types that throw in their destructors are strongly discouraged in C++, and even the STL doesn't define what happens if such types are stored in their containers. Make this more explicit for Qt and disallow storing those types in our containers. This will hopefully preempty any potential future bug reports about us not handling such a case. It also helps simplify some code in QList and other cases and makes it possible to explicitly mark more methods as noexcept. Some care needs to be taken where to add the static asserts, so that we don't disallow forward declarations of types stored in containers. Place the static assert into the destructor of the container where possible or otherwise into the templated d-pointer. Change-Id: If3aa40888f668d0f1b6c6b3ad4862b169d31280e Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QMultiHash: add a QHash&& constructor and unite() overloadMårten Nordheim2020-11-091-0/+19
| | | | | | | | Reaches into the internals to avoid erasing one entry at a time from the QHash. Change-Id: I47079592d130d2ecd844998dfa31e633e049d4c1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 04:56:35 +0000