OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2011 Google Inc. All rights reserved. | 2 * Copyright (C) 2011 Google 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 are | 5 * modification, are permitted provided that the following conditions are |
6 * met: | 6 * met: |
7 * | 7 * |
8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
(...skipping 13 matching lines...) Expand all Loading... |
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
29 */ | 29 */ |
30 | 30 |
31 #ifndef OrderIterator_h | 31 #ifndef OrderIterator_h |
32 #define OrderIterator_h | 32 #define OrderIterator_h |
33 | 33 |
| 34 #include "wtf/HashMap.h" |
34 #include "wtf/Noncopyable.h" | 35 #include "wtf/Noncopyable.h" |
35 #include "wtf/Vector.h" | 36 #include "wtf/Vector.h" |
36 | 37 |
37 namespace WebCore { | 38 namespace WebCore { |
38 | 39 |
39 class RenderBox; | 40 class RenderBox; |
40 | 41 |
| 42 // Normally, -1 and 0 are not valid in a HashSet, but these are relatively likel
y order: values. Instead, |
| 43 // we make the two smallest int values invalid order: values (in the css parser
code we clamp them to |
| 44 // int min + 2). |
| 45 struct OrdererValueMapKeyHashTraits : WTF::GenericHashTraits<int> { |
| 46 static const bool emptyValueIsZero = false; |
| 47 static int emptyValue() { return std::numeric_limits<int>::min(); } |
| 48 static void constructDeletedValue(int& slot) { slot = std::numeric_limits<in
t>::min() + 1; } |
| 49 static bool isDeletedValue(int value) { return value == std::numeric_limits<
int>::min() + 1; } |
| 50 }; |
| 51 |
41 class OrderIterator { | 52 class OrderIterator { |
42 WTF_MAKE_NONCOPYABLE(OrderIterator); | 53 WTF_MAKE_NONCOPYABLE(OrderIterator); |
43 public: | 54 public: |
44 friend class OrderIteratorPopulator; | 55 friend class OrderIteratorPopulator; |
45 | 56 |
46 OrderIterator(const RenderBox*); | 57 OrderIterator(const RenderBox*); |
47 | 58 |
48 RenderBox* currentChild() const { return m_currentChild; } | 59 RenderBox* currentChild() const { return m_currentChild; } |
49 RenderBox* first(); | 60 RenderBox* first(); |
50 RenderBox* next(); | 61 RenderBox* next(); |
51 void reset(); | 62 void reset(); |
52 | 63 |
53 private: | 64 private: |
54 const RenderBox* m_containerBox; | 65 const RenderBox* m_containerBox; |
55 RenderBox* m_currentChild; | 66 |
56 // The inline capacity for a single item is used to cover the most | 67 // The inline capacity for a single item is used to cover the most |
57 // common case by far: if we only have the default 'order' value 0. | 68 // common case by far: if we only have the default 'order' value 0. |
58 typedef Vector<int, 1> OrderValues; | 69 typedef Vector<int, 1> OrderValues; |
59 OrderValues m_orderValues; | 70 OrderValues m_orderValues; |
60 Vector<int>::const_iterator m_orderValuesIterator; | 71 |
| 72 RenderBox* m_currentChild; |
| 73 size_t m_currentOrderIndex; |
| 74 size_t m_currentChildIndex; |
| 75 |
| 76 // This HashMap is empty if there is only one value. |
| 77 typedef HashMap<int, Vector<RenderBox*>, DefaultHash<int>::Hash, OrdererValu
eMapKeyHashTraits > OrderedValuesMap; |
| 78 OrderedValuesMap m_orderedValues; |
61 }; | 79 }; |
62 | 80 |
63 class OrderIteratorPopulator { | 81 class OrderIteratorPopulator { |
64 public: | 82 public: |
65 OrderIteratorPopulator(OrderIterator& iterator) | 83 OrderIteratorPopulator(OrderIterator& iterator) |
66 : m_iterator(iterator) | 84 : m_iterator(iterator) |
67 , m_anyChildHasDefaultOrderValue(false) | |
68 { | 85 { |
69 // Note that we don't release the memory here, we only invalidate the si
ze. | 86 // Note that we don't release the memory here, we only invalidate the si
ze. |
70 // This avoids unneeded reallocation if the size ends up not changing. | 87 // This avoids unneeded reallocation if the size ends up not changing. |
71 m_iterator.m_orderValues.shrink(0); | 88 m_iterator.m_orderValues.shrink(0); |
| 89 m_iterator.m_orderedValues.clear(); |
72 } | 90 } |
73 | 91 |
74 ~OrderIteratorPopulator(); | 92 ~OrderIteratorPopulator(); |
75 | 93 |
76 void collectChild(const RenderBox*); | 94 void collectChild(RenderBox*); |
77 | 95 |
78 private: | 96 private: |
79 void removeDuplicatedOrderValues(); | |
80 | |
81 OrderIterator& m_iterator; | 97 OrderIterator& m_iterator; |
82 bool m_anyChildHasDefaultOrderValue; | |
83 }; | 98 }; |
84 | 99 |
85 } // namespace WebCore | 100 } // namespace WebCore |
86 | 101 |
87 #endif // OrderIterator_h | 102 #endif // OrderIterator_h |
OLD | NEW |