michael@0: 
michael@0: /*
michael@0:  * Copyright 2006 The Android Open Source Project
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: 
michael@0: #ifndef SkRegionPriv_DEFINED
michael@0: #define SkRegionPriv_DEFINED
michael@0: 
michael@0: #include "SkRegion.h"
michael@0: #include "SkThread.h"
michael@0: 
michael@0: #define assert_sentinel(value, isSentinel) \
michael@0:     SkASSERT(((value) == SkRegion::kRunTypeSentinel) == isSentinel)
michael@0: 
michael@0: //SkDEBUGCODE(extern int32_t gRgnAllocCounter;)
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: // Given the first interval (just past the interval-count), compute the
michael@0: // interval count, by search for the x-sentinel
michael@0: //
michael@0: static int compute_intervalcount(const SkRegion::RunType runs[]) {
michael@0:     const SkRegion::RunType* curr = runs;
michael@0:     while (*curr < SkRegion::kRunTypeSentinel) {
michael@0:         SkASSERT(curr[0] < curr[1]);
michael@0:         SkASSERT(curr[1] < SkRegion::kRunTypeSentinel);
michael@0:         curr += 2;
michael@0:     }
michael@0:     return (curr - runs) >> 1;
michael@0: }
michael@0: #endif
michael@0: 
michael@0: struct SkRegion::RunHead {
michael@0: private:
michael@0: 
michael@0: public:
michael@0:     int32_t fRefCnt;
michael@0:     int32_t fRunCount;
michael@0: 
michael@0:     /**
michael@0:      *  Number of spans with different Y values. This does not count the initial
michael@0:      *  Top value, nor does it count the final Y-Sentinel value. In the logical
michael@0:      *  case of a rectangle, this would return 1, and an empty region would
michael@0:      *  return 0.
michael@0:      */
michael@0:     int getYSpanCount() const {
michael@0:         return fYSpanCount;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Number of intervals in the entire region. This equals the number of
michael@0:      *  rects that would be returned by the Iterator. In the logical case of
michael@0:      *  a rect, this would return 1, and an empty region would return 0.
michael@0:      */
michael@0:     int getIntervalCount() const {
michael@0:         return fIntervalCount;
michael@0:     }
michael@0: 
michael@0:     static RunHead* Alloc(int count) {
michael@0:         //SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
michael@0:         //SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
michael@0: 
michael@0:         SkASSERT(count >= SkRegion::kRectRegionRuns);
michael@0: 
michael@0:         RunHead* head = (RunHead*)sk_malloc_throw(sizeof(RunHead) + count * sizeof(RunType));
michael@0:         head->fRefCnt = 1;
michael@0:         head->fRunCount = count;
michael@0:         // these must be filled in later, otherwise we will be invalid
michael@0:         head->fYSpanCount = 0;
michael@0:         head->fIntervalCount = 0;
michael@0:         return head;
michael@0:     }
michael@0: 
michael@0:     static RunHead* Alloc(int count, int yspancount, int intervalCount) {
michael@0:         SkASSERT(yspancount > 0);
michael@0:         SkASSERT(intervalCount > 1);
michael@0: 
michael@0:         RunHead* head = Alloc(count);
michael@0:         head->fYSpanCount = yspancount;
michael@0:         head->fIntervalCount = intervalCount;
michael@0:         return head;
michael@0:     }
michael@0: 
michael@0:     SkRegion::RunType* writable_runs() {
michael@0:         SkASSERT(fRefCnt == 1);
michael@0:         return (SkRegion::RunType*)(this + 1);
michael@0:     }
michael@0: 
michael@0:     const SkRegion::RunType* readonly_runs() const {
michael@0:         return (const SkRegion::RunType*)(this + 1);
michael@0:     }
michael@0: 
michael@0:     RunHead* ensureWritable() {
michael@0:         RunHead* writable = this;
michael@0:         if (fRefCnt > 1) {
michael@0:             // We need to alloc & copy the current region before we call
michael@0:             // sk_atomic_dec because it could be freed in the meantime,
michael@0:             // otherwise.
michael@0:             writable = Alloc(fRunCount, fYSpanCount, fIntervalCount);
michael@0:             memcpy(writable->writable_runs(), this->readonly_runs(),
michael@0:                    fRunCount * sizeof(RunType));
michael@0: 
michael@0:             // fRefCount might have changed since we last checked.
michael@0:             // If we own the last reference at this point, we need to
michael@0:             // free the memory.
michael@0:             if (sk_atomic_dec(&fRefCnt) == 1) {
michael@0:                 sk_free(this);
michael@0:             }
michael@0:         }
michael@0:         return writable;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      *  Given a scanline (including its Bottom value at runs[0]), return the next
michael@0:      *  scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
michael@0:      */
michael@0:     static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
michael@0:         // we are not the Y Sentinel
michael@0:         SkASSERT(runs[0] < SkRegion::kRunTypeSentinel);
michael@0: 
michael@0:         const int intervals = runs[1];
michael@0:         SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel);
michael@0: #ifdef SK_DEBUG
michael@0:         {
michael@0:             int n = compute_intervalcount(&runs[2]);
michael@0:             SkASSERT(n == intervals);
michael@0:         }
michael@0: #endif
michael@0: 
michael@0:         // skip the entire line [B N [L R] S]
michael@0:         runs += 1 + 1 + intervals * 2 + 1;
michael@0:         return const_cast<SkRegion::RunType*>(runs);
michael@0:     }
michael@0: 
michael@0: 
michael@0:     /**
michael@0:      *  Return the scanline that contains the Y value. This requires that the Y
michael@0:      *  value is already known to be contained within the bounds of the region,
michael@0:      *  and so this routine never returns NULL.
michael@0:      *
michael@0:      *  It returns the beginning of the scanline, starting with its Bottom value.
michael@0:      */
michael@0:     SkRegion::RunType* findScanline(int y) const {
michael@0:         const RunType* runs = this->readonly_runs();
michael@0: 
michael@0:         // if the top-check fails, we didn't do a quick check on the bounds
michael@0:         SkASSERT(y >= runs[0]);
michael@0: 
michael@0:         runs += 1;  // skip top-Y
michael@0:         for (;;) {
michael@0:             int bottom = runs[0];
michael@0:             // If we hit this, we've walked off the region, and our bounds check
michael@0:             // failed.
michael@0:             SkASSERT(bottom < SkRegion::kRunTypeSentinel);
michael@0:             if (y < bottom) {
michael@0:                 break;
michael@0:             }
michael@0:             runs = SkipEntireScanline(runs);
michael@0:         }
michael@0:         return const_cast<SkRegion::RunType*>(runs);
michael@0:     }
michael@0: 
michael@0:     // Copy src runs into us, computing interval counts and bounds along the way
michael@0:     void computeRunBounds(SkIRect* bounds) {
michael@0:         RunType* runs = this->writable_runs();
michael@0:         bounds->fTop = *runs++;
michael@0: 
michael@0:         int bot;
michael@0:         int ySpanCount = 0;
michael@0:         int intervalCount = 0;
michael@0:         int left = SK_MaxS32;
michael@0:         int rite = SK_MinS32;
michael@0: 
michael@0:         do {
michael@0:             bot = *runs++;
michael@0:             SkASSERT(bot < SkRegion::kRunTypeSentinel);
michael@0:             ySpanCount += 1;
michael@0: 
michael@0:             const int intervals = *runs++;
michael@0:             SkASSERT(intervals >= 0);
michael@0:             SkASSERT(intervals < SkRegion::kRunTypeSentinel);
michael@0: 
michael@0:             if (intervals > 0) {
michael@0: #ifdef SK_DEBUG
michael@0:                 {
michael@0:                     int n = compute_intervalcount(runs);
michael@0:                     SkASSERT(n == intervals);
michael@0:                 }
michael@0: #endif
michael@0:                 RunType L = runs[0];
michael@0:                 SkASSERT(L < SkRegion::kRunTypeSentinel);
michael@0:                 if (left > L) {
michael@0:                     left = L;
michael@0:                 }
michael@0: 
michael@0:                 runs += intervals * 2;
michael@0:                 RunType R = runs[-1];
michael@0:                 SkASSERT(R < SkRegion::kRunTypeSentinel);
michael@0:                 if (rite < R) {
michael@0:                     rite = R;
michael@0:                 }
michael@0: 
michael@0:                 intervalCount += intervals;
michael@0:             }
michael@0:             SkASSERT(SkRegion::kRunTypeSentinel == *runs);
michael@0:             runs += 1;  // skip x-sentinel
michael@0: 
michael@0:             // test Y-sentinel
michael@0:         } while (SkRegion::kRunTypeSentinel > *runs);
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:         // +1 to skip the last Y-sentinel
michael@0:         int runCount = runs - this->writable_runs() + 1;
michael@0:         SkASSERT(runCount == fRunCount);
michael@0: #endif
michael@0: 
michael@0:         fYSpanCount = ySpanCount;
michael@0:         fIntervalCount = intervalCount;
michael@0: 
michael@0:         bounds->fLeft = left;
michael@0:         bounds->fRight = rite;
michael@0:         bounds->fBottom = bot;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     int32_t fYSpanCount;
michael@0:     int32_t fIntervalCount;
michael@0: };
michael@0: 
michael@0: #endif