OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. | 2 * Copyright (C) 2005, 2006, 2007, 2008 Apple Inc. All rights reserved. |
3 * | 3 * |
4 * This library is free software; you can redistribute it and/or | 4 * This library is free software; you can redistribute it and/or |
5 * modify it under the terms of the GNU Library General Public | 5 * modify it under the terms of the GNU Library General Public |
6 * License as published by the Free Software Foundation; either | 6 * License as published by the Free Software Foundation; either |
7 * version 2 of the License, or (at your option) any later version. | 7 * version 2 of the License, or (at your option) any later version. |
8 * | 8 * |
9 * This library is distributed in the hope that it will be useful, | 9 * This library is distributed in the hope that it will be useful, |
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
(...skipping 17 matching lines...) Expand all Loading... |
28 #include "wtf/NotFound.h" | 28 #include "wtf/NotFound.h" |
29 #include "wtf/StdLibExtras.h" | 29 #include "wtf/StdLibExtras.h" |
30 #include "wtf/VectorTraits.h" | 30 #include "wtf/VectorTraits.h" |
31 #include "wtf/allocator/PartitionAllocator.h" | 31 #include "wtf/allocator/PartitionAllocator.h" |
32 #include <algorithm> | 32 #include <algorithm> |
33 #include <initializer_list> | 33 #include <initializer_list> |
34 #include <iterator> | 34 #include <iterator> |
35 #include <string.h> | 35 #include <string.h> |
36 #include <utility> | 36 #include <utility> |
37 | 37 |
38 // For ASAN builds, disable inline buffers completely as they cause various issu
es. | 38 // For ASAN builds, disable inline buffers completely as they cause various |
| 39 // issues. |
39 #ifdef ANNOTATE_CONTIGUOUS_CONTAINER | 40 #ifdef ANNOTATE_CONTIGUOUS_CONTAINER |
40 #define INLINE_CAPACITY 0 | 41 #define INLINE_CAPACITY 0 |
41 #else | 42 #else |
42 #define INLINE_CAPACITY inlineCapacity | 43 #define INLINE_CAPACITY inlineCapacity |
43 #endif | 44 #endif |
44 | 45 |
45 namespace WTF { | 46 namespace WTF { |
46 | 47 |
47 #if defined(MEMORY_SANITIZER_INITIAL_SIZE) | 48 #if defined(MEMORY_SANITIZER_INITIAL_SIZE) |
48 static const size_t kInitialVectorSize = 1; | 49 static const size_t kInitialVectorSize = 1; |
(...skipping 407 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
456 return true; | 457 return true; |
457 } | 458 } |
458 return false; | 459 return false; |
459 } | 460 } |
460 | 461 |
461 void resetBufferPointer() { | 462 void resetBufferPointer() { |
462 m_buffer = nullptr; | 463 m_buffer = nullptr; |
463 m_capacity = 0; | 464 m_capacity = 0; |
464 } | 465 } |
465 | 466 |
466 // See the other specialization for the meaning of |thisHole| and |otherHole|.
They are irrelevant in this case. | 467 // See the other specialization for the meaning of |thisHole| and |otherHole|. |
| 468 // They are irrelevant in this case. |
467 void swapVectorBuffer(VectorBuffer<T, 0, Allocator>& other, | 469 void swapVectorBuffer(VectorBuffer<T, 0, Allocator>& other, |
468 OffsetRange thisHole, | 470 OffsetRange thisHole, |
469 OffsetRange otherHole) { | 471 OffsetRange otherHole) { |
470 std::swap(m_buffer, other.m_buffer); | 472 std::swap(m_buffer, other.m_buffer); |
471 std::swap(m_capacity, other.m_capacity); | 473 std::swap(m_capacity, other.m_capacity); |
472 std::swap(m_size, other.m_size); | 474 std::swap(m_size, other.m_size); |
473 } | 475 } |
474 | 476 |
475 using Base::allocateBuffer; | 477 using Base::allocateBuffer; |
476 using Base::allocationSize; | 478 using Base::allocationSize; |
(...skipping 98 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
575 else | 577 else |
576 resetBufferPointer(); | 578 resetBufferPointer(); |
577 } | 579 } |
578 | 580 |
579 size_t allocationSize(size_t capacity) const { | 581 size_t allocationSize(size_t capacity) const { |
580 if (capacity <= inlineCapacity) | 582 if (capacity <= inlineCapacity) |
581 return m_inlineBufferSize; | 583 return m_inlineBufferSize; |
582 return Base::allocationSize(capacity); | 584 return Base::allocationSize(capacity); |
583 } | 585 } |
584 | 586 |
585 // Swap two vector buffers, both of which have the same non-zero inline capaci
ty. | 587 // Swap two vector buffers, both of which have the same non-zero inline |
| 588 // capacity. |
586 // | 589 // |
587 // If the data is in an out-of-line buffer, we can just pass the pointers acro
ss the two buffers. | 590 // If the data is in an out-of-line buffer, we can just pass the pointers |
588 // If the data is in an inline buffer, we need to either swap or move each ele
ment, depending on whether each | 591 // across the two buffers. If the data is in an inline buffer, we need to |
589 // slot is occupied or not. | 592 // either swap or move each element, depending on whether each slot is |
| 593 // occupied or not. |
590 // | 594 // |
591 // Further complication comes from the fact that VectorBuffer is also used as
the backing store of a Deque. | 595 // Further complication comes from the fact that VectorBuffer is also used as |
592 // Deque allocates the objects like a ring buffer, so there may be a "hole" (u
nallocated region) in the middle | 596 // the backing store of a Deque. Deque allocates the objects like a ring |
593 // of the buffer. This function assumes elements in a range [m_buffer, m_buffe
r + m_size) are all allocated | 597 // buffer, so there may be a "hole" (unallocated region) in the middle of the |
594 // except for elements within |thisHole|. The same applies for |other.m_buffer
| and |otherHole|. | 598 // buffer. This function assumes elements in a range [m_buffer, m_buffer + |
| 599 // m_size) are all allocated except for elements within |thisHole|. The same |
| 600 // applies for |other.m_buffer| and |otherHole|. |
595 void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, | 601 void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, |
596 OffsetRange thisHole, | 602 OffsetRange thisHole, |
597 OffsetRange otherHole) { | 603 OffsetRange otherHole) { |
598 using TypeOperations = VectorTypeOperations<T>; | 604 using TypeOperations = VectorTypeOperations<T>; |
599 | 605 |
600 if (buffer() != inlineBuffer() && other.buffer() != other.inlineBuffer()) { | 606 if (buffer() != inlineBuffer() && other.buffer() != other.inlineBuffer()) { |
601 // The easiest case: both buffers are non-inline. We just need to swap the
pointers. | 607 // The easiest case: both buffers are non-inline. We just need to swap the |
| 608 // pointers. |
602 std::swap(m_buffer, other.m_buffer); | 609 std::swap(m_buffer, other.m_buffer); |
603 std::swap(m_capacity, other.m_capacity); | 610 std::swap(m_capacity, other.m_capacity); |
604 std::swap(m_size, other.m_size); | 611 std::swap(m_size, other.m_size); |
605 return; | 612 return; |
606 } | 613 } |
607 | 614 |
608 Allocator::enterGCForbiddenScope(); | 615 Allocator::enterGCForbiddenScope(); |
609 | 616 |
610 // Otherwise, we at least need to move some elements from one inline buffer
to another. | 617 // Otherwise, we at least need to move some elements from one inline buffer |
| 618 // to another. |
611 // | 619 // |
612 // Terminology: "source" is a place from which elements are copied, and "des
tination" is a place to which | 620 // Terminology: "source" is a place from which elements are copied, and |
613 // elements are copied. thisSource or otherSource can be empty (represented
by nullptr) when this range or | 621 // "destination" is a place to which elements are copied. thisSource or |
| 622 // otherSource can be empty (represented by nullptr) when this range or |
614 // other range is in an out-of-line buffer. | 623 // other range is in an out-of-line buffer. |
615 // | 624 // |
616 // We first record which range needs to get moved and where elements in such
a range will go. Elements in | 625 // We first record which range needs to get moved and where elements in such |
617 // an inline buffer will go to the other buffer's inline buffer. Elements in
an out-of-line buffer won't move, | 626 // a range will go. Elements in an inline buffer will go to the other |
| 627 // buffer's inline buffer. Elements in an out-of-line buffer won't move, |
618 // because we can just swap pointers of out-of-line buffers. | 628 // because we can just swap pointers of out-of-line buffers. |
619 T* thisSourceBegin = nullptr; | 629 T* thisSourceBegin = nullptr; |
620 size_t thisSourceSize = 0; | 630 size_t thisSourceSize = 0; |
621 T* thisDestinationBegin = nullptr; | 631 T* thisDestinationBegin = nullptr; |
622 if (buffer() == inlineBuffer()) { | 632 if (buffer() == inlineBuffer()) { |
623 thisSourceBegin = buffer(); | 633 thisSourceBegin = buffer(); |
624 thisSourceSize = m_size; | 634 thisSourceSize = m_size; |
625 thisDestinationBegin = other.inlineBuffer(); | 635 thisDestinationBegin = other.inlineBuffer(); |
626 if (!thisHole.empty()) { // Sanity check. | 636 if (!thisHole.empty()) { // Sanity check. |
627 ASSERT(thisHole.begin < thisHole.end); | 637 ASSERT(thisHole.begin < thisHole.end); |
(...skipping 11 matching lines...) Expand all Loading... |
639 otherSourceSize = other.m_size; | 649 otherSourceSize = other.m_size; |
640 otherDestinationBegin = inlineBuffer(); | 650 otherDestinationBegin = inlineBuffer(); |
641 if (!otherHole.empty()) { | 651 if (!otherHole.empty()) { |
642 ASSERT(otherHole.begin < otherHole.end); | 652 ASSERT(otherHole.begin < otherHole.end); |
643 ASSERT(otherHole.end <= otherSourceSize); | 653 ASSERT(otherHole.end <= otherSourceSize); |
644 } | 654 } |
645 } else { | 655 } else { |
646 otherHole.begin = otherHole.end = 0; | 656 otherHole.begin = otherHole.end = 0; |
647 } | 657 } |
648 | 658 |
649 // Next, we mutate members and do other bookkeeping. We do pointer swapping
(for out-of-line buffers) here if | 659 // Next, we mutate members and do other bookkeeping. We do pointer swapping |
650 // we can. From now on, don't assume buffer() or capacity() maintains their
original values. | 660 // (for out-of-line buffers) here if we can. From now on, don't assume |
| 661 // buffer() or capacity() maintains their original values. |
651 std::swap(m_capacity, other.m_capacity); | 662 std::swap(m_capacity, other.m_capacity); |
652 if (thisSourceBegin && | 663 if (thisSourceBegin && |
653 !otherSourceBegin) { // Our buffer is inline, theirs is not. | 664 !otherSourceBegin) { // Our buffer is inline, theirs is not. |
654 ASSERT(buffer() == inlineBuffer()); | 665 ASSERT(buffer() == inlineBuffer()); |
655 ASSERT(other.buffer() != other.inlineBuffer()); | 666 ASSERT(other.buffer() != other.inlineBuffer()); |
656 ANNOTATE_DELETE_BUFFER(m_buffer, inlineCapacity, m_size); | 667 ANNOTATE_DELETE_BUFFER(m_buffer, inlineCapacity, m_size); |
657 m_buffer = other.buffer(); | 668 m_buffer = other.buffer(); |
658 other.m_buffer = other.inlineBuffer(); | 669 other.m_buffer = other.inlineBuffer(); |
659 std::swap(m_size, other.m_size); | 670 std::swap(m_size, other.m_size); |
660 ANNOTATE_NEW_BUFFER(other.m_buffer, inlineCapacity, other.m_size); | 671 ANNOTATE_NEW_BUFFER(other.m_buffer, inlineCapacity, other.m_size); |
661 } else if (!thisSourceBegin && | 672 } else if (!thisSourceBegin && |
662 otherSourceBegin) { // Their buffer is inline, ours is not. | 673 otherSourceBegin) { // Their buffer is inline, ours is not. |
663 ASSERT(buffer() != inlineBuffer()); | 674 ASSERT(buffer() != inlineBuffer()); |
664 ASSERT(other.buffer() == other.inlineBuffer()); | 675 ASSERT(other.buffer() == other.inlineBuffer()); |
665 ANNOTATE_DELETE_BUFFER(other.m_buffer, inlineCapacity, other.m_size); | 676 ANNOTATE_DELETE_BUFFER(other.m_buffer, inlineCapacity, other.m_size); |
666 other.m_buffer = buffer(); | 677 other.m_buffer = buffer(); |
667 m_buffer = inlineBuffer(); | 678 m_buffer = inlineBuffer(); |
668 std::swap(m_size, other.m_size); | 679 std::swap(m_size, other.m_size); |
669 ANNOTATE_NEW_BUFFER(m_buffer, inlineCapacity, m_size); | 680 ANNOTATE_NEW_BUFFER(m_buffer, inlineCapacity, m_size); |
670 } else { // Both buffers are inline. | 681 } else { // Both buffers are inline. |
671 ASSERT(thisSourceBegin && otherSourceBegin); | 682 ASSERT(thisSourceBegin && otherSourceBegin); |
672 ASSERT(buffer() == inlineBuffer()); | 683 ASSERT(buffer() == inlineBuffer()); |
673 ASSERT(other.buffer() == other.inlineBuffer()); | 684 ASSERT(other.buffer() == other.inlineBuffer()); |
674 ANNOTATE_CHANGE_SIZE(m_buffer, inlineCapacity, m_size, other.m_size); | 685 ANNOTATE_CHANGE_SIZE(m_buffer, inlineCapacity, m_size, other.m_size); |
675 ANNOTATE_CHANGE_SIZE(other.m_buffer, inlineCapacity, other.m_size, | 686 ANNOTATE_CHANGE_SIZE(other.m_buffer, inlineCapacity, other.m_size, |
676 m_size); | 687 m_size); |
677 std::swap(m_size, other.m_size); | 688 std::swap(m_size, other.m_size); |
678 } | 689 } |
679 | 690 |
680 // We are ready to move elements. We determine an action for each "section",
which is a contiguous range such | 691 // We are ready to move elements. We determine an action for each "section", |
681 // that all elements in the range are treated similarly. | 692 // which is a contiguous range such that all elements in the range are |
| 693 // treated similarly. |
682 size_t sectionBegin = 0; | 694 size_t sectionBegin = 0; |
683 while (sectionBegin < inlineCapacity) { | 695 while (sectionBegin < inlineCapacity) { |
684 // To determine the end of this section, we list up all the boundaries whe
re the "occupiedness" may change. | 696 // To determine the end of this section, we list up all the boundaries |
| 697 // where the "occupiedness" may change. |
685 size_t sectionEnd = inlineCapacity; | 698 size_t sectionEnd = inlineCapacity; |
686 if (thisSourceBegin && sectionBegin < thisSourceSize) | 699 if (thisSourceBegin && sectionBegin < thisSourceSize) |
687 sectionEnd = std::min(sectionEnd, thisSourceSize); | 700 sectionEnd = std::min(sectionEnd, thisSourceSize); |
688 if (!thisHole.empty() && sectionBegin < thisHole.begin) | 701 if (!thisHole.empty() && sectionBegin < thisHole.begin) |
689 sectionEnd = std::min(sectionEnd, thisHole.begin); | 702 sectionEnd = std::min(sectionEnd, thisHole.begin); |
690 if (!thisHole.empty() && sectionBegin < thisHole.end) | 703 if (!thisHole.empty() && sectionBegin < thisHole.end) |
691 sectionEnd = std::min(sectionEnd, thisHole.end); | 704 sectionEnd = std::min(sectionEnd, thisHole.end); |
692 if (otherSourceBegin && sectionBegin < otherSourceSize) | 705 if (otherSourceBegin && sectionBegin < otherSourceSize) |
693 sectionEnd = std::min(sectionEnd, otherSourceSize); | 706 sectionEnd = std::min(sectionEnd, otherSourceSize); |
694 if (!otherHole.empty() && sectionBegin < otherHole.begin) | 707 if (!otherHole.empty() && sectionBegin < otherHole.begin) |
(...skipping 12 matching lines...) Expand all Loading... |
707 thisOccupied = true; | 720 thisOccupied = true; |
708 } | 721 } |
709 bool otherOccupied = false; | 722 bool otherOccupied = false; |
710 if (otherSourceBegin && sectionBegin < otherSourceSize) { | 723 if (otherSourceBegin && sectionBegin < otherSourceSize) { |
711 if (otherHole.empty() || sectionBegin < otherHole.begin || | 724 if (otherHole.empty() || sectionBegin < otherHole.begin || |
712 sectionBegin >= otherHole.end) | 725 sectionBegin >= otherHole.end) |
713 otherOccupied = true; | 726 otherOccupied = true; |
714 } | 727 } |
715 | 728 |
716 if (thisOccupied && otherOccupied) { | 729 if (thisOccupied && otherOccupied) { |
717 // Both occupied; swap them. In this case, one's destination must be the
other's source (i.e. both | 730 // Both occupied; swap them. In this case, one's destination must be the |
718 // ranges are in inline buffers). | 731 // other's source (i.e. both ranges are in inline buffers). |
719 ASSERT(thisDestinationBegin == otherSourceBegin); | 732 ASSERT(thisDestinationBegin == otherSourceBegin); |
720 ASSERT(otherDestinationBegin == thisSourceBegin); | 733 ASSERT(otherDestinationBegin == thisSourceBegin); |
721 TypeOperations::swap(thisSourceBegin + sectionBegin, | 734 TypeOperations::swap(thisSourceBegin + sectionBegin, |
722 thisSourceBegin + sectionEnd, | 735 thisSourceBegin + sectionEnd, |
723 otherSourceBegin + sectionBegin); | 736 otherSourceBegin + sectionBegin); |
724 } else if (thisOccupied) { | 737 } else if (thisOccupied) { |
725 // Move from ours to theirs. | 738 // Move from ours to theirs. |
726 TypeOperations::move(thisSourceBegin + sectionBegin, | 739 TypeOperations::move(thisSourceBegin + sectionBegin, |
727 thisSourceBegin + sectionEnd, | 740 thisSourceBegin + sectionEnd, |
728 thisDestinationBegin + sectionBegin); | 741 thisDestinationBegin + sectionBegin); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
762 static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T); | 775 static const size_t m_inlineBufferSize = inlineCapacity * sizeof(T); |
763 T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); } | 776 T* inlineBuffer() { return reinterpret_cast_ptr<T*>(m_inlineBuffer.buffer); } |
764 const T* inlineBuffer() const { | 777 const T* inlineBuffer() const { |
765 return reinterpret_cast_ptr<const T*>(m_inlineBuffer.buffer); | 778 return reinterpret_cast_ptr<const T*>(m_inlineBuffer.buffer); |
766 } | 779 } |
767 | 780 |
768 AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; | 781 AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; |
769 template <typename U, size_t inlineBuffer, typename V> | 782 template <typename U, size_t inlineBuffer, typename V> |
770 friend class Deque; | 783 friend class Deque; |
771 }; | 784 }; |
772 | 785 // Heap-allocated vectors with no inlineCapacity never need a destructor. |
773 template < | 786 template <typename T, |
774 typename T, | 787 size_t inlineCapacity = 0, |
775 size_t inlineCapacity = 0, | 788 typename Allocator = PartitionAllocator> |
776 typename Allocator = | |
777 PartitionAllocator> // Heap-allocated vectors with no inlineCapacity ne
ver need a destructor. | |
778 class Vector | 789 class Vector |
779 : private VectorBuffer<T, INLINE_CAPACITY, Allocator>, | 790 : private VectorBuffer<T, INLINE_CAPACITY, Allocator>, |
780 public ConditionalDestructor<Vector<T, INLINE_CAPACITY, Allocator>, | 791 public ConditionalDestructor<Vector<T, INLINE_CAPACITY, Allocator>, |
781 (INLINE_CAPACITY == 0) && | 792 (INLINE_CAPACITY == 0) && |
782 Allocator::isGarbageCollected> { | 793 Allocator::isGarbageCollected> { |
783 WTF_USE_ALLOCATOR(Vector, Allocator); | 794 WTF_USE_ALLOCATOR(Vector, Allocator); |
784 using Base = VectorBuffer<T, INLINE_CAPACITY, Allocator>; | 795 using Base = VectorBuffer<T, INLINE_CAPACITY, Allocator>; |
785 using TypeOperations = VectorTypeOperations<T>; | 796 using TypeOperations = VectorTypeOperations<T>; |
786 using OffsetRange = typename Base::OffsetRange; | 797 using OffsetRange = typename Base::OffsetRange; |
787 | 798 |
(...skipping 799 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1587 visitor, *const_cast<T*>(bufferEntry)); | 1598 visitor, *const_cast<T*>(bufferEntry)); |
1588 checkUnusedSlots(buffer() + size(), buffer() + capacity()); | 1599 checkUnusedSlots(buffer() + size(), buffer() + capacity()); |
1589 } | 1600 } |
1590 } | 1601 } |
1591 | 1602 |
1592 } // namespace WTF | 1603 } // namespace WTF |
1593 | 1604 |
1594 using WTF::Vector; | 1605 using WTF::Vector; |
1595 | 1606 |
1596 #endif // WTF_Vector_h | 1607 #endif // WTF_Vector_h |
OLD | NEW |