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

Change-Id: I5ff864a361db4791bd5ff6be716f7ce692ef572d

3 files changed, 433 insertions, 0 deletions

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