Revert^2 "libui: rewrite Region with FatVector"

Revert submission 10449863-revert-fatvector

Reason for revert: b/149254345

Original change (of introducing FatVector) was reverted as a stop-gap solution to fix the aforementioned bug.

The bug was caused by an ABI lock between Surface's definition (that changed with Region) and lib-imsvt prebuilt.

Enabling this change now as we have re-compiled the prebuilt with the change enabled. Doing that via a revert of the revert.

Reverted Changes:
I8ac66acb8:Revert "hwui: remove FatVector"
Ib60dbf3ef:Revert "libui: rewrite Region with FatVector"

Original changes:
I09dc2fddd:hwui: remove FatVector
I265c6c831:libui: rewrite Region with FatVector

bug: 149254345

Change-Id: I723283a952e0908f595967af0037b0dc1351671b

5 files changed, 146 insertions, 50 deletions

diff --git a/include/ui/FatVector.h b/include/ui/FatVector.h
new file mode 120000
index 0000000000..c2047c07e1
--- /dev/null
+++ b/include/ui/FatVector.h
@@ -0,0 +1 @@
+../../libs/ui/include/ui/FatVector.h
\ No newline at end of file
diff --git a/libs/ui/Region.cpp b/libs/ui/Region.cpp
index bf487c4aec..cd2a448c3e 100644
--- a/libs/ui/Region.cpp
+++ b/libs/ui/Region.cpp
@@ -67,19 +67,20 @@ const Region Region::INVALID_REGION(Rect::INVALID_RECT);
 // ----------------------------------------------------------------------------
 
 Region::Region() {
-    mStorage.add(Rect(0,0));
+    mStorage.push_back(Rect(0, 0));
 }
 
 Region::Region(const Region& rhs)
-    : mStorage(rhs.mStorage)
 {
+    mStorage.clear();
+    mStorage.insert(mStorage.begin(), rhs.mStorage.begin(), rhs.mStorage.end());
 #if defined(VALIDATE_REGIONS)
     validate(rhs, "rhs copy-ctor");
 #endif
 }
 
 Region::Region(const Rect& rhs) {
-    mStorage.add(rhs);
+    mStorage.push_back(rhs);
 }
 
 Region::~Region()
@@ -100,8 +101,8 @@ Region::~Region()
  * final, correctly ordered region buffer. Each rectangle will be compared with the span directly
  * above it, and subdivided to resolve any remaining T-junctions.
  */
-static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
-        Vector<Rect>& dst, int spanDirection) {
+static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end, FatVector<Rect>& dst,
+                                           int spanDirection) {
     dst.clear();
 
     const Rect* current = end - 1;
@@ -109,7 +110,7 @@ static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
 
     // add first span immediately
     do {
-        dst.add(*current);
+        dst.push_back(*current);
         current--;
     } while (current->top == lastTop && current >= begin);
 
@@ -147,12 +148,12 @@ static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
                 if (prev.right <= left) break;
 
                 if (prev.right > left && prev.right < right) {
-                    dst.add(Rect(prev.right, top, right, bottom));
+                    dst.push_back(Rect(prev.right, top, right, bottom));
                     right = prev.right;
                 }
 
                 if (prev.left > left && prev.left < right) {
-                    dst.add(Rect(prev.left, top, right, bottom));
+                    dst.push_back(Rect(prev.left, top, right, bottom));
                     right = prev.left;
                 }
 
@@ -166,12 +167,12 @@ static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
                 if (prev.left >= right) break;
 
                 if (prev.left > left && prev.left < right) {
-                    dst.add(Rect(left, top, prev.left, bottom));
+                    dst.push_back(Rect(left, top, prev.left, bottom));
                     left = prev.left;
                 }
 
                 if (prev.right > left && prev.right < right) {
-                    dst.add(Rect(left, top, prev.right, bottom));
+                    dst.push_back(Rect(left, top, prev.right, bottom));
                     left = prev.right;
                 }
                 // if an entry in the previous span is too far left, nothing further right in the
@@ -183,7 +184,7 @@ static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
         }
 
         if (left < right) {
-            dst.add(Rect(left, top, right, bottom));
+            dst.push_back(Rect(left, top, right, bottom));
         }
 
         current--;
