From 9eff0dd19d6507ec400f036dd27efe960e4e5f78 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?S=C3=A9rgio=20Martins?= <sergio.martins@kdab.com>
Date: Mon, 25 May 2015 18:32:35 +0100
Subject: QSet: Introduce intersects().

The pattern "mySet.intersect(other).isEmpty()" has been spotted in
the wild and in Qt codebase. intersects() is much cheaper because it
bails out as soon as we find one common item and doesn't do any
allocations.

[ChangeLog][QtCore][QSet] Added intersects().

Change-Id: I44a350dc4cdb9deb835a23eee99fc99d6ca24c82
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
---
 src/corelib/tools/qset.h | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

(limited to 'src/corelib/tools/qset.h')

diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index e4688711d6..5a9c75fe07 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -137,6 +137,7 @@ public:
         typedef QHash<T, QHashDummyValue> Hash;
         typename Hash::const_iterator i;
         friend class iterator;
+        friend class QSet<T>;
 
     public:
         typedef std::bidirectional_iterator_tag iterator_category;
@@ -191,6 +192,7 @@ public:
     inline const_iterator constFind(const T &value) const { return find(value); }
     QSet<T> &unite(const QSet<T> &other);
     QSet<T> &intersect(const QSet<T> &other);
+    bool intersects(const QSet<T> &other) const;
     QSet<T> &subtract(const QSet<T> &other);
 
     // STL compatibility
@@ -283,6 +285,34 @@ Q_INLINE_TEMPLATE QSet<T> &QSet<T>::intersect(const QSet<T> &other)
     return *this;
 }
 
+template <class T>
+Q_INLINE_TEMPLATE bool QSet<T>::intersects(const QSet<T> &other) const
+{
+    const bool otherIsBigger = other.size() > size();
+    const QSet &smallestSet = otherIsBigger ? *this : other;
+    const QSet &biggestSet = otherIsBigger ? other : *this;
+    const bool equalSeeds = q_hash.d->seed == other.q_hash.d->seed;
+    typename QSet::const_iterator i = smallestSet.cbegin();
+    typename QSet::const_iterator e = smallestSet.cend();
+
+    if (Q_LIKELY(equalSeeds)) {
+        // If seeds are equal we take the fast path so no hash is recalculated.
+        while (i != e) {
+            if (*biggestSet.q_hash.findNode(*i, i.i.i->h) != biggestSet.q_hash.e)
+                return true;
+            ++i;
+        }
+    } else {
+        while (i != e) {
+            if (biggestSet.contains(*i))
+                return true;
+            ++i;
+        }
+     }
+
+    return false;
+}
+
 template <class T>
 Q_INLINE_TEMPLATE QSet<T> &QSet<T>::subtract(const QSet<T> &other)
 {
-- 
cgit v1.2.3