Home | History | Annotate | Download | only in ui
      1 /*
      2  * Copyright (C) 2007 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #define LOG_TAG "Region"
     18 
     19 #include <inttypes.h>
     20 #include <limits.h>
     21 
     22 #include <utils/Log.h>
     23 #include <utils/String8.h>
     24 #include <utils/CallStack.h>
     25 
     26 #include <ui/Rect.h>
     27 #include <ui/Region.h>
     28 #include <ui/Point.h>
     29 
     30 #include <private/ui/RegionHelper.h>
     31 
     32 // ----------------------------------------------------------------------------
     33 #define VALIDATE_REGIONS        (false)
     34 #define VALIDATE_WITH_CORECG    (false)
     35 // ----------------------------------------------------------------------------
     36 
     37 #if VALIDATE_WITH_CORECG
     38 #include <core/SkRegion.h>
     39 #endif
     40 
     41 namespace android {
     42 // ----------------------------------------------------------------------------
     43 
     44 enum {
     45     op_nand = region_operator<Rect>::op_nand,
     46     op_and  = region_operator<Rect>::op_and,
     47     op_or   = region_operator<Rect>::op_or,
     48     op_xor  = region_operator<Rect>::op_xor
     49 };
     50 
     51 enum {
     52     direction_LTR,
     53     direction_RTL
     54 };
     55 
     56 const Region Region::INVALID_REGION(Rect::INVALID_RECT);
     57 
     58 // ----------------------------------------------------------------------------
     59 
     60 Region::Region() {
     61     mStorage.add(Rect(0,0));
     62 }
     63 
     64 Region::Region(const Region& rhs)
     65     : mStorage(rhs.mStorage)
     66 {
     67 #if VALIDATE_REGIONS
     68     validate(rhs, "rhs copy-ctor");
     69 #endif
     70 }
     71 
     72 Region::Region(const Rect& rhs) {
     73     mStorage.add(rhs);
     74 }
     75 
     76 Region::~Region()
     77 {
     78 }
     79 
     80 /**
     81  * Copy rects from the src vector into the dst vector, resolving vertical T-Junctions along the way
     82  *
     83  * First pass through, divideSpanRTL will be set because the 'previous span' (indexing into the dst
     84  * vector) will be reversed. Each rectangle in the original list, starting from the bottom, will be
     85  * compared with the span directly below, and subdivided as needed to resolve T-junctions.
     86  *
     87  * The resulting temporary vector will be a completely reversed copy of the original, without any
     88  * bottom-up T-junctions.
     89  *
     90  * Second pass through, divideSpanRTL will be false since the previous span will index into the
     91  * final, correctly ordered region buffer. Each rectangle will be compared with the span directly
     92  * above it, and subdivided to resolve any remaining T-junctions.
     93  */
     94 static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
     95         Vector<Rect>& dst, int spanDirection) {
     96     dst.clear();
     97 
     98     const Rect* current = end - 1;
     99     int lastTop = current->top;
    100 
    101     // add first span immediately
    102     do {
    103         dst.add(*current);
    104         current--;
    105     } while (current->top == lastTop && current >= begin);
    106 
    107     int beginLastSpan = -1;
    108     int endLastSpan = -1;
    109     int top = -1;
    110     int bottom = -1;
    111 
    112     // for all other spans, split if a t-junction exists in the span directly above
    113     while (current >= begin) {
    114         if (current->top != (current + 1)->top) {
    115             // new span
    116             if ((spanDirection == direction_RTL && current->bottom != (current + 1)->top) ||
    117                     (spanDirection == direction_LTR && current->top != (current + 1)->bottom)) {
    118                 // previous span not directly adjacent, don't check for T junctions
    119                 beginLastSpan = INT_MAX;
    120             } else {
    121                 beginLastSpan = endLastSpan + 1;
    122             }
    123             endLastSpan = static_cast<int>(dst.size()) - 1;
    124 
    125             top = current->top;
    126             bottom = current->bottom;
    127         }
    128         int left = current->left;
    129         int right = current->right;
    130 
    131         for (int prevIndex = beginLastSpan; prevIndex <= endLastSpan; prevIndex++) {
    132             // prevIndex can't be -1 here because if endLastSpan is set to a
    133             // value greater than -1 (allowing the loop to execute),
    134             // beginLastSpan (and therefore prevIndex) will also be increased
    135             const Rect prev = dst[static_cast<size_t>(prevIndex)];
    136             if (spanDirection == direction_RTL) {
    137                 // iterating over previous span RTL, quit if it's too far left
    138                 if (prev.right <= left) break;
    139 
    140                 if (prev.right > left && prev.right < right) {
    141                     dst.add(Rect(prev.right, top, right, bottom));
    142                     right = prev.right;
    143                 }
    144 
    145                 if (prev.left > left && prev.left < right) {
    146                     dst.add(Rect(prev.left, top, right, bottom));
    147                     right = prev.left;
    148                 }
    149 
    150                 // if an entry in the previous span is too far right, nothing further left in the
    151                 // current span will need it
    152                 if (prev.left >= right) {
    153                     beginLastSpan = prevIndex;
    154                 }
    155             } else {
    156                 // iterating over previous span LTR, quit if it's too far right
    157                 if (prev.left >= right) break;
    158 
    159                 if (prev.left > left && prev.left < right) {
    160                     dst.add(Rect(left, top, prev.left, bottom));
    161                     left = prev.left;
    162                 }
    163 
    164                 if (prev.right > left && prev.right < right) {
    165                     dst.add(Rect(left, top, prev.right, bottom));
    166                     left = prev.right;
    167                 }
    168                 // if an entry in the previous span is too far left, nothing further right in the
    169                 // current span will need it
    170                 if (prev.right <= left) {
    171                     beginLastSpan = prevIndex;
    172                 }
    173             }
    174         }
    175 
    176         if (left < right) {
    177             dst.add(Rect(left, top, right, bottom));
    178         }
    179 
    180         current--;
    181     }
    182 }
    183 
    184 /**
    185  * Creates a new region with the same data as the argument, but divides rectangles as necessary to
    186  * remove T-Junctions
    187  *
    188  * Note: the output will not necessarily be a very efficient representation of the region, since it
    189  * may be that a triangle-based approach would generate significantly simpler geometry
    190  */
    191 Region Region::createTJunctionFreeRegion(const Region& r) {
    192     if (r.isEmpty()) return r;
    193     if (r.isRect()) return r;
    194 
    195     Vector<Rect> reversed;
    196     reverseRectsResolvingJunctions(r.begin(), r.end(), reversed, direction_RTL);
    197 
    198     Region outputRegion;
    199     reverseRectsResolvingJunctions(reversed.begin(), reversed.end(),
    200             outputRegion.mStorage, direction_LTR);
    201     outputRegion.mStorage.add(r.getBounds()); // to make region valid, mStorage must end with bounds
    202 
    203 #if VALIDATE_REGIONS
    204     validate(outputRegion, "T-Junction free region");
    205 #endif
    206 
    207     return outputRegion;
    208 }
    209 
    210 Region& Region::operator = (const Region& rhs)
    211 {
    212 #if VALIDATE_REGIONS
    213     validate(*this, "this->operator=");
    214     validate(rhs, "rhs.operator=");
    215 #endif
    216     mStorage = rhs.mStorage;
    217     return *this;
    218 }
    219 
    220 Region& Region::makeBoundsSelf()
    221 {
    222     if (mStorage.size() >= 2) {
    223         const Rect bounds(getBounds());
    224         mStorage.clear();
    225         mStorage.add(bounds);
    226     }
    227     return *this;
    228 }
    229 
    230 bool Region::contains(const Point& point) const {
    231     return contains(point.x, point.y);
    232 }
    233 
    234 bool Region::contains(int x, int y) const {
    235     const_iterator cur = begin();
    236     const_iterator const tail = end();
    237     while (cur != tail) {
    238         if (y >= cur->top && y < cur->bottom && x >= cur->left && x < cur->right) {
    239             return true;
    240         }
    241         cur++;
    242     }
    243     return false;
    244 }
    245 
    246 void Region::clear()
    247 {
    248     mStorage.clear();
    249     mStorage.add(Rect(0,0));
    250 }
    251 
    252 void Region::set(const Rect& r)
    253 {
    254     mStorage.clear();
    255     mStorage.add(r);
    256 }
    257 
    258 void Region::set(int32_t w, int32_t h)
    259 {
    260     mStorage.clear();
    261     mStorage.add(Rect(w, h));
    262 }
    263 
    264 void Region::set(uint32_t w, uint32_t h)
    265 {
    266     mStorage.clear();
    267     mStorage.add(Rect(w, h));
    268 }
    269 
    270 bool Region::isTriviallyEqual(const Region& region) const {
    271     return begin() == region.begin();
    272 }
    273 
    274 // ----------------------------------------------------------------------------
    275 
    276 void Region::addRectUnchecked(int l, int t, int r, int b)
    277 {
    278     Rect rect(l,t,r,b);
    279     size_t where = mStorage.size() - 1;
    280     mStorage.insertAt(rect, where, 1);
    281 }
    282 
    283 // ----------------------------------------------------------------------------
    284 
    285 Region& Region::orSelf(const Rect& r) {
    286     return operationSelf(r, op_or);
    287 }
    288 Region& Region::xorSelf(const Rect& r) {
    289     return operationSelf(r, op_xor);
    290 }
    291 Region& Region::andSelf(const Rect& r) {
    292     return operationSelf(r, op_and);
    293 }
    294 Region& Region::subtractSelf(const Rect& r) {
    295     return operationSelf(r, op_nand);
    296 }
    297 Region& Region::operationSelf(const Rect& r, int op) {
    298     Region lhs(*this);
    299     boolean_operation(op, *this, lhs, r);
    300     return *this;
    301 }
    302 
    303 // ----------------------------------------------------------------------------
    304 
    305 Region& Region::orSelf(const Region& rhs) {
    306     return operationSelf(rhs, op_or);
    307 }
    308 Region& Region::xorSelf(const Region& rhs) {
    309     return operationSelf(rhs, op_xor);
    310 }
    311 Region& Region::andSelf(const Region& rhs) {
    312     return operationSelf(rhs, op_and);
    313 }
    314 Region& Region::subtractSelf(const Region& rhs) {
    315     return operationSelf(rhs, op_nand);
    316 }
    317 Region& Region::operationSelf(const Region& rhs, int op) {
    318     Region lhs(*this);
    319     boolean_operation(op, *this, lhs, rhs);
    320     return *this;
    321 }
    322 
    323 Region& Region::translateSelf(int x, int y) {
    324     if (x|y) translate(*this, x, y);
    325     return *this;
    326 }
    327 
    328 // ----------------------------------------------------------------------------
    329 
    330 const Region Region::merge(const Rect& rhs) const {
    331     return operation(rhs, op_or);
    332 }
    333 const Region Region::mergeExclusive(const Rect& rhs) const {
    334     return operation(rhs, op_xor);
    335 }
    336 const Region Region::intersect(const Rect& rhs) const {
    337     return operation(rhs, op_and);
    338 }
    339 const Region Region::subtract(const Rect& rhs) const {
    340     return operation(rhs, op_nand);
    341 }
    342 const Region Region::operation(const Rect& rhs, int op) const {
    343     Region result;
    344     boolean_operation(op, result, *this, rhs);
    345     return result;
    346 }
    347 
    348 // ----------------------------------------------------------------------------
    349 
    350 const Region Region::merge(const Region& rhs) const {
    351     return operation(rhs, op_or);
    352 }
    353 const Region Region::mergeExclusive(const Region& rhs) const {
    354     return operation(rhs, op_xor);
    355 }
    356 const Region Region::intersect(const Region& rhs) const {
    357     return operation(rhs, op_and);
    358 }
    359 const Region Region::subtract(const Region& rhs) const {
    360     return operation(rhs, op_nand);
    361 }
    362 const Region Region::operation(const Region& rhs, int op) const {
    363     Region result;
    364     boolean_operation(op, result, *this, rhs);
    365     return result;
    366 }
    367 
    368 const Region Region::translate(int x, int y) const {
    369     Region result;
    370     translate(result, *this, x, y);
    371     return result;
    372 }
    373 
    374 // ----------------------------------------------------------------------------
    375 
    376 Region& Region::orSelf(const Region& rhs, int dx, int dy) {
    377     return operationSelf(rhs, dx, dy, op_or);
    378 }
    379 Region& Region::xorSelf(const Region& rhs, int dx, int dy) {
    380     return operationSelf(rhs, dx, dy, op_xor);
    381 }
    382 Region& Region::andSelf(const Region& rhs, int dx, int dy) {
    383     return operationSelf(rhs, dx, dy, op_and);
    384 }
    385 Region& Region::subtractSelf(const Region& rhs, int dx, int dy) {
    386     return operationSelf(rhs, dx, dy, op_nand);
    387 }
    388 Region& Region::operationSelf(const Region& rhs, int dx, int dy, int op) {
    389     Region lhs(*this);
    390     boolean_operation(op, *this, lhs, rhs, dx, dy);
    391     return *this;
    392 }
    393 
    394 // ----------------------------------------------------------------------------
    395 
    396 const Region Region::merge(const Region& rhs, int dx, int dy) const {
    397     return operation(rhs, dx, dy, op_or);
    398 }
    399 const Region Region::mergeExclusive(const Region& rhs, int dx, int dy) const {
    400     return operation(rhs, dx, dy, op_xor);
    401 }
    402 const Region Region::intersect(const Region& rhs, int dx, int dy) const {
    403     return operation(rhs, dx, dy, op_and);
    404 }
    405 const Region Region::subtract(const Region& rhs, int dx, int dy) const {
    406     return operation(rhs, dx, dy, op_nand);
    407 }
    408 const Region Region::operation(const Region& rhs, int dx, int dy, int op) const {
    409     Region result;
    410     boolean_operation(op, result, *this, rhs, dx, dy);
    411     return result;
    412 }
    413 
    414 // ----------------------------------------------------------------------------
    415 
    416 // This is our region rasterizer, which merges rects and spans together
    417 // to obtain an optimal region.
    418 class Region::rasterizer : public region_operator<Rect>::region_rasterizer
    419 {
    420     Rect bounds;
    421     Vector<Rect>& storage;
    422     Rect* head;
    423     Rect* tail;
    424     Vector<Rect> span;
    425     Rect* cur;
    426 public:
    427     rasterizer(Region& reg)
    428         : bounds(INT_MAX, 0, INT_MIN, 0), storage(reg.mStorage), head(), tail(), cur() {
    429         storage.clear();
    430     }
    431 
    432     virtual ~rasterizer();
    433 
    434     virtual void operator()(const Rect& rect);
    435 
    436 private:
    437     template<typename T>
    438     static inline T min(T rhs, T lhs) { return rhs < lhs ? rhs : lhs; }
    439     template<typename T>
    440     static inline T max(T rhs, T lhs) { return rhs > lhs ? rhs : lhs; }
    441 
    442     void flushSpan();
    443 };
    444 
    445 Region::rasterizer::~rasterizer()
    446 {
    447     if (span.size()) {
    448         flushSpan();
    449     }
    450     if (storage.size()) {
    451         bounds.top = storage.itemAt(0).top;
    452         bounds.bottom = storage.top().bottom;
    453         if (storage.size() == 1) {
    454             storage.clear();
    455         }
    456     } else {
    457         bounds.left  = 0;
    458         bounds.right = 0;
    459     }
    460     storage.add(bounds);
    461 }
    462 
    463 void Region::rasterizer::operator()(const Rect& rect)
    464 {
    465     //ALOGD(">>> %3d, %3d, %3d, %3d",
    466     //        rect.left, rect.top, rect.right, rect.bottom);
    467     if (span.size()) {
    468         if (cur->top != rect.top) {
    469             flushSpan();
    470         } else if (cur->right == rect.left) {
    471             cur->right = rect.right;
    472             return;
    473         }
    474     }
    475     span.add(rect);
    476     cur = span.editArray() + (span.size() - 1);
    477 }
    478 
    479 void Region::rasterizer::flushSpan()
    480 {
    481     bool merge = false;
    482     if (tail-head == ssize_t(span.size())) {
    483         Rect const* p = span.editArray();
    484         Rect const* q = head;
    485         if (p->top == q->bottom) {
    486             merge = true;
    487             while (q != tail) {
    488                 if ((p->left != q->left) || (p->right != q->right)) {
    489                     merge = false;
    490                     break;
    491                 }
    492                 p++, q++;
    493             }
    494         }
    495     }
    496     if (merge) {
    497         const int bottom = span[0].bottom;
    498         Rect* r = head;
    499         while (r != tail) {
    500             r->bottom = bottom;
    501             r++;
    502         }
    503     } else {
    504         bounds.left = min(span.itemAt(0).left, bounds.left);
    505         bounds.right = max(span.top().right, bounds.right);
    506         storage.appendVector(span);
    507         tail = storage.editArray() + storage.size();
    508         head = tail - span.size();
    509     }
    510     span.clear();
    511 }
    512 
    513 bool Region::validate(const Region& reg, const char* name, bool silent)
    514 {
    515     bool result = true;
    516     const_iterator cur = reg.begin();
    517     const_iterator const tail = reg.end();
    518     const_iterator prev = cur;
    519     Rect b(*prev);
    520     while (cur != tail) {
    521         if (cur->isValid() == false) {
    522             // We allow this particular flavor of invalid Rect, since it is used
    523             // as a signal value in various parts of the system
    524             if (*cur != Rect::INVALID_RECT) {
    525                 ALOGE_IF(!silent, "%s: region contains an invalid Rect", name);
    526                 result = false;
    527             }
    528         }
    529         if (cur->right > region_operator<Rect>::max_value) {
    530             ALOGE_IF(!silent, "%s: rect->right > max_value", name);
    531             result = false;
    532         }
    533         if (cur->bottom > region_operator<Rect>::max_value) {
    534             ALOGE_IF(!silent, "%s: rect->right > max_value", name);
    535             result = false;
    536         }
    537         if (prev != cur) {
    538             b.left   = b.left   < cur->left   ? b.left   : cur->left;
    539             b.top    = b.top    < cur->top    ? b.top    : cur->top;
    540             b.right  = b.right  > cur->right  ? b.right  : cur->right;
    541             b.bottom = b.bottom > cur->bottom ? b.bottom : cur->bottom;
    542             if ((*prev < *cur) == false) {
    543                 ALOGE_IF(!silent, "%s: region's Rects not sorted", name);
    544                 result = false;
    545             }
    546             if (cur->top == prev->top) {
    547                 if (cur->bottom != prev->bottom) {
    548                     ALOGE_IF(!silent, "%s: invalid span %p", name, cur);
    549                     result = false;
    550                 } else if (cur->left < prev->right) {
    551                     ALOGE_IF(!silent,
    552                             "%s: spans overlap horizontally prev=%p, cur=%p",
    553                             name, prev, cur);
    554                     result = false;
    555                 }
    556             } else if (cur->top < prev->bottom) {
    557                 ALOGE_IF(!silent,
    558                         "%s: spans overlap vertically prev=%p, cur=%p",
    559                         name, prev, cur);
    560                 result = false;
    561             }
    562             prev = cur;
    563         }
    564         cur++;
    565     }
    566     if (b != reg.getBounds()) {
    567         result = false;
    568         ALOGE_IF(!silent,
    569                 "%s: invalid bounds [%d,%d,%d,%d] vs. [%d,%d,%d,%d]", name,
    570                 b.left, b.top, b.right, b.bottom,
    571                 reg.getBounds().left, reg.getBounds().top,
    572                 reg.getBounds().right, reg.getBounds().bottom);
    573     }
    574     if (reg.mStorage.size() == 2) {
    575         result = false;
    576         ALOGE_IF(!silent, "%s: mStorage size is 2, which is never valid", name);
    577     }
    578     if (result == false && !silent) {
    579         reg.dump(name);
    580         CallStack stack(LOG_TAG);
    581     }
    582     return result;
    583 }
    584 
    585 void Region::boolean_operation(int op, Region& dst,
    586         const Region& lhs,
    587         const Region& rhs, int dx, int dy)
    588 {
    589 #if VALIDATE_REGIONS
    590     validate(lhs, "boolean_operation (before): lhs");
    591     validate(rhs, "boolean_operation (before): rhs");
    592     validate(dst, "boolean_operation (before): dst");
    593 #endif
    594 
    595     size_t lhs_count;
    596     Rect const * const lhs_rects = lhs.getArray(&lhs_count);
    597 
    598     size_t rhs_count;
    599     Rect const * const rhs_rects = rhs.getArray(&rhs_count);
    600 
    601     region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
    602     region_operator<Rect>::region rhs_region(rhs_rects, rhs_count, dx, dy);
    603     region_operator<Rect> operation(op, lhs_region, rhs_region);
    604     { // scope for rasterizer (dtor has side effects)
    605         rasterizer r(dst);
    606         operation(r);
    607     }
    608 
    609 #if VALIDATE_REGIONS
    610     validate(lhs, "boolean_operation: lhs");
    611     validate(rhs, "boolean_operation: rhs");
    612     validate(dst, "boolean_operation: dst");
    613 #endif
    614 
    615 #if VALIDATE_WITH_CORECG
    616     SkRegion sk_lhs;
    617     SkRegion sk_rhs;
    618     SkRegion sk_dst;
    619 
    620     for (size_t i=0 ; i<lhs_count ; i++)
    621         sk_lhs.op(
    622                 lhs_rects[i].left   + dx,
    623                 lhs_rects[i].top    + dy,
    624                 lhs_rects[i].right  + dx,
    625                 lhs_rects[i].bottom + dy,
    626                 SkRegion::kUnion_Op);
    627 
    628     for (size_t i=0 ; i<rhs_count ; i++)
    629         sk_rhs.op(
    630                 rhs_rects[i].left   + dx,
    631                 rhs_rects[i].top    + dy,
    632                 rhs_rects[i].right  + dx,
    633                 rhs_rects[i].bottom + dy,
    634                 SkRegion::kUnion_Op);
    635 
    636     const char* name = "---";
    637     SkRegion::Op sk_op;
    638     switch (op) {
    639         case op_or: sk_op = SkRegion::kUnion_Op; name="OR"; break;
    640         case op_xor: sk_op = SkRegion::kUnion_XOR; name="XOR"; break;
    641         case op_and: sk_op = SkRegion::kIntersect_Op; name="AND"; break;
    642         case op_nand: sk_op = SkRegion::kDifference_Op; name="NAND"; break;
    643     }
    644     sk_dst.op(sk_lhs, sk_rhs, sk_op);
    645 
    646     if (sk_dst.isEmpty() && dst.isEmpty())
    647         return;
    648 
    649     bool same = true;
    650     Region::const_iterator head = dst.begin();
    651     Region::const_iterator const tail = dst.end();
    652     SkRegion::Iterator it(sk_dst);
    653     while (!it.done()) {
    654         if (head != tail) {
    655             if (
    656                     head->left != it.rect().fLeft ||
    657                     head->top != it.rect().fTop ||
    658                     head->right != it.rect().fRight ||
    659                     head->bottom != it.rect().fBottom
    660             ) {
    661                 same = false;
    662                 break;
    663             }
    664         } else {
    665             same = false;
    666             break;
    667         }
    668         head++;
    669         it.next();
    670     }
    671 
    672     if (head != tail) {
    673         same = false;
    674     }
    675 
    676     if(!same) {
    677         ALOGD("---\nregion boolean %s failed", name);
    678         lhs.dump("lhs");
    679         rhs.dump("rhs");
    680         dst.dump("dst");
    681         ALOGD("should be");
    682         SkRegion::Iterator it(sk_dst);
    683         while (!it.done()) {
    684             ALOGD("    [%3d, %3d, %3d, %3d]",
    685                 it.rect().fLeft,
    686                 it.rect().fTop,
    687                 it.rect().fRight,
    688                 it.rect().fBottom);
    689             it.next();
    690         }
    691     }
    692 #endif
    693 }
    694 
    695 void Region::boolean_operation(int op, Region& dst,
    696         const Region& lhs,
    697         const Rect& rhs, int dx, int dy)
    698 {
    699     // We allow this particular flavor of invalid Rect, since it is used as a
    700     // signal value in various parts of the system
    701     if (!rhs.isValid() && rhs != Rect::INVALID_RECT) {
    702         ALOGE("Region::boolean_operation(op=%d) invalid Rect={%d,%d,%d,%d}",
    703                 op, rhs.left, rhs.top, rhs.right, rhs.bottom);
    704         return;
    705     }
    706 
    707 #if VALIDATE_WITH_CORECG || VALIDATE_REGIONS
    708     boolean_operation(op, dst, lhs, Region(rhs), dx, dy);
    709 #else
    710     size_t lhs_count;
    711     Rect const * const lhs_rects = lhs.getArray(&lhs_count);
    712 
    713     region_operator<Rect>::region lhs_region(lhs_rects, lhs_count);
    714     region_operator<Rect>::region rhs_region(&rhs, 1, dx, dy);
    715     region_operator<Rect> operation(op, lhs_region, rhs_region);
    716     { // scope for rasterizer (dtor has side effects)
    717         rasterizer r(dst);
    718         operation(r);
    719     }
    720 
    721 #endif
    722 }
    723 
    724 void Region::boolean_operation(int op, Region& dst,
    725         const Region& lhs, const Region& rhs)
    726 {
    727     boolean_operation(op, dst, lhs, rhs, 0, 0);
    728 }
    729 
    730 void Region::boolean_operation(int op, Region& dst,
    731         const Region& lhs, const Rect& rhs)
    732 {
    733     boolean_operation(op, dst, lhs, rhs, 0, 0);
    734 }
    735 
    736 void Region::translate(Region& reg, int dx, int dy)
    737 {
    738     if ((dx || dy) && !reg.isEmpty()) {
    739 #if VALIDATE_REGIONS
    740         validate(reg, "translate (before)");
    741 #endif
    742         size_t count = reg.mStorage.size();
    743         Rect* rects = reg.mStorage.editArray();
    744         while (count) {
    745             rects->offsetBy(dx, dy);
    746             rects++;
    747             count--;
    748         }
    749 #if VALIDATE_REGIONS
    750         validate(reg, "translate (after)");
    751 #endif
    752     }
    753 }
    754 
    755 void Region::translate(Region& dst, const Region& reg, int dx, int dy)
    756 {
    757     dst = reg;
    758     translate(dst, dx, dy);
    759 }
    760 
    761 // ----------------------------------------------------------------------------
    762 
    763 size_t Region::getFlattenedSize() const {
    764     return sizeof(uint32_t) + mStorage.size() * sizeof(Rect);
    765 }
    766 
    767 status_t Region::flatten(void* buffer, size_t size) const {
    768 #if VALIDATE_REGIONS
    769     validate(*this, "Region::flatten");
    770 #endif
    771     if (size < getFlattenedSize()) {
    772         return NO_MEMORY;
    773     }
    774     // Cast to uint32_t since the size of a size_t can vary between 32- and
    775     // 64-bit processes
    776     FlattenableUtils::write(buffer, size, static_cast<uint32_t>(mStorage.size()));
    777     for (auto rect : mStorage) {
    778         status_t result = rect.flatten(buffer, size);
    779         if (result != NO_ERROR) {
    780             return result;
    781         }
    782         FlattenableUtils::advance(buffer, size, sizeof(rect));
    783     }
    784     return NO_ERROR;
    785 }
    786 
    787 status_t Region::unflatten(void const* buffer, size_t size) {
    788     if (size < sizeof(uint32_t)) {
    789         return NO_MEMORY;
    790     }
    791 
    792     uint32_t numRects = 0;
    793     FlattenableUtils::read(buffer, size, numRects);
    794     if (size < numRects * sizeof(Rect)) {
    795         return NO_MEMORY;
    796     }
    797 
    798     Region result;
    799     result.mStorage.clear();
    800     for (size_t r = 0; r < numRects; ++r) {
    801         Rect rect;
    802         status_t status = rect.unflatten(buffer, size);
    803         if (status != NO_ERROR) {
    804             return status;
    805         }
    806         FlattenableUtils::advance(buffer, size, sizeof(rect));
    807         result.mStorage.push_back(rect);
    808     }
    809 
    810 #if VALIDATE_REGIONS
    811     validate(result, "Region::unflatten");
    812 #endif
    813 
    814     if (!result.validate(result, "Region::unflatten", true)) {
    815         ALOGE("Region::unflatten() failed, invalid region");
    816         return BAD_VALUE;
    817     }
    818     mStorage = result.mStorage;
    819     return NO_ERROR;
    820 }
    821 
    822 // ----------------------------------------------------------------------------
    823 
    824 Region::const_iterator Region::begin() const {
    825     return mStorage.array();
    826 }
    827 
    828 Region::const_iterator Region::end() const {
    829     size_t numRects = isRect() ? 1 : mStorage.size() - 1;
    830     return mStorage.array() + numRects;
    831 }
    832 
    833 Rect const* Region::getArray(size_t* count) const {
    834     if (count) *count = static_cast<size_t>(end() - begin());
    835     return begin();
    836 }
    837 
    838 SharedBuffer const* Region::getSharedBuffer(size_t* count) const {
    839     // We can get to the SharedBuffer of a Vector<Rect> because Rect has
    840     // a trivial destructor.
    841     SharedBuffer const* sb = SharedBuffer::bufferFromData(mStorage.array());
    842     if (count) {
    843         size_t numRects = isRect() ? 1 : mStorage.size() - 1;
    844         count[0] = numRects;
    845     }
    846     sb->acquire();
    847     return sb;
    848 }
    849 
    850 // ----------------------------------------------------------------------------
    851 
    852 void Region::dump(String8& out, const char* what, uint32_t /* flags */) const
    853 {
    854     const_iterator head = begin();
    855     const_iterator const tail = end();
    856 
    857     out.appendFormat("  Region %s (this=%p, count=%" PRIdPTR ")\n",
    858             what, this, tail - head);
    859     while (head != tail) {
    860         out.appendFormat("    [%3d, %3d, %3d, %3d]\n", head->left, head->top,
    861                 head->right, head->bottom);
    862         ++head;
    863     }
    864 }
    865 
    866 void Region::dump(const char* what, uint32_t /* flags */) const
    867 {
    868     const_iterator head = begin();
    869     const_iterator const tail = end();
    870     ALOGD("  Region %s (this=%p, count=%" PRIdPTR ")\n", what, this, tail-head);
    871     while (head != tail) {
    872         ALOGD("    [%3d, %3d, %3d, %3d]\n",
    873                 head->left, head->top, head->right, head->bottom);
    874         head++;
    875     }
    876 }
    877 
    878 // ----------------------------------------------------------------------------
    879 
    880 }; // namespace android
    881