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 m_segments.reserveCapacity(segmentsCapacity); |
| 245 m_spans.reserveCapacity(spansCapacity); |
| 246 } |
| 247 |
236 void Region::Shape::appendSpan(int y) | 248 void Region::Shape::appendSpan(int y) |
237 { | 249 { |
238 m_spans.append(Span(y, m_segments.size())); | 250 m_spans.append(Span(y, m_segments.size())); |
239 } | 251 } |
240 | 252 |
241 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) | 253 bool Region::Shape::canCoalesce(SegmentIterator begin, SegmentIterator end) |
242 { | 254 { |
243 if (m_spans.isEmpty()) | 255 if (m_spans.isEmpty()) |
244 return false; | 256 return false; |
245 | 257 |
(...skipping 140 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
386 Shape1, | 398 Shape1, |
387 Shape2, | 399 Shape2, |
388 }; | 400 }; |
389 | 401 |
390 template<typename Operation> | 402 template<typename Operation> |
391 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
ape2) | 403 Region::Shape Region::Shape::shapeOperation(const Shape& shape1, const Shape& sh
ape2) |
392 { | 404 { |
393 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operatio
n::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); | 405 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSegmentsFromSpan1 && Operatio
n::shouldAddRemainingSegmentsFromSpan2), invalid_segment_combination); |
394 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation:
:shouldAddRemainingSpansFromShape2), invalid_span_combination); | 406 COMPILE_ASSERT(!(!Operation::shouldAddRemainingSpansFromShape1 && Operation:
:shouldAddRemainingSpansFromShape2), invalid_span_combination); |
395 | 407 |
396 Shape result; | 408 size_t segmentsCapacity = shape1.segmentsSize() + shape2.segmentsSize(); |
| 409 size_t spansCapacity = shape1.spansSize() + shape2.spansSize(); |
| 410 Shape result(segmentsCapacity, spansCapacity); |
397 if (Operation::trySimpleOperation(shape1, shape2, result)) | 411 if (Operation::trySimpleOperation(shape1, shape2, result)) |
398 return result; | 412 return result; |
399 | 413 |
400 SpanIterator spans1 = shape1.spansBegin(); | 414 SpanIterator spans1 = shape1.spansBegin(); |
401 SpanIterator spans1End = shape1.spansEnd(); | 415 SpanIterator spans1End = shape1.spansEnd(); |
402 | 416 |
403 SpanIterator spans2 = shape2.spansBegin(); | 417 SpanIterator spans2 = shape2.spansBegin(); |
404 SpanIterator spans2End = shape2.spansEnd(); | 418 SpanIterator spans2End = shape2.spansEnd(); |
405 | 419 |
406 SegmentIterator segments1 = 0; | 420 SegmentIterator segments1 = 0; |
407 SegmentIterator segments1End = 0; | 421 SegmentIterator segments1End = 0; |
408 | 422 |
409 SegmentIterator segments2 = 0; | 423 SegmentIterator segments2 = 0; |
410 SegmentIterator segments2End = 0; | 424 SegmentIterator segments2End = 0; |
411 | 425 |
| 426 Vector<int, 32> segments; |
| 427 segments.reserveCapacity(std::max(shape1.segmentsSize(), shape2.segmentsSize
())); |
| 428 |
412 // Iterate over all spans. | 429 // Iterate over all spans. |
413 while (spans1 != spans1End && spans2 != spans2End) { | 430 while (spans1 != spans1End && spans2 != spans2End) { |
414 int y = 0; | 431 int y = 0; |
415 int test = spans1->y - spans2->y; | 432 int test = spans1->y - spans2->y; |
416 | 433 |
417 if (test <= 0) { | 434 if (test <= 0) { |
418 y = spans1->y; | 435 y = spans1->y; |
419 | 436 |
420 segments1 = shape1.segmentsBegin(spans1); | 437 segments1 = shape1.segmentsBegin(spans1); |
421 segments1End = shape1.segmentsEnd(spans1); | 438 segments1End = shape1.segmentsEnd(spans1); |
422 ++spans1; | 439 ++spans1; |
423 } | 440 } |
424 if (test >= 0) { | 441 if (test >= 0) { |
425 y = spans2->y; | 442 y = spans2->y; |
426 | 443 |
427 segments2 = shape2.segmentsBegin(spans2); | 444 segments2 = shape2.segmentsBegin(spans2); |
428 segments2End = shape2.segmentsEnd(spans2); | 445 segments2End = shape2.segmentsEnd(spans2); |
429 ++spans2; | 446 ++spans2; |
430 } | 447 } |
431 | 448 |
432 int flag = 0; | 449 int flag = 0; |
433 int oldFlag = 0; | 450 int oldFlag = 0; |
434 | 451 |
435 SegmentIterator s1 = segments1; | 452 SegmentIterator s1 = segments1; |
436 SegmentIterator s2 = segments2; | 453 SegmentIterator s2 = segments2; |
437 | 454 |
438 Vector<int, 32> segments; | 455 // Clear vector without dropping capacity. |
| 456 segments.resize(0); |
| 457 ASSERT(segments.capacity()); |
439 | 458 |
440 // Now iterate over the segments in each span and construct a new vector
of segments. | 459 // Now iterate over the segments in each span and construct a new vector
of segments. |
441 while (s1 != segments1End && s2 != segments2End) { | 460 while (s1 != segments1End && s2 != segments2End) { |
442 int test = *s1 - *s2; | 461 int test = *s1 - *s2; |
443 int x; | 462 int x; |
444 | 463 |
445 if (test <= 0) { | 464 if (test <= 0) { |
446 x = *s1; | 465 x = *s1; |
447 flag = flag ^ 1; | 466 flag = flag ^ 1; |
448 ++s1; | 467 ++s1; |
(...skipping 20 matching lines...) Expand all Loading... |
469 if (!segments.isEmpty() || !result.isEmpty()) | 488 if (!segments.isEmpty() || !result.isEmpty()) |
470 result.appendSpan(y, segments.data(), segments.data() + segments.siz
e()); | 489 result.appendSpan(y, segments.data(), segments.data() + segments.siz
e()); |
471 } | 490 } |
472 | 491 |
473 // Add any remaining spans. | 492 // Add any remaining spans. |
474 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) | 493 if (Operation::shouldAddRemainingSpansFromShape1 && spans1 != spans1End) |
475 result.appendSpans(shape1, spans1, spans1End); | 494 result.appendSpans(shape1, spans1, spans1End); |
476 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End
) | 495 else if (Operation::shouldAddRemainingSpansFromShape2 && spans2 != spans2End
) |
477 result.appendSpans(shape2, spans2, spans2End); | 496 result.appendSpans(shape2, spans2, spans2End); |
478 | 497 |
| 498 result.trimCapacities(); |
| 499 |
479 return result; | 500 return result; |
480 } | 501 } |
481 | 502 |
482 struct Region::Shape::UnionOperation { | 503 struct Region::Shape::UnionOperation { |
483 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Sha
pe& result) | 504 static bool trySimpleOperation(const Shape& shape1, const Shape& shape2, Sha
pe& result) |
484 { | 505 { |
485 if (shape1.isEmpty()) { | 506 if (shape1.isEmpty()) { |
486 result = shape2; | 507 result = shape2; |
487 return true; | 508 return true; |
488 } | 509 } |
(...skipping 112 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
601 m_bounds = m_shape.bounds(); | 622 m_bounds = m_shape.bounds(); |
602 } | 623 } |
603 | 624 |
604 void Region::translate(const IntSize& offset) | 625 void Region::translate(const IntSize& offset) |
605 { | 626 { |
606 m_bounds.move(offset); | 627 m_bounds.move(offset); |
607 m_shape.translate(offset); | 628 m_shape.translate(offset); |
608 } | 629 } |
609 | 630 |
610 } // namespace WebCore | 631 } // namespace WebCore |
OLD | NEW |