summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qlist.h
Commit message (Collapse)AuthorAgeFilesLines
* Replace usages of Q_CLANG_QDOC with Q_QDOCLuca Di Sera2022-10-211-2/+2
| | | | | | | | | | | | | | | | | | | | | | | 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>
* QList: don't detach twice in operator[]Mårten Nordheim2022-08-281-1/+1
| | | | | | | | | We first detached in operator[] itself, then in the data() call. Change-Id: I18b8b282b3b879125db350e0127953f83f773619 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.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>
* QtCore: replace qSwap with std::swap/member-swap where possibleMarc Mutz2022-01-201-1/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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>
* Properly detect and declare contiguous iteratorsGiuseppe D'Angelo2022-01-131-7/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The recommended way to detect a contiguous iterator isn't to check the iterator_category; it's to use the iterator concepts. Similarly, the recommendation set in place by P2259 (for being backwards-compatible) is to declare a iterator_concept member, not to change iterator_category to a C++20 category, (also) because legacy code may be checking for equality against a specific category, rather than for convertibility. This is erroneous, but such code exists, alas. This is enshrined in C++20's stdlib: for instance, iterator_traits<Foo*> has random_access_category_tag as iterator_category, but contiguous_iterator_tag as its iterator_concept. Hence: 1) in QArrayDataOps use the concept, and not the category, to do the check 2) when declaring iterators, keep the category as random access, and introduce the concept alias (if supported). Pick-to: 6.2 6.3 Change-Id: Ib600da7331d687a15082becaa6be06aefc24bb9c Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QList: fix typo in QList(It, It)Marc Mutz2021-12-101-1/+1
| | | | | | | | | | | | Remove scaffolding in the test again. [ChangeLog][QtCore][QList] Fixed a regression that caused the range constructor to fail for pure input_iterator's. Pick-to: 6.2 Fixes: QTBUG-99036 Change-Id: I72d01a9c44c3862c335d96538f26a453b4c7c554 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList::count(T): remove the &* hack on iteratorsThiago Macieira2021-11-301-1/+1
| | | | | | | | | | | | Use data() and data() + size() instead. This solves an UB when the list is in its default-constructed state, for which constData() == nullptr. Pick-to: 6.2 Fixes: QTBUG-98770 Change-Id: I2cffe62afda945079b63fffd16bc165978c769f6 Reviewed-by: Marc Mutz <marc.mutz@qt.io>
* Fix docs for comparison/debug/data stream operators of Qt containersSona Kurazyan2021-10-181-0/+9
| | | | | | | | | | | | | | 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>
* QList: deprecate iterator<->pointer implicit conversions (3/3)Giuseppe D'Angelo2021-10-161-2/+14
| | | | | | | | | | Follow-up of the previous commit: in case the implicit conversions between iterator and pointers are disabled, then reintroduce the non-template arithmetic operators for the iterator classes. Change-Id: I8cee60fe77ee3a47e189b4b53a08e39408f9db18 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList: deprecate iterator<->pointer implicit conversions (2/3)Giuseppe D'Angelo2021-10-161-4/+20
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The constructor from a raw pointer should be 1) constexpr, 2) explicit, and 3) *private*. We can do 1) without too much trouble. 2) is a (easy to fix) SIC in case of implicit conversions accidentally relied upon from somewhere. 3) cannot be "easily" fixed by user code (they have to refactor), and also, it's a BIC on Windows which encodes class members' access in symbols. Someone may have been exporting some QList subclass, in turn exporting the iterator classes, and therefore that someone now has the constructors' symbols with a given access. So, don't do 2+3 _just yet_ for user code, but set a deadline: Qt 6.5 is the last that will support this. On Qt 6.6, we switch. All of this on non-Windows, againt to avoid an ABI break. One can opt-in at any time via a suitable define. Given we have this define, use it to guard the other way around as well: conversions from an iterator to a raw pointer should never be explicit (there's std::to_address for this). [ChangeLog][QtCore][QList] Converting a QList's iterator from and to a raw pointer is deprecated, and will get removed in Qt 6.6. User code can prepare for the change by defining QT_STRICT_QLIST_ITERATORS. Change-Id: I0f34bfa3ac055c02af5a3ca159180304660dfc11 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList: deprecate iterator<->pointer implicit conversions (1/3)Giuseppe D'Angelo2021-10-161-8/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | QList<T>::(const_)iterator both feature an implicit operator T*. This operator exists in order to keep compatibility with Qt 5 code, where QVector<T>::iterator _was_ indeed a T*. However, iterators are not proxy objects and should not convert to T* (at least, not implictly). In fact we've already seen compilers complain about ambiguous calls when e.g. moving an iterator through an arithmetic operation (say, operator+). For instance, if one does it + number and the numeric argument of that call is not precisely qsizetype (but, say, int), then the call is ambiguous between operator+(iterator, int promoted to qsizetype) operator+(pointer (converted from iterator), int) One can imagine similar failures in generic code. In short: let's deprecate (not remove) the implicit conversion, and let people use iterators for what they are. Task-number: QTBUG-96128 Change-Id: I008348beefe00e4449b2d95c21c842d676390a26 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList: add mixed comparison operators between (const_)iteratorsGiuseppe D'Angelo2021-10-151-2/+15
| | | | | | | | | | | | | It is currently possible to compare a QList iterator with a const_iterator and viceversa, even though these operations aren't defined, because they are actually routed through the relational operators between iterators and raw pointers after a conversion (!). With the deprecation of iterator->pointer implicit conversions, this is going to break, so add the missig mixed comparison operators. Change-Id: Ic645ab0246f79f64b04334ecd02e9fe8fa46f0fa Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList: remove yet another iterator->pointer implicit conversionGiuseppe D'Angelo2021-10-131-1/+5
| | | | | | | | | | | | | | The ranged constructor for QList has an optimization when the iterators are QList's own iterators. In that case, it uses a "contiguous append" shortcut by converting the iterators to pointers. Avoid that conversion by extracting the pointers from the iterators. Note that this is an optimization for C++17 only; in C++20 appendIteratorRange will deal with this case as well. Leave a note. Change-Id: I761c36ff500dee95b4ae1b0a4479d22db0c8e3de Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QList: code tidiesGiuseppe D'Angelo2021-10-131-19/+19
| | | | | | | | Do not rely on implicit pointer->QList::(const_)iterator conversions. Amend QList's own code so to avoid them. Change-Id: Ia3e7a83631943e636831217cdad28b73c98c1dc7 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* QList::iterator: use templates for advancing operatorsThiago Macieira2021-10-121-10/+22
| | | | | | | | | | | | | | | | | | | | | | | | | Because of the addition of the operator T*(), the expression "it + N" where N was not exactly qsizetype but any other integer type was a compilation failure because of ambiguous overload resolution. With GCC it's apparently a warning: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second: note: candidate 1: ‘QList<T>::iterator QList<T>::iterator::operator+(qsizetype) const [with T = char; qsizetype = long long int]’ note: candidate 2: ‘operator+(char*, ptrdiff_t {aka long int})’ (built-in) With Clang, it's an error: error: use of overloaded operator '+' is ambiguous (with operand types 'QList<int>::const_iterator' and 'ptrdiff_t' (aka 'long')) note: candidate function inline const_iterator operator+(qsizetype j) const { return const_iterator(i+j); } note: built-in candidate operator+(const int *, long) Pick-to: 6.2 Fixes: QTBUG-96128 Change-Id: Ie72b0dd0fbe84d2caae0fffd16a06f23dd56b060 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* Remove checks for features available in C++17Ievgenii Meshcheriakov2021-10-021-2/+0
| | | | | | | | | | This patch removes most of the checks that are made using C++20 __cpp_* macros for features available in C++17 and earlier. Library feature check macros (__cpp_lib_*) are unaffected. Change-Id: I557b2bd0d4ff09b13837555e9880eb28e0355f64 Reviewed-by: Edward Welbourne <edward.welbourne@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Fix compilation for recursive Qt containersSona Kurazyan2021-09-071-6/+6
| | | | | | | | | | | | | | | | | | | | 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>
* Resurrect data moves in QListAndrei Golubev2021-04-271-11/+10
| | | | | | | | | | | | | | | | | Use the data moves to readjust the free space in the QList, which ultimately fixes the out-of-memory issues caused by cases like: forever { list.prepend(list.back()); list.removeLast(); } Task-number: QTBUG-91801 Task-number: QTBUG-91360 Task-number: QTBUG-93019 Change-Id: Iacff69cbf36b8b5b176bb2663df635ec972c875c Reviewed-by: Lars Knoll <lars.knoll@qt.io> (cherry picked from commit a0253f5f0249024580050e4ec22d50cb139ef8d9)
* QList::(const_)iterator: protect element_type on GCC < 11Giuseppe D'Angelo2021-04-161-2/+2
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | GCC 10 in C++20 mode will still try to use std::indirectly_readable_traits on QList iterators, and since it does not have the fixes for LWG 3346 / 3541, it will fail to build: /usr/include/c++/10/bits/iterator_concepts.h: In substitution of ‘template<class _Tp> using __iter_value_t = typename std::__detail::__iter_traits_impl<_Tp, std::indirectly_readable_traits<_Iter> >::type::value_type [with _Tp = QList<std::pair<int, int> >::const_iterator]’: /usr/include/c++/10/bits/iterator_concepts.h:248:11: required by substitution of ‘template<class _Tp> using iter_value_t = std::__detail::__iter_value_t<typename std::remove_cv<typename std::remove_reference<_Tp>::type>::type> [with _Tp = QList<std::pair<int, int> >::const_iterator]’ /usr/include/c++/10/bits/iterator_concepts.h:468:11: required from ‘class std::reverse_iterator<QList<std::pair<int, int> >::const_iterator>’ ../src/corelib/itemmodels/qsortfilterproxymodel.cpp:669:43: required from here /usr/include/c++/10/bits/iterator_concepts.h:243:13: error: ambiguous template instantiation for ‘struct std::indirectly_readable_traits<QList<std::pair<int, int> >::const_iterator>’ 243 | using __iter_value_t = typename | ^~~~~~~~~~~~~~ /usr/include/c++/10/bits/iterator_concepts.h:231:12: note: candidates are: ‘template<class _Tp> requires requires{typename _Tp::value_type;} struct std::indirectly_readable_traits<_Iter> [with _Tp = QList<std::pair<int, int> >::const_iterator]’ 231 | struct indirectly_readable_traits<_Tp> | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ /usr/include/c++/10/bits/iterator_concepts.h:236:12: note: ‘template<class _Tp> requires requires{typename _Tp::element_type;} struct std::indirectly_readable_traits<_Iter> [with _Tp = QList<std::pair<int, int> >::const_iterator]’ 236 | struct indirectly_readable_traits<_Tp> | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ So hide element_type as well. The CI didn't catch this because the CI doesn't build in C++20 mode. Amends 595b4e1a9b4. Change-Id: I5c8e47d693ca584571cd89f856d08ba249dd05ab Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
* QList: Satisfy contiguous_range requirementsFabian Kosmale2021-04-061-2/+15
| | | | | | | | | | | | | | | | | | With C++20, there is a new iterator_category: contiguous_iterator, for containers whose elements are stored contiguously in memory. In Qt 6, QList satisfies this requirement. However, we still need to tell the standard machinery about it. Step one is to mark the iterators as contiguous_iterator; as that exists only in C++20, we have to ifdef accordingly. We also have to ensure that the iterators satisfy pointer_traits by defining element_type due to how contiguous_range is specified. As this runs afoul of LWG 3346, we check for known bad _GLIBCXX_RELEASE versions. Change-Id: I8c134544e694ba937e4d912393eb72fa75b49e3d Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* QList: replace typedef with usingFabian Kosmale2021-03-301-10/+10
| | | | | | Change-Id: Ie3fa605cf05d65ca422df738dcce1fa49d6371c7 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
* Restore pre-Qt6 QList::fill() behaviorAndrei Golubev2021-02-101-1/+4
| | | | | | | | | | | | | | | | | | Somehow QList::fill(t, newSize) introduced a regression in Qt6: when newSize < QList::size() we should resize to the newSize. This is aligned with QVector::fill() in 5.15 and std::vector::assign() While 6.0 is already out, picking it to 6.0.x could save someone who haven't migrated yet as well as fix some accidental bugs in Qt's code [ChangeLog][QtCore][QList] Fixed QList::fill() regression introduced in 6.0: calling fill() with size < current list size wouldn't truncate the list Fixes: QTBUG-91042 Pick-to: 6.0 6.1 Change-Id: Ic166e2c5e42390b61df1030f7c705e344433f7f2 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Mark places where we missed conversion to unicode character typesEdward Welbourne2021-01-081-0/+1
| | | | | | | | | | | We should use char32_t for the toUcs4() methods of QString and QStringView and use char16_t for QString::utf16(), thereby matching QStringView. These naturally imply knock-on changes in various places. Unfortunately, we didn't make those changes in Qt 6, so they'll have to wait for Qt 7. Change-Id: I18451d4b31b76658092e19d3fcbc8bc0fe5ce307 Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* QList: make an indirect inclusion directGiuseppe D'Angelo2020-12-041-0/+1
| | | | | Change-Id: Ief36ac375f5c26b4a5de6bc18ee3f2f777051024 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Sequential general purpose containers: add erase/erase_ifGiuseppe D'Angelo2020-12-011-22/+22
| | | | | | | | | | | | | | | | | | | | This is refactor/revisit for Qt 6 of the original commit [1] by Marc, limited to QList and QVLA. [1] see 11aa9a2276ba5367adbbd96d0ba13111d58145f8 [ChangeLog][QtCore][QList] Added erase() and erase_if(), for consistent container erasure. Added removeIf() as a method, complementing removeOne() / removeAll(). [ChangeLog][QtCore][QVarLengthArray] Added erase() and erase_if(), for consistent container erasure. Added removeIf() as a method, complementing removeOne() / removeAll(). Change-Id: I2499504e221431ead754dd64cc8a4d4e9f116183 Done-by: Marc Mutz Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Lars Knoll <lars.knoll@qt.io>
* Move the iterator from QTypedArrayData to QListLars Knoll2020-11-171-12/+78
| | | | | | | | | | The low level implementation does not use it at all, so there's no point having the iterator in QTypedArrayData. Having it in QList removes and indirection and will lead to clearer error messages. Change-Id: I4af270c3cdb39620e5e52e835eb8fe1aa659e038 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Clean up QList(iterator, iterator)Lars Knoll2020-11-171-11/+14
| | | | | | | | | | Fold the two overloads into one, and distinguish the cases using if constexpr. Do not overload QArrayOps::copyAppend(), to make it clear which one is being used. Change-Id: If6a894841aacb84ba190fb2209246f5f61034b42 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Fix signature of QArrayDataOps::erase()Lars Knoll2020-11-171-3/+3
| | | | | | | | | | | | Bring it in line with the other methods that also take a pointer and a size. Also use truncate() in removeAll() as that's more efficient for the use case. Change-Id: Ib1073b7c048ceb96fb6391b308ef8feb77896866 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Remove the special code for emplaceFront/Back againLars Knoll2020-11-171-2/+2
| | | | | | | | | emplace() itself now handles those cases fast enough, so there should not be a need to add special code paths for those methods. Change-Id: I3277eb77dd54194e46f96f24de44d7785a6f860a Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Add a couple of noexcept to methods that can't throwLars Knoll2020-11-171-18/+18
| | | | | | | | | | | | | Trivial methods that don't modify any data for the most part. Also mark removeFirst/Last() as noexcept. Those methods can't throw exceptions as we require ~T() to be noexcept. Change-Id: I8698705c6113909aa8f7ae021a932df48a224d5d Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Move emplaceFront/Back() implementation into QArrayDataOpsLars Knoll2020-11-171-16/+2
| | | | | | | | This simplifies and clean up the code. Change-Id: I4cbfa69bda95187f97daf814eb3d44d90c502d92 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Simplify the code for QList::emplace()Lars Knoll2020-11-171-19/+1
| | | | | | | | | | | | Unify it with the code in QArrayDataOps and only have one emplace method there that handles it all. Adjust autotests to API changes in QArrayDataOps and fix a wrong test case (that just happened to pass by chance before). Change-Id: Ia08cadebe2f74b82c31f856b1ff8a3d8dc400a3c Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Simplify reallocation handling in QListLars Knoll2020-11-171-70/+29
| | | | | | | | | | Have one generic method for detaching and reallocations. Use that method throughout QList to avoid duplicated instantiations of code paths that are rarely used. Change-Id: I5b9add3be5f17b387e2d34028b72c8f52db68444 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Smaller code cleanups in QListLars Knoll2020-11-171-11/+10
| | | | | | | | | | Some cosmetics, but also some optimizations where we avoid a temporary copy, or calling detach() twice. Change-Id: I26803fdecf943ed9fab9baf58124091c7cebe1f3 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* QList::append(QList) doesn't require a temp copyLars Knoll2020-11-171-3/+1
| | | | | | | | | | The method can simply forward to the append overload taking iterators. That method is safe against the iterators being part of the list itself. Change-Id: I4bebd6c1118cd4a428fa9248235029b997ef60b2 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Fix error on MSVC when QList with disabled rvalues is instantiatedLars Knoll2020-11-161-6/+32
| | | | | | | | | | | MSVC does in some case full instantiation of the template. Make sure all of it expands to valid C++, even in the case where those methods are supposed to be disabled. Fixes: QTBUG-86289 Change-Id: Iaae39ef60fc5cf5fee273b0934a5a52b6ae4ec17 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Do not shrink on remove()Lars Knoll2020-11-091-16/+5
| | | | | | | | | | This is in line with Qt 5 behavior, how std::vector works and also how QString and QByteArray behave. If you need the shrink allocated storage, call squeeze() manually. Change-Id: I16cadd4f2a89bb2ec5de02fe69186f5da321cd06 Reviewed-by: Paul Wicking <paul.wicking@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Implement fast paths for removeFirst() and removeLast()Lars Knoll2020-11-091-2/+20
| | | | | | | | | This avoids lots of the code and checks in remove() making the methods a lot faster. Change-Id: If99c39f5b55672b341f9331b5903bf77e9e67477 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Rename AllocationPosition enum and its membersLars Knoll2020-11-041-6/+6
| | | | | | | Use GrowsAt* and GrowthPosition as that is clearer. Change-Id: I3c173797dec3620f508156efc0c51b4d2cd3e142 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Properly implement emplaceBack/Front() in QArrayDataOpsLars Knoll2020-11-041-4/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This improves the performance of QList<QString>::append/prepend() and we now beat QVector in Qt 5. QList from Qt 5 is still a bit better for QString, but this might be related to the fact that QString in Qt 6 is larger than in Qt 5. Appending 20M integers to the list gives: Qt 6: 35ms Qt 5.15/QVector: 99ms Qt 5.15/QList: 78ms Appending 20M QStrings to the list gives: Qt 6: 172ms Qt 5.15/QVector: 194ms Qt 5.15/QList: 136ms Appending 20M structs of three pointers gives (100M will crash in Qt5 as 100M*24bytes overflows): Qt 6: 109ms Qt 5.15/QVector: 272ms Qt 5.15/QList: 469ms Prepending 20M integers to the list gives: Qt 6: 58ms Qt 5.15/QList: 90ms Prepending 20M QStrings to the list gives: Qt 6: 448ms Qt 5.15/QList: 147ms Prepending 20M structs of three pointers gives (100M will crash in Qt5 as 100M*24bytes overflows): Qt 6: 267ms Qt 5.15/QList: 435ms No numbers for prepending to a QVector in 5.15 as the operation was O(n) there. The difference in time between append and prepend comes from the fact that our growth policy favors appending to some extent. Change-Id: Ice4598df5ca408413bfb00f5fe05e0b8d512623d Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Introduce QADP::reallocateGrow()Andrei Golubev2020-11-041-4/+16
| | | | | | | | | | | | | | Added realloc() code path to QMovableArrayOps Implemented fast realloc() based growing for QADP and used it in QList::emplaceBack. This gives quite a bit of speedup and shows better results than 5.15 at 100k+ iterations of "list.append(elem)", meanwhile also closing a gap between movable types Task-number: QTBUG-87330 Change-Id: I42fc182ecd93c85600dac622385152fc57735da8 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Implement QList::emplaceBack as a proper functionAndrei Golubev2020-11-041-4/+18
| | | | | | | | | | | | | | | | | | | | | | | | | | My endeavours figuring out why QList::append(elem) gives worst performance compared to 5.15 ended up into this commit. After some straightforward fixes, what was left is "everything is uniformly worse" and takes more CPU cycles Introduce emplaceBack implementation as append is quite a special case that could be greatly simplified. This is a "straightforward" part of the optimizations While at it, change append(t) to use emplaceBack(t) For workloads like: QList<int> list; forever { list.append(0); } this gives huge improvement (roughly 30% for 10k+ elements), movable and complex types also get a tiny speedup Task-number: QTBUG-87330 Change-Id: I9261084e545c24e5473234220d2a3f2cd26c2b7f Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Move insert() operation into QArrayDataOpsLars Knoll2020-11-041-23/+1
| | | | | | | | | This allows us to unify and simplify the code base between QList, QString and QByteArray. Change-Id: Idc8f360d78f508a68f38eb3ef0ed6e5d37f90574 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
* Clean up out allocation handlingLars Knoll2020-11-041-19/+17
| | | | | | | | | | Get rid of the allocation options inside the flags field of QArrayData, they are really a completely separate thing. Change-Id: I823750ab9e4ca85642a0bd0e471ee79c9cde43fb Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Avoid expensive iterator calculations in append()Lars Knoll2020-11-041-37/+29
| | | | | | | | | | | | | Avoid moving data inside the array to create free space at one end. This is a performance bottleneck, as it required quite a lot of calculations for every insert. Rather reallocate and grow in this case, so we only need to do expensive work when we reallocate the array. Change-Id: Ifc955fbcf9967c3b66aa2600e0627aac15f0c917 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Andrei Golubev <andrei.golubev@qt.io>
* Remove unused parameterLars Knoll2020-11-041-4/+4
| | | | | | Change-Id: Idceb7ee3ce752b62ed6800b0a1004832a4c48af7 Reviewed-by: Andrei Golubev <andrei.golubev@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Add QList::emplaceFront() that fixes huge performance issue in prependAndrei Golubev2020-11-041-9/+28
| | | | | | | | | | | | | | | | | | | | | | Prepend in QList was using insert() logic that always uses append-aware functions. This results in the fact that freeSpaceAtBegin() is always 0 and forces us to actually allocate on *every* call (with the same capacity!). Vicious cycle is hot-fixable with introduction of emplaceFront (or anything prepend-aware, really) This brings me from 632ms to 0.65ms for 100k iterations of list.prepend(int(0)). Still ~3x worse than QList in 5.15 but much faster than QVector, which takes 382ms in the same workload Not addressed: - QString/QBA - Other prepend functions in QList e.g. prepend(it1, it2) - Lower-level array operations that should just be extended Task-number: QTBUG-86583 Change-Id: Ie82b07d81a67605cd308d9fabf9532d57935647f Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
* Hide QList comparisons from ADLAllan Sandfeld Jensen2020-10-301-62/+48
| | | | | | | | | | Makes them member methods instead of hidden inline, as those actually gets listed in documentation, and two were already documented as such. Task-number: QTBUG-87975 Change-Id: I382ff8b701753f1fe150a38f4c530a52c98ad292 Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org> Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* QList: also default count()'s template parameterGiuseppe D'Angelo2020-10-261-1/+1
| | | | | | | | Also fix the docs. Change-Id: If08116cb8657d00d610de9451be0ba73ce19dcd1 Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io> Reviewed-by: Volker Hilsheimer <volker.hilsheimer@qt.io>
* Update QList::append(const_reference) -> QList::append(parameter_type)Andrei Golubev2020-10-241-1/+1
| | | | | | | | | | Forgotten during previous round of replacing const lvalue references with parameter_type in QList methods Task-number: QTBUG-86553 Change-Id: I9abda4db3b504521b64fab1f220559c36bfeb9f5 Reviewed-by: Lars Knoll <lars.knoll@qt.io> Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-15 07:01:46 +0000