@@ -201,13 +202,14 @@ Region Region::createTJunctionFreeRegion(const Region& r) {
     if (r.isEmpty()) return r;
     if (r.isRect()) return r;
 
-    Vector<Rect> reversed;
+    FatVector<Rect> reversed;
     reverseRectsResolvingJunctions(r.begin(), r.end(), reversed, direction_RTL);
 
     Region outputRegion;
-    reverseRectsResolvingJunctions(reversed.begin(), reversed.end(),
-            outputRegion.mStorage, direction_LTR);
-    outputRegion.mStorage.add(r.getBounds()); // to make region valid, mStorage must end with bounds
+    reverseRectsResolvingJunctions(reversed.data(), reversed.data() + reversed.size(),
+                                   outputRegion.mStorage, direction_LTR);
+    outputRegion.mStorage.push_back(
+            r.getBounds()); // to make region valid, mStorage must end with bounds
 
 #if defined(VALIDATE_REGIONS)
     validate(outputRegion, "T-Junction free region");
@@ -222,7 +224,8 @@ Region& Region::operator = (const Region& rhs)
     validate(*this, "this->operator=");
     validate(rhs, "rhs.operator=");
 #endif
-    mStorage = rhs.mStorage;
+    mStorage.clear();
+    mStorage.insert(mStorage.begin(), rhs.mStorage.begin(), rhs.mStorage.end());
     return *this;
 }
 
@@ -231,7 +234,7 @@ Region& Region::makeBoundsSelf()
     if (mStorage.size() >= 2) {
         const Rect bounds(getBounds());
         mStorage.clear();
-        mStorage.add(bounds);
+        mStorage.push_back(bounds);
     }
     return *this;
 }
