summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.cpp
Commit message (Collapse)AuthorAgeFilesLines
* QHash: optimize value(key) and key(value) callersMarc Mutz2021-11-191-13/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | ... 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>
* QMultiHash: Add forgotten documentationMårten Nordheim2021-11-031-6/+16
| | | | | | | | | | | After the split of QHash and QMultiHash this function was not documented since it was previously inherited from QHash. As a drive-by also update 'int' to 'qsizetype' in docs Pick-to: 6.2 Change-Id: I5d168886f13c2cdd4482038e66d0cf218789c847 Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* QHash: use the shadow seedThiago Macieira2021-10-261-21/+20
| | | | | | | | | | | | | [ChangeLog][Important Behavior Changes] The qHash functions operating on string-like types and the qHashBits function will now mix in a shadow seed (not available in any API) if the provided main seed is not 0. This means the hashing value for any particular input has an almost zero chance of being equal in two different processes, even if processes of the same application. This unpredictability makes QHash more strongly resist denial-of-service attacks through degenerate hashing tables. Change-Id: Id2983978ad544ff79911fffd167240196f7cd5c8 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QHash: double the size of the stored seedThiago Macieira2021-10-261-66/+114
| | | | | | | | | | | | | | | | There's now another half of the seed which will be used by the hashers. This is not stored in QHash, so it is never changed for the lifetime of the application (not even when QHashSeed::setDeterministicGlobalSeed() is called). However, we will not use it when we're in deterministic mode. This commit uses the compiler thread-safe statics to implement the initialization of more than one atomic word, thus freeing us from having to have a reserved value. As a bonus, the QT_HASH_SEED warning will only be printed once. Change-Id: Id2983978ad544ff79911fffd16723f1673f9a5b4 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Doc: Fix documentation issues for Qt CoreTopi Reinio2021-08-241-1/+1
| | | | | | | | | | | | | | * Tag deprecated Q(Multi)Map operators in the header to correctly match them with documentation \fn commands. * Add documentation for QByteArrayView comparison operators. * Add a dummy typedef 'jfieldID' for generating docs correctly on non-Android platforms * Fix other minor issues Pick-to: 6.2 Task-number: QTBUG-95860 Change-Id: I141d2f75d6aa10557aa374201f09ad74b4cd6e81 Reviewed-by: Paul Wicking <paul.wicking@qt.io>
* Doc: Ensure deprecated APIs in Qt Core are documented as suchNico Vertriest2021-07-231-4/+4
| | | | | | | | | | Added \deprecated [version_since] when needed Remove references to deprecated functions in \sa statements Fixes: QTBUG-94534 Pick-to: 6.2 Change-Id: I3b3d4277d63fc5d6d207c28ff2484aed30b83247 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* Doc: QtCore: Fix documentation issuesTopi Reinio2021-06-011-1/+0
| | | | | | | | | | | | | | | | | | * Add module header wrapper that loads the real QtCore header and qandroidextras_p.h to generate docs for those types * Add missing dummy typedefs to doc/include/jni.h * Use the correct \namespace name (QtAndroidPrivate) and mark it as \preliminary * Add missing 'const' specifier for Q[Untyped]Bindable methods * Drop documentation for removed method QProperty::markDirty() * qmath.h: Fix \fn commands for qFloor(), qCeil() * QHashSeed: Drop incorrect usage of \relates Fixes: QTBUG-93942 Task-number: QTBUG-93995 Change-Id: If76b5aa4b79a64add3cb6275eac82ec44ef10319 Reviewed-by: Assam Boudjelthia <assam.boudjelthia@qt.io> Reviewed-by: Paul Wicking <paul.wicking@qt.io>
* Doc: Use \deprecated instead of \obsoletePaul Wicking2021-05-261-2/+2
| | | | | | Task-number: QTBUG-93990 Change-Id: I4e512354a49dde6678ca89cabc56bc76ba666bb3 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>
* QRandomGenerator: let qt_initial_random_value() return 128 bits of dataThiago Macieira2021-05-231-1/+2
| | | | | | | | | | | | It's how much there is in Linux's AT_RANDOM block. I've also removed the check for validity. It's highly unlikely that 128 bits are bad. Change-Id: Id2983978ad544ff79911fffd16723161ea7ec315 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Allan Sandfeld Jensen <allan.jensen@qt.io>
* QHash & QRandomGenerator: cooperate to provide a simpler initial seedThiago Macieira2021-05-231-4/+10
| | | | | | | | | | | | | | | | | | | | | | Instead of initializing the whole QRandomGenerator::system(), which in turn gets to checking CPUID and whether the HWRNG works, trust the operating system functions for an initial value. On Linux, we'll use 4 or 8 of the 16 bytes of random data that the kernel populates for us on AT_RANDOM. This should make Qt applications not stall on an early system launch without an RNG daemon, if compiled without getentropy() support. And avoids silly mistakes causing recursion, like QTBUG-78007 found. Additionally, qt_random_initial_value() will most likely not throw either. It's marked noexcept, even though SystemGenerator::fillBuffer could throw on Linux, if the current thread is canceled, but Linux also has AT_RANDOM. That leaves the other Unix systems without getentropy() (read: macOS, since the BSDs have getentropy()). Fixes: QTBUG-69555 Change-Id: Id2983978ad544ff79911fffd1671fca1a9f9044d Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Deprecate qGlobalQHashSeed and qSetGlobalQHashSeed in Qt 6.6Thiago Macieira2021-05-231-1/+4
| | | | | | | That's two years from when the replacements were added (6.2). Change-Id: Id2983978ad544ff79911fffd1671f7dd38fede02 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Mark QHashSeed::globalSeed() noexceptThiago Macieira2021-05-231-5/+8
| | | | | | | | | | | | | | | It is noexcept, except when initializing. When initializing, let's just use qEnvironmentVariableIntValue (which we should have used anyway), which avoids the memory allocation and is noexcept. The QRandomGenerator functions are not marked noexcept, but are mostly so: they can't throw regular exceptions, but some implementations do call POSIX Thread Cancellation Points, which may cause forced stack unwinding. That's unlikely to happen at the moment of the QHash initialization. This is also mitigated in the next commit. Change-Id: Id2983978ad544ff79911fffd1671fd16f8d6378d Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Introduce QHashSeed and switch to size_t seedsThiago Macieira2021-05-231-35/+127
| | | | | | | | | | | Commit 37e0953613ef9a3db137bc8d3076441d9ae317d9 added a to-do, but we can actually change the type, since we've documented since Qt 5.10 that setting a non-zero value (aside from -1) with qSetGlobalQHashSeed was not allowed. Storing a value to be reset later is simply not supported. Change-Id: Id2983978ad544ff79911fffd1671f7b5de284bab Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* Use __has_* instead QT_HAS_*JiDe Zhang2021-05-211-1/+1
| | | | | | | | Use __has_include instead QT_HAS_INCLUDE Use __has_feature instead QT_HAS_FEATURE Change-Id: If9b0af1f4386f7bcae6ca2fb911ffaba422750dd Reviewed-by: Tor Arne Vestbø <tor.arne.vestbo@qt.io>
* Add runtime ARM64 AES checkAllan Sandfeld Jensen2021-05-201-3/+8
| | | | | | | | | | | | Adds runtime CPU detection for Windows and macOS, and switches feature detection of AES to runtime like for x86, So far only on ARM64, since gcc doesn't do function versioning on ARM32, but clang can, so it could be added later. Change-Id: Ibe5d60f48cdae3e366a8ecd6263534ba2b09b131 Reviewed-by: Tor Arne Vestbø <tor.arne.vestbo@qt.io> Reviewed-by: Alexandru Croitor <alexandru.croitor@qt.io>
* QHash: disable the AES based one on the bootstrap libraryThiago Macieira2021-05-011-2/+2
| | | | | | | | | | | | | | The bootstrap library doesn't need it. All bootstrapped tools are expected to produce deterministic output, given the enforced seed of 0: #ifdef QT_BOOTSTRAPPED // the seed is always 0 in bootstrapped mode (no seed generation code), // so help the compiler do dead code elimination seed = 0; #endif Change-Id: I755911ae7d0341f49039fffd167afc934ff1c9e1 Reviewed-by: Tor Arne Vestbø <tor.arne.vestbo@qt.io>
* Add runtime aes/crypto check for ARMAllan Sandfeld Jensen2021-04-211-1/+3
| | | | | | | Yocto apparantly enables it hard at compile time. Change-Id: I1d4c7402eacc714859c61f469ebed85682d48b51 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* MSVC: Fix size_to to int warning in qhash.cppKai Köhne2021-04-211-1/+1
| | | | | | | Pick-to: 6.1 Change-Id: I5da2ae57b0f626bd46b71bab28af668bd1fbc7de Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: allow an empty QT_HASH_SEED env variable to resetThiago Macieira2021-04-161-1/+1
| | | | | | | | | | | | | | | | | | It's much easier to un-do a QT_HASH_SEED=0 by simply setting it to empty in a command-line, as in: QT_HASH_SEED= ./appname [ChangeLog][Important Behavior Changes] Previously, if the QT_HASH_SEED environment variable was set but empty, Qt would interpret that as if it had been set to 0, thus disabling the hash salting functionality. Since this makes setting and unsetting this variable difficult in scripts, it has been changed: if the variable is set but empty, it is interpreted now as if it had not been set and the hash salting functionality is enabled. Change-Id: Id2983978ad544ff79911fffd1671f5473978a6bc Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QHash: remove the ability to set a non-zero global seedThiago Macieira2021-04-161-6/+5
| | | | | | | | | We've been warning since commit 4ba740b3bac6e1824c18614f579d106eee930d42 (2017-03-31, Qt 5.9.0). Change-Id: Id2983978ad544ff79911fffd1671f505fee6f282 Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QMultiHash: Fix docFabian Kosmale2021-04-161-3/+2
| | | | | | | | In Qt 6, QMultiHash does not iherit QHash Pick-to: 6.1 6.0 Change-Id: Iaad8768d681a9aad2bb1f80fd87904f0dd9683d4 Reviewed-by: Paul Wicking <paul.wicking@qt.io>
* QHash: add a Qt 7 TODOGiuseppe D'Angelo2021-03-211-0/+1
| | | | | | | | | | The hashing seed's type has been changed from int to size_t in Qt 6. However the functions setting/getting the seed, and the seed itself, are still simply int, meaning that we've crippled our seeding. Add a TODO to amend it. Change-Id: Ie9dd177149ec299ccf16d4e31f9f4b065804cfed Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Add ARM version of the "AES" qhash algorithmAllan Sandfeld Jensen2021-03-051-0/+135
| | | | | Change-Id: Ia2c20e970a0149efb7665a5690538f83965e7be7 Reviewed-by: Erik Verbruggen <erik.verbruggen@me.com>
* Add a qHashEquals() method and use it to compare keys in QHashLars Knoll2020-12-041-0/+15
| | | | | | | | | | | | | | | 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>
* Document QMultiHash::clear functionAndreas Buhr2020-12-021-0/+9
| | | | | | | | | | | When QMultiHash derived from QHash, it inherited the clear function and no separate documentation was necessary. Now, QMultiHash::clear needs its own documentation. This patch adds it. Task-number: 88533 Pick-to: 6.0 Change-Id: I93c59b66aa3d8ccf1888b6e24a4cc47004318e37 Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* Associative containers: add erase_ifGiuseppe D'Angelo2020-12-021-0/+58
| | | | | | | | | | | | | | | | | | | | 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-10/+30
| | | | | | | | | | | | | | | | | | | | 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>
* Make the QMultiHash(const QHash &) constructor explicitLars Knoll2020-11-031-0/+10
| | | | | | | | | And add a QMultiHash::unite(const QHash &) method to avoid a copy of the data when inserting a QHash into a multi hash. Change-Id: I864aa9d2b9b7b2c367c3c4d140a2ce2f5408ae09 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Remove documentation for removed qHash overloadVolker Hilsheimer2020-10-291-15/+0
| | | | | | | | QPair is an alias to std::pair in Qt 6, so no need for two qHash functions. Also remove note and snippet from std::pair overload documentation. Change-Id: Ica8f6961af1eac493e909ad06fe46f8f68542bc5 Reviewed-by: Paul Wicking <paul.wicking@qt.io>
* Do not use QHash's aeshash() under Clang's sanitizerAndrei Golubev2020-10-051-2/+14
| | | | | | | | | | | | | | | | | | | aeshash() has a heap-buffer-overflow when the passed in buffer length is less than 16 bytes (and I expect there's a similar issue when we process the tail when length is not divisible by 16). Despite being a real issue, the code has guarding mechanisms to make sure that: 1) no crash happens 2) out-of-range bits are not used in the computation Disabled the usage of aeshash() under Clang's sanitizer similarly to how it was done for GCC (apparently it uses its own preprocessor mechanism). Likely, this will pop up again with MSVC, but I have no clue which defines it uses Task-number: QTBUG-87112 Task-number: QTBUG-86051 Change-Id: I614d7b3082e91c9d16e0441649d6a153b222bd2e Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Switch QBitArray to qsizetypeAllan Sandfeld Jensen2020-09-291-2/+2
| | | | | | | To make it consistent with other containers in Qt6. Change-Id: I5578845390248baf80daa282237b706857e57661 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Fix some qdoc warnings from QHash and QMultiHashVolker Hilsheimer2020-09-281-21/+8
| | | | | | | | | | | | | | It's no longer possible to decrement an iterator, and the class uses qsizetype, not int for sizes. Fix incorrect function prototypes in the documentation, and remove documentation for functions/overloads that don't exist. QMultiHash doesn't have Java style iterators (not a new issue in Qt 6), so remove the references to QMultiHashIterator. Change-Id: I149b4620963f2087f3f66bb70a9c97b292a35378 Reviewed-by: Paul Wicking <paul.wicking@qt.io>
* Fix mistake in AESHASH algorithmAllan Sandfeld Jensen2020-08-231-2/+2
| | | | | | | The read data wasn't encoded into the state correctly. Change-Id: Ib0a3b50bfeb56968de5c5e8353b28383cb586271 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Move QStringRef and remains to Qt5CompatKarsten Heimrich2020-08-201-7/+0
| | | | | | | | | 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>
* Another round of using noexcept instead of pre-C++11 definesAllan Sandfeld Jensen2020-08-131-1/+1
| | | | | | | A few new files were added with old-school defines. Change-Id: Ieb2c71e094e55102f3f39fb9551823f36863f5f4 Reviewed-by: Laszlo Agocs <laszlo.agocs@qt.io>
* Add an AES-based qHash function, inspired on Go'sThiago Macieira2020-08-041-0/+137
| | | | | Change-Id: I09100678ff4443e6be06fffd1481e94089c47799 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Document that keys() and values() run in linear timeMitch Curtis2020-07-311-0/+16
| | | | | | | | | | | | keys() and values() can be slower for large containers. I ran into this recently when profiling, and was surprised that keys() had to build the list of keys (by appending in a loop). Pick-to: 5.15 5.12 Change-Id: I73215f5a917790236704ad7ef78cefc4a049cd89 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>
* Introduce QByteArrayViewSona Kurazyan2020-07-081-0/+12
| | | | | | | | | | | | | | | | | | | | Created a QByteArrayView in symmetry with QStringView. Added the basic tests symmetrical to QStringView tests. Moved the implementations of non-modifying methods of QByteArray to namespace QtPrivate, to be reused inline from both QByteArray and QByteArrayView. Changed QByteArray's counterparts of those methods to take QByteArrayView as argument instead of QByteArray. Removed QByteArray's operator QNoImplicitBoolCast(), because it was causing ambiguity when calling those methods with QByteArray argument (it was there to perevnt if(!ba)/if(ba) from compiling, but currently that would be ambiguous and won't compile anyway). [ChangeLog][QtCore][QByteArrayView] New class. Task-number: QTBUG-84321 Change-Id: I05f92e654cf65c95f2bb31b9c9018746ac110426 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Port remaining usages of QStringRef in QtCore to QStringViewLars Knoll2020-06-121-12/+0
| | | | | | Task-number: QTBUG-84319 Change-Id: If77bc94c18e8d522b4577050091cd7d7aa941311 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Long live qHashMulti(Commutative)Giuseppe D'Angelo2020-05-121-5/+48
| | | | | | | | | | | | | | | | | | | | | | | | | | Add a helper function so that we have a shortcut. Instead of writing: QHashCombine hash; seed = hash(seed, fieldA); seed = hash(seed, fieldB); // etc. return seed; one can now simply write: return qHashMulti(seed, fieldA, fieldB, fieldC); Port a few usages inside qtbase as a demonstration. [ChangeLog][QtCore][QHash] Added the qHashMulti and qHashMultiCommutative functions as convenience helpers to calculate a hash from multiple variables (typically, data members of a class). Change-Id: I881a9ad41168df20ceecc6588a94abe7ddc6a532 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
* Provide qHash for all C++ fundamental typesGiuseppe D'Angelo2020-05-081-0/+35
| | | | | | | | | | Except for (void and) bool, which we may not want to have to avoid accidental implicit conversions. Drive-by, rearrange qHash overloads to C++ types first, and then Qt ones. Change-Id: I9c4ecef5f28568d35ca52e339583851ce53b3bae Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Optimize hashing of floating point numbersLars Knoll2020-04-091-9/+16
| | | | | | Change-Id: Id5e091b135c006b10987f229f45319228edb8675 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* Replace Qt's hashing function with SipHashThiago Macieira2020-04-091-11/+220
| | | | | | | | | | | | | | | | | | | | This commit replaces MurmurHash with SipHash for all strings longer than the size of a pointer. The most important difference between those algorithms is that MurmurHash has this unwelcome property: for two byte sequences x and y, if you know that x and y have the same hashing for a given seed, then they have the same hashing for all seeds. SipHash has no such issue. If the seed changes, the strings that used to compute to the same hash are no longer likely to do so. We've chosen to implement a SipHash-1-2 algorithm instead of the regular 2-4 as that has roughly the same performance as the old DJB33XA algorithm. It's around 50% slower than MurmurHash, which is acceptable given the added security. Task-number: QTBUG-47566 Change-Id: I09100678ff4443e6be06fffd14819c8878d223e2 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Change qHashBits to use MurmurHash2Lars Knoll2020-04-091-139/+102
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* Implement emplace() for QHash and QMultiHashLars Knoll2020-04-091-0/+47
| | | | | | | | | | At the same time use the opportunity to refactor the insertion code inside the implementation of QHash to avoid copy and move constructors as much as possible and always construct nodes in place. Change-Id: I951b4cf2c77a17f7db825c6a776aae38c2662d23 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Change qHash() to work with size_t instead of uintLars Knoll2020-04-091-42/+42
| | | | | | | | | | | 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>
* Fix the documentation for QHash and QMultiHashLars Knoll2020-04-091-312/+749
| | | | | | Change-Id: Iecf742c5e5bd4716e2d17394770e992024c5bdbb Reviewed-by: Simon Hausmann <simon.hausmann@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* New QHash implementationLars Knoll2020-04-091-322/+0
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* Merge remote-tracking branch 'origin/5.15' into devQt Forward Merge Bot2020-04-081-2/+16
|\ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Conflicts: examples/opengl/doc/src/cube.qdoc src/corelib/global/qlibraryinfo.cpp src/corelib/text/qbytearray_p.h src/corelib/text/qlocale_data_p.h src/corelib/time/qhijricalendar_data_p.h src/corelib/time/qjalalicalendar_data_p.h src/corelib/time/qromancalendar_data_p.h src/network/ssl/qsslcertificate.h src/widgets/doc/src/graphicsview.qdoc src/widgets/widgets/qcombobox.cpp src/widgets/widgets/qcombobox.h tests/auto/corelib/tools/qscopeguard/tst_qscopeguard.cpp tests/auto/widgets/widgets/qcombobox/tst_qcombobox.cpp tests/benchmarks/corelib/io/qdiriterator/qdiriterator.pro tests/manual/diaglib/debugproxystyle.cpp tests/manual/diaglib/qwidgetdump.cpp tests/manual/diaglib/qwindowdump.cpp tests/manual/diaglib/textdump.cpp util/locale_database/cldr2qlocalexml.py util/locale_database/qlocalexml.py util/locale_database/qlocalexml2cpp.py Resolution of util/locale_database/ are based on: https://codereview.qt-project.org/c/qt/qtbase/+/294250 and src/corelib/{text,time}/*_data_p.h were then regenerated by running those scripts. Updated CMakeLists.txt in each of tests/auto/corelib/serialization/qcborstreamreader/ tests/auto/corelib/serialization/qcborvalue/ tests/auto/gui/kernel/ and generated new ones in each of tests/auto/gui/kernel/qaddpostroutine/ tests/auto/gui/kernel/qhighdpiscaling/ tests/libfuzzer/corelib/text/qregularexpression/optimize/ tests/libfuzzer/gui/painting/qcolorspace/fromiccprofile/ tests/libfuzzer/gui/text/qtextdocument/sethtml/ tests/libfuzzer/gui/text/qtextdocument/setmarkdown/ tests/libfuzzer/gui/text/qtextlayout/beginlayout/ by running util/cmake/pro2cmake.py on their changed .pro files. Changed target name in tests/auto/gui/kernel/qaction/qaction.pro tests/auto/gui/kernel/qaction/qactiongroup.pro tests/auto/gui/kernel/qshortcut/qshortcut.pro to ensure unique target names for CMake Changed tst_QComboBox::currentIndex to not test the currentIndexChanged(QString), as that one does not exist in Qt 6 anymore. Change-Id: I9a85705484855ae1dc874a81f49d27a50b0dcff7
| * Doc: Expand reasoning for QHash deprecationsTopi Reinio2020-03-261-2/+16
| | | | | | | | | | | | | | | | and mark QHash::[const_|key_]iterator operators correctly as deprecated. Change-Id: I01da16254759b9bdb7920709de45a72933d6b5c8 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Paul Wicking <paul.wicking@qt.io>
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-06 05:43:00 +0000