gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp@129ffea94266
gfx/skia/trunk/src/gpu/GrRectanizer_skyline.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rwxr-xr-x
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
2 /*
3 * Copyright 2013 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 */
9 #include "GrRectanizer.h"
10 #include "SkTDArray.h"
12 // Pack rectangles and track the current silhouette
13 // Based in part on Jukka Jylänki's work at http://clb.demon.fi
15 class GrRectanizerSkyline : public GrRectanizer {
16 public:
17 GrRectanizerSkyline(int w, int h) : GrRectanizer(w, h) {
18 reset();
19 }
21 virtual ~GrRectanizerSkyline() {
22 }
24 virtual void reset() {
25 fAreaSoFar = 0;
26 fSkyline.reset();
27 SkylineSegment* seg = fSkyline.append(1);
28 seg->fX = 0;
29 seg->fY = 0;
30 seg->fWidth = width();
31 }
33 virtual bool addRect(int w, int h, GrIPoint16* loc);
35 virtual float percentFull() const {
36 return fAreaSoFar / ((float)this->width() * this->height());
37 }
39 virtual int stripToPurge(int height) const { return -1; }
40 virtual void purgeStripAtY(int yCoord) { }
42 ///////////////////////////////////////////////////////////////////////////
44 struct SkylineSegment {
45 int fX;
46 int fY;
47 int fWidth;
48 };
50 SkTDArray<SkylineSegment> fSkyline;
52 int32_t fAreaSoFar;
54 bool rectangleFits(int skylineIndex, int width, int height, int* y) const;
55 void addSkylineLevel(int skylineIndex, int x, int y, int width, int height);
56 };
58 bool GrRectanizerSkyline::addRect(int width, int height, GrIPoint16* loc) {
59 if ((unsigned)width > (unsigned)this->width() ||
60 (unsigned)height > (unsigned)this->height()) {
61 return false;
62 }
64 // find position for new rectangle
65 int bestWidth = this->width() + 1;
66 int bestX;
67 int bestY = this->height() + 1;
68 int bestIndex = -1;
69 for (int i = 0; i < fSkyline.count(); ++i) {
70 int y;
71 if (this->rectangleFits(i, width, height, &y)) {
72 // minimize y position first, then width of skyline
73 if (y < bestY || (y == bestY && fSkyline[i].fWidth < bestWidth)) {
74 bestIndex = i;
75 bestWidth = fSkyline[i].fWidth;
76 bestX = fSkyline[i].fX;
77 bestY = y;
78 }
79 }
80 }
82 // add rectangle to skyline
83 if (-1 != bestIndex) {
84 this->addSkylineLevel(bestIndex, bestX, bestY, width, height);
85 loc->fX = bestX;
86 loc->fY = bestY;
88 fAreaSoFar += width*height;
89 return true;
90 }
92 loc->fX = 0;
93 loc->fY = 0;
94 return false;
95 }
97 bool GrRectanizerSkyline::rectangleFits(int skylineIndex, int width, int height, int* ypos) const {
98 int x = fSkyline[skylineIndex].fX;
99 if (x + width > this->width()) {
100 return false;
101 }
103 int widthLeft = width;
104 int i = skylineIndex;
105 int y = fSkyline[skylineIndex].fY;
106 while (widthLeft > 0) {
107 y = SkMax32(y, fSkyline[i].fY);
108 if (y + height > this->height()) {
109 return false;
110 }
111 widthLeft -= fSkyline[i].fWidth;
112 ++i;
113 SkASSERT(i < fSkyline.count() || widthLeft <= 0);
114 }
116 *ypos = y;
117 return true;
118 }
120 void GrRectanizerSkyline::addSkylineLevel(int skylineIndex, int x, int y, int width, int height) {
121 SkylineSegment newSegment;
122 newSegment.fX = x;
123 newSegment.fY = y + height;
124 newSegment.fWidth = width;
125 fSkyline.insert(skylineIndex, 1, &newSegment);
127 SkASSERT(newSegment.fX + newSegment.fWidth <= this->width());
128 SkASSERT(newSegment.fY <= this->height());
130 // delete width of this skyline segment from following ones
131 for (int i = skylineIndex+1; i < fSkyline.count(); ++i) {
132 SkASSERT(fSkyline[i-1].fX <= fSkyline[i].fX);
134 if (fSkyline[i].fX < fSkyline[i-1].fX + fSkyline[i-1].fWidth) {
135 int shrink = fSkyline[i-1].fX + fSkyline[i-1].fWidth - fSkyline[i].fX;
137 fSkyline[i].fX += shrink;
138 fSkyline[i].fWidth -= shrink;
140 if (fSkyline[i].fWidth <= 0) {
141 fSkyline.remove(i);
142 --i;
143 }
144 else
145 break;
146 }
147 else
148 break;
149 }
151 // merge fSkylines
152 for (int i = 0; i < fSkyline.count()-1; ++i) {
153 if (fSkyline[i].fY == fSkyline[i+1].fY) {
154 fSkyline[i].fWidth += fSkyline[i+1].fWidth;
155 fSkyline.remove(i+1);
156 --i;
157 }
158 }
159 }
161 ///////////////////////////////////////////////////////////////////////////////
163 GrRectanizer* GrRectanizer::Factory(int width, int height) {
164 return SkNEW_ARGS(GrRectanizerSkyline, (width, height));
165 }
