1 files changed, 70 insertions, 0 deletions

diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 023dafb223..57e67d52d7 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -66,6 +66,14 @@ template <typename T> struct QListSpecialMethods { };
 template <> struct QListSpecialMethods<QByteArray>;
 
 struct Q_CORE_EXPORT QListData {
+    // tags for tag-dispatching of QList implementations,
+    // based on QList's three different memory layouts:
+    struct NotArrayCompatibleLayout {};
+    struct NotIndirectLayout {};
+    struct ArrayCompatibleLayout   : NotIndirectLayout {};                           // data laid out like a C array
+    struct InlineWithPaddingLayout : NotArrayCompatibleLayout, NotIndirectLayout {}; // data laid out like a C array with padding
+    struct IndirectLayout          : NotArrayCompatibleLayout {};                    // data allocated on the heap
+
     struct Data {
         QtPrivate::RefCount ref;
         int alloc, begin, end;
@@ -99,6 +107,17 @@ struct Q_CORE_EXPORT QListData {
 template <typename T>
 class QList : public QListSpecialMethods<T>
 {
+public:
+    struct MemoryLayout
+        : QtPrivate::if_<
+            QTypeInfo<T>::isStatic || QTypeInfo<T>::isLarge,
+            QListData::IndirectLayout,
+            typename QtPrivate::if_<
+                sizeof(T) == sizeof(void*),
+                QListData::ArrayCompatibleLayout,
+                QListData::InlineWithPaddingLayout
+             >::type>::type {};
+private:
     struct Node { void *v;
 #if defined(Q_CC_BOR)
         Q_INLINE_TEMPLATE T &t();
@@ -358,6 +377,14 @@ private:
     {
         return (constBegin().i <= i.i) && (i.i <= constEnd().i);
     }
+
+private:
+    inline bool op_eq_impl(const QList &other, QListData::NotArrayCompatibleLayout) const;
+    inline bool op_eq_impl(const QList &other, QListData::ArrayCompatibleLayout) const;
+    inline bool contains_impl(const T &, QListData::NotArrayCompatibleLayout) const;
+    inline bool contains_impl(const T &, QListData::ArrayCompatibleLayout) const;
+    inline int count_impl(const T &, QListData::NotArrayCompatibleLayout) const;
+    inline int count_impl(const T &, QListData::ArrayCompatibleLayout) const;
 };
 
 #if defined(Q_CC_BOR)
@@ -771,6 +798,12 @@ Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
         return true;
     if (p.size() != l.p.size())
         return false;
+    return this->op_eq_impl(l, MemoryLayout());
+}
+
+template <typename T>
+inline bool QList<T>::op_eq_impl(const QList &l, QListData::NotArrayCompatibleLayout) const
+{
     Node *i = reinterpret_cast<Node *>(p.begin());
     Node *e = reinterpret_cast<Node *>(p.end());
     Node *li = reinterpret_cast<Node *>(l.p.begin());
@@ -782,6 +815,15 @@ Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
 }
 
 template <typename T>
+inline bool QList<T>::op_eq_impl(const QList &l, QListData::ArrayCompatibleLayout) const
+{
+    const T *lb = reinterpret_cast<const T*>(l.p.begin());
+    const T *b  = reinterpret_cast<const T*>(p.begin());
+    const T *e  = reinterpret_cast<const T*>(p.end());
+    return std::equal(b, e, lb);
+}
+
+template <typename T>
 Q_OUTOFLINE_TEMPLATE void QList<T>::dealloc(QListData::Data *data)
 {
     node_destruct(reinterpret_cast<Node *>(data->array + data->begin),
@@ -922,6 +964,12 @@ Q_OUTOFLINE_TEMPLATE int QList<T>::lastIndexOf(const T &t, int from) const
 template <typename T>
 Q_OUTOFLINE_TEMPLATE bool QList<T>::contains(const T &t) const
 {
+    return contains_impl(t, MemoryLayout());
+}
+
+template <typename T>
+inline bool QList<T>::contains_impl(const T &t, QListData::NotArrayCompatibleLayout) const
+{
     Node *e = reinterpret_cast<Node *>(p.end());
     Node *i = reinterpret_cast<Node *>(p.begin());
     for (; i != e; ++i)
@@ -931,8 +979,22 @@ Q_OUTOFLINE_TEMPLATE bool QList<T>::contains(const T &t) const
 }
 
 template <typename T>
+inline bool QList<T>::contains_impl(const T &t, QListData::ArrayCompatibleLayout) const
+{
+    const T *b = reinterpret_cast<const T*>(p.begin());
+    const T *e = reinterpret_cast<const T*>(p.end());
+    return std::find(b, e, t) != e;
+}
+
+template <typename T>
 Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const
 {
+    return this->count_impl(t, MemoryLayout());
+}
+
+template <typename T>
+inline int QList<T>::count_impl(const T &t, QListData::NotArrayCompatibleLayout) const
+{
     int c = 0;
     Node *e = reinterpret_cast<Node *>(p.end());
     Node *i = reinterpret_cast<Node *>(p.begin());
@@ -942,6 +1004,14 @@ Q_OUTOFLINE_TEMPLATE int QList<T>::count(const T &t) const
     return c;
 }
 
+template <typename T>
+inline int QList<T>::count_impl(const T &t, QListData::ArrayCompatibleLayout) const
+{
+    return int(std::count(reinterpret_cast<const T*>(p.begin()),
+                          reinterpret_cast<const T*>(p.end()),
+                          t));
+}
+
 Q_DECLARE_SEQUENTIAL_ITERATOR(List)
 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List)