get rid of our LayerVector implementation

we now use SortedVector<> with a special compare implementation.

Change-Id: I910459cf3b3c8993b55ad0786a8c348369262de5

4 files changed, 22 insertions, 113 deletions

diff --git a/services/surfaceflinger/LayerBase.cpp b/services/surfaceflinger/LayerBase.cpp
index d5aa53f..75a9db5 100644
--- a/services/surfaceflinger/LayerBase.cpp
+++ b/services/surfaceflinger/LayerBase.cpp
@@ -39,8 +39,11 @@ namespace android {
 
 // ---------------------------------------------------------------------------
 
+int32_t LayerBase::sSequence = 1;
+
 LayerBase::LayerBase(SurfaceFlinger* flinger, DisplayID display)
     : dpy(display), contentDirty(false),
+      sequence(uint32_t(android_atomic_inc(&sSequence))),
       mFlinger(flinger),
       mNeedsFiltering(false),
       mOrientation(0),
diff --git a/services/surfaceflinger/LayerBase.h b/services/surfaceflinger/LayerBase.h
index 4288cf7..22bf857 100644
--- a/services/surfaceflinger/LayerBase.h
+++ b/services/surfaceflinger/LayerBase.h
@@ -53,6 +53,8 @@ class Texture;
 
 class LayerBase : public RefBase
 {
+    static int32_t sSequence;
+
 public:
             LayerBase(SurfaceFlinger* flinger, DisplayID display);
 
@@ -61,6 +63,7 @@ public:
             Region      visibleRegionScreen;
             Region      transparentRegionScreen;
             Region      coveredRegionScreen;
+            int32_t     sequence;
             
             struct State {
                 uint32_t        w;
@@ -210,12 +213,6 @@ public:
     inline  const State&    currentState() const    { return mCurrentState; }
     inline  State&          currentState()          { return mCurrentState; }
 
-    static int compareCurrentStateZ(
-            sp<LayerBase> const * layerA,
-            sp<LayerBase> const * layerB) {
-        return layerA[0]->currentState().z - layerB[0]->currentState().z;
-    }
-
     int32_t  getOrientation() const { return mOrientation; }
     int  tx() const             { return mLeft; }
     int  ty() const             { return mTop; }
diff --git a/services/surfaceflinger/SurfaceFlinger.cpp b/services/surfaceflinger/SurfaceFlinger.cpp
index c630a0d..637ae48 100644
--- a/services/surfaceflinger/SurfaceFlinger.cpp
+++ b/services/surfaceflinger/SurfaceFlinger.cpp
@@ -65,95 +65,6 @@
 namespace android {
 // ---------------------------------------------------------------------------
 
-SurfaceFlinger::LayerVector::LayerVector(const SurfaceFlinger::LayerVector& rhs)
-    : lookup(rhs.lookup), layers(rhs.layers)
-{
-}
-
-ssize_t SurfaceFlinger::LayerVector::indexOf(
-        const sp<LayerBase>& key, size_t guess) const
-{
-    if (guess<size() && lookup.keyAt(guess) == key)
-        return guess;
-    const ssize_t i = lookup.indexOfKey(key);
-    if (i>=0) {
-        const size_t idx = lookup.valueAt(i);
-        LOGE_IF(layers[idx]!=key,
-            "LayerVector[%p]: layers[%d]=%p, key=%p",
-            this, int(idx), layers[idx].get(), key.get());
-        return idx;
-    }
-    return i;
-}
-
-ssize_t SurfaceFlinger::LayerVector::add(
-        const sp<LayerBase>& layer,
-        Vector< sp<LayerBase> >::compar_t cmp)
-{
-    size_t count = layers.size();
-    ssize_t l = 0;
-    ssize_t h = count-1;
-    ssize_t mid;
-    sp<LayerBase> const* a = layers.array();
-    while (l <= h) {
-        mid = l + (h - l)/2;
-        const int c = cmp(a+mid, &layer);
-        if (c == 0)     { l = mid; break; }
-        else if (c<0)   { l = mid+1; }
-        else            { h = mid-1; }
-    }
-    size_t order = l;
-    while (order<count && !cmp(&layer, a+order)) {
-        order++;
-    }
-    count = lookup.size();
-    for (size_t i=0 ; i<count ; i++) {
-        if (lookup.valueAt(i) >= order) {
-            lookup.editValueAt(i)++;
-        }
-    }
-    layers.insertAt(layer, order);
-    lookup.add(layer, order);
-    return order;
-}
-
-ssize_t SurfaceFlinger::LayerVector::remove(const sp<LayerBase>& layer)
-{
-    const ssize_t keyIndex = lookup.indexOfKey(layer);
-    if (keyIndex >= 0) {
-        const size_t index = lookup.valueAt(keyIndex);
-        LOGE_IF(layers[index]!=layer,
-                "LayerVector[%p]: layers[%u]=%p, layer=%p",
-                this, int(index), layers[index].get(), layer.get());
-        layers.removeItemsAt(index);
-        lookup.removeItemsAt(keyIndex);
-        const size_t count = lookup.size();
-        for (size_t i=0 ; i<count ; i++) {
-            if (lookup.valueAt(i) >= size_t(index)) {
-                lookup.editValueAt(i)--;
-            }
-        }
-        return index;
-    }
-    return NAME_NOT_FOUND;
-}
-
-ssize_t SurfaceFlinger::LayerVector::reorder(
-        const sp<LayerBase>& layer,
-        Vector< sp<LayerBase> >::compar_t cmp)
-{
-    // XXX: it's a little lame. but oh well...
-    ssize_t err = remove(layer);
-    if (err >=0)
-        err = add(layer, cmp);
-    return err;
-}
-
-// ---------------------------------------------------------------------------
-#if 0
-#pragma mark -
-#endif
-
 SurfaceFlinger::SurfaceFlinger()
     :   BnSurfaceComposer(), Thread(false),
         mTransactionFlags(0),
@@ -1045,8 +956,7 @@ status_t SurfaceFlinger::addLayer(const sp<LayerBase>& layer)
 
 status_t SurfaceFlinger::addLayer_l(const sp<LayerBase>& layer)
 {
-    ssize_t i = mCurrentState.layersSortedByZ.add(
-                layer, &LayerBase::compareCurrentStateZ);
+    ssize_t i = mCurrentState.layersSortedByZ.add(layer);
     return (i < 0) ? status_t(i) : status_t(NO_ERROR);
 }
 
@@ -1388,9 +1298,10 @@ status_t SurfaceFlinger::setClientState(
                     flags |= eTraversalNeeded;
             }
             if (what & eLayerChanged) {
+                ssize_t idx = mCurrentState.layersSortedByZ.indexOf(layer);
                 if (layer->setLayer(s.z)) {
-                    mCurrentState.layersSortedByZ.reorder(
-                            layer, &Layer::compareCurrentStateZ);
+                    mCurrentState.layersSortedByZ.removeAt(idx);
+                    mCurrentState.layersSortedByZ.add(layer);
                     // we need traversal (state changed)
                     // AND transaction (list changed)
                     flags |= eTransactionNeeded|eTraversalNeeded;
diff --git a/services/surfaceflinger/SurfaceFlinger.h b/services/surfaceflinger/SurfaceFlinger.h
index c8b9512..8ecfc01 100644
--- a/services/surfaceflinger/SurfaceFlinger.h
+++ b/services/surfaceflinger/SurfaceFlinger.h
@@ -243,21 +243,19 @@ private:
     status_t setClientState(const sp<Client>& client,
             int32_t count, const layer_state_t* states);
 
-
-    class LayerVector {
+    class LayerVector : public SortedVector< sp<LayerBase> > {
     public:
-        inline              LayerVector() { }
-                            LayerVector(const LayerVector&);
-        inline size_t       size() const { return layers.size(); }
-        inline sp<LayerBase> const* array() const { return layers.array(); }
-        ssize_t             add(const sp<LayerBase>&, Vector< sp<LayerBase> >::compar_t);
-        ssize_t             remove(const sp<LayerBase>&);
-        ssize_t             reorder(const sp<LayerBase>&, Vector< sp<LayerBase> >::compar_t);
-        ssize_t             indexOf(const sp<LayerBase>& key, size_t guess=0) const;
-        inline sp<LayerBase> operator [] (size_t i) const { return layers[i]; }
-    private:
-        KeyedVector< sp<LayerBase> , size_t> lookup;
-        Vector< sp<LayerBase> >              layers;
+        LayerVector() { }
+        LayerVector(const LayerVector& rhs) : SortedVector< sp<LayerBase> >(rhs) { }
+        virtual int do_compare(const void* lhs, const void* rhs) const {
+            const sp<LayerBase>& l(*reinterpret_cast<const sp<LayerBase>*>(lhs));
+            const sp<LayerBase>& r(*reinterpret_cast<const sp<LayerBase>*>(rhs));
+            // sort layers by Z order
+            uint32_t lz = l->currentState().z;
+            uint32_t rz = r->currentState().z;
+            // then by sequence, so we get a stable ordering
+            return (lz != rz) ? (lz - rz) : (l->sequence - r->sequence);
+        }
     };
 
     struct State {