Region now has its own implementation instead of relying on SkRegion, which allows us to break libui's dependency on libcorecg.

3 files changed, 370 insertions, 45 deletions

diff --git a/include/private/ui/RegionHelper.h b/include/private/ui/RegionHelper.h
new file mode 100644
index 0000000..6c847ff
--- /dev/null
+++ b/include/private/ui/RegionHelper.h
@@ -0,0 +1,279 @@
+/*
+ * Copyright (C) 2009 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_PRIVATE_REGION_HELPER_H
+#define ANDROID_UI_PRIVATE_REGION_HELPER_H
+
+#include <stdint.h>
+#include <sys/types.h>
+
+namespace android {
+// ----------------------------------------------------------------------------
+
+template<typename RECT>
+class region_operator
+{
+    typedef typename RECT::value_type TYPE;    
+    static const TYPE max_value = 0x7FFFFFF;
+
+public:
+    /* 
+     * Common boolean operations:
+     * value is computed as 0b101 op 0b110
+     *    other boolean operation are possible, simply compute
+     *    their corresponding value with the above formulae and use
+     *    it when instantiating a region_operator.
+     */
+    static const uint32_t LHS = 0x5;  // 0b101
+    static const uint32_t RHS = 0x6;  // 0b110
+    enum {
+        op_nand = LHS & ~RHS,
+        op_and  = LHS &  RHS,
+        op_or   = LHS |  RHS,
+        op_xor  = LHS ^  RHS
+    };
+
+    struct region {
+        RECT const* rects;
+        size_t count;
+        TYPE dx;
+        TYPE dy;
+        inline region(const region& rhs) 
+            : rects(rhs.rects), count(rhs.count), dx(rhs.dx), dy(rhs.dy) { }
+        inline region(RECT const* r, size_t c) 
+            : rects(r), count(c), dx(), dy() { }
+        inline region(RECT const* r, size_t c, TYPE dx, TYPE dy) 
+            : rects(r), count(c), dx(dx), dy(dy) { }
+    };
+
+    class region_rasterizer {
+        friend class region_operator;
+        virtual void operator()(const RECT& rect) = 0;
+    };
+    
+    inline region_operator(int op, const region& lhs, const region& rhs) 
+        : op_mask(op), spanner(lhs, rhs) 
+    {
+    }
+
+    void operator()(region_rasterizer& rasterizer) {
+        RECT current;
+        do {
+            SpannerInner spannerInner(spanner.lhs, spanner.rhs);
+            int inside = spanner.next(current.top, current.bottom);
+            spannerInner.prepare(inside);
+            do {
+                TYPE left, right;
+                int inside = spannerInner.next(current.left, current.right);
+                if ((op_mask >> inside) & 1) {
+                    if (current.left < current.right && 
+                            current.top < current.bottom) {
+                        rasterizer(current);
+                    }
+                }
+            } while(!spannerInner.isDone());            
+        } while(!spanner.isDone());
+    }
+
+private:    
+    uint32_t op_mask;
+
+    class SpannerBase
+    {
+    public:
+        enum {
+            lhs_before_rhs   = 0,
+            lhs_after_rhs    = 1,
+            lhs_coincide_rhs = 2
+        };
+
+    protected:
+        TYPE lhs_head;
+        TYPE lhs_tail;
+        TYPE rhs_head;
+        TYPE rhs_tail;
+
+        inline int next(TYPE& head, TYPE& tail,
+                bool& more_lhs, bool& more_rhs) 
+        {
+            int inside;
+            more_lhs = false;
+            more_rhs = false;
+            if (lhs_head < rhs_head) {
+                inside = lhs_before_rhs;
+                head = lhs_head;
+                if (lhs_tail <= rhs_head) {
+                    tail = lhs_tail;
+                    more_lhs = true;
+                } else {
+                    lhs_head = rhs_head;
+                    tail = rhs_head;
+                }
+            } else if (rhs_head < lhs_head) {
+                inside = lhs_after_rhs;
+                head = rhs_head;
+                if (rhs_tail <= lhs_head) {
+                    tail = rhs_tail;
+                    more_rhs = true;
+                } else {
+                    rhs_head = lhs_head;
+                    tail = lhs_head;
+                }
+            } else {
+                inside = lhs_coincide_rhs;
+                head = lhs_head;
+                if (lhs_tail <= rhs_tail) {
+                    tail = rhs_head = lhs_tail;
+                    more_lhs = true;
+                }
+                if (rhs_tail <= lhs_tail) {
+                    tail = lhs_head = rhs_tail;
+                    more_rhs = true;
+                }
+            }
+            return inside;
+        }
+    };
+
+    class Spanner : protected SpannerBase 
+    {
+        friend class region_operator;
+        region lhs;
+        region rhs;
+
+    public:
+        inline Spanner(const region& lhs, const region& rhs)
+            : lhs(lhs), rhs(rhs) 
+        {
+            SpannerBase::lhs_head = lhs.rects->top      + lhs.dy;
+            SpannerBase::lhs_tail = lhs.rects->bottom   + lhs.dy;
+            SpannerBase::rhs_head = rhs.rects->top      + rhs.dy;
+            SpannerBase::rhs_tail = rhs.rects->bottom   + rhs.dy;
+        }
+
+        inline bool isDone() const {
+            return !rhs.count && !lhs.count;
+        }
+
+        inline int next(TYPE& top, TYPE& bottom) 
+        {
+            bool more_lhs = false;
+            bool more_rhs = false;
+            int inside = SpannerBase::next(top, bottom, more_lhs, more_rhs);
+            if (more_lhs) {
+                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
+            }
+            if (more_rhs) {
+                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
+            }
+            return inside;
+        }
+
+    private:
+        static inline 
+        void advance(region& reg, TYPE& aTop, TYPE& aBottom) {
+            // got to next span
+            size_t count = reg.count;
+            RECT const * rects = reg.rects;
+            RECT const * const end = rects + count;
+            const int top = rects->top;
+            while (rects != end && rects->top == top) {
+                rects++;
+                count--;
+            }
+            if (rects != end) {
+                aTop    = rects->top    + reg.dy;
+                aBottom = rects->bottom + reg.dy;
+            } else {
+                aTop    = max_value;
+                aBottom = max_value;
+            }
+            reg.rects = rects;
+            reg.count = count;
+        }
+    };
+
+    class SpannerInner : protected SpannerBase 
+    {
+        region lhs;
+        region rhs;
+        
+    public:
+        inline SpannerInner(const region& lhs, const region& rhs)
+            : lhs(lhs), rhs(rhs) 
+        {
+        }
+
+        inline void prepare(int inside) {
+            SpannerBase::lhs_head = lhs.rects->left  + lhs.dx;
+            SpannerBase::lhs_tail = lhs.rects->right + lhs.dx;
+            SpannerBase::rhs_head = rhs.rects->left  + rhs.dx;
+            SpannerBase::rhs_tail = rhs.rects->right + rhs.dx;
+            if (inside == SpannerBase::lhs_before_rhs) {
+                SpannerBase::rhs_head = max_value;
+                SpannerBase::rhs_tail = max_value;
+            } else if (inside == SpannerBase::lhs_after_rhs) {
+                SpannerBase::lhs_head = max_value;
+                SpannerBase::lhs_tail = max_value;
+            } else {
+                // use both spans
+            }
+        }
+
+        inline bool isDone() const {
+            return SpannerBase::lhs_head == max_value && 
+                   SpannerBase::rhs_head == max_value;
+        }
+
+        inline int next(TYPE& left, TYPE& right) 
+        {
+            bool more_lhs = false;
+            bool more_rhs = false;
+            int inside = SpannerBase::next(left, right, more_lhs, more_rhs);
+            if (more_lhs) {
+                advance(lhs, SpannerBase::lhs_head, SpannerBase::lhs_tail);
+            }
+            if (more_rhs) {
+                advance(rhs, SpannerBase::rhs_head, SpannerBase::rhs_tail);
+            }
+            return inside;
+        }
+
+    private:
+        static inline 
+        void advance(region& reg, TYPE& left, TYPE& right) {
+            if (reg.rects && reg.count) {
+                const int cur_span_top = reg.rects->top;
+                reg.rects++;
+                reg.count--;
+                if (!reg.count || reg.rects->top != cur_span_top) {
+                    left  = max_value;
+                    right = max_value;
+                } else {
+                    left  = reg.rects->left  + reg.dx;
+                    right = reg.rects->right + reg.dx;
+                }
+            }
+        }
+    };
+
+    Spanner spanner;
+};
+
+// ----------------------------------------------------------------------------
+};
+
+#endif /* ANDROID_UI_PRIVATE_REGION_HELPER_H */
diff --git a/include/ui/Rect.h b/include/ui/Rect.h
index d232847..902324d 100644
--- a/include/ui/Rect.h
+++ b/include/ui/Rect.h
@@ -30,6 +30,8 @@ public:
     int right;
     int bottom;
 
