3 files changed, 80 insertions, 10 deletions

diff --git a/src/particles/qquickparticlesystem.cpp b/src/particles/qquickparticlesystem.cpp
index e9bd073133..f4c9121007 100644
--- a/src/particles/qquickparticlesystem.cpp
+++ b/src/particles/qquickparticlesystem.cpp
@@ -339,11 +339,11 @@ void QQuickParticleGroupData::setSize(int newSize)
         return;
     Q_ASSERT(newSize > m_size);//XXX allow shrinking
     data.resize(newSize);
+    freeList.resize(newSize);
     for (int i=m_size; i<newSize; i++) {
         data[i] = new QQuickParticleData;
         data[i]->groupId = index;
         data[i]->index = i;
-        reusableIndexes << i;
     }
     int delta = newSize - m_size;
     m_size = newSize;
@@ -362,16 +362,15 @@ void QQuickParticleGroupData::kill(QQuickParticleData* d)
     d->lifeSpan = 0;//Kill off
     foreach (QQuickParticlePainter* p, painters)
         p->reload(d);
-    reusableIndexes << d->index;
+    freeList.free(d->index);
 }
 
 QQuickParticleData* QQuickParticleGroupData::newDatum(bool respectsLimits)
 {
     //recycle();//Extra recycler round to be sure?
 
-    while (!reusableIndexes.empty()) {
-        int idx = *(reusableIndexes.begin());
-        reusableIndexes.remove(idx);
+    while (freeList.hasUnusedEntries()) {
+        int idx = freeList.alloc();
         if (data[idx]->stillAlive(m_system)) {// ### This means resurrection of 'dead' particles. Is that allowed?
             prepareRecycler(data[idx]);
             continue;
@@ -383,8 +382,9 @@ QQuickParticleData* QQuickParticleGroupData::newDatum(bool respectsLimits)
 
     int oldSize = m_size;
     setSize(oldSize + 10);//###+1,10%,+10? Choose something non-arbitrarily
-    reusableIndexes.remove(oldSize);
-    return data[oldSize];
+    int idx = freeList.alloc();
+    Q_ASSERT(idx == oldSize);
+    return data[idx];
 }
 
 bool QQuickParticleGroupData::recycle()
@@ -392,7 +392,7 @@ bool QQuickParticleGroupData::recycle()
     while (dataHeap.top() <= m_system->timeInt) {
         foreach (QQuickParticleData* datum, dataHeap.pop()) {
             if (!datum->stillAlive(m_system)) {
-                reusableIndexes << datum->index;
+                freeList.free(datum->index);
             } else {
                 prepareRecycler(datum); //ttl has been altered mid-way, put it back
             }
@@ -400,7 +400,7 @@ bool QQuickParticleGroupData::recycle()
     }
 
     //TODO: If the data is clear, gc (consider shrinking stack size)?
-    return reusableIndexes.count() == m_size;
+    return freeList.count() == 0;
 }
 
 void QQuickParticleGroupData::prepareRecycler(QQuickParticleData* d)
diff --git a/src/particles/qquickparticlesystem_p.h b/src/particles/qquickparticlesystem_p.h
index fcdd027a54..182fc6aed6 100644
--- a/src/particles/qquickparticlesystem_p.h
+++ b/src/particles/qquickparticlesystem_p.h
@@ -61,6 +61,7 @@
 #include <QAbstractAnimation>
 #include <QtQml/qqml.h>
 #include <private/qv8engine_p.h> //For QQmlV4Handle
+#include <private/qv4util_p.h>
 #include "qtquickparticlesglobal_p.h"
 
 QT_BEGIN_NAMESPACE
@@ -134,6 +135,65 @@ private:
 };
 
 class Q_QUICKPARTICLES_PRIVATE_EXPORT QQuickParticleGroupData {
+    class FreeList
+    {
+    public:
+        FreeList()
+            : firstUnused(UINT_MAX)
+            , allocated(0)
+        {}
+
+        void resize(int newSize)
+        {
+            Q_ASSERT(newSize >= 0);
+            int oldSize = isUnused.size();
+            isUnused.resize(newSize, true);
+            if (newSize > oldSize) {
+                if (firstUnused == UINT_MAX) {
+                    firstUnused = oldSize;
+                } else {
+                    firstUnused = std::min(firstUnused, unsigned(oldSize));
+                }
+            } else if (firstUnused >= unsigned(newSize)) {
+                firstUnused = UINT_MAX;
+            }
+        }
+
+        void free(int index)
+        {
+            isUnused.setBit(index);
+            firstUnused = std::min(firstUnused, unsigned(index));
+            --allocated;
+        }
+
+        int count() const
+        { return allocated; }
+
+        bool hasUnusedEntries() const
+        { return firstUnused != UINT_MAX; }
+
+        int alloc()
+        {
+            if (hasUnusedEntries()) {
+                int nextFree = firstUnused;
+                isUnused.clearBit(firstUnused);
+                firstUnused = isUnused.findNext(firstUnused, true, false);
+                if (firstUnused >= unsigned(isUnused.size())) {
+                    firstUnused = UINT_MAX;
+                }
+                ++allocated;
+                return nextFree;
+            } else {
+                return -1;
+            }
+        }
+
+    private:
+        QV4::BitVector isUnused;
+        unsigned firstUnused;
+        int allocated;
+    };
+
 public: // types
     typedef int ID;
     enum { InvalidID = -1, DefaultGroupID = 0 };
@@ -154,7 +214,7 @@ public:
 
     //TODO: Refactor particle data list out into a separate class
     QVector<QQuickParticleData*> data;
-    QSet<int> reusableIndexes;
+    FreeList freeList;
     QQuickParticleDataHeap dataHeap;
     bool recycle(); //Force recycling round, returns true if all indexes are now reusable
 
diff --git a/src/qml/jsruntime/qv4util_p.h b/src/qml/jsruntime/qv4util_p.h
index 132abd211e..59c12c5e46 100644
--- a/src/qml/jsruntime/qv4util_p.h
+++ b/src/qml/jsruntime/qv4util_p.h
@@ -102,6 +102,9 @@ public:
     void resize(int newSize)
     { bits.resize(newSize); }
 
+    void resize(int newSize, bool newValue)
+    { bits.resize(newSize, newValue); }
+
     void assign(int newSize, bool value)
     { bits.assign(newSize, value); }
 
@@ -159,6 +162,13 @@ public:
     void resize(int newSize)
     { bits.resize(newSize); }
 
+    void resize(int newSize, bool newValue)
+    {
+        int oldSize = bits.size();
+        bits.resize(newSize);
+        bits.fill(newValue, oldSize, bits.size());
+    }
+
     void assign(int newSize, bool value)
     {
         bits.resize(newSize);