store x-interval-count per scanline, so we can skip lines in O(1)
Review URL: https://codereview.appspot.com/6147043
git-svn-id: http://skia.googlecode.com/svn/trunk@3825 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/core/SkRegionPriv.h b/src/core/SkRegionPriv.h
index fe0dfbe..84c726d 100644
--- a/src/core/SkRegionPriv.h
+++ b/src/core/SkRegionPriv.h
@@ -18,7 +18,25 @@
//SkDEBUGCODE(extern int32_t gRgnAllocCounter;)
+#ifdef SK_DEBUG
+// Given the first interval (just past the interval-count), compute the
+// interval count, by search for the x-sentinel
+//
+static int compute_intervalcount(const SkRegion::RunType runs[]) {
+ const SkRegion::RunType* curr = runs;
+ while (*curr < SkRegion::kRunTypeSentinel) {
+ SkASSERT(curr[0] < curr[1]);
+ SkASSERT(curr[1] < SkRegion::kRunTypeSentinel);
+ curr += 2;
+ }
+ return (curr - runs) >> 1;
+}
+#endif
+
struct SkRegion::RunHead {
+private:
+
+public:
int32_t fRefCnt;
int32_t fRunCount;
@@ -41,16 +59,6 @@
return fIntervalCount;
}
- void updateYSpanCount(int n) {
- SkASSERT(n > 0);
- fYSpanCount = n;
- }
-
- void updateIntervalCount(int n) {
- SkASSERT(n > 1);
- fIntervalCount = n;
- }
-
static RunHead* Alloc(int count) {
//SkDEBUGCODE(sk_atomic_inc(&gRgnAllocCounter);)
//SkDEBUGF(("************** gRgnAllocCounter::alloc %d\n", gRgnAllocCounter));
@@ -112,6 +120,118 @@
}
return writable;
}
+
+ /**
+ * Given a scanline (including its Bottom value at runs[0]), return the next
+ * scanline. Asserts that there is one (i.e. runs[0] < Sentinel)
+ */
+ static SkRegion::RunType* SkipEntireScanline(const SkRegion::RunType runs[]) {
+ // we are not the Y Sentinel
+ SkASSERT(runs[0] < SkRegion::kRunTypeSentinel);
+
+ const int intervals = runs[1];
+ SkASSERT(runs[2 + intervals * 2] == SkRegion::kRunTypeSentinel);
+#ifdef SK_DEBUG
+ {
+ int n = compute_intervalcount(&runs[2]);
+ SkASSERT(n == intervals);
+ }
+#endif
+
+ // skip the entire line [B N [L R] S]
+ runs += 1 + 1 + intervals * 2 + 1;
+ return const_cast<SkRegion::RunType*>(runs);
+ }
+
+
+ /**
+ * Return the scanline that contains the Y value. This requires that the Y
+ * value is already known to be contained within the bounds of the region,
+ * and so this routine never returns NULL.
+ *
+ * It returns the beginning of the scanline, starting with its Bottom value.
+ */
+ SkRegion::RunType* findScanline(int y) const {
+ const RunType* runs = this->readonly_runs();
+
+ // if the top-check fails, we didn't do a quick check on the bounds
+ SkASSERT(y >= runs[0]);
+
+ runs += 1; // skip top-Y
+ for (;;) {
+ int bottom = runs[0];
+ // If we hit this, we've walked off the region, and our bounds check
+ // failed.
+ SkASSERT(bottom < SkRegion::kRunTypeSentinel);
+ if (y < bottom) {
+ break;
+ }
+ runs = SkipEntireScanline(runs);
+ }
+ return const_cast<SkRegion::RunType*>(runs);
+ }
+
+ // Copy src runs into us, computing interval counts and bounds along the way
+ void computeRunBounds(SkIRect* bounds) {
+ RunType* runs = this->writable_runs();
+ bounds->fTop = *runs++;
+
+ int bot;
+ int ySpanCount = 0;
+ int intervalCount = 0;
+ int left = SK_MaxS32;
+ int rite = SK_MinS32;
+
+ do {
+ bot = *runs++;
+ SkASSERT(bot < SkRegion::kRunTypeSentinel);
+ ySpanCount += 1;
+
+ const int intervals = *runs++;
+ SkASSERT(intervals >= 0);
+ SkASSERT(intervals < SkRegion::kRunTypeSentinel);
+
+ if (intervals > 0) {
+#ifdef SK_DEBUG
+ {
+ int n = compute_intervalcount(runs);
+ SkASSERT(n == intervals);
+ }
+#endif
+ RunType L = runs[0];
+ SkASSERT(L < SkRegion::kRunTypeSentinel);
+ if (left > L) {
+ left = L;
+ }
+
+ runs += intervals * 2;
+ RunType R = runs[-1];
+ SkASSERT(R < SkRegion::kRunTypeSentinel);
+ if (rite < R) {
+ rite = R;
+ }
+
+ intervalCount += intervals;
+ }
+ SkASSERT(SkRegion::kRunTypeSentinel == *runs);
+ runs += 1; // skip x-sentinel
+
+ // test Y-sentinel
+ } while (SkRegion::kRunTypeSentinel > *runs);
+
+#ifdef SK_DEBUG
+ // +1 to skip the last Y-sentinel
+ int runCount = runs - this->writable_runs() + 1;
+ SkASSERT(runCount == fRunCount);
+#endif
+
+ fYSpanCount = ySpanCount;
+ fIntervalCount = intervalCount;
+
+ bounds->fLeft = left;
+ bounds->fRight = rite;
+ bounds->fBottom = bot;
+ }
private:
int32_t fYSpanCount;