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 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
57 template <typename T, size_t inlineBuffer, typename Allocator> | 57 template <typename T, size_t inlineBuffer, typename Allocator> |
58 class Deque; | 58 class Deque; |
59 | 59 |
60 // | 60 // |
61 // Vector Traits | 61 // Vector Traits |
62 // | 62 // |
63 | 63 |
64 // Bunch of traits for Vector are defined here, with which you can customize | 64 // Bunch of traits for Vector are defined here, with which you can customize |
65 // Vector's behavior. In most cases the default traits are appropriate, so you | 65 // Vector's behavior. In most cases the default traits are appropriate, so you |
66 // usually don't have to specialize those traits by yourself. | 66 // usually don't have to specialize those traits by yourself. |
| 67 // |
| 68 // The behavior of the implementation below can be controlled by VectorTraits. |
| 69 // If you want to change the behavior of your type, take a look at VectorTraits |
| 70 // (defined in VectorTraits.h), too. |
67 | 71 |
68 template <bool needsDestruction, typename T> | 72 template <bool needsDestruction, typename T> |
69 struct VectorDestructor; | 73 struct VectorDestructor; |
70 | 74 |
71 template <typename T> | 75 template <typename T> |
72 struct VectorDestructor<false, T> { | 76 struct VectorDestructor<false, T> { |
73 STATIC_ONLY(VectorDestructor); | 77 STATIC_ONLY(VectorDestructor); |
74 static void destruct(T*, T*) {} | 78 static void destruct(T*, T*) {} |
75 }; | 79 }; |
76 | 80 |
(...skipping 204 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
281 template <typename T> | 285 template <typename T> |
282 struct VectorElementComparer<std::unique_ptr<T>> { | 286 struct VectorElementComparer<std::unique_ptr<T>> { |
283 STATIC_ONLY(VectorElementComparer); | 287 STATIC_ONLY(VectorElementComparer); |
284 template <typename U> | 288 template <typename U> |
285 static bool compareElement(const std::unique_ptr<T>& left, const U& right) { | 289 static bool compareElement(const std::unique_ptr<T>& left, const U& right) { |
286 return left.get() == right; | 290 return left.get() == right; |
287 } | 291 } |
288 }; | 292 }; |
289 | 293 |
290 // A collection of all the traits used by Vector. This is basically an | 294 // A collection of all the traits used by Vector. This is basically an |
291 // implementation detail of Vector, and you should specialize individual traits | 295 // implementation detail of Vector, and you probably don't want to change this. |
292 // defined above, if you want to customize Vector's behavior. | 296 // If you want to customize Vector's behavior, you should specialize |
| 297 // VectorTraits instead (defined in VectorTraits.h). |
293 template <typename T> | 298 template <typename T> |
294 struct VectorTypeOperations { | 299 struct VectorTypeOperations { |
295 STATIC_ONLY(VectorTypeOperations); | 300 STATIC_ONLY(VectorTypeOperations); |
296 static void destruct(T* begin, T* end) { | 301 static void destruct(T* begin, T* end) { |
297 VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, | 302 VectorDestructor<VectorTraits<T>::needsDestruction, T>::destruct(begin, |
298 end); | 303 end); |
299 } | 304 } |
300 | 305 |
301 static void initialize(T* begin, T* end) { | 306 static void initialize(T* begin, T* end) { |
302 VectorInitializer<VectorTraits<T>::canInitializeWithMemset, T>::initialize( | 307 VectorInitializer<VectorTraits<T>::canInitializeWithMemset, T>::initialize( |
(...skipping 511 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
814 | 819 |
815 AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; | 820 AlignedBuffer<m_inlineBufferSize, WTF_ALIGN_OF(T)> m_inlineBuffer; |
816 template <typename U, size_t inlineBuffer, typename V> | 821 template <typename U, size_t inlineBuffer, typename V> |
817 friend class Deque; | 822 friend class Deque; |
818 }; | 823 }; |
819 | 824 |
820 // | 825 // |
821 // Vector | 826 // Vector |
822 // | 827 // |
823 | 828 |
| 829 // Vector is a container that works just like std::vector. WTF's Vector has |
| 830 // several extra functionalities: inline buffer, behavior customization via |
| 831 // traits, and Oilpan support. Those are explained in the sections below. |
| 832 // |
| 833 // Vector is the most basic container, which stores its element in a contiguous |
| 834 // buffer. The buffer is expanded automatically when necessary. The elements |
| 835 // are automatically moved to the new buffer. This event is called a |
| 836 // reallocation. A reallocation takes O(N)-time (N = number of elements), but |
| 837 // its occurrences are rare, so its time cost should not be significant, |
| 838 // compared to the time cost of other operations to the vector. |
| 839 // |
| 840 // Time complexity of key operations is as follows: |
| 841 // |
| 842 // * Indexed access -- O(1) |
| 843 // * Insertion or removal of an element at the end -- amortized O(1) |
| 844 // * Other insertion or removal -- O(N) |
| 845 // * Swapping with another vector -- O(1) |
| 846 // |
| 847 // 1. Iterator invalidation semantics |
| 848 // |
| 849 // Vector provides STL-compatible iterators and reverse iterators. Iterators |
| 850 // are _invalidated_ on certain occasions. Reading an invalidated iterator |
| 851 // causes undefined behavior. |
| 852 // |
| 853 // Iterators are invalidated on the following situations: |
| 854 // |
| 855 // * When a reallocation happens on a vector, all the iterators for that |
| 856 // vector will be invalidated. |
| 857 // * Some member functions invalidate part of the existing iterators for |
| 858 // the vector; see comments on the individual functions. |
| 859 // * [Oilpan only] Heap compaction invalidates all the iterators for any |
| 860 // HeapVectors. This means you can only store an iterator on stack, as |
| 861 // a local variable. |
| 862 // |
| 863 // In this context, pointers or references to an element of a Vector are |
| 864 // essentially equivalent to iterators, in that they also become invalid |
| 865 // whenever corresponding iterators are invalidated. |
| 866 // |
| 867 // 2. Inline buffer |
| 868 // |
| 869 // Vectors may have an _inline buffer_. An inline buffer is a storage area |
| 870 // that is contained in the vector itself, along with other metadata like |
| 871 // m_size. It is used as a storage space when the vector's elements fit in |
| 872 // that space. If the inline buffer becomes full and further space is |
| 873 // necessary, an out-of-line buffer is allocated in the heap, and it will |
| 874 // take over the role of the inline buffer. |
| 875 // |
| 876 // The existence of an inline buffer is indicated by non-zero |inlineCapacity| |
| 877 // template argument. The value represents the number of elements that can be |
| 878 // stored in the inline buffer. Zero |inlineCapacity| means the vector has no |
| 879 // inline buffer. |
| 880 // |
| 881 // An inline buffer increases the size of the Vector instances, and, in trade |
| 882 // for that, it gives you several performance benefits, as long as the number |
| 883 // of elements do not exceed |inlineCapacity|: |
| 884 // |
| 885 // * No heap allocation will be made. |
| 886 // * Memory locality will improve. |
| 887 // |
| 888 // Generally, having an inline buffer is useful for vectors that (1) are |
| 889 // frequently accessed or modified, and (2) contain only a few elements at |
| 890 // most. |
| 891 // |
| 892 // 3. Behavior customization |
| 893 // |
| 894 // You usually do not need to customize Vector's behavior, since the default |
| 895 // behavior is appropriate for normal usage. The behavior is controlled by |
| 896 // VectorTypeOperations traits template above. Read VectorTypeOperations |
| 897 // and VectorTraits if you want to change the behavior for your types (i.e. |
| 898 // if you really want faster vector operations). |
| 899 // |
| 900 // The default traits basically do the following: |
| 901 // |
| 902 // * Skip constructor call and fill zeros with memset for simple types; |
| 903 // * Skip destructor call for simple types; |
| 904 // * Copy or move by memcpy for simple types; and |
| 905 // * Customize the comparisons for smart pointer types, so you can look |
| 906 // up a std::unique_ptr<T> element with a raw pointer, for instance. |
| 907 // |
| 908 // 4. Oilpan |
| 909 // |
| 910 // If you want to store garbage collected objects in Vector, (1) use HeapVector |
| 911 // (defined in HeapAllocator.h) instead of Vector, and (2) make sure your |
| 912 // garbage-collected type is wrapped with Member, like: |
| 913 // |
| 914 // HeapVector<Member<Node>> nodes; |
| 915 // |
| 916 // Unlike normal garbage-collected objects, a HeapVector object itself is |
| 917 // NOT a garbage-collected object, but its backing buffer is allocated in |
| 918 // Oilpan heap, and it may still carry garbage-collected objects. |
| 919 // |
| 920 // Even though a HeapVector object is not garbage-collected, you still need |
| 921 // to trace it, if you stored it in your class. Also, you can allocate it |
| 922 // as a local variable. This is useful when you want to build a vector locally |
| 923 // and put it in an on-heap vector with swap(). |
| 924 // |
| 925 // Also, heap compaction, which may happen at any time when Blink code is not |
| 926 // running (i.e. Blink code does not appear in the call stack), may invalidate |
| 927 // existing iterators for any HeapVectors. So, essentially, you should always |
| 928 // allocate an iterator on stack (as a local variable), and you should not |
| 929 // store iterators in another heap object. |
| 930 |
824 template <typename T, | 931 template <typename T, |
825 size_t inlineCapacity = 0, | 932 size_t inlineCapacity = 0, |
826 typename Allocator = PartitionAllocator> | 933 typename Allocator = PartitionAllocator> |
827 class Vector | 934 class Vector |
828 : private VectorBuffer<T, INLINE_CAPACITY, Allocator>, | 935 : private VectorBuffer<T, INLINE_CAPACITY, Allocator>, |
829 // Heap-allocated vectors with no inlineCapacity never need a destructor. | 936 // Heap-allocated vectors with no inlineCapacity never need a destructor. |
830 public ConditionalDestructor<Vector<T, INLINE_CAPACITY, Allocator>, | 937 public ConditionalDestructor<Vector<T, INLINE_CAPACITY, Allocator>, |
831 (INLINE_CAPACITY == 0) && | 938 (INLINE_CAPACITY == 0) && |
832 Allocator::isGarbageCollected> { | 939 Allocator::isGarbageCollected> { |
833 USE_ALLOCATOR(Vector, Allocator); | 940 USE_ALLOCATOR(Vector, Allocator); |
(...skipping 959 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1793 visitor, *const_cast<T*>(bufferEntry)); | 1900 visitor, *const_cast<T*>(bufferEntry)); |
1794 checkUnusedSlots(buffer() + size(), buffer() + capacity()); | 1901 checkUnusedSlots(buffer() + size(), buffer() + capacity()); |
1795 } | 1902 } |
1796 } | 1903 } |
1797 | 1904 |
1798 } // namespace WTF | 1905 } // namespace WTF |
1799 | 1906 |
1800 using WTF::Vector; | 1907 using WTF::Vector; |
1801 | 1908 |
1802 #endif // WTF_Vector_h | 1909 #endif // WTF_Vector_h |
OLD | NEW |