Remove the rest of utils/Vector.h usage

Change-Id: I90ab2c17ba1903a8241cba7f623b74ed136dd845

8 files changed, 29 insertions, 481 deletions

diff --git a/libs/hwui/Android.common.mk b/libs/hwui/Android.common.mk
index ed88237bb04d..fe4f1be81bb9 100644
--- a/libs/hwui/Android.common.mk
+++ b/libs/hwui/Android.common.mk
@@ -23,7 +23,6 @@ LOCAL_SRC_FILES := \
     utils/Blur.cpp \
     utils/GLUtils.cpp \
     utils/LinearAllocator.cpp \
-    utils/SortedListImpl.cpp \
     AmbientShadow.cpp \
     AnimationContext.cpp \
     Animator.cpp \
diff --git a/libs/hwui/LayerCache.cpp b/libs/hwui/LayerCache.cpp
index ade2ac7a8364..33f40b006092 100644
--- a/libs/hwui/LayerCache.cpp
+++ b/libs/hwui/LayerCache.cpp
@@ -87,9 +87,8 @@ void LayerCache::deleteLayer(Layer* layer) {
 }
 
 void LayerCache::clear() {
-    size_t count = mCache.size();
-    for (size_t i = 0; i < count; i++) {
-        deleteLayer(mCache.itemAt(i).mLayer);
+    for (auto entry : mCache) {
+        deleteLayer(entry.mLayer);
     }
     mCache.clear();
 }
@@ -98,11 +97,11 @@ Layer* LayerCache::get(RenderState& renderState, const uint32_t width, const uin
     Layer* layer = nullptr;
 
     LayerEntry entry(width, height);
-    ssize_t index = mCache.indexOf(entry);
+    auto iter = mCache.find(entry);
 
-    if (index >= 0) {
-        entry = mCache.itemAt(index);
-        mCache.removeAt(index);
+    if (iter != mCache.end()) {
+        entry = *iter;
+        mCache.erase(iter);
 
         layer = entry.mLayer;
         layer->state = Layer::kState_RemovedFromCache;
@@ -129,9 +128,7 @@ Layer* LayerCache::get(RenderState& renderState, const uint32_t width, const uin
 }
 
 void LayerCache::dump() {
-    size_t size = mCache.size();
-    for (size_t i = 0; i < size; i++) {
-        const LayerEntry& entry = mCache.itemAt(i);
+    for (auto entry : mCache) {
         ALOGD("  Layer size %dx%d", entry.mWidth, entry.mHeight);
     }
 }
@@ -144,13 +141,9 @@ bool LayerCache::put(Layer* layer) {
     if (size < mMaxSize) {
         // TODO: Use an LRU
         while (mSize + size > mMaxSize) {
-            size_t position = 0;
-#if LAYER_REMOVE_BIGGEST_FIRST
-            position = mCache.size() - 1;
-#endif
-            Layer* victim = mCache.itemAt(position).mLayer;
+            Layer* victim = mCache.begin()->mLayer;
             deleteLayer(victim);
-            mCache.removeAt(position);
+            mCache.erase(mCache.begin());
 
             LAYER_LOGD("  Deleting layer %.2fx%.2f", victim->layer.getWidth(),
                     victim->layer.getHeight());
@@ -160,7 +153,7 @@ bool LayerCache::put(Layer* layer) {
 
         LayerEntry entry(layer);
 
-        mCache.add(entry);
+        mCache.insert(entry);
         mSize += size;
 
         layer->state = Layer::kState_InCache;
diff --git a/libs/hwui/LayerCache.h b/libs/hwui/LayerCache.h
index 7d17b9ba41aa..6fe7b3aae859 100644
--- a/libs/hwui/LayerCache.h
+++ b/libs/hwui/LayerCache.h
@@ -19,7 +19,8 @@
 
 #include "Debug.h"
 #include "Layer.h"
-#include "utils/SortedList.h"
+
+#include <set>
 
 namespace android {
 namespace uirenderer {
@@ -118,12 +119,8 @@ private:
             return compare(*this, other) != 0;
         }
 
-        friend inline int strictly_order_type(const LayerEntry& lhs, const LayerEntry& rhs) {
-            return LayerEntry::compare(lhs, rhs) < 0;
-        }
-
-        friend inline int compare_type(const LayerEntry& lhs, const LayerEntry& rhs) {
-            return LayerEntry::compare(lhs, rhs);
+        bool operator<(const LayerEntry& other) const {
+            return LayerEntry::compare(*this, other) < 0;
         }
 
         Layer* mLayer;
@@ -133,7 +130,7 @@ private:
 
     void deleteLayer(Layer* layer);
 
-    SortedList<LayerEntry> mCache;
+    std::multiset<LayerEntry> mCache;
 
     uint32_t mSize;
     uint32_t mMaxSize;
diff --git a/libs/hwui/RenderBufferCache.cpp b/libs/hwui/RenderBufferCache.cpp
index 39e0dbf4f1e1..8beed2540e1c 100644
--- a/libs/hwui/RenderBufferCache.cpp
+++ b/libs/hwui/RenderBufferCache.cpp
@@ -98,9 +98,8 @@ void RenderBufferCache::deleteBuffer(RenderBuffer* buffer) {
 }
 
 void RenderBufferCache::clear() {
-    size_t count = mCache.size();
-    for (size_t i = 0; i < count; i++) {
-        deleteBuffer(mCache.itemAt(i).mBuffer);
+    for (auto entry : mCache) {
+        deleteBuffer(entry.mBuffer);
     }
     mCache.clear();
 }
@@ -109,11 +108,11 @@ RenderBuffer* RenderBufferCache::get(GLenum format, const uint32_t width, const
     RenderBuffer* buffer = nullptr;
 
     RenderBufferEntry entry(format, width, height);
-    ssize_t index = mCache.indexOf(entry);
+    auto iter = mCache.find(entry);
 
-    if (index >= 0) {
-        entry = mCache.itemAt(index);
-        mCache.removeAt(index);
+    if (iter != mCache.end()) {
+        entry = *iter;
+        mCache.erase(iter);
 
         buffer = entry.mBuffer;
         mSize -= buffer->getSize();
@@ -139,16 +138,14 @@ bool RenderBufferCache::put(RenderBuffer* buffer) {
     const uint32_t size = buffer->getSize();
     if (size < mMaxSize) {
         while (mSize + size > mMaxSize) {
-            size_t position = 0;
-
-            RenderBuffer* victim = mCache.itemAt(position).mBuffer;
+            RenderBuffer* victim = mCache.begin()->mBuffer;
             deleteBuffer(victim);
-            mCache.removeAt(position);
+            mCache.erase(mCache.begin());
         }
 
         RenderBufferEntry entry(buffer);
 
-        mCache.add(entry);
+        mCache.insert(entry);
         mSize += size;
 
         RENDER_BUFFER_LOGD("Added %s render buffer (%dx%d)",
diff --git a/libs/hwui/RenderBufferCache.h b/libs/hwui/RenderBufferCache.h
index 6c668b09c40d..7f59ec1c48b1 100644
--- a/libs/hwui/RenderBufferCache.h
+++ b/libs/hwui/RenderBufferCache.h
@@ -20,7 +20,8 @@
 #include <GLES2/gl2.h>
 
 #include "RenderBuffer.h"
-#include "utils/SortedList.h"
+
+#include <set>
 
 namespace android {
 namespace uirenderer {
@@ -100,14 +101,8 @@ private:
             return compare(*this, other) != 0;
         }
 
-        friend inline int strictly_order_type(const RenderBufferEntry& lhs,
-                const RenderBufferEntry& rhs) {
-            return RenderBufferEntry::compare(lhs, rhs) < 0;
-        }
-
-        friend inline int compare_type(const RenderBufferEntry& lhs,
-                const RenderBufferEntry& rhs) {
-            return RenderBufferEntry::compare(lhs, rhs);
+        bool operator<(const RenderBufferEntry& other) const {
+            return RenderBufferEntry::compare(*this, other) < 0;
         }
 
         RenderBuffer* mBuffer;
@@ -118,7 +113,7 @@ private:
 
     void deleteBuffer(RenderBuffer* buffer);
 
-    SortedList<RenderBufferEntry> mCache;
+    std::multiset<RenderBufferEntry> mCache;
 
     uint32_t mSize;
     uint32_t mMaxSize;
diff --git a/libs/hwui/utils/SortedList.h b/libs/hwui/utils/SortedList.h
deleted file mode 100644
index a2c8c52fcbc7..000000000000
--- a/libs/hwui/utils/SortedList.h
+++ /dev/null
@@ -1,242 +0,0 @@
-/*
- * 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_HWUI_SORTED_LIST_H
-#define ANDROID_HWUI_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 override;
-    virtual void do_destroy(void* storage, size_t num) const override;
-    virtual void do_copy(void* dest, const void* from, size_t num) const override;
-    virtual void do_splat(void* dest, const void* item, size_t num) const override;
-    virtual void do_move_forward(void* dest, const void* from, size_t num) const override;
-    virtual void do_move_backward(void* dest, const void* from, size_t num) const override;
-    virtual int do_compare(const void* lhs, const void* rhs) const override;
-}; // 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_HWUI_SORTED_LIST_H
diff --git a/libs/hwui/utils/SortedListImpl.cpp b/libs/hwui/utils/SortedListImpl.cpp
deleted file mode 100644
index 35171d5b1a5b..000000000000
--- a/libs/hwui/utils/SortedListImpl.cpp
+++ /dev/null
@@ -1,126 +0,0 @@
-/*
- * 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
deleted file mode 100644
index b1018265566a..000000000000
--- a/libs/hwui/utils/SortedListImpl.h
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * 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_HWUI_SORTED_LIST_IMPL_H
-#define ANDROID_HWUI_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 = nullptr) 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_HWUI_SORTED_LIST_IMPL_H