Better cache for layers, reduce memory usage and increase framerate.
Change-Id: I5ff864a361db4791bd5ff6be716f7ce692ef572d
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 @@
# 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 @@
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 @@
}
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 @@
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 @@
* 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 @@
// 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(uint32_t maxByteSize):
- mCache(GenerationCache<LayerSize, Layer*>::kUnlimitedCapacity),
- mSize(0), mMaxSize(maxByteSize) {
-}
-
LayerCache::~LayerCache() {
clear();
}
@@ -64,19 +57,8 @@
}
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::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::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;
- mSize -= layer->layer.getWidth() * layer->layer.getHeight() * 4;
+ LayerEntry entry(width, height);
+ ssize_t index = mCache.indexOf(entry);
+
+ 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 @@
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 @@
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 @@
// 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 @@
// 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 @@
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 @@
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 @@
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 @@
// 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 @@
// 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 @@
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 @@
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