Better cache for layers, reduce memory usage and increase framerate.

Change-Id: I5ff864a361db4791bd5ff6be716f7ce692ef572d

10 files changed, 563 insertions, 97 deletions

diff --git a/libs/hwui/Android.mk b/libs/hwui/Android.mk
index 43af702..437a9ef 100644
--- a/libs/hwui/Android.mk
+++ b/libs/hwui/Android.mk
@@ -5,6 +5,7 @@ include $(CLEAR_VARS)
 # defined in the current device/board configuration
 ifeq ($(USE_OPENGL_RENDERER),true)
 	LOCAL_SRC_FILES:= \
+		utils/SortedListImpl.cpp \
 		DisplayListRenderer.cpp \
 		FboCache.cpp \
 		FontRenderer.cpp \
diff --git a/libs/hwui/GenerationCache.h b/libs/hwui/GenerationCache.h
index 35c6bea..5cea30f 100644
--- a/libs/hwui/GenerationCache.h
+++ b/libs/hwui/GenerationCache.h
@@ -62,7 +62,7 @@ public:
     bool contains(K key) const;
     V get(K key);
     K getKeyAt(uint32_t index) const;
-    void put(K key, V value);
+    bool put(K key, V value);
     V remove(K key);
     V removeOldest();
     V getValueAt(uint32_t index) const;
@@ -149,7 +149,7 @@ V GenerationCache<K, V>::get(K key) {
 }
 
 template<typename K, typename V>