+    typedef int value_type;
+    
     // we don't provide copy-ctor and operator= on purpose
     // because we want the compiler generated versions
 
@@ -54,6 +56,10 @@ public:
 
     void makeInvalid();
     
+    inline void clear() {
+        left = top = right = bottom = 0;
+    }
+    
     // a valid rectangle has a non negative width and height
     inline bool isValid() const {
         return (width()>=0) && (height()>=0);
@@ -78,28 +84,29 @@ public:
         return bottom-top;
     }
 
-    // returns left-top Point non-const reference, can be assigned
-    inline Point& leftTop() {
-        return reinterpret_cast<Point&>(left);
-    }
-    // returns right bottom non-const reference, can be assigned
-    inline Point& rightBottom() {
-        return reinterpret_cast<Point&>(right);
-    }
-    
     // the following 4 functions return the 4 corners of the rect as Point
-    inline const Point& leftTop() const {
-        return reinterpret_cast<const Point&>(left);
+    inline Point leftTop() const {
+        return Point(left, top);
     }
-    inline const Point& rightBottom() const {
-        return reinterpret_cast<const Point&>(right);
+    inline Point rightBottom() const {
+        return Point(right, bottom);
     }
-    Point rightTop() const {
+    inline Point rightTop() const {
         return Point(right, top);
     }
-    Point leftBottom() const {
+    inline Point leftBottom() const {
         return Point(left, bottom);
     }
+    
+    inline void setLeftTop(const Point& p) {
+        left = p.x;
+        top  = p.y;
+    }
+
+    inline void setRightBottom(const Point& p) {
+        right  = p.x;
+        bottom = p.y;
+    }
 
     // comparisons
     inline bool operator == (const Rect& rhs) const {
diff --git a/include/ui/Region.h b/include/ui/Region.h
index 5efeff7..849369d 100644
--- a/include/ui/Region.h
+++ b/include/ui/Region.h
@@ -27,8 +27,6 @@
 
 #include <hardware/copybit.h>
 
-#include <core/SkRegion.h>
-
 namespace android {
 // ---------------------------------------------------------------------------
 
@@ -40,7 +38,6 @@ class Region
 public:
                         Region();
                         Region(const Region& rhs);
-    explicit            Region(const SkRegion& rhs);
     explicit            Region(const Rect& rhs);
     explicit            Region(const Parcel& parcel);
     explicit            Region(const void* buffer);
@@ -48,12 +45,11 @@ public:
                         
         Region& operator = (const Region& rhs);
 
-    inline  bool        isEmpty() const     { return mRegion.isEmpty(); }
-    inline  bool        isRect() const      { return mRegion.isRect(); }
-
-            Rect        bounds() const;
+    inline  bool        isEmpty() const     { return mBounds.isEmpty();  }
+    inline  bool        isRect() const      { return mStorage.isEmpty(); }
 
-            const SkRegion& toSkRegion() const;
+    inline  const Rect& getBounds() const   { return mBounds; }
+    inline  const Rect& bounds() const      { return getBounds(); }
 
             void        clear();
             void        set(const Rect& r);
@@ -61,17 +57,17 @@ public:
         
             Region&     orSelf(const Rect& rhs);
             Region&     andSelf(const Rect& rhs);
+            Region&     subtractSelf(const Rect& rhs);
 
             // boolean operators, applied on this
             Region&     orSelf(const Region& rhs);
             Region&     andSelf(const Region& rhs);
             Region&     subtractSelf(const Region& rhs);
 
-            // these translate rhs first
-            Region&     translateSelf(int dx, int dy);
-            Region&     orSelf(const Region& rhs, int dx, int dy);
-            Region&     andSelf(const Region& rhs, int dx, int dy);
-            Region&     subtractSelf(const Region& rhs, int dx, int dy);
+            // boolean operators
+            Region      merge(const Rect& rhs) const;
+            Region      intersect(const Rect& rhs) const;
+            Region      subtract(const Rect& rhs) const;
 
             // boolean operators
             Region      merge(const Region& rhs) const;
@@ -79,6 +75,12 @@ public:
             Region      subtract(const Region& rhs) const;
 
             // these translate rhs first
+            Region&     translateSelf(int dx, int dy);
+            Region&     orSelf(const Region& rhs, int dx, int dy);
+            Region&     andSelf(const Region& rhs, int dx, int dy);
+            Region&     subtractSelf(const Region& rhs, int dx, int dy);
+
+            // these translate rhs first
             Region      translate(int dx, int dy) const;
             Region      merge(const Region& rhs, int dx, int dy) const;
             Region      intersect(const Region& rhs, int dx, int dy) const;
@@ -95,19 +97,23 @@ public:
     inline  Region&     operator -= (const Region& rhs);
     inline  Region&     operator += (const Point& pt);
 
-    class iterator {
-        SkRegion::Iterator  mIt;
-    public:
-        iterator(const Region& r);
-        inline operator bool () const { return !done(); }
-        int iterate(Rect* rect);
-    private:
-        inline bool done() const {
-            return const_cast<SkRegion::Iterator&>(mIt).done();
-        }
-    };
+    
+    /* various ways to access the rectangle list */
+    
+    typedef Rect const* const_iterator;
+    
+            const_iterator begin() const;
+            const_iterator end() const;
+
+    /* no user serviceable parts here... */
+            
+            size_t      getRects(Vector<Rect>& rectList) const;
+            Rect const* getArray(size_t* count) const;
 
-            size_t      rects(Vector<Rect>& rectList) const;
+            
+            // add a rectangle to the internal list. This rectangle must
+            // be sorted in Y and X and must not make the region invalid.
+            void        addRectUnchecked(int l, int t, int r, int b);
 
             // flatten/unflatten a region to/from a Parcel
             status_t    write(Parcel& parcel) const;
@@ -124,7 +130,33 @@ public:
     void        dump(const char* what, uint32_t flags=0) const;
 
 private:
-    SkRegion    mRegion;
+    class rasterizer;
+    friend class rasterizer;
+    
+    Region& operationSelf(const Rect& r, int op);
+    Region& operationSelf(const Region& r, int op);
+    Region& operationSelf(const Region& r, int dx, int dy, int op);
+    Region operation(const Rect& rhs, int op) const;
+    Region operation(const Region& rhs, int op) const;
+    Region operation(const Region& rhs, int dx, int dy, int op) const;
+
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Region& rhs, int dx, int dy);
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Rect& rhs, int dx, int dy);
+
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Region& rhs);
+    static void boolean_operation(int op, Region& dst,
+            const Region& lhs, const Rect& rhs);
+
+    static void translate(Region& reg, int dx, int dy);
+    static void translate(Region& dst, const Region& reg, int dx, int dy);
+
+    static bool validate(const Region& reg, const char* name);
+    
+    Rect            mBounds;
+    Vector<Rect>    mStorage;
 };
 
 
@@ -158,16 +190,23 @@ Region& Region::operator += (const Point& pt) {
 // ---------------------------------------------------------------------------
 
 struct region_iterator : public copybit_region_t {
-    region_iterator(const Region& region) : i(region) {
+    region_iterator(const Region& region)
+        : b(region.begin()), e(region.end()) {
         this->next = iterate;
     }
 private:
     static int iterate(copybit_region_t const * self, copybit_rect_t* rect) {
-        return static_cast<const region_iterator*>(self)
-        ->i.iterate(reinterpret_cast<Rect*>(rect));
+        region_iterator const* me = static_cast<region_iterator const*>(self);
+        if (me->b != me->e) {
+            *reinterpret_cast<Rect*>(rect) = *me->b++;
+            return 1;
+        }
+        return 0;
     }
-    mutable Region::iterator i;
+    mutable Region::const_iterator b;
+    Region::const_iterator const e;
 };
+
 // ---------------------------------------------------------------------------
 }; // namespace android