1 /**************************************************************************** 2 ** 3 ** Copyright (C) 2016 The Qt Company Ltd. 4 ** Contact: https://www.qt.io/licensing/ 5 ** 6 ** This file is part of the QtCore module of the Qt Toolkit. 7 ** 8 ** $QT_BEGIN_LICENSE:LGPL$ 9 ** Commercial License Usage 10 ** Licensees holding valid commercial Qt licenses may use this file in 11 ** accordance with the commercial license agreement provided with the 12 ** Software or, alternatively, in accordance with the terms contained in 13 ** a written agreement between you and The Qt Company. For licensing terms 14 ** and conditions see https://www.qt.io/terms-conditions. For further 15 ** information use the contact form at https://www.qt.io/contact-us. 16 ** 17 ** GNU Lesser General Public License Usage 18 ** Alternatively, this file may be used under the terms of the GNU Lesser 19 ** General Public License version 3 as published by the Free Software 20 ** Foundation and appearing in the file LICENSE.LGPL3 included in the 21 ** packaging of this file. Please review the following information to 22 ** ensure the GNU Lesser General Public License version 3 requirements 23 ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. 24 ** 25 ** GNU General Public License Usage 26 ** Alternatively, this file may be used under the terms of the GNU 27 ** General Public License version 2.0 or (at your option) the GNU General 28 ** Public license version 3 or any later version approved by the KDE Free 29 ** Qt Foundation. The licenses are as published by the Free Software 30 ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 31 ** included in the packaging of this file. Please review the following 32 ** information to ensure the GNU General Public License requirements will 33 ** be met: https://www.gnu.org/licenses/gpl-2.0.html and 34 ** https://www.gnu.org/licenses/gpl-3.0.html. 35 ** 36 ** $QT_END_LICENSE$ 37 ** 38 ****************************************************************************/ 39 40 #ifndef QLIST_H 41 #define QLIST_H 42 43 #include <QtCore/qalgorithms.h> 44 #include <QtCore/qiterator.h> 45 #include <QtCore/qrefcount.h> 46 #include <QtCore/qarraydata.h> 47 #include <QtCore/qhashfunctions.h> 48 #include <QtCore/qvector.h> 49 #include <QtCore/qcontainertools_impl.h> 50 51 #include <algorithm> 52 #include <initializer_list> 53 #include <iterator> 54 #if QT_VERSION < QT_VERSION_CHECK(6,0,0) 55 #include <list> 56 #endif 57 58 #include <stdlib.h> 59 #include <new> 60 #include <limits.h> 61 #include <string.h> 62 63 #ifdef Q_CC_MSVC 64 #pragma warning( push ) 65 #pragma warning( disable : 4127 ) // "conditional expression is constant" 66 #endif 67 68 QT_BEGIN_NAMESPACE 69 70 71 template <typename T> class QVector; 72 template <typename T> class QSet; 73 74 template <typename T> struct QListSpecialMethods 75 { 76 protected: 77 ~QListSpecialMethods() = default; 78 }; 79 template <> struct QListSpecialMethods<QByteArray>; 80 template <> struct QListSpecialMethods<QString>; 81 82 struct Q_CORE_EXPORT QListData { 83 // tags for tag-dispatching of QList implementations, 84 // based on QList's three different memory layouts: 85 struct NotArrayCompatibleLayout {}; 86 struct NotIndirectLayout {}; 87 struct ArrayCompatibleLayout : NotIndirectLayout {}; // data laid out like a C array 88 struct InlineWithPaddingLayout : NotArrayCompatibleLayout, NotIndirectLayout {}; // data laid out like a C array with padding 89 struct IndirectLayout : NotArrayCompatibleLayout {}; // data allocated on the heap 90 91 struct Data { 92 QtPrivate::RefCount ref; 93 int alloc, begin, end; 94 void *array[1]; 95 }; 96 enum { DataHeaderSize = sizeof(Data) - sizeof(void *) }; 97 98 Data *detach(int alloc); 99 Data *detach_grow(int *i, int n); 100 void realloc(int alloc); 101 void realloc_grow(int growth); 102 inline void dispose() { dispose(d); } 103 static void dispose(Data *d); 104 static const Data shared_null; 105 Data *d; 106 void **erase(void **xi); 107 void **append(int n); 108 void **append(); 109 void **append(const QListData &l); 110 void **prepend(); 111 void **insert(int i); 112 void remove(int i); 113 void remove(int i, int n); 114 void move(int from, int to); 115 inline int size() const noexcept { return int(d->end - d->begin); } // q6sizetype 116 inline bool isEmpty() const noexcept { return d->end == d->begin; } 117 inline void **at(int i) const noexcept { return d->array + d->begin + i; } 118 inline void **begin() const noexcept { return d->array + d->begin; } 119 inline void **end() const noexcept { return d->array + d->end; } 120 }; 121 122 namespace QtPrivate { 123 template <typename V, typename U> int indexOf(const QList<V> &list, const U &u, int from); 124 template <typename V, typename U> int lastIndexOf(const QList<V> &list, const U &u, int from); 125 } 126 127 template <typename T> 128 class QList 129 #ifndef Q_QDOC 130 : public QListSpecialMethods<T> 131 #endif 132 { 133 public: 134 struct MemoryLayout 135 : std::conditional< 136 // must stay isStatic until ### Qt 6 for BC reasons (don't use !isRelocatable)! 137 QTypeInfo<T>::isStatic || QTypeInfo<T>::isLarge, 138 QListData::IndirectLayout, 139 typename std::conditional< 140 sizeof(T) == sizeof(void*), 141 QListData::ArrayCompatibleLayout, 142 QListData::InlineWithPaddingLayout 143 >::type>::type {}; 144 private: 145 template <typename V, typename U> friend int QtPrivate::indexOf(const QList<V> &list, const U &u, int from); 146 template <typename V, typename U> friend int QtPrivate::lastIndexOf(const QList<V> &list, const U &u, int from); 147 struct Node { void *v; 148 #if defined(Q_CC_BOR) 149 Q_INLINE_TEMPLATE T &t(); 150 #else 151 Q_INLINE_TEMPLATE T &t() 152 { return *reinterpret_cast<T*>(QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic 153 ? v : this); } 154 #endif 155 }; 156 157 union { QListData p; QListData::Data *d; }; 158 159 public: 160 inline QList() noexcept : d(const_cast<QListData::Data *>(&QListData::shared_null)) { } 161 QList(const QList<T> &l); 162 ~QList(); 163 QList<T> &operator=(const QList<T> &l); 164 inline QList(QList<T> &&other) noexcept 165 : d(other.d) { other.d = const_cast<QListData::Data *>(&QListData::shared_null); } 166 inline QList &operator=(QList<T> &&other) noexcept 167 { QList moved(std::move(other)); swap(moved); return *this; } 168 inline void swap(QList<T> &other) noexcept { qSwap(d, other.d); } 169 inline QList(std::initializer_list<T> args) 170 : QList(args.begin(), args.end()) {} 171 template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> 172 QList(InputIterator first, InputIterator last); 173 bool operator==(const QList<T> &l) const; 174 inline bool operator!=(const QList<T> &l) const { return !(*this == l); } 175 176 inline int size() const noexcept { return p.size(); } 177 178 inline void detach() { if (d->ref.isShared()) detach_helper(); } 179 180 inline void detachShared() 181 { 182 // The "this->" qualification is needed for GCCE. 183 if (d->ref.isShared() && this->d != &QListData::shared_null) 184 detach_helper(); 185 } 186 187 inline bool isDetached() const { return !d->ref.isShared(); } 188 #if !defined(QT_NO_UNSHARABLE_CONTAINERS) 189 inline void setSharable(bool sharable) 190 { 191 if (sharable == d->ref.isSharable()) 192 return; 193 if (!sharable) 194 detach(); 195 if (d != &QListData::shared_null) 196 d->ref.setSharable(sharable); 197 } 198 #endif 199 inline bool isSharedWith(const QList<T> &other) const noexcept { return d == other.d; } 200 201 inline bool isEmpty() const noexcept { return p.isEmpty(); } 202 203 void clear(); 204 205 const T &at(int i) const; 206 const T &operator[](int i) const; 207 T &operator[](int i); 208 209 void reserve(int size); 210 void append(const T &t); 211 void append(const QList<T> &t); 212 void prepend(const T &t); 213 void insert(int i, const T &t); 214 void replace(int i, const T &t); 215 void removeAt(int i); 216 int removeAll(const T &t); 217 bool removeOne(const T &t); 218 T takeAt(int i); 219 T takeFirst(); 220 T takeLast(); 221 void move(int from, int to); 222 void swapItemsAt(int i, int j); 223 #if QT_DEPRECATED_SINCE(5, 13) && QT_VERSION < QT_VERSION_CHECK(6,0,0) 224 QT_DEPRECATED_VERSION_X_5_13("Use QList<T>::swapItemsAt()") 225 void swap(int i, int j) { swapItemsAt(i, j); } 226 #endif 227 int indexOf(const T &t, int from = 0) const; 228 int lastIndexOf(const T &t, int from = -1) const; 229 bool contains(const T &t) const; 230 int count(const T &t) const; 231 232 class const_iterator; 233 234 class iterator { 235 public: 236 Node *i; 237 typedef std::random_access_iterator_tag iterator_category; 238 // ### Qt6: use int 239 typedef qptrdiff difference_type; 240 typedef T value_type; 241 typedef T *pointer; 242 typedef T &reference; 243 244 inline iterator() noexcept : i(nullptr) {} 245 inline iterator(Node *n) noexcept : i(n) {} 246 #if QT_VERSION < QT_VERSION_CHECK(6,0,0) 247 // can't remove it in Qt 5, since doing so would make the type trivial, 248 // which changes the way it's passed to functions by value. 249 inline iterator(const iterator &o) noexcept : i(o.i){} 250 inline iterator &operator=(const iterator &o) noexcept 251 { i = o.i; return *this; } 252 #endif 253 inline T &operator*() const { return i->t(); } 254 inline T *operator->() const { return &i->t(); } 255 inline T &operator[](difference_type j) const { return i[j].t(); } 256 inline bool operator==(const iterator &o) const noexcept { return i == o.i; } 257 inline bool operator!=(const iterator &o) const noexcept { return i != o.i; } 258 inline bool operator<(const iterator& other) const noexcept { return i < other.i; } 259 inline bool operator<=(const iterator& other) const noexcept { return i <= other.i; } 260 inline bool operator>(const iterator& other) const noexcept { return i > other.i; } 261 inline bool operator>=(const iterator& other) const noexcept { return i >= other.i; } 262 #ifndef QT_STRICT_ITERATORS 263 inline bool operator==(const const_iterator &o) const noexcept 264 { return i == o.i; } 265 inline bool operator!=(const const_iterator &o) const noexcept 266 { return i != o.i; } 267 inline bool operator<(const const_iterator& other) const noexcept 268 { return i < other.i; } 269 inline bool operator<=(const const_iterator& other) const noexcept 270 { return i <= other.i; } 271 inline bool operator>(const const_iterator& other) const noexcept 272 { return i > other.i; } 273 inline bool operator>=(const const_iterator& other) const noexcept 274 { return i >= other.i; } 275 #endif 276 inline iterator &operator++() { ++i; return *this; } 277 inline iterator operator++(int) { Node *n = i; ++i; return n; } 278 inline iterator &operator--() { i--; return *this; } 279 inline iterator operator--(int) { Node *n = i; i--; return n; } 280 inline iterator &operator+=(difference_type j) { i+=j; return *this; } 281 inline iterator &operator-=(difference_type j) { i-=j; return *this; } 282 inline iterator operator+(difference_type j) const { return iterator(i+j); } 283 inline iterator operator-(difference_type j) const { return iterator(i-j); } 284 friend inline iterator operator+(difference_type j, iterator k) { return k + j; } 285 inline int operator-(iterator j) const { return int(i - j.i); } 286 }; 287 friend class iterator; 288 289 class const_iterator { 290 public: 291 Node *i; 292 typedef std::random_access_iterator_tag iterator_category; 293 // ### Qt6: use int 294 typedef qptrdiff difference_type; 295 typedef T value_type; 296 typedef const T *pointer; 297 typedef const T &reference; 298 299 inline const_iterator() noexcept : i(nullptr) {} 300 inline const_iterator(Node *n) noexcept : i(n) {} 301 #if QT_VERSION < QT_VERSION_CHECK(6,0,0) 302 // can't remove it in Qt 5, since doing so would make the type trivial, 303 // which changes the way it's passed to functions by value. 304 inline const_iterator(const const_iterator &o) noexcept : i(o.i) {} 305 inline const_iterator &operator=(const const_iterator &o) noexcept 306 { i = o.i; return *this; } 307 #endif 308 #ifdef QT_STRICT_ITERATORS 309 inline explicit const_iterator(const iterator &o) noexcept : i(o.i) {} 310 #else 311 inline const_iterator(const iterator &o) noexcept : i(o.i) {} 312 #endif 313 inline const T &operator*() const { return i->t(); } 314 inline const T *operator->() const { return &i->t(); } 315 inline const T &operator[](difference_type j) const { return i[j].t(); } 316 inline bool operator==(const const_iterator &o) const noexcept { return i == o.i; } 317 inline bool operator!=(const const_iterator &o) const noexcept { return i != o.i; } 318 inline bool operator<(const const_iterator& other) const noexcept { return i < other.i; } 319 inline bool operator<=(const const_iterator& other) const noexcept { return i <= other.i; } 320 inline bool operator>(const const_iterator& other) const noexcept { return i > other.i; } 321 inline bool operator>=(const const_iterator& other) const noexcept { return i >= other.i; } 322 inline const_iterator &operator++() { ++i; return *this; } 323 inline const_iterator operator++(int) { Node *n = i; ++i; return n; } 324 inline const_iterator &operator--() { i--; return *this; } 325 inline const_iterator operator--(int) { Node *n = i; i--; return n; } 326 inline const_iterator &operator+=(difference_type j) { i+=j; return *this; } 327 inline const_iterator &operator-=(difference_type j) { i-=j; return *this; } 328 inline const_iterator operator+(difference_type j) const { return const_iterator(i+j); } 329 inline const_iterator operator-(difference_type j) const { return const_iterator(i-j); } 330 friend inline const_iterator operator+(difference_type j, const_iterator k) { return k + j; } 331 inline int operator-(const_iterator j) const { return int(i - j.i); } 332 }; 333 friend class const_iterator; 334 335 // stl style 336 typedef std::reverse_iterator<iterator> reverse_iterator; 337 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 338 inline iterator begin() { detach(); return reinterpret_cast<Node *>(p.begin()); } 339 inline const_iterator begin() const noexcept { return reinterpret_cast<Node *>(p.begin()); } 340 inline const_iterator cbegin() const noexcept { return reinterpret_cast<Node *>(p.begin()); } 341 inline const_iterator constBegin() const noexcept { return reinterpret_cast<Node *>(p.begin()); } 342 inline iterator end() { detach(); return reinterpret_cast<Node *>(p.end()); } 343 inline const_iterator end() const noexcept { return reinterpret_cast<Node *>(p.end()); } 344 inline const_iterator cend() const noexcept { return reinterpret_cast<Node *>(p.end()); } 345 inline const_iterator constEnd() const noexcept { return reinterpret_cast<Node *>(p.end()); } 346 reverse_iterator rbegin() { return reverse_iterator(end()); } 347 reverse_iterator rend() { return reverse_iterator(begin()); } 348 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } 349 const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } 350 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } 351 const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } 352 iterator insert(iterator before, const T &t); 353 iterator erase(iterator pos); 354 iterator erase(iterator first, iterator last); 355 356 // more Qt 357 typedef iterator Iterator; 358 typedef const_iterator ConstIterator; 359 inline int count() const { return p.size(); } 360 inline int length() const { return p.size(); } // Same as count() 361 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } 362 inline const T& constFirst() const { return first(); } 363 inline const T& first() const { Q_ASSERT(!isEmpty()); return at(0); } 364 T& last() { Q_ASSERT(!isEmpty()); return *(--end()); } 365 const T& last() const { Q_ASSERT(!isEmpty()); return at(count() - 1); } 366 inline const T& constLast() const { return last(); } 367 inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(begin()); } 368 inline void removeLast() { Q_ASSERT(!isEmpty()); erase(--end()); } 369 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } 370 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } 371 QList<T> mid(int pos, int length = -1) const; 372 373 T value(int i) const; 374 T value(int i, const T &defaultValue) const; 375 376 // stl compatibility 377 inline void push_back(const T &t) { append(t); } 378 inline void push_front(const T &t) { prepend(t); } 379 inline T& front() { return first(); } 380 inline const T& front() const { return first(); } 381 inline T& back() { return last(); } 382 inline const T& back() const { return last(); } 383 inline void pop_front() { removeFirst(); } 384 inline void pop_back() { removeLast(); } 385 inline bool empty() const { return isEmpty(); } 386 typedef int size_type; 387 typedef T value_type; 388 typedef value_type *pointer; 389 typedef const value_type *const_pointer; 390 typedef value_type &reference; 391 typedef const value_type &const_reference; 392 // ### Qt6: use int 393 typedef qptrdiff difference_type; 394 395 // comfort 396 QList<T> &operator+=(const QList<T> &l); 397 inline QList<T> operator+(const QList<T> &l) const 398 { QList n = *this; n += l; return n; } 399 inline QList<T> &operator+=(const T &t) 400 { append(t); return *this; } 401 inline QList<T> &operator<< (const T &t) 402 { append(t); return *this; } 403 inline QList<T> &operator<<(const QList<T> &l) 404 { *this += l; return *this; } 405 406 static QList<T> fromVector(const QVector<T> &vector); 407 QVector<T> toVector() const; 408 409 #if QT_DEPRECATED_SINCE(5, 14) && QT_VERSION < QT_VERSION_CHECK(6,0,0) 410 QT_DEPRECATED_VERSION_X_5_14("Use QList<T>(set.begin(), set.end()) instead.") 411 static QList<T> fromSet(const QSet<T> &set); 412 QT_DEPRECATED_VERSION_X_5_14("Use QSet<T>(list.begin(), list.end()) instead.") 413 QSet<T> toSet() const; 414 415 QT_DEPRECATED_VERSION_X_5_14("Use QList<T>(list.begin(), list.end()) instead.") 416 static inline QList<T> fromStdList(const std::list<T> &list) 417 { return QList<T>(list.begin(), list.end()); } 418 QT_DEPRECATED_VERSION_X_5_14("Use std::list<T>(list.begin(), list.end()) instead.") 419 inline std::list<T> toStdList() const 420 { return std::list<T>(begin(), end()); } 421 #endif 422 423 private: 424 Node *detach_helper_grow(int i, int n); 425 void detach_helper(int alloc); 426 void detach_helper(); 427 void dealloc(QListData::Data *d); 428 429 void node_construct(Node *n, const T &t); 430 void node_destruct(Node *n); 431 void node_copy(Node *from, Node *to, Node *src); 432 void node_destruct(Node *from, Node *to); 433 434 bool isValidIterator(const iterator &i) const noexcept 435 { 436 const std::less<const Node *> less = {}; 437 return !less(i.i, cbegin().i) && !less(cend().i, i.i); 438 } 439 440 private: 441 inline bool op_eq_impl(const QList &other, QListData::NotArrayCompatibleLayout) const; 442 inline bool op_eq_impl(const QList &other, QListData::ArrayCompatibleLayout) const; 443 inline bool contains_impl(const T &, QListData::NotArrayCompatibleLayout) const; 444 inline bool contains_impl(const T &, QListData::ArrayCompatibleLayout) const; 445 inline int count_impl(const T &, QListData::NotArrayCompatibleLayout) const; 446 inline int count_impl(const T &, QListData::ArrayCompatibleLayout) const; 447 }; 448 449 #if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606 450 template <typename InputIterator, 451 typename ValueType = typename std::iterator_traits<InputIterator>::value_type, 452 QtPrivate::IfIsInputIterator<InputIterator> = true> 453 QList(InputIterator, InputIterator) -> QList<ValueType>; 454 #endif 455 456 #if defined(Q_CC_BOR) 457 template <typename T> 458 Q_INLINE_TEMPLATE T &QList<T>::Node::t() 459 { return QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic ? *(T*)v:*(T*)this; } 460 #endif 461 462 template <typename T> 463 Q_INLINE_TEMPLATE void QList<T>::node_construct(Node *n, const T &t) 464 { 465 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) n->v = new T(t); 466 else if (QTypeInfo<T>::isComplex) new (n) T(t); 467 #if (defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__IBMCPP__)) && !defined(__OPTIMIZE__) 468 // This violates pointer aliasing rules, but it is known to be safe (and silent) 469 // in unoptimized GCC builds (-fno-strict-aliasing). The other compilers which 470 // set the same define are assumed to be safe. 471 else *reinterpret_cast<T*>(n) = t; 472 #else 473 // This is always safe, but penaltizes unoptimized builds a lot. 474 else ::memcpy(n, static_cast<const void *>(&t), sizeof(T)); 475 #endif 476 } 477 478 template <typename T> 479 Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *n) 480 { 481 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) delete reinterpret_cast<T*>(n->v); 482 else if (QTypeInfo<T>::isComplex) reinterpret_cast<T*>(n)->~T(); 483 } 484 485 template <typename T> 486 Q_INLINE_TEMPLATE void QList<T>::node_copy(Node *from, Node *to, Node *src) 487 { 488 Node *current = from; 489 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { 490 QT_TRY { 491 while(current != to) { 492 current->v = new T(*reinterpret_cast<T*>(src->v)); 493 ++current; 494 ++src; 495 } 496 } QT_CATCH(...) { 497 while (current-- != from) 498 delete reinterpret_cast<T*>(current->v); 499 QT_RETHROW; 500 } 501 502 } else if (QTypeInfo<T>::isComplex) { 503 QT_TRY { 504 while(current != to) { 505 new (current) T(*reinterpret_cast<T*>(src)); 506 ++current; 507 ++src; 508 } 509 } QT_CATCH(...) { 510 while (current-- != from) 511 (reinterpret_cast<T*>(current))->~T(); 512 QT_RETHROW; 513 } 514 } else { 515 if (src != from && to - from > 0) 516 memcpy(from, src, (to - from) * sizeof(Node)); 517 } 518 } 519 520 template <typename T> 521 Q_INLINE_TEMPLATE void QList<T>::node_destruct(Node *from, Node *to) 522 { 523 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) 524 while(from != to) --to, delete reinterpret_cast<T*>(to->v); 525 else if (QTypeInfo<T>::isComplex) 526 while (from != to) --to, reinterpret_cast<T*>(to)->~T(); 527 } 528 529 template <typename T> 530 Q_INLINE_TEMPLATE QList<T> &QList<T>::operator=(const QList<T> &l) 531 { 532 if (d != l.d) { 533 QList<T> tmp(l); 534 tmp.swap(*this); 535 } 536 return *this; 537 } 538 template <typename T> 539 inline typename QList<T>::iterator QList<T>::insert(iterator before, const T &t) 540 { 541 Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid"); 542 543 int iBefore = int(before.i - reinterpret_cast<Node *>(p.begin())); 544 Node *n = nullptr; 545 if (d->ref.isShared()) 546 n = detach_helper_grow(iBefore, 1); 547 else 548 n = reinterpret_cast<Node *>(p.insert(iBefore)); 549 QT_TRY { 550 node_construct(n, t); 551 } QT_CATCH(...) { 552 p.remove(iBefore); 553 QT_RETHROW; 554 } 555 return n; 556 } 557 template <typename T> 558 inline typename QList<T>::iterator QList<T>::erase(iterator it) 559 { 560 Q_ASSERT_X(isValidIterator(it), "QList::erase", "The specified iterator argument 'it' is invalid"); 561 if (d->ref.isShared()) { 562 int offset = int(it.i - reinterpret_cast<Node *>(p.begin())); 563 it = begin(); // implies detach() 564 it += offset; 565 } 566 node_destruct(it.i); 567 return reinterpret_cast<Node *>(p.erase(reinterpret_cast<void**>(it.i))); 568 } 569 template <typename T> 570 inline const T &QList<T>::at(int i) const 571 { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::at", "index out of range"); 572 return reinterpret_cast<Node *>(p.at(i))->t(); } 573 template <typename T> 574 inline const T &QList<T>::operator[](int i) const 575 { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range"); 576 return reinterpret_cast<Node *>(p.at(i))->t(); } 577 template <typename T> 578 inline T &QList<T>::operator[](int i) 579 { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::operator[]", "index out of range"); 580 detach(); return reinterpret_cast<Node *>(p.at(i))->t(); } 581 template <typename T> 582 inline void QList<T>::removeAt(int i) 583 { 584 #if !QT_DEPRECATED_SINCE(5, 15) 585 Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::removeAt", "index out of range"); 586 #endif 587 if (i < 0 || i >= p.size()) { 588 #if !defined(QT_NO_DEBUG) 589 qWarning("QList::removeAt(): Index out of range."); 590 #endif 591 return; 592 } 593 detach(); 594 node_destruct(reinterpret_cast<Node *>(p.at(i))); p.remove(i); 595 } 596 template <typename T> 597 inline T QList<T>::takeAt(int i) 598 { Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::take", "index out of range"); 599 detach(); Node *n = reinterpret_cast<Node *>(p.at(i)); T t = std::move(n->t()); node_destruct(n); 600 p.remove(i); return t; } 601 template <typename T> 602 inline T QList<T>::takeFirst() 603 { T t = std::move(first()); removeFirst(); return t; } 604 template <typename T> 605 inline T QList<T>::takeLast() 606 { T t = std::move(last()); removeLast(); return t; } 607 608 template <typename T> 609 Q_OUTOFLINE_TEMPLATE void QList<T>::reserve(int alloc) 610 { 611 if (d->alloc < alloc) { 612 if (d->ref.isShared()) 613 detach_helper(alloc); 614 else 615 p.realloc(alloc); 616 } 617 } 618 619 template <typename T> 620 Q_OUTOFLINE_TEMPLATE void QList<T>::append(const T &t) 621 { 622 if (d->ref.isShared()) { 623 Node *n = detach_helper_grow(INT_MAX, 1); 624 QT_TRY { 625 node_construct(n, t); 626 } QT_CATCH(...) { 627 --d->end; 628 QT_RETHROW; 629 } 630 } else { 631 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { 632 Node *n = reinterpret_cast<Node *>(p.append()); 633 QT_TRY { 634 node_construct(n, t); 635 } QT_CATCH(...) { 636 --d->end; 637 QT_RETHROW; 638 } 639 } else { 640 Node *n, copy; 641 node_construct(©, t); // t might be a reference to an object in the array 642 QT_TRY { 643 n = reinterpret_cast<Node *>(p.append());; 644 } QT_CATCH(...) { 645 node_destruct(©); 646 QT_RETHROW; 647 } 648 *n = copy; 649 } 650 } 651 } 652 653 template <typename T> 654 inline void QList<T>::prepend(const T &t) 655 { 656 if (d->ref.isShared()) { 657 Node *n = detach_helper_grow(0, 1); 658 QT_TRY { 659 node_construct(n, t); 660 } QT_CATCH(...) { 661 ++d->begin; 662 QT_RETHROW; 663 } 664 } else { 665 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { 666 Node *n = reinterpret_cast<Node *>(p.prepend()); 667 QT_TRY { 668 node_construct(n, t); 669 } QT_CATCH(...) { 670 ++d->begin; 671 QT_RETHROW; 672 } 673 } else { 674 Node *n, copy; 675 node_construct(©, t); // t might be a reference to an object in the array 676 QT_TRY { 677 n = reinterpret_cast<Node *>(p.prepend());; 678 } QT_CATCH(...) { 679 node_destruct(©); 680 QT_RETHROW; 681 } 682 *n = copy; 683 } 684 } 685 } 686 687 template <typename T> 688 inline void QList<T>::insert(int i, const T &t) 689 { 690 #if !QT_DEPRECATED_SINCE(5, 15) 691 Q_ASSERT_X(i >= 0 && i <= p.size(), "QList<T>::insert", "index out of range"); 692 #elif !defined(QT_NO_DEBUG) 693 if (i < 0 || i > p.size()) 694 qWarning("QList::insert(): Index out of range."); 695 #endif 696 if (d->ref.isShared()) { 697 Node *n = detach_helper_grow(i, 1); 698 QT_TRY { 699 node_construct(n, t); 700 } QT_CATCH(...) { 701 p.remove(i); 702 QT_RETHROW; 703 } 704 } else { 705 if (QTypeInfo<T>::isLarge || QTypeInfo<T>::isStatic) { 706 Node *n = reinterpret_cast<Node *>(p.insert(i)); 707 QT_TRY { 708 node_construct(n, t); 709 } QT_CATCH(...) { 710 p.remove(i); 711 QT_RETHROW; 712 } 713 } else { 714 Node *n, copy; 715 node_construct(©, t); // t might be a reference to an object in the array 716 QT_TRY { 717 n = reinterpret_cast<Node *>(p.insert(i));; 718 } QT_CATCH(...) { 719 node_destruct(©); 720 QT_RETHROW; 721 } 722 *n = copy; 723 } 724 } 725 } 726 727 template <typename T> 728 inline void QList<T>::replace(int i, const T &t) 729 { 730 Q_ASSERT_X(i >= 0 && i < p.size(), "QList<T>::replace", "index out of range"); 731 detach(); 732 reinterpret_cast<Node *>(p.at(i))->t() = t; 733 } 734 735 template <typename T> 736 inline void QList<T>::swapItemsAt(int i, int j) 737 { 738 Q_ASSERT_X(i >= 0 && i < p.size() && j >= 0 && j < p.size(), 739 "QList<T>::swap", "index out of range"); 740 detach(); 741 qSwap(d->array[d->begin + i], d->array[d->begin + j]); 742 } 743 744 template <typename T> 745 inline void QList<T>::move(int from, int to) 746 { 747 Q_ASSERT_X(from >= 0 && from < p.size() && to >= 0 && to < p.size(), 748 "QList<T>::move", "index out of range"); 749 detach(); 750 p.move(from, to); 751 } 752 753 template<typename T> 754 Q_OUTOFLINE_TEMPLATE QList<T> QList<T>::mid(int pos, int alength) const 755 { 756 using namespace QtPrivate; 757 switch (QContainerImplHelper::mid(size(), &pos, &alength)) { 758 case QContainerImplHelper::Null: 759 case QContainerImplHelper::Empty: 760 return QList<T>(); 761 case QContainerImplHelper::Full: 762 return *this; 763 case QContainerImplHelper::Subset: 764 break; 765 } 766 767 QList<T> cpy; 768 if (alength <= 0) 769 return cpy; 770 cpy.reserve(alength); 771 cpy.d->end = alength; 772 QT_TRY { 773 cpy.node_copy(reinterpret_cast<Node *>(cpy.p.begin()), 774 reinterpret_cast<Node *>(cpy.p.end()), 775 reinterpret_cast<Node *>(p.begin() + pos)); 776 } QT_CATCH(...) { 777 // restore the old end 778 cpy.d->end = 0; 779 QT_RETHROW; 780 } 781 return cpy; 782 } 783 784 template<typename T> 785 Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i) const 786 { 787 if (i < 0 || i >= p.size()) { 788 return T(); 789 } 790 return reinterpret_cast<Node *>(p.at(i))->t(); 791 } 792 793 template<typename T> 794 Q_OUTOFLINE_TEMPLATE T QList<T>::value(int i, const T& defaultValue) const 795 { 796 return ((i < 0 || i >= p.size()) ? defaultValue : reinterpret_cast<Node *>(p.at(i))->t()); 797 } 798 799 template <typename T> 800 Q_OUTOFLINE_TEMPLATE typename QList<T>::Node *QList<T>::detach_helper_grow(int i, int c) 801 { 802 Node *n = reinterpret_cast<Node *>(p.begin()); 803 QListData::Data *x = p.detach_grow(&i, c); 804 QT_TRY { 805 node_copy(reinterpret_cast<Node *>(p.begin()), 806 reinterpret_cast<Node *>(p.begin() + i), n); 807 } QT_CATCH(...) { 808 p.dispose(); 809 d = x; 810 QT_RETHROW; 811 } 812 QT_TRY { 813 node_copy(reinterpret_cast<Node *>(p.begin() + i + c), 814 reinterpret_cast<Node *>(p.end()), n + i); 815 } QT_CATCH(...) { 816 node_destruct(reinterpret_cast<Node *>(p.begin()), 817 reinterpret_cast<Node *>(p.begin() + i)); 818 p.dispose(); 819 d = x; 820 QT_RETHROW; 821 } 822 823 if (!x->ref.deref()) 824 dealloc(x); 825 826 return reinterpret_cast<Node *>(p.begin() + i); 827 } 828 829 template <typename T> 830 Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper(int alloc) 831 { 832 Node *n = reinterpret_cast<Node *>(p.begin()); 833 QListData::Data *x = p.detach(alloc); 834 QT_TRY { 835 node_copy(reinterpret_cast<Node *>(p.begin()), reinterpret_cast<Node *>(p.end()), n); 836 } QT_CATCH(...) { 837 p.dispose(); 838 d = x; 839 QT_RETHROW; 840 } 841 842 if (!x->ref.deref()) 843 dealloc(x); 844 } 845 846 template <typename T> 847 Q_OUTOFLINE_TEMPLATE void QList<T>::detach_helper() 848 { 849 detach_helper(d->alloc); 850 } 851 852 template <typename T> 853 Q_OUTOFLINE_TEMPLATE QList<T>::QList(const QList<T> &l) 854 : QListSpecialMethods<T>(l), d(l.d) 855 { 856 if (!d->ref.ref()) { 857 p.detach(d->alloc); 858 859 QT_TRY { 860 node_copy(reinterpret_cast<Node *>(p.begin()), 861 reinterpret_cast<Node *>(p.end()), 862 reinterpret_cast<Node *>(l.p.begin())); 863 } QT_CATCH(...) { 864 QListData::dispose(d); 865 QT_RETHROW; 866 } 867 } 868 } 869 870 template <typename T> 871 Q_OUTOFLINE_TEMPLATE QList<T>::~QList() 872 { 873 if (!d->ref.deref()) 874 dealloc(d); 875 } 876 877 template <typename T> 878 template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>> 879 QList<T>::QList(InputIterator first, InputIterator last) 880 : QList() 881 { 882 QtPrivate::reserveIfForwardIterator(this, first, last); 883 std::copy(first, last, std::back_inserter(*this)); 884 } 885 886 template <typename T> 887 Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const 888 { 889 if (d == l.d) 890 return true; 891 if (p.size() != l.p.size()) 892 return false; 893 return this->op_eq_impl(l, MemoryLayout()); 894 } 895 896 template <typename T> 897 inline bool QList<T>::op_eq_impl(const QList &l, QListData::NotArrayCompatibleLayout) const 898 { 899 Node *i = reinterpret_cast<Node *>(p.begin()); 900 Node *e = reinterpret_cast<Node *>(p.end()); 901 Node *li = reinterpret_cast<Node *>(l.p.begin()); 902 for (; i != e; ++i, ++li) { 903 if (!(i->t() == li->t())) 904 return false; 905 } 906 return true; 907 } 908 909 template <typename T> 910 inline bool QList<T>::op_eq_impl(const QList &l, QListData::ArrayCompatibleLayout) const 911 { 912 const T *lb = reinterpret_cast<const T*>(l.p.begin()); 913 const T *b = reinterpret_cast<const T*>(p.begin()); 914 const T *e = reinterpret_cast<const T*>(p.end()); 915 return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(lb, l.p.size())); 916 } 917 918 template <typename T> 919 Q_OUTOFLINE_TEMPLATE void QList<T>::dealloc(QListData::Data *data) 920 { 921 node_destruct(reinterpret_cast<Node *>(data->array + data->begin), 922 reinterpret_cast<Node *>(data->array + data->end)); 923 QListData::dispose(data); 924 } 925 926 927 template <typename T> 928 Q_OUTOFLINE_TEMPLATE void QList<T>::clear() 929 { 930 *this = QList<T>(); 931 } 932 933 template <typename T> 934 Q_OUTOFLINE_TEMPLATE int QList<T>::removeAll(const T &_t) 935 { 936 int index = indexOf(_t); 937 if (index == -1) 938 return 0; 939 940 const T t = _t; 941 detach(); 942 943 Node *i = reinterpret_cast<Node *>(p.at(index)); 944 Node *e = reinterpret_cast<Node *>(p.end()); 945 Node *n = i; 946 node_destruct(i); 947 while (++i != e) { 948 if (i->t() == t) 949 node_destruct(i); 950 else 951 *n++ = *i; 952 } 953 954 int removedCount = int(e - n); 955 d->end -= removedCount; 956 return removedCount; 957 } 958 959 template <typename T> 960 Q_OUTOFLINE_TEMPLATE bool QList<T>::removeOne(const T &_t) 961 { 962 int index = indexOf(_t); 963 if (index != -1) { 964 removeAt(index); 965 return true; 966 } 967 return false; 968 } 969 970 template <typename T> 971 Q_OUTOFLINE_TEMPLATE typename QList<T>::iterator QList<T>::erase(typename QList<T>::iterator afirst, 972 typename QList<T>::iterator alast) 973 { 974 Q_ASSERT_X(isValidIterator(afirst), "QList::erase", "The specified iterator argument 'afirst' is invalid"); 975 Q_ASSERT_X(isValidIterator(alast), "QList::erase", "The specified iterator argument 'alast' is invalid"); 976 977 if (d->ref.isShared()) { 978 // ### A block is erased and a detach is needed. We should shrink and only copy relevant items. 979 int offsetfirst = int(afirst.i - reinterpret_cast<Node *>(p.begin())); 980 int offsetlast = int(alast.i - reinterpret_cast<Node *>(p.begin())); 981 afirst = begin(); // implies detach() 982 alast = afirst; 983 afirst += offsetfirst; 984 alast += offsetlast; 985 } 986 987 for (Node *n = afirst.i; n < alast.i; ++n) 988 node_destruct(n); 989 int idx = afirst - begin(); 990 p.remove(idx, alast - afirst); 991 return begin() + idx; 992 } 993 994 template <typename T> 995 Q_OUTOFLINE_TEMPLATE QList<T> &QList<T>::operator+=(const QList<T> &l) 996 { 997 if (!l.isEmpty()) { 998 if (d == &QListData::shared_null) { 999 *this = l; 1000 } else { 1001 Node *n = (d->ref.isShared()) 1002 ? detach_helper_grow(INT_MAX, l.size()) 1003 : reinterpret_cast<Node *>(p.append(l.p)); 1004 QT_TRY { 1005 node_copy(n, reinterpret_cast<Node *>(p.end()), 1006 reinterpret_cast<Node *>(l.p.begin())); 1007 } QT_CATCH(...) { 1008 // restore the old end 1009 d->end -= int(reinterpret_cast<Node *>(p.end()) - n); 1010 QT_RETHROW; 1011 } 1012 } 1013 } 1014 return *this; 1015 } 1016 1017 template <typename T> 1018 inline void QList<T>::append(const QList<T> &t) 1019 { 1020 *this += t; 1021 } 1022 1023 template <typename T> 1024 Q_OUTOFLINE_TEMPLATE int QList<T>::indexOf(const T &t, int from) const 1025 { 1026 return QtPrivate::indexOf<T, T>(*this, t, from); 1027 } 1028 1029 namespace QtPrivate 1030 { 1031 template <typename T, typename U> 1032 int indexOf(const QList<T> &list, const U &u, int from) 1033 { 1034 typedef typename QList<T>::Node Node; 1035 1036 if (from < 0) 1037 from = qMax(from + list.p.size(), 0); 1038 if (from < list.p.size()) { 1039 Node *n = reinterpret_cast<Node *>(list.p.at(from -1)); 1040 Node *e = reinterpret_cast<Node *>(list.p.end()); 1041 while (++n != e) 1042 if (n->t() == u) 1043 return int(n - reinterpret_cast<Node *>(list.p.begin())); 1044 } 1045 return -1; 1046 } 1047 } 1048 1049 template <typename T> 1050 Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const 1051 { 1052 return QtPrivate::lastIndexOf<T, T>(*this, t, from); 1053 } 1054 1055 namespace QtPrivate 1056 { 1057 template <typename T, typename U> 1058 int lastIndexOf(const QList<T> &list, const U &u, int from) 1059 { 1060 typedef typename QList<T>::Node Node; 1061 1062 if (from < 0) 1063 from += list.p.size(); 1064 else if (from >= list.p.size()) 1065 from = list.p.size()-1; 1066 if (from >= 0) { 1067 Node *b = reinterpret_cast<Node *>(list.p.begin()); 1068 Node *n = reinterpret_cast<Node *>(list.p.at(from + 1)); 1069 while (n-- != b) { 1070 if (n->t() == u) 1071 return int(n - b); 1072 } 1073 } 1074 return -1; 1075 } 1076 } 1077 1078 template <typename T> 1079 Q_OUTOFLINE_TEMPLATE bool QList<T>::contains(const T &t) const 1080 { 1081 return contains_impl(t, MemoryLayout()); 1082 } 1083 1084 template <typename T> 1085 inline bool QList<T>::contains_impl(const T &t, QListData::NotArrayCompatibleLayout) const 1086 { 1087 Node *e = reinterpret_cast<Node *>(p.end()); 1088 Node *i = reinterpret_cast<Node *>(p.begin()); 1089 for (; i != e; ++i) 1090 if (i->t() == t) 1091 return true; 1092 return false; 1093 } 1094 1095 template <typename T> 1096 inline bool QList<T>::contains_impl(const T &t, QListData::ArrayCompatibleLayout) const 1097 { 1098 const T *b = reinterpret_cast<const T*>(p.begin()); 1099 const T *e = reinterpret_cast<const T*>(p.end()); 1100 return std::find(b, e, t) != e; 1101 } 1102 1103 template <typename T> 1104 Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const 1105 { 1106 return this->count_impl(t, MemoryLayout()); 1107 } 1108 1109 template <typename T> 1110 inline int QList<T>::count_impl(const T &t, QListData::NotArrayCompatibleLayout) const 1111 { 1112 int c = 0; 1113 Node *e = reinterpret_cast<Node *>(p.end()); 1114 Node *i = reinterpret_cast<Node *>(p.begin()); 1115 for (; i != e; ++i) 1116 if (i->t() == t) 1117 ++c; 1118 return c; 1119 } 1120 1121 template <typename T> 1122 inline int QList<T>::count_impl(const T &t, QListData::ArrayCompatibleLayout) const 1123 { 1124 return int(std::count(reinterpret_cast<const T*>(p.begin()), 1125 reinterpret_cast<const T*>(p.end()), 1126 t)); 1127 } 1128 1129 template <typename T> 1130 Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const 1131 { 1132 return QVector<T>(begin(), end()); 1133 } 1134 1135 template <typename T> 1136 QList<T> QList<T>::fromVector(const QVector<T> &vector) 1137 { 1138 return vector.toList(); 1139 } 1140 1141 template <typename T> 1142 Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const 1143 { 1144 return QList<T>(begin(), end()); 1145 } 1146 1147 template <typename T> 1148 QVector<T> QVector<T>::fromList(const QList<T> &list) 1149 { 1150 return list.toVector(); 1151 } 1152 1153 Q_DECLARE_SEQUENTIAL_ITERATOR(List) 1154 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List) 1155 1156 template <typename T> 1157 uint qHash(const QList<T> &key, uint seed = 0) 1158 noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed))) 1159 { 1160 return qHashRange(key.cbegin(), key.cend(), seed); 1161 } 1162 1163 template <typename T> 1164 bool operator<(const QList<T> &lhs, const QList<T> &rhs) 1165 noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(), 1166 rhs.begin(), rhs.end()))) 1167 { 1168 return std::lexicographical_compare(lhs.begin(), lhs.end(), 1169 rhs.begin(), rhs.end()); 1170 } 1171 1172 template <typename T> 1173 inline bool operator>(const QList<T> &lhs, const QList<T> &rhs) 1174 noexcept(noexcept(lhs < rhs)) 1175 { 1176 return rhs < lhs; 1177 } 1178 1179 template <typename T> 1180 inline bool operator<=(const QList<T> &lhs, const QList<T> &rhs) 1181 noexcept(noexcept(lhs < rhs)) 1182 { 1183 return !(lhs > rhs); 1184 } 1185 1186 template <typename T> 1187 inline bool operator>=(const QList<T> &lhs, const QList<T> &rhs) 1188 noexcept(noexcept(lhs < rhs)) 1189 { 1190 return !(lhs < rhs); 1191 } 1192 1193 QT_END_NAMESPACE 1194 1195 #include <QtCore/qbytearraylist.h> 1196 #include <QtCore/qstringlist.h> 1197 1198 #ifdef Q_CC_MSVC 1199 #pragma warning( pop ) 1200 #endif 1201 1202 #endif // QLIST_H 1203