summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qmap.h
Commit message (Collapse)AuthorAgeFilesLines
* QMap - add multiInsert with hintThorbjørn Martsum2013-03-061-0/+54
| | | | | | | | This provides a fast multiInsert in QMap (and a fast insert in QMultiMap) when providing a correct hint. Change-Id: I3c864c3a7842765fe63f8ecb4b54d0e8c9fd22d7 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QMap - add insert overload that provide a hintThorbjørn Lund Martsum2013-03-061-0/+67
| | | | | | | | This adds a fast insert on QMap when providing a correct hint. Change-Id: I256bba342932c1d4f24c6e65074e1bf47b519537 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Lars Knoll <lars.knoll@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/+19
| | | | | | | | | 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>
* QMap - improve QMap stl-map ctorThorbjørn Lund Martsum2012-10-291-1/+1
| | | | | | | | | | We can insert directly on the most left-most Node. We always enforce an insert here (unlike the insert call), but that is not a problem since the keys in a std::map are unique. Change-Id: Ib409b90ffc57a5a43dab4a4b08d34f6fdabd057f Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap 5.0 - keep track of leftmost node (BIC)Thorbjørn Lund Martsum2012-10-271-2/+6
| | | | | | | | | | | | | | | | | | | | | This suggestion keeps track of the most left node. The point is that constBegin() becomes a lot faster. That speeds up iteration a bit, and makes it O(1) to get the first element. The penalty in insert and remove is very small. On large trees it seems to be less than 1%. It should be noticed that constBegin() is a very common hint on my planned change to 5.1, and this opperation will without this patch cost 2 x log N. One when the user calls the hint with begin - and one where it is compared with begin. Other std::maps has a very fast begin(). E.g http://www.cplusplus.com/reference/stl/map/begin/ (begin with constant time) Change-Id: I221f6755aa8bd16a5189771c5bc8ae56c8ee0fb4 Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap - use hint on insert in QMap::toStdMapThorbjørn Lund Martsum2012-10-271-1/+1
| | | | | | | | | Giving the std-map a hint (normally) improves insert performance. There seems to be no reason not to provide this hint. Change-Id: I4344607ebf54574a3ae9666d87a41a3c14762361 Reviewed-by: Robin Burchell <robin+qt@viroteck.net> Reviewed-by: Lars Knoll <lars.knoll@digia.com>
* QMap - remove unused maximumNode() functionsThorbjørn Lund Martsum2012-10-081-4/+0
| | | | | | | | | QMap has 4 different maximumNode() functions, but they are all unused and just in the way. Change-Id: I012145cfae32898830ec95e229514d9be838ae2f Reviewed-by: Lars Knoll <lars.knoll@digia.com> Reviewed-by: Robin Burchell <robin+qt@viroteck.net>
* 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>
* Rename QMapData::free to destroyThiago Macieira2012-08-091-3/+3
| | | | | | | | | | | | | The convention for QMap is that "free" methods simply free memory and that "destroy" ones also run destructors of types affected. Since this function calls destroySubTree, it should be more properly called "destroy". This also gets rid of another function called simply "free" in our headers. Change-Id: I3fa621c78848ede33dd5b78428c704d0423ba4e7 Reviewed-by: Lars Knoll <lars.knoll@nokia.com>
* Remove the unnecessary comment about operator== not being necessaryThiago Macieira2012-05-311-4/+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>
* Remove references to QT_NO_STL from QtCoreThiago Macieira2012-04-071-8/+0
| | | | | | | | QT_NO_STL is now no longer defined, so remove the conditionals and select the STL side. Change-Id: Ieedd248ae16e5a128b4ac287f850b3ebc8fb6181 Reviewed-by: João Abecasis <joao.abecasis@nokia.com>
* Rewrite QMap to use a RB treeLars Knoll2012-03-231-394/+428
| | | | | | | | | | | | | | | | | | | | QMap used to use a skiplist in Qt 4.x, which has variable sized nodes and we can thus not optimise using custom allocators. The rewrite now uses a red-black tree, and all allocations and tree operations happen in the cpp file. This will allow us to introduce custom allocation schemes in later versions of Qt. Added some more tests and a benchmark. Memory consumption of the new QMap implementation is pretty much the same as before. Performance of insertion and lookup has increased by 10-30%. iteration is slower, but still extremely fast and should not matter compared to the work usually done when iterating. Change-Id: I8796c0e4b207d01111e2ead7ae55afb464dd88f5 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>
* | Don't expect null d-pointer in destructorsJoão Abecasis2012-02-131-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | The feature was introduced in commit 83497587b2 (2004, private history), to allow static containers to remain uninitialized until needed. This finishes reverting said commit. The feature had been silently removed from QByteArray and QString in commit a5a0985476 (2004, private history); removed from QList in aef03d80f7. Change-Id: I9947be7758d5730d2d6e6eb2a8a308db6e9bef39 Reviewed-by: Robin Burchell <robin+qt@viroteck.net> 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>
* Remove unused QMapData::createData()/node_create() overloads.Robin Burchell2011-12-081-2/+0
| | | | | | | Change-Id: I79010e1ecfdfe579d996db65681ab1559598f3ce Reviewed-by: Bradley T. Hughes <bradley.hughes@nokia.com> Reviewed-by: João Abecasis <joao.abecasis@nokia.com> Reviewed-by: Olivier Goffart <ogoffart@woboq.com>
* Don't crash by modifying read-only shared_nullBradley T. Hughes2011-10-041-2/+2
| | | | | | | | | | | | | | | | | | | 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>
* Make QMapData::shared_null constBradley T. Hughes2011-09-261-4/+4
| | | | | | | | | | Similar to QVector, QByteArray and QString, keep the shared_null in shareable memory and never modify it. Change-Id: I062825684b79f2b01ec7ce65e0cf74f417b760b8 Reviewed-on: http://codereview.qt-project.org/4530 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
* Remove all non-const operator==Harald Fernengel2011-08-091-2/+2
| | | | | | | | | | | We had to leave the non-const operator== for binary compatibility. Remove them all, just leave the const version in there. 100% source compatible. Change-Id: Ib7a70fb441fe51d5164d9cbf495cbeda0f48fafe Reviewed-on: http://codereview.qt.nokia.com/2773 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Robert Griebl <robert.griebl@nokia.com>
* remove QT3_SUPPORT from corelib/toolsLars Knoll2011-06-291-36/+0
| | | | | | | Change-Id: Ie224cf992be675c7d405d4be05e4acd4157e590e Reviewed-on: http://codereview.qt.nokia.com/863 Reviewed-by: Qt Sanity Bot <qt_sanity_bot@ovi.com> Reviewed-by: Liang Qi <liang.qi@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/+1090
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-10 09:56:09 +0000