OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2010, 2011 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
(...skipping 189 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
200 } | 200 } |
201 | 201 |
202 if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutside B(result)) | 202 if (aSpan != aSpanEnd && aSpan + 1 != aSpanEnd && CompareOperation::aOutside B(result)) |
203 return result; | 203 return result; |
204 if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutside A(result)) | 204 if (bSpan != bSpanEnd && bSpan + 1 != bSpanEnd && CompareOperation::bOutside A(result)) |
205 return result; | 205 return result; |
206 | 206 |
207 return result; | 207 return result; |
208 } | 208 } |
209 | 209 |
210 void Region::Shape::trimCapacities() | |
211 { | |
212 m_segments.shrinkToReasonableCapacity(); | |
213 m_spans.shrinkToReasonableCapacity(); | |
214 } | |
215 | |
210 struct Region::Shape::CompareContainsOperation { | 216 struct Region::Shape::CompareContainsOperation { |
211 const static bool defaultResult = true; | 217 const static bool defaultResult = true; |
212 inline static bool aOutsideB(bool& /* result */) { return false; } | 218 inline static bool aOutsideB(bool& /* result */) { return false; } |
213 inline static bool bOutsideA(bool& result) { result = false; return true; } | 219 inline static bool bOutsideA(bool& result) { result = false; return true; } |
214 inline static bool aOverlapsB(bool& /* result */) { return false; } | 220 inline static bool aOverlapsB(bool& /* result */) { return false; } |
215 }; | 221 }; |
216 | 222 |
217 struct Region::Shape::CompareIntersectsOperation { | 223 struct Region::Shape::CompareIntersectsOperation { |
218 const static bool defaultResult = false; | 224 const static bool defaultResult = false; |
219 inline static bool aOutsideB(bool& /* result */) { return false; } | 225 inline static bool aOutsideB(bool& /* result */) { return false; } |
220 inline static bool bOutsideA(bool& /* result */) { return false; } | 226 inline static bool bOutsideA(bool& /* result */) { return false; } |
221 inline static bool aOverlapsB(bool& result) { result = true; return true; } | 227 inline static bool aOverlapsB(bool& result) { result = true; return true; } |
222 }; | 228 }; |
223 | 229 |
224 Region::Shape::Shape() | 230 Region::Shape::Shape() |
225 { | 231 { |
226 } | 232 } |
227 | 233 |
228 Region::Shape::Shape(const IntRect& rect) | 234 Region::Shape::Shape(const IntRect& rect) |
229 { | 235 { |
230 appendSpan(rect.y()); | 236 appendSpan(rect.y()); |
231 appendSegment(rect.x()); | 237 appendSegment(rect.x()); |
232 appendSegment(rect.maxX()); | 238 appendSegment(rect.maxX()); |
233 appendSpan(rect.maxY()); | 239 appendSpan(rect.maxY()); |
234 } | 240 } |
235 | 241 |
242 Region::Shape::Shape(size_t segmentsCapacity, size_t spansCapacity) | |
243 { | |
244 if (segmentsCapacity > m_segments.capacity()) { | |
245 segmentsCapacity = (segmentsCapacity + segmentsMask) & ~segmentsMask; | |
eseidel
2014/05/29 15:45:16
Why is all this capacity dance needed? Can't we j
ostap
2014/05/29 22:35:21
Yes, we can.
Tried to reserve some more space beca
| |
246 m_segments.reserveCapacity(segmentsCapacity); | |
247 } | |
248 | |
249 if (spansCapacity > m_spans.capacity()) { | |
250 spansCapacity = (spansCapacity + spansMask) & ~spansMask; | |
251 m_spans.reserveCapacity(spansCapacity); | |
252 } | |
253 } | |
254 | |
236 void Region::Shape::appendSpan(int y) | 255 void Region::Shape::appendSpan(int y) |
237 { | 256 { |
238 m_spans.append(Span(y, m_segments.size())); | 257 m_spans.append(Span(y, m_segments.size())); |
239 } | 258 } |
240 | 259 |
241 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) | 260 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) |
242 { | 261 { |
243 if (m_spans.isEmpty()) | 262 if (m_spans.isEmpty()) |
244 return false; | 263 return false; |
245 | 264 |
(...skipping 140 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
386 Shape1, | 405 Shape1, |
387 Shape2, | 406 Shape2, |
388 }; | 407 }; |
389 | 408 |
390 template<typename Operation> | 409 template<typename Operation> |
391 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh ape2) | 410 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh ape2) |
392 { | 411 { |
393 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operatio n::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); | 412 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operatio n::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); |
394 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation: :shouldAddRemainingSpansFromShape2), invalid_span_combination); | 413 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation: :shouldAddRemainingSpansFromShape2), invalid_span_combination); |
395 | 414 |
396 Shape result; | 415 size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize(); |
416 size_t spansCapacity = shape1.spansSize() + shape2.spansSize(); | |
417 Shape result(segmentsCapacity, spansCapacity); | |
397 if (Operation::trySimpleOperation(shape1, shape2, result)) | 418 if (Operation::trySimpleOperation(shape1, shape2, result)) |
398 return result; | 419 return result; |
399 | 420 |
400 SpanIterator spans1 = shape1.spansBegin(); | 421 SpanIterator spans1 = shape1.spansBegin(); |
401 SpanIterator spans1End = shape1.spansEnd(); | 422 SpanIterator spans1End = shape1.spansEnd(); |
402 | 423 |
403 SpanIterator spans2 = shape2.spansBegin(); | 424 SpanIterator spans2 = shape2.spansBegin(); |
404 SpanIterator spans2End = shape2.spansEnd(); | 425 SpanIterator spans2End = shape2.spansEnd(); |
405 | 426 |
406 SegmentIterator segments1 = 0; | 427 SegmentIterator segments1 = 0; |
407 SegmentIterator segments1End = 0; | 428 SegmentIterator segments1End = 0; |
408 | 429 |
409 SegmentIterator segments2 = 0; | 430 SegmentIterator segments2 = 0; |
410 SegmentIterator segments2End = 0; | 431 SegmentIterator segments2End = 0; |
411 | 432 |
433 Vector<int, segmentsDefaultCapacity> segments; | |
434 segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize ())); | |
435 | |
412 // Iterate over all spans. | 436 // Iterate over all spans. |
413 while (spans1 != spans1End && spans2 != spans2End) { | 437 while (spans1 != spans1End && spans2 != spans2End) { |
414 int y = 0; | 438 int y = 0; |
415 int test = spans1->y - spans2->y; | 439 int test = spans1->y - spans2->y; |
416 | 440 |
417 if (test <= 0) { | 441 if (test <= 0) { |
418 y = spans1->y; | 442 y = spans1->y; |
419 | 443 |
420 segments1 = shape1.segmentsBegin(spans1); | 444 segments1 = shape1.segmentsBegin(spans1); |
421 segments1End = shape1.segmentsEnd(spans1); | 445 segments1End = shape1.segmentsEnd(spans1); |
422 ++spans1; | 446 ++spans1; |
423 } | 447 } |
424 if (test >= 0) { | 448 if (test >= 0) { |
425 y = spans2->y; | 449 y = spans2->y; |
426 | 450 |
427 segments2 = shape2.segmentsBegin(spans2); | 451 segments2 = shape2.segmentsBegin(spans2); |
428 segments2End = shape2.segmentsEnd(spans2); | 452 segments2End = shape2.segmentsEnd(spans2); |
429 ++spans2; | 453 ++spans2; |
430 } | 454 } |
431 | 455 |
432 int flag = 0; | 456 int flag = 0; |
433 int oldFlag = 0; | 457 int oldFlag = 0; |
434 | 458 |
435 SegmentIterator s1 = segments1; | 459 SegmentIterator s1 = segments1; |
436 SegmentIterator s2 = segments2; | 460 SegmentIterator s2 = segments2; |
437 | 461 |
438 Vector<int, 32> segments; | 462 // Clear vector without dropping capacity. |
463 segments.resize(0); | |
464 ASSERT(segments.capacity()); | |
439 | 465 |
440 // Now iterate over the segments in each span and construct a new vector of segments. | 466 // Now iterate over the segments in each span and construct a new vector of segments. |
441 while (s1 != segments1End && s2 != segments2End) { | 467 while (s1 != segments1End && s2 != segments2End) { |
442 int test = *s1 - *s2; | 468 int test = *s1 - *s2; |
443 int x; | 469 int x; |
444 | 470 |
445 if (test <= 0) { | 471 if (test <= 0) { |
446 x = *s1; | 472 x = *s1; |
447 flag = flag ^ 1; | 473 flag = flag ^ 1; |
448 ++s1; | 474 ++s1; |
(...skipping 20 matching lines...) Expand all Loading... | |
469 if (!segments.isEmpty() || !result.isEmpty()) | 495 if (!segments.isEmpty() || !result.isEmpty()) |
470 result.appendSpan(y, segments.data(), segments.data() + segments.siz e()); | 496 result.appendSpan(y, segments.data(), segments.data() + segments.siz e()); |
471 } | 497 } |
472 | 498 |
473 // Add any remaining spans. | 499 // Add any remaining spans. |
474 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) | 500 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) |
475 result.appendSpans(shape1, spans1, spans1End); | 501 result.appendSpans(shape1, spans1, spans1End); |
476 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End ) | 502 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End ) |
477 result.appendSpans(shape2, spans2, spans2End); | 503 result.appendSpans(shape2, spans2, spans2End); |
478 | 504 |
505 result.trimCapacities(); | |
506 | |
479 return result; | 507 return result; |
480 } | 508 } |
481 | 509 |
482 struct Region::Shape::UnionOperation { | 510 struct Region::Shape::UnionOperation { |
483 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Sha pe& result) | 511 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Sha pe& result) |
484 { | 512 { |
485 if (shape1.isEmpty()) { | 513 if (shape1.isEmpty()) { |
486 result = shape2; | 514 result = shape2; |
487 return true; | 515 return true; |
488 } | 516 } |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
601 m_bounds = m_shape.bounds(); | 629 m_bounds = m_shape.bounds(); |
602 } | 630 } |
603 | 631 |
604 void Region::translate(const IntSize& offset) | 632 void Region::translate(const IntSize& offset) |
605 { | 633 { |
606 m_bounds.move(offset); | 634 m_bounds.move(offset); |
607 m_shape.translate(offset); | 635 m_shape.translate(offset); |
608 } | 636 } |
609 | 637 |
610 } // namespace WebCore | 638 } // namespace WebCore |
OLD | NEW |