1
2/*
3 * Copyright 2011 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8#include "SkRegion.h"
9#include "SkChunkAlloc.h"
10#include "SkTDArray.h"
11#include "SkTemplates.h"
12
13#if 0
14
15struct VEdge {
16    VEdge*  fPrev;
17    VEdge*  fNext;
18
19    SkRegion::RunType   fX;
20    SkRegion::RunType   fTop;
21    SkRegion::RunType   fBottom;
22    int                 fWinding;
23
24    void removeFromList() {
25        fPrev->fNext = fNext;
26        fNext->fPrev = fPrev;
27    }
28
29    void backwardsInsert() {
30        while (fPrev->fX > fX) {
31            VEdge* prev = fPrev;
32            VEdge* next = this;
33
34            // remove prev from the list
35            prev->fPrev->fNext = next;
36            next->fPrev = prev->fPrev;
37
38            // insert prev after next
39            prev->fNext = next->fNext;
40            next->fNext->fPrev = prev;
41            next->fNext = prev;
42            prev->fPrev = next;
43        }
44    }
45
46    static void SetFromRect(VEdge edges[], const SkIRect& r) {
47        edges[0].fX = r.fLeft;
48        edges[0].fTop = r.fTop;
49        edges[0].fBottom = r.fBottom;
50        edges[0].fWinding = -1;
51
52        edges[1].fX = r.fRight;
53        edges[1].fTop = r.fTop;
54        edges[1].fBottom = r.fBottom;
55        edges[1].fWinding = 1;
56    }
57};
58
59class Accumulator {
60public:
61    Accumulator(SkRegion::RunType top, int numRects);
62    ~Accumulator() {}
63
64    SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge);
65
66    int count() const { return fTotalCount; }
67    void copyTo(SkRegion::RunType dst[]);
68
69private:
70    struct Row {
71        SkRegion::RunType*  fPtr;
72        SkRegion::RunType   fBottom;
73        int                 fCount; // just [L R] count
74    };
75    SkChunkAlloc    fAlloc;
76    SkTDArray<Row>  fRows;
77    SkRegion::RunType fTop;
78    int             fTotalCount;
79    int             fRectCount;
80};
81
82Accumulator::Accumulator(SkRegion::RunType top, int numRects)
83        : fAlloc((1 + numRects * 2 + 1) * sizeof(int32_t)) {
84    fRectCount = numRects;
85    fTop = top;
86    fTotalCount = 2; // Top + final sentinel
87}
88
89//#define TRACE_ROW(code) code
90#define TRACE_ROW(code)
91
92SkRegion::RunType Accumulator::append(SkRegion::RunType currY, const VEdge* edge) {
93    // worst-case size
94    size_t size = fRectCount * 2 * sizeof(SkRegion::RunType);
95    SkRegion::RunType* row = (SkRegion::RunType*)fAlloc.allocThrow(size);
96    SkRegion::RunType* rowHead = row;
97
98    SkRegion::RunType nextY = SkRegion::kRunTypeSentinel;
99    int winding = edge->fWinding;
100
101    // record the L R values for this row
102
103    if (edge->fTop > currY) {
104        nextY = SkMin32(nextY, edge->fTop);
105        TRACE_ROW(SkDebugf("Y %d\n", currY);)
106    } else {
107        SkRegion::RunType currR;
108        *row++ = edge->fX;
109        TRACE_ROW(SkDebugf("Y %d [%d", currY, edge->fX);)
110        edge = edge->fNext;
111        for (;;) {
112            if (edge->fTop > currY) {
113                nextY = SkMin32(nextY, edge->fTop);
114                break;
115            }
116
117            int prevWinding = winding;
118            winding += edge->fWinding;
119            if (0 == winding) { // we finished an interval
120                currR = edge->fX;
121            } else if (0 == prevWinding && edge->fX > currR) {
122                *row++ = currR;
123                *row++ = edge->fX;
124                TRACE_ROW(SkDebugf(" %d] [%d", currR, edge->fX);)
125            }
126
127            nextY = SkMin32(nextY, edge->fBottom);
128            edge = edge->fNext;
129        }
130        SkASSERT(0 == winding);
131        *row++ = currR;
132        TRACE_ROW(SkDebugf(" %d]\n", currR);)
133    }
134    int rowCount = row - rowHead;
135
136    // now see if we have already seen this row, or if its unique
137
138    Row* r = fRows.count() ? &fRows[fRows.count() - 1] : NULL;
139    if (r && (r->fCount == rowCount) &&
140        !memcmp(r->fPtr, rowHead,
141                rowCount * sizeof(SkRegion::RunType))) {
142            r->fBottom = nextY;    // update bottom
143            fAlloc.unalloc(rowHead);
144        } else {
145            Row* r = fRows.append();
146            r->fPtr = rowHead;
147            r->fBottom = nextY;
148            r->fCount = rowCount;
149            fTotalCount += 1 + rowCount + 1;
150        }
151
152    return nextY;
153}
154
155void Accumulator::copyTo(SkRegion::RunType dst[]) {
156    SkDEBUGCODE(SkRegion::RunType* startDst = dst;)
157
158    *dst++ = fTop;
159
160    const Row* curr = fRows.begin();
161    const Row* stop = fRows.end();
162    while (curr < stop) {
163        *dst++ = curr->fBottom;
164        memcpy(dst, curr->fPtr, curr->fCount * sizeof(SkRegion::RunType));
165        dst += curr->fCount;
166        *dst++ = SkRegion::kRunTypeSentinel;
167        curr += 1;
168    }
169    *dst++ = SkRegion::kRunTypeSentinel;
170    SkASSERT(dst - startDst == fTotalCount);
171}
172
173///////////////////////////////////////////////////////////////////////////////
174
175template <typename T> int SkTCmp2Int(const T& a, const T& b) {
176    return (a < b) ? -1 : ((b < a) ? 1 : 0);
177}
178
179static inline int SkCmp32(int32_t a, int32_t b) {
180    return (a < b) ? -1 : ((b < a) ? 1 : 0);
181}
182
183static int compare_edgeptr(const void* p0, const void* p1) {
184    const VEdge* e0 = *static_cast<VEdge*const*>(p0);
185    const VEdge* e1 = *static_cast<VEdge*const*>(p1);
186
187    SkRegion::RunType v0 = e0->fTop;
188    SkRegion::RunType v1 = e1->fTop;
189
190    if (v0 == v1) {
191        v0 = e0->fX;
192        v1 = e1->fX;
193    }
194    return SkCmp32(v0, v1);
195}
196
197// fillout edge[] from rects[], sorted. Return the head, and set the tail
198//
199static VEdge* sort_edges(VEdge** edgePtr, VEdge edge[], const SkIRect rects[],
200                         int rectCount, VEdge** edgeTail) {
201    int i;
202    VEdge** ptr = edgePtr;
203    for (int i = 0; i < rectCount; i++) {
204        if (!rects[i].isEmpty()) {
205            VEdge::SetFromRect(edge, rects[i]);
206            *ptr++ = edge++;
207            *ptr++ = edge++;
208        }
209    }
210
211    int edgeCount = ptr - edgePtr;
212    if (0 == edgeCount) {
213        // all the rects[] were empty
214        return NULL;
215    }
216
217    qsort(edgePtr, edgeCount, sizeof(*edgePtr), compare_edgeptr);
218    for (i = 1; i < edgeCount; i++) {
219        edgePtr[i - 1]->fNext = edgePtr[i];
220        edgePtr[i]->fPrev = edgePtr[i - 1];
221    }
222    *edgeTail = edgePtr[edgeCount - 1];
223    return edgePtr[0];
224}
225
226bool SkRegion::setRects(const SkIRect rects[], int rectCount) {
227    if (0 == rectCount) {
228        return this->setEmpty();
229    }
230    if (1 == rectCount) {
231        return this->setRect(rects[0]);
232    }
233
234    int edgeCount = rectCount * 2;
235    SkAutoMalloc memory((sizeof(VEdge) + sizeof(VEdge*)) * edgeCount);
236    VEdge** edgePtr = (VEdge**)memory.get();
237    VEdge* tail, *head = (VEdge*)(edgePtr + edgeCount);
238    head = sort_edges(edgePtr, head, rects, rectCount, &tail);
239    // check if we have no edges
240    if (NULL == head) {
241        return this->setEmpty();
242    }
243
244    // at this stage, we don't really care about edgeCount, or if rectCount is
245    // larger that it should be (since sort_edges might have skipped some
246    // empty rects[]). rectCount now is just used for worst-case allocations
247
248    VEdge headEdge, tailEdge;
249    headEdge.fPrev = NULL;
250    headEdge.fNext = head;
251    headEdge.fTop = SK_MinS32;
252    headEdge.fX = SK_MinS32;
253    head->fPrev = &headEdge;
254
255    tailEdge.fPrev = tail;
256    tailEdge.fNext = NULL;
257    tailEdge.fTop = SK_MaxS32;
258    tail->fNext = &tailEdge;
259
260    int32_t currY = head->fTop;
261    Accumulator accum(currY, rectCount);
262
263    while (head->fNext) {
264        VEdge* edge = head;
265        // accumulate the current
266        SkRegion::RunType nextY = accum.append(currY, edge);
267        // remove the old
268        while (edge->fTop <= currY) {
269            VEdge* next = edge->fNext;
270            if (edge->fBottom <= nextY) {
271                edge->removeFromList();
272            }
273            edge = next;
274        }
275        // insert (sorted) the new
276        while (edge->fTop == nextY) {
277            VEdge* next = edge->fNext;
278            edge->backwardsInsert();
279            edge = next;
280        }
281        currY = nextY;
282        head = headEdge.fNext;
283    }
284
285    SkAutoTArray<RunType> runs(accum.count());
286    accum.copyTo(runs.get());
287    return this->setRuns(runs.get(), accum.count());
288}
289
290#endif
291