-void GenerationCache<K, V>::put(K key, V value) {
+bool GenerationCache<K, V>::put(K key, V value) {
     if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) {
         removeOldest();
     }
@@ -158,7 +158,10 @@ void GenerationCache<K, V>::put(K key, V value) {
     if (index < 0) {
         sp<Entry<K, V> > entry = new Entry<K, V>;
         addToCache(entry, key, value);
+        return true;
     }
+
+    return false;
 }
 
 template<typename K, typename V>
diff --git a/libs/hwui/Layer.h b/libs/hwui/Layer.h
index 6024765..2afe2fa 100644
--- a/libs/hwui/Layer.h
+++ b/libs/hwui/Layer.h
@@ -28,46 +28,33 @@
 namespace android {
 namespace uirenderer {
 
-/**
- * Dimensions of a layer.
- */
-struct LayerSize {
-    LayerSize(): width(0), height(0) { }
-    LayerSize(const uint32_t width, const uint32_t height): width(width), height(height) { }
-    LayerSize(const LayerSize& size): width(size.width), height(size.height) { }
-
-    uint32_t width;
-    uint32_t height;
-
-    bool operator<(const LayerSize& rhs) const {
-        if (width == rhs.width) {
-            return height < rhs.height;
-        }
-        return width < rhs.width;
-    }
-
-    bool operator==(const LayerSize& rhs) const {
-        return width == rhs.width && height == rhs.height;
-    }
-}; // struct LayerSize
+///////////////////////////////////////////////////////////////////////////////
+// Layers
+///////////////////////////////////////////////////////////////////////////////
 
 /**
  * A layer has dimensions and is backed by an OpenGL texture or FBO.
  */
 struct Layer {
+    Layer(const uint32_t layerWidth, const uint32_t layerHeight):
+            width(layerWidth), height(layerHeight) {
+    }
+
     /**
-     * Coordinates of the layer.
+     * Bounds of the layer.
      */
     Rect layer;
     /**
-     * Name of the texture used to render the layer.
+     * Texture coordinates of the layer.
      */
-    GLuint texture;
+    Rect texCoords;
+
     /**
      * Name of the FBO used to render the layer. If the name is 0
      * this layer is not backed by an FBO, but a simple texture.
      */
     GLuint fbo;
+
     /**
      * Opacity of the layer.
      */
@@ -80,10 +67,24 @@ struct Layer {
      * Indicates whether this layer should be blended.
      */
     bool blend;
+
     /**
      * Indicates whether this layer has been used already.
      */
     bool empty;
+
+    /**
+     * Name of the texture used to render the layer.
+     */
+    GLuint texture;
+    /**
+     * Width of the layer texture.
+     */
+    uint32_t width;
+    /**
+     * Height of the layer texture.
+     */
+    uint32_t height;
 }; // struct Layer
 
 }; // namespace uirenderer
diff --git a/libs/hwui/LayerCache.cpp b/libs/hwui/LayerCache.cpp
index 2183718..31da924 100644
--- a/libs/hwui/LayerCache.cpp
+++ b/libs/hwui/LayerCache.cpp
@@ -30,9 +30,7 @@ namespace uirenderer {
 // Constructors/destructor
 ///////////////////////////////////////////////////////////////////////////////
 
-LayerCache::LayerCache():
-        mCache(GenerationCache<LayerSize, Layer*>::kUnlimitedCapacity),
-        mSize(0), mMaxSize(MB(DEFAULT_LAYER_CACHE_SIZE)) {
+LayerCache::LayerCache(): mSize(0), mMaxSize(MB(DEFAULT_LAYER_CACHE_SIZE)) {
     char property[PROPERTY_VALUE_MAX];
     if (property_get(PROPERTY_LAYER_CACHE_SIZE, property, NULL) > 0) {
         LOGD("  Setting layer cache size to %sMB", property);
@@ -42,11 +40,6 @@ LayerCache::LayerCache():
     }
 }
 
-LayerCache::LayerCache(uint32_t maxByteSize):
-        mCache(GenerationCache<LayerSize, Layer*>::kUnlimitedCapacity),
-        mSize(0), mMaxSize(maxByteSize) {
-}
-
 LayerCache::~LayerCache() {
     clear();
 }
@@ -64,19 +57,8 @@ uint32_t LayerCache::getMaxSize() {
 }
 
 void LayerCache::setMaxSize(uint32_t maxSize) {
+    clear();
     mMaxSize = maxSize;
-    while (mSize > mMaxSize) {
-        Layer* oldest = mCache.removeOldest();
-        deleteLayer(oldest);
-    }
-}
-
-///////////////////////////////////////////////////////////////////////////////
-// Callbacks
-///////////////////////////////////////////////////////////////////////////////
-
-void LayerCache::operator()(LayerSize& size, Layer*& layer) {
-    deleteLayer(layer);
 }
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -85,7 +67,7 @@ void LayerCache::operator()(LayerSize& size, Layer*& layer) {
 
 void LayerCache::deleteLayer(Layer* layer) {
     if (layer) {
-        mSize -= layer->layer.getWidth() * layer->layer.getHeight() * 4;
+        mSize -= layer->width * layer->height * 4;
 
         glDeleteTextures(1, &layer->texture);
         delete layer;
@@ -93,21 +75,31 @@ void LayerCache::deleteLayer(Layer* layer) {
 }
 
 void LayerCache::clear() {
-    mCache.setOnEntryRemovedListener(this);
+    size_t count = mCache.size();
+    for (size_t i = 0; i < count; i++) {
+        deleteLayer(mCache.itemAt(i).mLayer);
+    }
     mCache.clear();
-    mCache.setOnEntryRemovedListener(NULL);
 }
 
-Layer* LayerCache::get(LayerSize& size) {
-    Layer* layer = mCache.remove(size);
-    if (layer) {
-        LAYER_LOGD("Reusing layer");
+Layer* LayerCache::get(const uint32_t width, const uint32_t height) {
+    Layer* layer = NULL;
+
+    LayerEntry entry(width, height);
+    ssize_t index = mCache.indexOf(entry);
 
-        mSize -= layer->layer.getWidth() * layer->layer.getHeight() * 4;
+    if (index >= 0) {
+        entry = mCache.itemAt(index);
+        mCache.removeAt(index);
+
+        layer = entry.mLayer;
+        mSize -= layer->width * layer->height * 4;
+
+        LAYER_LOGD("Reusing layer %dx%d", layer->width, layer->height);
     } else {
-        LAYER_LOGD("Creating new layer");
+        LAYER_LOGD("Creating new layer %dx%d", entry.mWidth, entry.mHeight);
 
-        layer = new Layer;
+        layer = new Layer(entry.mWidth, entry.mHeight);
         layer->blend = true;
         layer->empty = true;
         layer->fbo = 0;
@@ -124,10 +116,10 @@ Layer* LayerCache::get(LayerSize& size) {
         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_CLAMP_TO_EDGE);
 
 #if DEBUG_LAYERS
-        uint32_t size = mCache.size();
-        for (uint32_t i = 0; i < size; i++) {
-            LayerSize ls = mCache.getKeyAt(i);
-            LAYER_LOGD("  Layer size %dx%d", ls.width, ls.height);
+        size_t size = mCache.size();
+        for (size_t i = 0; i < size; i++) {
+            const LayerEntry& entry = mCache.itemAt(i);
+            LAYER_LOGD("  Layer size %dx%d", entry.mWidth, entry.mHeight);
         }
 #endif
     }
@@ -135,18 +127,23 @@ Layer* LayerCache::get(LayerSize& size) {
     return layer;
 }
 
-bool LayerCache::put(LayerSize& layerSize, Layer* layer) {
-    const uint32_t size = layerSize.width * layerSize.height * 4;
+bool LayerCache::put(Layer* layer) {
+    const uint32_t size = layer->width * layer->height * 4;
     // Don't even try to cache a layer that's bigger than the cache
     if (size < mMaxSize) {
+        // TODO: Use an LRU
         while (mSize + size > mMaxSize) {
-            Layer* oldest = mCache.removeOldest();
-            deleteLayer(oldest);
-            LAYER_LOGD("  Deleting layer %.2fx%.2f", oldest->layer.getWidth(),
-                    oldest->layer.getHeight());
+            Layer* biggest = mCache.top().mLayer;
+            deleteLayer(biggest);
+            mCache.removeAt(mCache.size() - 1);
+
+            LAYER_LOGD("  Deleting layer %.2fx%.2f", biggest->layer.getWidth(),
+                    biggest->layer.getHeight());
         }
 
-        mCache.put(layerSize, layer);
+        LayerEntry entry(layer);
+
+        mCache.add(entry);
         mSize += size;
 
         return true;
diff --git a/libs/hwui/LayerCache.h b/libs/hwui/LayerCache.h
index cbb7ae2..e64366f 100644
--- a/libs/hwui/LayerCache.h
+++ b/libs/hwui/LayerCache.h
@@ -18,7 +18,7 @@
 #define ANDROID_UI_LAYER_CACHE_H
 
 #include "Layer.h"
-#include "GenerationCache.h"
+#include "utils/SortedList.h"
 
 namespace android {
 namespace uirenderer {
@@ -30,6 +30,9 @@ namespace uirenderer {
 // Debug
 #define DEBUG_LAYERS 0
 
+// Textures used by layers must have dimensions multiples of this number
+#define LAYER_SIZE 64
+
 // Debug
 #if DEBUG_LAYERS
     #define LAYER_LOGD(...) LOGD(__VA_ARGS__)
@@ -41,40 +44,34 @@ namespace uirenderer {
 // Cache
 ///////////////////////////////////////////////////////////////////////////////
 
-class LayerCache: public OnEntryRemoved<LayerSize, Layer*> {
+class LayerCache {
 public:
     LayerCache();
-    LayerCache(uint32_t maxByteSize);
     ~LayerCache();
 
     /**
-     * Used as a callback when an entry is removed from the cache.
-     * Do not invoke directly.
-     */
-    void operator()(LayerSize& size, Layer*& layer);
-
-    /**
-     * Returns the layer of specified dimensions. If not suitable layer
-     * can be found, a new one is created and returned. If creating a new
+     * Returns a layer large enough for the specified dimensions. If no suitable
+     * layer can be found, a new one is created and returned. If creating a new
      * layer fails, NULL is returned.
      *
      * When a layer is obtained from the cache, it is removed and the total
      * size of the cache goes down.
      *
-     * @param size The dimensions of the desired layer
+     * @param width The desired width of the layer
+     * @param width The desired height of the layer
      */
-    Layer* get(LayerSize& size);
+    Layer* get(const uint32_t width, const uint32_t height);
 
     /**
      * Adds the layer to the cache. The layer will not be added if there is
-     * not enough space available.
+     * not enough space available. Adding a layer can cause other layers to
+     * be removed from the cache.
      *
-     * @param size The dimensions of the layer
      * @param layer The layer to add to the cache
      *
      * @return True if the layer was added, false otherwise.
      */
-    bool put(LayerSize& size, Layer* layer);
+    bool put(Layer* layer);
     /**
      * Clears the cache. This causes all layers to be deleted.
      */
@@ -96,7 +93,41 @@ public:
 private:
     void deleteLayer(Layer* layer);
 
-    GenerationCache<LayerSize, Layer*> mCache;
+    struct LayerEntry {
+        LayerEntry():
+            mLayer(NULL), mWidth(0), mHeight(0) {
+        }
+
+        LayerEntry(const uint32_t layerWidth, const uint32_t layerHeight): mLayer(NULL) {
+            mWidth = uint32_t(ceilf(layerWidth / float(LAYER_SIZE)) * LAYER_SIZE);
+            mHeight = uint32_t(ceilf(layerHeight / float(LAYER_SIZE)) * LAYER_SIZE);
+        }
+
+        LayerEntry(const LayerEntry& entry):
+            mLayer(entry.mLayer), mWidth(entry.mWidth), mHeight(entry.mHeight) {
+        }
+
+        LayerEntry(Layer* layer):
+            mLayer(layer), mWidth(layer->width), mHeight(layer->height) {
+        }
+
+        bool operator<(const LayerEntry& rhs) const {
+            if (mWidth == rhs.mWidth) {
+                return mHeight < rhs.mHeight;
+            }
+            return mWidth < rhs.mWidth;
+        }
+
+        bool operator==(const LayerEntry& rhs) const {
+            return mWidth == rhs.mWidth && mHeight == rhs.mHeight;
+        }
+
+        Layer* mLayer;
+        uint32_t mWidth;
+        uint32_t mHeight;
+    }; // struct LayerEntry
+
+    SortedList<LayerEntry> mCache;
 
     uint32_t mSize;
     uint32_t mMaxSize;
diff --git a/libs/hwui/OpenGLRenderer.cpp b/libs/hwui/OpenGLRenderer.cpp
index 5399668..62c590d 100644
--- a/libs/hwui/OpenGLRenderer.cpp
+++ b/libs/hwui/OpenGLRenderer.cpp
@@ -385,8 +385,7 @@ bool OpenGLRenderer::createLayer(sp<Snapshot> snapshot, float left, float top,
 
     glActiveTexture(GL_TEXTURE0);
 
-    LayerSize size(bounds.getWidth(), bounds.getHeight());
-    Layer* layer = mCaches.layerCache.get(size);
+    Layer* layer = mCaches.layerCache.get(bounds.getWidth(), bounds.getHeight());
     if (!layer) {
         return false;
     }
@@ -394,6 +393,8 @@ bool OpenGLRenderer::createLayer(sp<Snapshot> snapshot, float left, float top,
     layer->mode = mode;
     layer->alpha = alpha;
     layer->layer.set(bounds);
+    layer->texCoords.set(0.0f, bounds.getHeight() / float(layer->height),
+            bounds.getWidth() / float(layer->width), 0.0f);
 
     // Save the layer in the snapshot
     snapshot->flags |= Snapshot::kFlagIsLayer;
@@ -420,7 +421,7 @@ bool OpenGLRenderer::createLayer(sp<Snapshot> snapshot, float left, float top,
         // Initialize the texture if needed
         if (layer->empty) {
             layer->empty = false;
-            glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, size.width, size.height, 0,
+            glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, layer->width, layer->height, 0,
                     GL_RGBA, GL_UNSIGNED_BYTE, NULL);
         }
 
@@ -455,12 +456,12 @@ bool OpenGLRenderer::createLayer(sp<Snapshot> snapshot, float left, float top,
 
         // TODO: Workaround for b/3054204
         glCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, bounds.left, mHeight - bounds.bottom,
-                bounds.getWidth(), bounds.getHeight(), 0);
+                layer->width, layer->height, 0);
 
         // TODO: Waiting for b/3054204 to be fixed
         // if (layer->empty) {
         //     glCopyTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA, bounds.left, mHeight - bounds.bottom,
-        //             bounds.getWidth(), bounds.getHeight(), 0);
+        //             layer->width, layer->height, 0);
         //     layer->empty = false;
         // } else {
         //     glCopyTexSubImage2D(GL_TEXTURE_2D, 0, 0, 0, bounds.left, mHeight - bounds.bottom,
@@ -502,8 +503,8 @@ void OpenGLRenderer::composeLayer(sp<Snapshot> current, sp<Snapshot> previous) {
                 layer->alpha << 24, SkXfermode::kDstIn_Mode, true);
     }
 
-    // Layers are already drawn with a top-left origin, don't flip the texture
-    resetDrawTextureTexCoords(0.0f, 1.0f, 1.0f, 0.0f);
+    const Rect& texCoords = layer->texCoords;
+    resetDrawTextureTexCoords(texCoords.left, texCoords.top, texCoords.right, texCoords.bottom);
 
     if (fboLayer) {
         drawTextureRect(rect.left, rect.top, rect.right, rect.bottom,
@@ -526,9 +527,8 @@ void OpenGLRenderer::composeLayer(sp<Snapshot> current, sp<Snapshot> previous) {
         mCaches.fboCache.put(current->fbo);
     }
 
-    LayerSize size(rect.getWidth(), rect.getHeight());
     // Failing to add the layer to the cache should happen only if the layer is too large
-    if (!mCaches.layerCache.put(size, layer)) {
+    if (!mCaches.layerCache.put(layer)) {
         LAYER_LOGD("Deleting layer");
         glDeleteTextures(1, &layer->texture);
         delete layer;
diff --git a/libs/hwui/Properties.h b/libs/hwui/Properties.h
index 3012824..277aacc 100644
--- a/libs/hwui/Properties.h
+++ b/libs/hwui/Properties.h
@@ -44,9 +44,9 @@
 // Converts a number of mega-bytes into bytes
 #define MB(s) s * 1024 * 1024
 
-#define DEFAULT_TEXTURE_CACHE_SIZE 18.0f
-#define DEFAULT_LAYER_CACHE_SIZE 8.0f
-#define DEFAULT_PATH_CACHE_SIZE 5.0f
+#define DEFAULT_TEXTURE_CACHE_SIZE 22.0f
+#define DEFAULT_LAYER_CACHE_SIZE 4.0f
+#define DEFAULT_PATH_CACHE_SIZE 4.0f
 #define DEFAULT_PATCH_CACHE_SIZE 100
 #define DEFAULT_GRADIENT_CACHE_SIZE 0.5f
 #define DEFAULT_DROP_SHADOW_CACHE_SIZE 2.0f
diff --git a/libs/hwui/utils/SortedList.h b/libs/hwui/utils/SortedList.h
new file mode 100644
index 0000000..68f5e9d
--- /dev/null
+++ b/libs/hwui/utils/SortedList.h
@@ -0,0 +1,242 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ANDROID_UI_SORTED_LIST_H
+#define ANDROID_UI_SORTED_LIST_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+#include <utils/Vector.h>
+#include <utils/TypeHelpers.h>
+
+#include "SortedListImpl.h"
+
+namespace android {
+namespace uirenderer {
+
+///////////////////////////////////////////////////////////////////////////////
+// Sorted list
+///////////////////////////////////////////////////////////////////////////////
+
+template<class TYPE>
+class SortedList: private SortedListImpl {
+public:
+    typedef TYPE value_type;
+
+    SortedList();
+    SortedList(const SortedList<TYPE>& rhs);
+    virtual ~SortedList();
+
+    const SortedList<TYPE>& operator =(const SortedList<TYPE>& rhs) const;
+    SortedList<TYPE>& operator =(const SortedList<TYPE>& rhs);
+
+    inline void clear() {
+        VectorImpl::clear();
+    }
+
+    inline size_t size() const {
+        return VectorImpl::size();
+    }
+
+    inline bool isEmpty() const {
+        return VectorImpl::isEmpty();
+    }
+
+    inline size_t capacity() const {
+        return VectorImpl::capacity();
+    }
+
+    inline ssize_t setCapacity(size_t size) {
+        return VectorImpl::setCapacity(size);
+    }
+
+    inline const TYPE* array() const;
+
+    TYPE* editArray();
+
+    ssize_t indexOf(const TYPE& item) const;
+    size_t orderOf(const TYPE& item) const;
+
+    inline const TYPE& operator [](size_t index) const;
+    inline const TYPE& itemAt(size_t index) const;
+    const TYPE& top() const;
+    const TYPE& mirrorItemAt(ssize_t index) const;
+
+    ssize_t add(const TYPE& item);
+
+    TYPE& editItemAt(size_t index) {
+        return *(static_cast<TYPE *> (VectorImpl::editItemLocation(index)));
+    }
+
+    ssize_t merge(const Vector<TYPE>& vector);
+    ssize_t merge(const SortedList<TYPE>& vector);
+
+    ssize_t remove(const TYPE&);
+
+    inline ssize_t removeItemsAt(size_t index, size_t count = 1);
+    inline ssize_t removeAt(size_t index) {
+        return removeItemsAt(index);
+    }
+
+protected:
+    virtual void do_construct(void* storage, size_t num) const;
+    virtual void do_destroy(void* storage, size_t num) const;
+    virtual void do_copy(void* dest, const void* from, size_t num) const;
+    virtual void do_splat(void* dest, const void* item, size_t num) const;
+    virtual void do_move_forward(void* dest, const void* from, size_t num) const;
+    virtual void do_move_backward(void* dest, const void* from, size_t num) const;
+    virtual int do_compare(const void* lhs, const void* rhs) const;
+}; // class SortedList
+
+///////////////////////////////////////////////////////////////////////////////
+// Implementation
+///////////////////////////////////////////////////////////////////////////////
+
+template<class TYPE>
+inline SortedList<TYPE>::SortedList():
+        SortedListImpl(sizeof(TYPE), ((traits<TYPE>::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0)
+            | (traits<TYPE>::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0)
+            | (traits<TYPE>::has_trivial_copy ? HAS_TRIVIAL_COPY : 0))) {
+}
+
+template<class TYPE>
+inline SortedList<TYPE>::SortedList(const SortedList<TYPE>& rhs): SortedListImpl(rhs) {
+}
+
+template<class TYPE> inline SortedList<TYPE>::~SortedList() {
+    finish_vector();
+}
+
+template<class TYPE>
+inline SortedList<TYPE>& SortedList<TYPE>::operator =(const SortedList<TYPE>& rhs) {
+    SortedListImpl::operator =(rhs);
+    return *this;
+}
+
+template<class TYPE>
+inline const SortedList<TYPE>& SortedList<TYPE>::operator =(
+        const SortedList<TYPE>& rhs) const {
+    SortedListImpl::operator =(rhs);
+    return *this;
+}
+
+template<class TYPE>
+inline const TYPE* SortedList<TYPE>::array() const {
+    return static_cast<const TYPE *> (arrayImpl());
+}
+
+template<class TYPE>
+inline TYPE* SortedList<TYPE>::editArray() {
+    return static_cast<TYPE *> (editArrayImpl());
+}
+
+template<class TYPE>
+inline const TYPE& SortedList<TYPE>::operator[](size_t index) const {
+    assert( index<size() );
+    return *(array() + index);
+}
+
+template<class TYPE>
+inline const TYPE& SortedList<TYPE>::itemAt(size_t index) const {
+    return operator[](index);
+}
+
+template<class TYPE>
+inline const TYPE& SortedList<TYPE>::mirrorItemAt(ssize_t index) const {
+    assert( (index>0 ? index : -index)<size() );
+    return *(array() + ((index < 0) ? (size() - index) : index));
+}
+
+template<class TYPE>
+inline const TYPE& SortedList<TYPE>::top() const {
+    return *(array() + size() - 1);
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::add(const TYPE& item) {
+    return SortedListImpl::add(&item);
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::indexOf(const TYPE& item) const {
+    return SortedListImpl::indexOf(&item);
+}
+
+template<class TYPE>
+inline size_t SortedList<TYPE>::orderOf(const TYPE& item) const {
+    return SortedListImpl::orderOf(&item);
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::merge(const Vector<TYPE>& vector) {
+    return SortedListImpl::merge(reinterpret_cast<const VectorImpl&> (vector));
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::merge(const SortedList<TYPE>& vector) {
+    return SortedListImpl::merge(reinterpret_cast<const SortedListImpl&> (vector));
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::remove(const TYPE& item) {
+    return SortedListImpl::remove(&item);
+}
+
+template<class TYPE>
+inline ssize_t SortedList<TYPE>::removeItemsAt(size_t index, size_t count) {
+    return VectorImpl::removeItemsAt(index, count);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_construct(void* storage, size_t num) const {
+    construct_type(reinterpret_cast<TYPE*> (storage), num);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_destroy(void* storage, size_t num) const {
+    destroy_type(reinterpret_cast<TYPE*> (storage), num);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_copy(void* dest, const void* from, size_t num) const {
+    copy_type(reinterpret_cast<TYPE*> (dest), reinterpret_cast<const TYPE*> (from), num);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_splat(void* dest, const void* item, size_t num) const {
+    splat_type(reinterpret_cast<TYPE*> (dest), reinterpret_cast<const TYPE*> (item), num);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_move_forward(void* dest, const void* from, size_t num) const {
+    move_forward_type(reinterpret_cast<TYPE*> (dest), reinterpret_cast<const TYPE*> (from), num);
+}
+
+template<class TYPE>
+void SortedList<TYPE>::do_move_backward(void* dest, const void* from, size_t num) const {
+    move_backward_type(reinterpret_cast<TYPE*> (dest), reinterpret_cast<const TYPE*> (from), num);
+}
+
+template<class TYPE>
+int SortedList<TYPE>::do_compare(const void* lhs, const void* rhs) const {
+    return compare_type(*reinterpret_cast<const TYPE*> (lhs), *reinterpret_cast<const TYPE*> (rhs));
+}
+
+}; // namespace uirenderer
+}; // namespace android
+
+#endif // ANDROID_UI_SORTED_LIST_H
diff --git a/libs/hwui/utils/SortedListImpl.cpp b/libs/hwui/utils/SortedListImpl.cpp
new file mode 100644
index 0000000..35171d5
--- /dev/null
+++ b/libs/hwui/utils/SortedListImpl.cpp
@@ -0,0 +1,126 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "SortedListImpl.h"
+
+namespace android {
+namespace uirenderer {
+
+///////////////////////////////////////////////////////////////////////////////
+// Sorted list implementation, not for direct use
+///////////////////////////////////////////////////////////////////////////////
+
+SortedListImpl::SortedListImpl(size_t itemSize, uint32_t flags): VectorImpl(itemSize, flags) {
+}
+
+SortedListImpl::SortedListImpl(const VectorImpl& rhs): VectorImpl(rhs) {
+}
+
+SortedListImpl::~SortedListImpl() {
+}
+
+SortedListImpl& SortedListImpl::operator =(const SortedListImpl& rhs) {
+    return static_cast<SortedListImpl&>
+            (VectorImpl::operator =(static_cast<const VectorImpl&> (rhs)));
+}
+
+ssize_t SortedListImpl::indexOf(const void* item) const {
+    return _indexOrderOf(item);
+}
+
+size_t SortedListImpl::orderOf(const void* item) const {
+    size_t o;
+    _indexOrderOf(item, &o);
+    return o;
+}
+
+ssize_t SortedListImpl::_indexOrderOf(const void* item, size_t* order) const {
+    // binary search
+    ssize_t err = NAME_NOT_FOUND;
+    ssize_t l = 0;
+    ssize_t h = size() - 1;
+    ssize_t mid;
+    const void* a = arrayImpl();
+    const size_t s = itemSize();
+    while (l <= h) {
+        mid = l + (h - l) / 2;
+        const void* const curr = reinterpret_cast<const char *> (a) + (mid * s);
+        const int c = do_compare(curr, item);
+        if (c == 0) {
+            err = l = mid;
+            break;
+        } else if (c < 0) {
+            l = mid + 1;
+        } else {
+            h = mid - 1;
+        }
+    }
+    if (order) {
+        *order = l;
+    }
+    return err;
+}
+
+ssize_t SortedListImpl::add(const void* item) {
+    size_t order;
+    ssize_t index = _indexOrderOf(item, &order);
+    index = VectorImpl::insertAt(item, order, 1);
+    return index;
+}
+
+ssize_t SortedListImpl::merge(const VectorImpl& vector) {
+    // naive merge...
+    if (!vector.isEmpty()) {
+        const void* buffer = vector.arrayImpl();
+        const size_t is = itemSize();
+        size_t s = vector.size();
+        for (size_t i = 0; i < s; i++) {
+            ssize_t err = add(reinterpret_cast<const char*> (buffer) + i * is);
+            if (err < 0) {
+                return err;
+            }
+        }
+    }
+    return NO_ERROR;
+}
+
+ssize_t SortedListImpl::merge(const SortedListImpl& vector) {
+    // we've merging a sorted vector... nice!
+    ssize_t err = NO_ERROR;
+    if (!vector.isEmpty()) {
+        // first take care of the case where the vectors are sorted together
+        if (do_compare(vector.itemLocation(vector.size() - 1), arrayImpl()) <= 0) {
+            err = VectorImpl::insertVectorAt(static_cast<const VectorImpl&> (vector), 0);
+        } else if (do_compare(vector.arrayImpl(), itemLocation(size() - 1)) >= 0) {
+            err = VectorImpl::appendVector(static_cast<const VectorImpl&> (vector));
+        } else {
+            // this could be made a little better
+            err = merge(static_cast<const VectorImpl&> (vector));
+        }
+    }
+    return err;
+}
+
+ssize_t SortedListImpl::remove(const void* item) {
+    ssize_t i = indexOf(item);
+    if (i >= 0) {
+        VectorImpl::removeItemsAt(i, 1);
+    }
+    return i;
+}
+
+}; // namespace uirenderer
+}; // namespace android
diff --git a/libs/hwui/utils/SortedListImpl.h b/libs/hwui/utils/SortedListImpl.h
new file mode 100644
index 0000000..7da09ef
--- /dev/null
+++ b/libs/hwui/utils/SortedListImpl.h
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ANDROID_UI_SORTED_LIST_IMPL_H
+#define ANDROID_UI_SORTED_LIST_IMPL_H
+
+#include <utils/VectorImpl.h>
+
+namespace android {
+namespace uirenderer {
+
+class SortedListImpl: public VectorImpl {
+public:
+    SortedListImpl(size_t itemSize, uint32_t flags);
+    SortedListImpl(const VectorImpl& rhs);
+    virtual ~SortedListImpl();
+
+    SortedListImpl& operator =(const SortedListImpl& rhs);
+
+    ssize_t indexOf(const void* item) const;
+    size_t orderOf(const void* item) const;
+    ssize_t add(const void* item);
+    ssize_t merge(const VectorImpl& vector);
+    ssize_t merge(const SortedListImpl& vector);
+    ssize_t remove(const void* item);
+
+protected:
+    virtual int do_compare(const void* lhs, const void* rhs) const = 0;
+
+private:
+    ssize_t _indexOrderOf(const void* item, size_t* order = 0) const;
+
+    // these are made private, because they can't be used on a SortedVector
+    // (they don't have an implementation either)
+    ssize_t add();
+    void pop();
+    void push();
+    void push(const void* item);
+    ssize_t insertVectorAt(const VectorImpl& vector, size_t index);
+    ssize_t appendVector(const VectorImpl& vector);
+    ssize_t insertArrayAt(const void* array, size_t index, size_t length);
+    ssize_t appendArray(const void* array, size_t length);
+    ssize_t insertAt(size_t where, size_t numItems = 1);
+    ssize_t insertAt(const void* item, size_t where, size_t numItems = 1);
+    ssize_t replaceAt(size_t index);
+    ssize_t replaceAt(const void* item, size_t index);
+};
+
+}; // namespace uirenderer
+}; // namespace android
+
+#endif // ANDROID_UI_SORTED_LIST_IMPL_H