From 8550c4c7b5952b7a4e1e0ede95c9492d03099a13 Mon Sep 17 00:00:00 2001 From: Romain Guy Date: Fri, 8 Oct 2010 15:49:53 -0700 Subject: Better cache for layers, reduce memory usage and increase framerate. Change-Id: I5ff864a361db4791bd5ff6be716f7ce692ef572d --- libs/hwui/Android.mk | 1 + libs/hwui/GenerationCache.h | 7 +- libs/hwui/Layer.h | 51 ++++---- libs/hwui/LayerCache.cpp | 79 ++++++------ libs/hwui/LayerCache.h | 65 +++++++--- libs/hwui/OpenGLRenderer.cpp | 18 +-- libs/hwui/Properties.h | 6 +- libs/hwui/utils/SortedList.h | 242 +++++++++++++++++++++++++++++++++++++ libs/hwui/utils/SortedListImpl.cpp | 126 +++++++++++++++++++ libs/hwui/utils/SortedListImpl.h | 65 ++++++++++ 10 files changed, 563 insertions(+), 97 deletions(-) create mode 100644 libs/hwui/utils/SortedList.h create mode 100644 libs/hwui/utils/SortedListImpl.cpp create mode 100644 libs/hwui/utils/SortedListImpl.h 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::get(K key) { } template -void GenerationCache::put(K key, V value) { +bool GenerationCache::put(K key, V value) { if (mMaxCapacity != kUnlimitedCapacity && mCache.size() >= mMaxCapacity) { removeOldest(); } @@ -158,7 +158,10 @@ void GenerationCache::put(K key, V value) { if (index < 0) { sp > entry = new Entry; addToCache(entry, key, value); + return true; } + + return false; } template 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::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::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 { +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 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 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, 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, 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, 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, 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 current, sp 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 current, sp 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 +#include + +#include +#include + +#include "SortedListImpl.h" + +namespace android { +namespace uirenderer { + +/////////////////////////////////////////////////////////////////////////////// +// Sorted list +/////////////////////////////////////////////////////////////////////////////// + +template +class SortedList: private SortedListImpl { +public: + typedef TYPE value_type; + + SortedList(); + SortedList(const SortedList& rhs); + virtual ~SortedList(); + + const SortedList& operator =(const SortedList& rhs) const; + SortedList& operator =(const SortedList& 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 (VectorImpl::editItemLocation(index))); + } + + ssize_t merge(const Vector& vector); + ssize_t merge(const SortedList& 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 +inline SortedList::SortedList(): + SortedListImpl(sizeof(TYPE), ((traits::has_trivial_ctor ? HAS_TRIVIAL_CTOR : 0) + | (traits::has_trivial_dtor ? HAS_TRIVIAL_DTOR : 0) + | (traits::has_trivial_copy ? HAS_TRIVIAL_COPY : 0))) { +} + +template +inline SortedList::SortedList(const SortedList& rhs): SortedListImpl(rhs) { +} + +template inline SortedList::~SortedList() { + finish_vector(); +} + +template +inline SortedList& SortedList::operator =(const SortedList& rhs) { + SortedListImpl::operator =(rhs); + return *this; +} + +template +inline const SortedList& SortedList::operator =( + const SortedList& rhs) const { + SortedListImpl::operator =(rhs); + return *this; +} + +template +inline const TYPE* SortedList::array() const { + return static_cast (arrayImpl()); +} + +template +inline TYPE* SortedList::editArray() { + return static_cast (editArrayImpl()); +} + +template +inline const TYPE& SortedList::operator[](size_t index) const { + assert( index +inline const TYPE& SortedList::itemAt(size_t index) const { + return operator[](index); +} + +template +inline const TYPE& SortedList::mirrorItemAt(ssize_t index) const { + assert( (index>0 ? index : -index) +inline const TYPE& SortedList::top() const { + return *(array() + size() - 1); +} + +template +inline ssize_t SortedList::add(const TYPE& item) { + return SortedListImpl::add(&item); +} + +template +inline ssize_t SortedList::indexOf(const TYPE& item) const { + return SortedListImpl::indexOf(&item); +} + +template +inline size_t SortedList::orderOf(const TYPE& item) const { + return SortedListImpl::orderOf(&item); +} + +template +inline ssize_t SortedList::merge(const Vector& vector) { + return SortedListImpl::merge(reinterpret_cast (vector)); +} + +template +inline ssize_t SortedList::merge(const SortedList& vector) { + return SortedListImpl::merge(reinterpret_cast (vector)); +} + +template +inline ssize_t SortedList::remove(const TYPE& item) { + return SortedListImpl::remove(&item); +} + +template +inline ssize_t SortedList::removeItemsAt(size_t index, size_t count) { + return VectorImpl::removeItemsAt(index, count); +} + +template +void SortedList::do_construct(void* storage, size_t num) const { + construct_type(reinterpret_cast (storage), num); +} + +template +void SortedList::do_destroy(void* storage, size_t num) const { + destroy_type(reinterpret_cast (storage), num); +} + +template +void SortedList::do_copy(void* dest, const void* from, size_t num) const { + copy_type(reinterpret_cast (dest), reinterpret_cast (from), num); +} + +template +void SortedList::do_splat(void* dest, const void* item, size_t num) const { + splat_type(reinterpret_cast (dest), reinterpret_cast (item), num); +} + +template +void SortedList::do_move_forward(void* dest, const void* from, size_t num) const { + move_forward_type(reinterpret_cast (dest), reinterpret_cast (from), num); +} + +template +void SortedList::do_move_backward(void* dest, const void* from, size_t num) const { + move_backward_type(reinterpret_cast (dest), reinterpret_cast (from), num); +} + +template +int SortedList::do_compare(const void* lhs, const void* rhs) const { + return compare_type(*reinterpret_cast (lhs), *reinterpret_cast (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 + (VectorImpl::operator =(static_cast (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 (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 (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 (vector), 0); + } else if (do_compare(vector.arrayImpl(), itemLocation(size() - 1)) >= 0) { + err = VectorImpl::appendVector(static_cast (vector)); + } else { + // this could be made a little better + err = merge(static_cast (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 + +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 -- cgit v1.1