Index: src/core/SkRegion_rects.cpp |
diff --git a/src/core/SkRegion_rects.cpp b/src/core/SkRegion_rects.cpp |
deleted file mode 100644 |
index 4121080c417dd757a9d0f4ce2772fe861fd79e9c..0000000000000000000000000000000000000000 |
--- a/src/core/SkRegion_rects.cpp |
+++ /dev/null |
@@ -1,290 +0,0 @@ |
- |
-/* |
- * Copyright 2011 Google Inc. |
- * |
- * Use of this source code is governed by a BSD-style license that can be |
- * found in the LICENSE file. |
- */ |
-#include "SkRegion.h" |
-#include "SkChunkAlloc.h" |
-#include "SkTDArray.h" |
-#include "SkTemplates.h" |
- |
-#if 0 |
- |
-struct VEdge { |
- VEdge* fPrev; |
- VEdge* fNext; |
- |
- SkRegion::RunType fX; |
- SkRegion::RunType fTop; |
- SkRegion::RunType fBottom; |
- int fWinding; |
- |
- void removeFromList() { |
- fPrev->fNext = fNext; |
- fNext->fPrev = fPrev; |
- } |
- |
- void backwardsInsert() { |
- while (fPrev->fX > fX) { |
- VEdge* prev = fPrev; |
- VEdge* next = this; |
- |
- // remove prev from the list |
- prev->fPrev->fNext = next; |
- next->fPrev = prev->fPrev; |
- |
- // insert prev after next |
- prev->fNext = next->fNext; |
- next->fNext->fPrev = prev; |
- next->fNext = prev; |
- prev->fPrev = next; |
- } |
- } |
- |
- static void SetFromRect(VEdge edges[], const SkIRect& r) { |
- edges[0].fX = r.fLeft; |
- edges[0].fTop = r.fTop; |
- edges[0].fBottom = r.fBottom; |
- edges[0].fWinding = -1; |
- |
- edges[1].fX = r.fRight; |
- edges[1].fTop = r.fTop; |
- edges[1].fBottom = r.fBottom; |
- edges[1].fWinding = 1; |
- } |
-}; |
- |
-class Accumulator { |
-public: |
- Accumulator(SkRegion::RunType top, int numRects); |
- ~Accumulator() {} |
- |
- SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge); |
- |
- int count() const { return fTotalCount; } |
- void copyTo(SkRegion::RunType dst[]); |
- |
-private: |
- struct Row { |
- SkRegion::RunType* fPtr; |
- SkRegion::RunType fBottom; |
- int fCount; // just [L R] count |
- }; |
- SkChunkAlloc fAlloc; |
- SkTDArray<Row> fRows; |
- SkRegion::RunType fTop; |
- int fTotalCount; |
- int fRectCount; |
-}; |
- |
-Accumulator::Accumulator(SkRegion::RunType top, int numRects) |
- : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) { |
- fRectCount = numRects; |
- fTop = top; |
- fTotalCount = 2; // Top + final sentinel |
-} |
- |
-//#define TRACE_ROW(code) code |
-#define TRACE_ROW(code) |
- |
-SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) { |
- // worst-case size |
- size_t size = fRectCount * 2 * sizeof(SkRegion::RunType); |
- SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size); |
- SkRegion::RunType* rowHead = row; |
- |
- SkRegion::RunType nextY = SkRegion::kRunTypeSentinel; |
- int winding = edge->fWinding; |
- |
- // record the L R values for this row |
- |
- if (edge->fTop > currY) { |
- nextY = SkMin32(nextY, edge->fTop); |
- TRACE_ROW(SkDebugf("Y %d\n", currY);) |
- } else { |
- SkRegion::RunType currR; |
- *row++ = edge->fX; |
- TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);) |
- edge = edge->fNext; |
- for (;;) { |
- if (edge->fTop > currY) { |
- nextY = SkMin32(nextY, edge->fTop); |
- break; |
- } |
- |
- int prevWinding = winding; |
- winding += edge->fWinding; |
- if (0 == winding) { // we finished an interval |
- currR = edge->fX; |
- } else if (0 == prevWinding && edge->fX > currR) { |
- *row++ = currR; |
- *row++ = edge->fX; |
- TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);) |
- } |
- |
- nextY = SkMin32(nextY, edge->fBottom); |
- edge = edge->fNext; |
- } |
- SkASSERT(0 == winding); |
- *row++ = currR; |
- TRACE_ROW(SkDebugf(" %d]\n", currR);) |
- } |
- int rowCount = row - rowHead; |
- |
- // now see if we have already seen this row, or if its unique |
- |
- Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL; |
- if (r && (r->fCount == rowCount) && |
- !memcmp(r->fPtr, rowHead, |
- rowCount * sizeof(SkRegion::RunType))) { |
- r->fBottom = nextY; // update bottom |
- fAlloc.unalloc(rowHead); |
- } else { |
- Row* r = fRows.append(); |
- r->fPtr = rowHead; |
- r->fBottom = nextY; |
- r->fCount = rowCount; |
- fTotalCount += 1 + rowCount + 1; |
- } |
- |
- return nextY; |
-} |
- |
-void Accumulator::copyTo(SkRegion::RunType dst[]) { |
- SkDEBUGCODE(SkRegion::RunType* startDst = dst;) |
- |
- *dst++ = fTop; |
- |
- const Row* curr = fRows.begin(); |
- const Row* stop = fRows.end(); |
- while (curr < stop) { |
- *dst++ = curr->fBottom; |
- memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType)); |
- dst += curr->fCount; |
- *dst++ = SkRegion::kRunTypeSentinel; |
- curr += 1; |
- } |
- *dst++ = SkRegion::kRunTypeSentinel; |
- SkASSERT(dst - startDst == fTotalCount); |
-} |
- |
-/////////////////////////////////////////////////////////////////////////////// |
- |
-template <typename T> int SkTCmp2Int(const T& a, const T& b) { |
- return (a < b) ? -1 : ((b < a) ? 1 : 0); |
-} |
- |
-static inline int SkCmp32(int32_t a, int32_t b) { |
- return (a < b) ? -1 : ((b < a) ? 1 : 0); |
-} |
- |
-static int compare_edgeptr(const void* p0, const void* p1) { |
- const VEdge* e0 = *static_cast<VEdge*const*>(p0); |
- const VEdge* e1 = *static_cast<VEdge*const*>(p1); |
- |
- SkRegion::RunType v0 = e0->fTop; |
- SkRegion::RunType v1 = e1->fTop; |
- |
- if (v0 == v1) { |
- v0 = e0->fX; |
- v1 = e1->fX; |
- } |
- return SkCmp32(v0, v1); |
-} |
- |
-// fillout edge[] from rects[], sorted. Return the head, and set the tail |
-// |
-static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[], |
- int rectCount, VEdge** edgeTail) { |
- int i; |
- VEdge** ptr = edgePtr; |
- for (int i = 0; i < rectCount; i++) { |
- if (!rects[i].isEmpty()) { |
- VEdge::SetFromRect(edge, rects[i]); |
- *ptr++ = edge++; |
- *ptr++ = edge++; |
- } |
- } |
- |
- int edgeCount = ptr - edgePtr; |
- if (0 == edgeCount) { |
- // all the rects[] were empty |
- return NULL; |
- } |
- |
- qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr); |
- for (i = 1; i < edgeCount; i++) { |
- edgePtr[i - 1]->fNext = edgePtr[i]; |
- edgePtr[i]->fPrev = edgePtr[i - 1]; |
- } |
- *edgeTail = edgePtr[edgeCount - 1]; |
- return edgePtr[0]; |
-} |
- |
-bool SkRegion::setRects(const SkIRect rects[], int rectCount) { |
- if (0 == rectCount) { |
- return this->setEmpty(); |
- } |
- if (1 == rectCount) { |
- return this->setRect(rects[0]); |
- } |
- |
- int edgeCount = rectCount * 2; |
- SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount); |
- VEdge** edgePtr = (VEdge**)memory.get(); |
- VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount); |
- head = sort_edges(edgePtr, head, rects, rectCount, &tail); |
- // check if we have no edges |
- if (NULL == head) { |
- return this->setEmpty(); |
- } |
- |
- // at this stage, we don't really care about edgeCount, or if rectCount is |
- // larger that it should be (since sort_edges might have skipped some |
- // empty rects[]). rectCount now is just used for worst-case allocations |
- |
- VEdge headEdge, tailEdge; |
- headEdge.fPrev = NULL; |
- headEdge.fNext = head; |
- headEdge.fTop = SK_MinS32; |
- headEdge.fX = SK_MinS32; |
- head->fPrev = &headEdge; |
- |
- tailEdge.fPrev = tail; |
- tailEdge.fNext = NULL; |
- tailEdge.fTop = SK_MaxS32; |
- tail->fNext = &tailEdge; |
- |
- int32_t currY = head->fTop; |
- Accumulator accum(currY, rectCount); |
- |
- while (head->fNext) { |
- VEdge* edge = head; |
- // accumulate the current |
- SkRegion::RunType nextY = accum.append(currY, edge); |
- // remove the old |
- while (edge->fTop <= currY) { |
- VEdge* next = edge->fNext; |
- if (edge->fBottom <= nextY) { |
- edge->removeFromList(); |
- } |
- edge = next; |
- } |
- // insert (sorted) the new |
- while (edge->fTop == nextY) { |
- VEdge* next = edge->fNext; |
- edge->backwardsInsert(); |
- edge = next; |
- } |
- currY = nextY; |
- head = headEdge.fNext; |
- } |
- |
- SkAutoTArray<RunType> runs(accum.count()); |
- accum.copyTo(runs.get()); |
- return this->setRuns(runs.get(), accum.count()); |
-} |
- |
-#endif |