/*
* 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