gfx/skia/trunk/src/core/SkRegion_rects.cpp@deefc01c0e14
gfx/skia/trunk/src/core/SkRegion_rects.cpp
Thu, 15 Jan 2015 21:03:48 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 15 Jan 2015 21:03:48 +0100
- branch
- TOR_BUG_9701
- changeset 11
- deefc01c0e14
- permissions
- -rw-r--r--
Integrate friendly tips from Tor colleagues to make (or not) 4.5 alpha 3;
This includes removal of overloaded (but unused) methods, and addition of
a overlooked call to DataStruct::SetData(nsISupports, uint32_t, bool.)
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"
13 #if 0
15 struct VEdge {
16 VEdge* fPrev;
17 VEdge* fNext;
19 SkRegion::RunType fX;
20 SkRegion::RunType fTop;
21 SkRegion::RunType fBottom;
22 int fWinding;
24 void removeFromList() {
25 fPrev->fNext = fNext;
26 fNext->fPrev = fPrev;
27 }
29 void backwardsInsert() {
30 while (fPrev->fX > fX) {
31 VEdge* prev = fPrev;
32 VEdge* next = this;
34 // remove prev from the list
35 prev->fPrev->fNext = next;
36 next->fPrev = prev->fPrev;
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 }
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;
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 };
59 class Accumulator {
60 public:
61 Accumulator(SkRegion::RunType top, int numRects);
62 ~Accumulator() {}
64 SkRegion::RunType append(SkRegion::RunType top, const VEdge* edge);
66 int count() const { return fTotalCount; }
67 void copyTo(SkRegion::RunType dst[]);
69 private:
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 };
82 Accumulator::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 }
89 //#define TRACE_ROW(code) code
90 #define TRACE_ROW(code)
92 SkRegion::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;
98 SkRegion::RunType nextY = SkRegion::kRunTypeSentinel;
99 int winding = edge->fWinding;
101 // record the L R values for this row
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 }
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 }
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;
136 // now see if we have already seen this row, or if its unique
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 }
152 return nextY;
153 }
155 void Accumulator::copyTo(SkRegion::RunType dst[]) {
156 SkDEBUGCODE(SkRegion::RunType* startDst = dst;)
158 *dst++ = fTop;
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 }
173 ///////////////////////////////////////////////////////////////////////////////
175 template <typename T> int SkTCmp2Int(const T& a, const T& b) {
176 return (a < b) ? -1 : ((b < a) ? 1 : 0);
177 }
179 static inline int SkCmp32(int32_t a, int32_t b) {
180 return (a < b) ? -1 : ((b < a) ? 1 : 0);
181 }
183 static 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);
187 SkRegion::RunType v0 = e0->fTop;
188 SkRegion::RunType v1 = e1->fTop;
190 if (v0 == v1) {
191 v0 = e0->fX;
192 v1 = e1->fX;
193 }
194 return SkCmp32(v0, v1);
195 }
197 // fillout edge[] from rects[], sorted. Return the head, and set the tail
198 //
199 static 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 }
211 int edgeCount = ptr - edgePtr;
212 if (0 == edgeCount) {
213 // all the rects[] were empty
214 return NULL;
215 }
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 }
226 bool 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 }
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 }
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
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;
255 tailEdge.fPrev = tail;
256 tailEdge.fNext = NULL;
257 tailEdge.fTop = SK_MaxS32;
258 tail->fNext = &tailEdge;
260 int32_t currY = head->fTop;
261 Accumulator accum(currY, rectCount);
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 }
285 SkAutoTArray<RunType> runs(accum.count());
286 accum.copyTo(runs.get());
287 return this->setRuns(runs.get(), accum.count());
288 }
290 #endif
