summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
Commit message (Collapse)AuthorAgeFilesLines
* Don't compare const_iterator with iterator.Stephen Kelly2013-08-271-2/+2
| | | | | | | | | Commit 93ffb81df6e2cdc57ac8f70c6578f132024d7117 introduced this bug. As it is in the header, it affects downstreams. Change-Id: I02e86927e648153ca7c0b66ac945a7f99cc4cd89 Reviewed-by: Thorbjørn Lund Martsum <tmartsum@gmail.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash/QSet - fix QHash::erase when the hash is sharedThorbjørn Martsum2013-08-241-0/+16
| | | | | | | | | | | | | Before a call to erase on a shared instance would imply that the item was removed from the shared data (i.e all instances) This patch improves the behavior to detach and erase the item specified by the iterator (i.e same behavior as QVector) Since QSet uses QHash it improves QSet the same way. Change-Id: I850b1efcf7bdfc85ceddb23128b048af95f75063 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash: fix compilation with gcc-4.2.1 (Mac OS X)David Faure2013-08-211-7/+2
| | | | | | | | | The anonymous union isn't supported and can be replaced with a reinterpret_cast. Change-Id: Ic76a31f36e61d910db16312d7a6c4bdc728aa825 Reviewed-by: Thorbjørn Lund Martsum <tmartsum@gmail.com> Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@digia.com> Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* QSet - check if iterator argument is valid (in debugmode)Thorbjørn Martsum2013-07-121-0/+1
| | | | | | | This adds a check on erase that the iterator is from the set. Change-Id: I9f4e127d53a5b1f5f8c70652604f1f5574c73688 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash - checks if iterator argument is valid (in debugmode)Thorbjørn Martsum2013-07-121-0/+20
| | | | | | | This checks if the iterator argument in erase is valid in debug mode. Change-Id: I8768f4263d1464ff78986a1a30702e210e561dc1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Add qt_hash(QStringRef) overloadGiuseppe D'Angelo2013-05-071-0/+1
| | | | | | | | This enables fixing a performance regression compared to Qt 4. Also, add some qt_hash tests. Change-Id: Id830e17dec99fb67e5930c80029ac2233b2f427e Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@digia.com>
* Remove QT_{BEGIN,END}_HEADER macro usageSergio Ahumada2013-01-291-4/+0
| | | | | | | | | | | The macro was made empty in ba3dc5f3b56d1fab6fe37fe7ae08096d7dc68bcb and is no longer necessary or used. Discussed-on: http://lists.qt-project.org/pipermail/development/2013-January/009284.html Change-Id: Id2bb2e2cabde059305d4af5f12593344ba30f001 Reviewed-by: Laszlo Papp <lpapp@kde.org> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com> Reviewed-by: hjk <hjk121@nokiamail.com>
* Added initializer list constructors for Qt associative containers.Roman Pasechnik2013-01-241-0/+21
| | | | | | | | | Affected: QSet, QMap, QMultiMap, QHash, QMultiHash. Task-number: QTBUG-25679 Change-Id: I01f3ecfbca805f4c053a75232188bd2a77fdb1f2 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@digia.com>
* Update copyright year in Digia's license headersSergio Ahumada2013-01-181-1/+1
| | | | | Change-Id: Ic804938fc352291d011800d21e549c10acac66fb Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QHash: constify some QHashNode membersGiuseppe D'Angelo2012-11-151-6/+6
| | | | | | | | | | They're read-only member variables (key, hash value of the key) set only in the ctors, or a "comparison" member function. All of them can be constified. Change-Id: Ifd9242577213f38439a4f998b678f5b05413ad21 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: João Abecasis <joao@abecasis.name>
* Change copyrights from Nokia to DigiaIikka Eklund2012-09-221-24/+24
| | | | | | | | Change copyrights and license headers from Nokia to Digia Change-Id: If1cc974286d29fd01ec6c19dd4719a67f4c3f00e Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Sergio Ahumada <sergio.ahumada@digia.com>
* Add Q_DECL_NOTHROW to some qHash functionsThiago Macieira2012-08-201-20/+23
| | | | | | | | | | | | The hashing functions for QDateTime and QHostAddress did not get the noexcept keyword because they might allocate memory. QDateTime doesn't do it now, but it could in the future. QHostAddress does allocate memory today. Change-Id: Ia5f80942944bfc2b8c405306c467bfd88ef0e48c Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com> Reviewed-by: Marc Mutz <marc.mutz@kdab.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix compilation: Move qHash(const T &t, uint seed) up.Friedemann Kleint2012-08-011-2/+2
| | | | | | | | | It needs to be visible from qHash(const QPair<T1, T2> &key, uint seed). Change-Id: Ibb63ce6da1e655bfb841c5e580e184ef66c5b766 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Friedemann Kleint <Friedemann.Kleint@nokia.com>
* More qHash(T, uint) supportGiuseppe D'Angelo2012-07-231-4/+4
| | | | | | | | Add the seed to QPair, QUuid, QPersistentModelIndex's qHash(), and fix qHash documentation for them and for many other datatypes. Change-Id: I1386f3ed42ee1a832371a242ee5c82895ba92c2b Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Forward-declare QLatin1String tooThiago Macieira2012-06-151-1/+1
| | | | | | | | | | | | qhash.h doesn't include qstring.h and was depending on an indirect inclusion (probably via qpair.h -> qdatastream.h -> qiodevice.h -> qobject.h -> qstring.h, which I've broken). Since it forward-declares QString and QStringRef, let's add QLatin1String too. Change-Id: I179ebb22f761b88423ef13643afa2e5ce91ef6a2 Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Remove the unnecessary comment about operator== not being necessaryThiago Macieira2012-05-311-5/+2
| | | | | | | | | | The mysterious comment was just suggesting that they weren't necessary. Turns out the comment is wrong: they are necessary for non-strict iterator modes. Task-number: QTBUG-25063 Change-Id: I20ada17035642ee656c431d6bf2152a5243cecdb Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Replace `const QLatin1String &` with `QLatin1String` where appropriateKonstantin Ritt2012-05-251-1/+1
| | | | | | | Task-Id: QTBUG-24502 Change-Id: I360dee4dc68c165de0631ce4cf34e76fd873080e Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Implement the move constructor for containers.Olivier Goffart2012-05-111-0/+1
| | | | | | | | | | | | | | | This changes all the containers that uses QtPrivate::RefCount (QMap already had one), and QVariant In Qt 4.8, it was pointless to have the move constructor because we did not have quick way to re-initialize a null container. (shared_null still needed to be refcounted) But now that we have RefCount, and that the shared_null do not have reference count, we can implement a fast move constructor that do not generate code to increment the reference count. Change-Id: I2bc3c6ae96983f08aa7b1c7cb98d44a89255160b Reviewed-by: Jędrzej Nowacki <jedrzej.nowacki@nokia.com>
* Restructure how we initialize hash nodes a littleLars Knoll2012-05-011-14/+14
| | | | | | | | | This should help to silence coverity which was complaining hundreds of times about Qt not initializing h and next in QHashNode. Change-Id: Ib7977693e9786d4b310799e4f428115c65bb3fee Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QHash security fix (2/2): enable QHash random seedGiuseppe D'Angelo2012-04-141-1/+1
| | | | | | | | | | | | | | | | | | Algorithmic complexity attacks against hash tables have been known since 2003 (cf. [1, 2]), and they have been left unpatched for years until the 2011 attacks [3] against many libraries / (reference) implementations of programming languages. This patch makes qHash use the QHash seed introduced in the previous commits, thus truly randomizing bucketing in QHash. [1] http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf [2] http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks [3] http://www.ocert.org/advisories/ocert-2011-003.html Task-number: QTBUG-23529 Change-Id: Ibee9cf6aa820af5d777fcde478647665c728052a Reviewed-by: Jason McDonald <jason.mcdonald@nokia.com>
* QHash: remove optimization for QHash<int, T>Giuseppe D'Angelo2012-04-141-1/+14
| | | | | | | | | | | | | | QHash employs an optimization for int/uints, squashing the hash value and the key value inside an union. This obviously works iff qHash(int k) = k. If the hash value gets salted, the hash table is corrupted. This patch removes that optimization by means of a #if 0, so if further research finds out that we want those 4 bytes back it's pretty simple to revert. Change-Id: If273f0bf2ff007f4f2f7c46d2aab364a3b455cf1 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* qHash: qHash(T*) two arguments supportGiuseppe D'Angelo2012-04-141-2/+2
| | | | | Change-Id: I1b78914fe9c6ee9251d68af1f2e95f1e3e0f1db5 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* qHash: two arguments support for simple integer types (and QChar)Giuseppe D'Angelo2012-04-141-16/+16
| | | | | | Change-Id: I24bed73422fb1d2e90cf3dd4e5375e249b3dcac4 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: João Abecasis <joao.abecasis@nokia.com>
* Stop relying on qHash always giving the same resultsGiuseppe D'Angelo2012-04-081-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | The implementation of the various qHash overloads offered by Qt can change at any time for any reason (speed, quality, security, ...). Therefore, relying on the fact that qHash will always give an identical result across Qt versions (... across different processes, etc.), given identical input, is wrong. Note that this also implies that one cannot rely on QHash having a stable ordering (even without the random qHash seed). For such use cases, one must use f.i. a private hash function that will never change outside his own control. This patch adds a private hash function for QStrings, which is identical to the Qt(4) qHash(QString) implementation. A couple of spots in Qt where the results of a qHash call were actually saved on disk are ported to use the new function, and a bit of documentation is added to QHash docs. Change-Id: Ia3731ea26ac68649b535b95e9f36fbec3df693c8 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Robin Burchell <robin+qt@viroteck.net>
* qHash: always use the seed in the catch-all templateGiuseppe D'Angelo2012-04-061-1/+1
| | | | | | | | | This pertubates the results of the calls to the one-argument version of qHash through the catch-all template. Change-Id: I7037b25d545e6f1360384a83ff895f4bb62ed195 Reviewed-by: João Abecasis <joao.abecasis@nokia.com> Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
* QLatin1String: add qHash overloadGiuseppe D'Angelo2012-04-051-0/+1
| | | | | | | | | It was never introduced in Qt 4, probably because of the implicit conversion to QString (that is, adding the qHash overload for QLatin1String in Qt 4 would have been a BIC). Change-Id: I2ebc8e73a85be497866820e0ca416dd11167bb53 Reviewed-by: Robin Burchell <robin+qt@viroteck.net>
* QHash security fix (1.5/2): qHash two arguments overload supportGiuseppe D'Angelo2012-04-041-5/+7
| | | | | | | | | | | | | | | | | | | | | | | Algorithmic complexity attacks against hash tables have been known since 2003 (cf. [1, 2]), and they have been left unpatched for years until the 2011 attacks [3] against many libraries / (reference) implementations of programming languages. This patch adds a qHash overload taking two arguments: the value to be hashed, and a uint to be used as a seed for the hash function itself (support the global QHash seed was added in a previous patch). The seed itself is not used just yet; instead, 0 is passed. Compatibility with the one-argument qHash(T) implementation is kept through a catch-all template. [1] http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf [2] http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks [3] http://www.ocert.org/advisories/ocert-2011-003.html Task-number: QTBUG-23529 Change-Id: I1d0a84899476d134db455418c8043a349a7e5317 Reviewed-by: João Abecasis <joao.abecasis@nokia.com>
* QHash security fix (1/2): add global QHash seedGiuseppe D'Angelo2012-04-031-0/+1
| | | | | | | | | | | | | | | | | | | | | | Algorithmic complexity attacks against hash tables have been known since 2003 (cf. [1, 2]), and they have been left unpatched for years until the 2011 attacks [3] against many libraries / (reference) implementations of programming languages. This patch adds a global integer, to be used as a seed for the hash function itself. The seed is randomly initialized the first time a QHash detaches from shared_null. Right now the seed is not used at all -- another patch will modify qHash to make use of it. [1] http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf [2] http://perldoc.perl.org/perlsec.html#Algorithmic-Complexity-Attacks [3] http://www.ocert.org/advisories/ocert-2011-003.html Task-number: QTBUG-23529 Change-Id: I7519e4c02b9c2794d1c14079b01330eb356e9c65 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fallback implementation of Q_ALIGNOFJoão Abecasis2012-03-231-5/+0
| | | | | | | | | | | | For all practical purposes, the fallback introduced here returns the desired value. Having a fallback enables unconditional use of Q_ALIGNOF. For compilers that provide native support for it, Q_ALIGNOF is otherwise #defined in qcompilerdetection.h. Change-Id: Ie148ca8936cbbf8b80fe87771a14797c39a9d30c Reviewed-by: Marc Mutz <marc.mutz@kdab.com> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Merge master into api_changesKent Hansen2012-03-191-0/+2
|\ | | | | | | | | | | | | | | Conflicts: src/corelib/tools/qvector.h tests/auto/corelib/kernel/qmetatype/tst_qmetatype.cpp Change-Id: I877256e95f3788e617437f4e9661a88047f38cd6
| * containers: add C++11-style c{begin,end}() as alias for const{Begin,End}()Marc Mutz2012-03-171-0/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | C++11 adds cbegin()/cend() functions for the same reason Qt has constBegin()/constEnd(). This patch adds these functions to the Qt containers with the same implementation as constBegin()/constEnd(). It also fixes the return types in the documentation of existing constFind() functions (documentation only). C++11 only adds cbegin()/cend() (and crbegin()/crend(), which Qt doesn't have). In particular, it doesn't add cfind(), so I didn't supply these, even though Qt comes with constFind(). This is a forward-port of https://qt.gitorious.org/qt/qt/merge_requests/1365. Change-Id: Ida086b64246b24e25254eafbcb06c8e33388502b Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* | Merge remote-tracking branch 'gerrit/master' into containersJoão Abecasis2012-02-051-3/+2
|\| | | | | | | | | | | | | Conflicts: src/corelib/tools/qstring.cpp Change-Id: I23d214bf33c2badfae1876da3cc7d6d8f6e635fb
| * Remove "All rights reserved" line from license headers.Jason McDonald2012-01-301-1/+1
| | | | | | | | | | | | | | | | | | | | As in the past, to avoid rewriting various autotests that contain line-number information, an extra blank line has been inserted at the end of the license text to ensure that this commit does not change the total number of lines in the license header. Change-Id: I311e001373776812699d6efc045b5f742890c689 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
| * Remove use of QT_MODULE from libraryGunnar Sletta2012-01-251-1/+0
| | | | | | | | | | | | | | | | | | | | These defines were there to aid in the commercial licensing scheme we used long ago, and are no longer needed. Keep a QT_MODULE(x) define so other modules continue compiling. Change-Id: I8fd76cd5270df8f14aee746b6cf32ebf7c23fec7 Reviewed-by: Lars Knoll <lars.knoll@nokia.com>
| * Update contact information in license headers.Jason McDonald2012-01-231-1/+1
| | | | | | | | | | | | | | Replace Nokia contact email address with Qt Project website. Change-Id: I431bbbf76d7c27d8b502f87947675c116994c415 Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* | Don't use RefCount int operatorsJoão Abecasis2012-01-231-2/+2
|/ | | | | | | | | | | | | , as those are going away. The comment in QString/QByteArray::squeeze about shared_null was updated as it also affects other static data, such as that generated by QStringLiteral and QByteArrayLiteral. Change-Id: I26a757d29db62b1e3566a1f7c8d4030918ed8a89 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Bradley T. Hughes <bradley.hughes@nokia.com> Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Update copyright year in license headers.Jason McDonald2012-01-051-1/+1
| | | | | Change-Id: I02f2c620296fcd91d4967d58767ea33fc4e1e7dc Reviewed-by: Rohan McGovern <rohan.mcgovern@nokia.com>
* Fix "may be used uninitialized" compiler warning.Morten Sorvig2011-10-191-1/+1
| | | | | Change-Id: I96e9dbf0f3df527785e03661b9c25bd2d214cd44 Reviewed-by: João Abecasis <joao.abecasis@nokia.com>
* Don't crash by modifying read-only shared_nullBradley T. Hughes2011-10-041-1/+1
| | | | | | | | | | | | | | | | | | | Functions that modify the d-pointer must detach or otherwise take measures to not modify the const, read-only shared_null. The setSharable(bool) function takes care to detach when setting sharable to false, but should avoid setting the sharable data member unless d is not the shared null. Similarly, QMap<Key, T>::setInsertInOrder() needs to detach if it is shared with the shared_null (the logic has been updated to be the same as setSharable()). Change-Id: Ida5cb9818b86695f1b9f0264418b955c56424898 Reviewed-on: http://codereview.qt-project.org/5929 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Bradley T. Hughes <bradley.hughes@nokia.com> Reviewed-by: Jan-Arve Sæther <jan-arve.saether@nokia.com>
* Update QHash for Qt 5Bradley T. Hughes2011-09-261-27/+5
| | | | | | | | | | | Dealt with all necessary changes that are marked in the code: removing methods left only for binary compatibility with earlier Qt 4 versions and other methods marked for removal. Change-Id: I47109ccd9ed40addc345416be9e172570723955e Reviewed-on: http://codereview.qt-project.org/4534 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
* Make QHashData::shared_null constBradley T. Hughes2011-09-261-4/+4
| | | | | | | | | | Similar to QLinkedList QList, QMap, QVector, QByteArray and QString, keep the shared_null in shareable memory and never modify it. Change-Id: Ia8b72ef0288575bed658153d9d54434580988bda Reviewed-on: http://codereview.qt-project.org/4533 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
* don't calculate hash when the map is empty and we are not insertingOswald Buddenhagen2011-09-261-3/+6
| | | | | | | | | | | | the alternative would be splitting the function into two separate overloads. that might result in better branch prediction, but will create a bit more code. Change-Id: Ia2c685bbb34a9681c71f2249d073dd960368209a Reviewed-on: http://codereview.qt-project.org/5332 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Samuel Rødal <samuel.rodal@nokia.com> Reviewed-by: Lars Knoll <lars.knoll@nokia.com>
* Update licenseheader text in source files for qtbase Qt moduleJyri Tahtela2011-05-241-17/+17
| | | | | | | Updated version of LGPL and FDL licenseheaders. Apply release phase licenseheaders for all source files. Reviewed-by: Trust Me
* Initial import from the monolithic Qt.Qt by Nokia2011-04-271-0/+1043
This is the beginning of revision history for this module. If you want to look at revision history older than this, please refer to the Qt Git wiki for how to use Git history grafting. At the time of writing, this wiki is located here: http://qt.gitorious.org/qt/pages/GitIntroductionWithQt If you have already performed the grafting and you don't see any history beyond this commit, try running "git log" with the "--follow" argument. Branched from the monolithic repo, Qt master branch, at commit 896db169ea224deb96c59ce8af800d019de63f12
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-05 17:50:44 +0000