@@ -255,25 +258,25 @@ bool Region::contains(int x, int y) const {
 void Region::clear()
 {
     mStorage.clear();
-    mStorage.add(Rect(0,0));
+    mStorage.push_back(Rect(0, 0));
 }
 
 void Region::set(const Rect& r)
 {
     mStorage.clear();
-    mStorage.add(r);
+    mStorage.push_back(r);
 }
 
 void Region::set(int32_t w, int32_t h)
 {
     mStorage.clear();
-    mStorage.add(Rect(w, h));
+    mStorage.push_back(Rect(w, h));
 }
 
 void Region::set(uint32_t w, uint32_t h)
 {
     mStorage.clear();
-    mStorage.add(Rect(w, h));
+    mStorage.push_back(Rect(w, h));
 }
 
 bool Region::isTriviallyEqual(const Region& region) const {
@@ -299,8 +302,7 @@ bool Region::hasSameRects(const Region& other) const {
 void Region::addRectUnchecked(int l, int t, int r, int b)
 {
     Rect rect(l,t,r,b);
-    size_t where = mStorage.size() - 1;
-    mStorage.insertAt(rect, where, 1);
+    mStorage.insert(mStorage.end() - 1, rect);
 }
 
 // ----------------------------------------------------------------------------
@@ -350,7 +352,7 @@ Region& Region::translateSelf(int x, int y) {
 
 Region& Region::scaleSelf(float sx, float sy) {
     size_t count = mStorage.size();
-    Rect* rects = mStorage.editArray();
+    Rect* rects = mStorage.data();
     while (count) {
         rects->left = static_cast<int32_t>(static_cast<float>(rects->left) * sx + 0.5f);
         rects->right = static_cast<int32_t>(static_cast<float>(rects->right) * sx + 0.5f);
@@ -455,10 +457,10 @@ const Region Region::operation(const Region& rhs, int dx, int dy, uint32_t op) c
 class Region::rasterizer : public region_operator<Rect>::region_rasterizer
 {
     Rect bounds;
-    Vector<Rect>& storage;
+    FatVector<Rect>& storage;
     Rect* head;
     Rect* tail;
-    Vector<Rect> span;
+    FatVector<Rect> span;
     Rect* cur;
 public:
     explicit rasterizer(Region& reg)
@@ -485,8 +487,8 @@ Region::rasterizer::~rasterizer()
         flushSpan();
     }
     if (storage.size()) {
-        bounds.top = storage.itemAt(0).top;
-        bounds.bottom = storage.top().bottom;
+        bounds.top = storage.front().top;
+        bounds.bottom = storage.back().bottom;
         if (storage.size() == 1) {
             storage.clear();
         }
@@ -494,7 +496,7 @@ Region::rasterizer::~rasterizer()
         bounds.left  = 0;
         bounds.right = 0;
     }
-    storage.add(bounds);
+    storage.push_back(bounds);
 }
 
 void Region::rasterizer::operator()(const Rect& rect)
@@ -509,15 +511,15 @@ void Region::rasterizer::operator()(const Rect& rect)
             return;
         }
     }
-    span.add(rect);
-    cur = span.editArray() + (span.size() - 1);
+    span.push_back(rect);
+    cur = span.data() + (span.size() - 1);
 }
 
 void Region::rasterizer::flushSpan()
 {
     bool merge = false;
     if (tail-head == ssize_t(span.size())) {
-        Rect const* p = span.editArray();
+        Rect const* p = span.data();
         Rect const* q = head;
         if (p->top == q->bottom) {
             merge = true;
@@ -532,17 +534,17 @@ void Region::rasterizer::flushSpan()
         }
     }
     if (merge) {
-        const int bottom = span[0].bottom;
+        const int bottom = span.front().bottom;
         Rect* r = head;
         while (r != tail) {
             r->bottom = bottom;
             r++;
         }
     } else {
-        bounds.left = min(span.itemAt(0).left, bounds.left);
-        bounds.right = max(span.top().right, bounds.right);
-        storage.appendVector(span);
-        tail = storage.editArray() + storage.size();
+        bounds.left = min(span.front().left, bounds.left);
+        bounds.right = max(span.back().right, bounds.right);
+        storage.insert(storage.end(), span.begin(), span.end());
+        tail = storage.data() + storage.size();
         head = tail - span.size();
     }
     span.clear();
@@ -550,7 +552,7 @@ void Region::rasterizer::flushSpan()
 
 bool Region::validate(const Region& reg, const char* name, bool silent)
 {
-    if (reg.mStorage.isEmpty()) {
+    if (reg.mStorage.empty()) {
         ALOGE_IF(!silent, "%s: mStorage is empty, which is never valid", name);
         // return immediately as the code below assumes mStorage is non-empty
         return false;
@@ -689,9 +691,8 @@ void Region::boolean_operation(uint32_t op, Region& dst,
     }
     sk_dst.op(sk_lhs, sk_rhs, sk_op);
 
-    if (sk_dst.isEmpty() && dst.isEmpty())
-        return;
-    
+    if (sk_dst.empty() && dst.empty()) return;
+
     bool same = true;
     Region::const_iterator head = dst.begin();
     Region::const_iterator const tail = dst.end();
@@ -786,7 +787,7 @@ void Region::translate(Region& reg, int dx, int dy)
         validate(reg, "translate (before)");
 #endif
         size_t count = reg.mStorage.size();
-        Rect* rects = reg.mStorage.editArray();
+        Rect* rects = reg.mStorage.data();
         while (count) {
             rects->offsetBy(dx, dy);
             rects++;
@@ -866,24 +867,25 @@ status_t Region::unflatten(void const* buffer, size_t size) {
         ALOGE("Region::unflatten() failed, invalid region");
         return BAD_VALUE;
     }
-    mStorage = result.mStorage;
+    mStorage.clear();
+    mStorage.insert(mStorage.begin(), result.mStorage.begin(), result.mStorage.end());
     return NO_ERROR;
 }
 
 // ----------------------------------------------------------------------------
 
 Region::const_iterator Region::begin() const {
-    return mStorage.array();
+    return mStorage.data();
 }
 
 Region::const_iterator Region::end() const {
     // Workaround for b/77643177
     // mStorage should never be empty, but somehow it is and it's causing
     // an abort in ubsan
-    if (mStorage.isEmpty()) return mStorage.array();
+    if (mStorage.empty()) return mStorage.data();
 
     size_t numRects = isRect() ? 1 : mStorage.size() - 1;
-    return mStorage.array() + numRects;
+    return mStorage.data() + numRects;
 }
 
 Rect const* Region::getArray(size_t* count) const {
diff --git a/libs/ui/include/ui/FatVector.h b/libs/ui/include/ui/FatVector.h
new file mode 100644
index 0000000000..25fe3a0a2a
--- /dev/null
+++ b/libs/ui/include/ui/FatVector.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright 2019, 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_REGION_FAT_VECTOR_H
+#define ANDROID_REGION_FAT_VECTOR_H
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <utils/Log.h>
+#include <type_traits>
+
+#include <vector>
+
+namespace android {
+
+template <typename T, size_t SIZE = 4>
+class InlineStdAllocator {
+public:
+    struct Allocation {
+    private:
+        Allocation(const Allocation&) = delete;
+        void operator=(const Allocation&) = delete;
+
+    public:
+        Allocation() {}
+        // char array instead of T array, so memory is uninitialized, with no destructors run
+        char array[sizeof(T) * SIZE];
+        bool inUse = false;
+    };
+
+    typedef T value_type; // needed to implement std::allocator
+    typedef T* pointer;   // needed to implement std::allocator
+
+    explicit InlineStdAllocator(Allocation& allocation) : mAllocation(allocation) {}
+    InlineStdAllocator(const InlineStdAllocator& other) : mAllocation(other.mAllocation) {}
+    ~InlineStdAllocator() {}
+
+    T* allocate(size_t num, const void* = 0) {
+        if (!mAllocation.inUse && num <= SIZE) {
+            mAllocation.inUse = true;
+            return static_cast<T*>(static_cast<void*>(mAllocation.array));
+        } else {
+            return static_cast<T*>(static_cast<void*>(malloc(num * sizeof(T))));
+        }
+    }
+
+    void deallocate(pointer p, size_t) {
+        if (p == static_cast<T*>(static_cast<void*>(mAllocation.array))) {
+            mAllocation.inUse = false;
+        } else {
+            // 'free' instead of delete here - destruction handled separately
+            free(p);
+        }
+    }
+    Allocation& mAllocation;
+};
+
+/**
+ * std::vector with SIZE elements preallocated into an internal buffer.
+ *
+ * Useful for avoiding the cost of malloc in cases where only SIZE or
+ * fewer elements are needed in the common case.
+ */
+template <typename T, size_t SIZE = 4>
+class FatVector : public std::vector<T, InlineStdAllocator<T, SIZE>> {
+public:
+    FatVector()
+          : std::vector<T, InlineStdAllocator<T, SIZE>>(InlineStdAllocator<T, SIZE>(mAllocation)) {
+        this->reserve(SIZE);
+    }
+
+    explicit FatVector(size_t capacity) : FatVector() { this->resize(capacity); }
+
+private:
+    typename InlineStdAllocator<T, SIZE>::Allocation mAllocation;
+};
+
+} // namespace android
+
+#endif // ANDROID_REGION_FAT_VECTOR_H
diff --git a/libs/ui/include/ui/Region.h b/libs/ui/include/ui/Region.h
index 2db3b10f13..6bb7b8d21c 100644
--- a/libs/ui/include/ui/Region.h
+++ b/libs/ui/include/ui/Region.h
@@ -21,13 +21,13 @@
 #include <sys/types.h>
 #include <ostream>
 
-#include <utils/Vector.h>
-
 #include <ui/Rect.h>
 #include <utils/Flattenable.h>
 
 #include <android-base/macros.h>
 
+#include "FatVector.h"
+
 #include <string>
 
 namespace android {
@@ -180,7 +180,7 @@ private:
     // with an extra Rect as the last element which is set to the
     // bounds of the region. However, if the region is
     // a simple Rect then mStorage contains only that rect.
-    Vector<Rect> mStorage;
+    FatVector<Rect> mStorage;
 };
 
 
@@ -235,4 +235,3 @@ static inline void PrintTo(const Region& region, ::std::ostream* os) {
 }; // namespace android
 
 #endif // ANDROID_UI_REGION_H
-
diff --git a/libs/ui/include_vndk/ui/FatVector.h b/libs/ui/include_vndk/ui/FatVector.h
new file mode 120000
index 0000000000..bf30166784
--- /dev/null
+++ b/libs/ui/include_vndk/ui/FatVector.h
@@ -0,0 +1 @@
+../../include/ui/FatVector.h
\ No newline at end of file