webkitgtk-2.16.5HEADwebkitgtk-2.16.5master

1 files changed, 83 insertions, 61 deletions

diff --git a/Source/WTF/wtf/SegmentedVector.h b/Source/WTF/wtf/SegmentedVector.h
index 048aa5366..3e3fe0072 100644
--- a/Source/WTF/wtf/SegmentedVector.h
+++ b/Source/WTF/wtf/SegmentedVector.h
@@ -10,7 +10,7 @@
  * 2.  Redistributions in binary form must reproduce the above copyright
  *     notice, this list of conditions and the following disclaimer in the
  *     documentation and/or other materials provided with the distribution.
- * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
+ * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
  *     its contributors may be used to endorse or promote products derived
  *     from this software without specific prior written permission.
  *
@@ -35,65 +35,50 @@
 namespace WTF {
 
     // An iterator for SegmentedVector. It supports only the pre ++ operator
-    template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVector;
-    template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVectorIterator {
+    template <typename T, size_t SegmentSize = 8> class SegmentedVector;
+    template <typename T, size_t SegmentSize = 8> class SegmentedVectorIterator {
     private:
-        friend class SegmentedVector<T, SegmentSize, InlineCapacity>;
+        friend class SegmentedVector<T, SegmentSize>;
     public:
-        typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
+        typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
 
         ~SegmentedVectorIterator() { }
 
-        T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); }
-        T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); }
+        T& operator*() const { return m_vector.at(m_index); }
+        T* operator->() const { return &m_vector.at(m_index); }
 
         // Only prefix ++ operator supported
         Iterator& operator++()
         {
-            ASSERT(m_index != SegmentSize);
-            ++m_index;
-            if (m_index >= m_vector.m_segments.at(m_segment)->size())  {
-                if (m_segment + 1 < m_vector.m_segments.size()) {
-                    ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
-                    ++m_segment;
-                    m_index = 0;
-                } else {
-                    // Points to the "end" symbol
-                    m_segment = 0;
-                    m_index = SegmentSize;
-                }
-            }
+            m_index++;
             return *this;
         }
 
         bool operator==(const Iterator& other) const
         {
-            return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector;
+            return m_index == other.m_index && &m_vector == &other.m_vector;
         }
 
         bool operator!=(const Iterator& other) const
         {
-            return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector;
+            return m_index != other.m_index || &m_vector != &other.m_vector;
         }
 
-        SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize, InlineCapacity>& other)
+        SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
         {
             m_vector = other.m_vector;
-            m_segment = other.m_segment;
             m_index = other.m_index;
             return *this;
         }
 
     private:
-        SegmentedVectorIterator(SegmentedVector<T, SegmentSize, InlineCapacity>& vector, size_t segment, size_t index)
+        SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t index)
             : m_vector(vector)
-            , m_segment(segment)
             , m_index(index)
         {
         }
 
-        SegmentedVector<T, SegmentSize, InlineCapacity>& m_vector;
-        size_t m_segment;
+        SegmentedVector<T, SegmentSize>& m_vector;
         size_t m_index;
     };
 
@@ -101,19 +86,17 @@ namespace WTF {
     // stored in its buffer when it grows. Therefore, it is safe to keep
     // pointers into a SegmentedVector. The default tuning values are
     // optimized for segmented vectors that get large; you may want to use
-    // SegmentedVector<thingy, 1, 0> if you don't expect a lot of entries.
-    template <typename T, size_t SegmentSize, size_t InlineCapacity>
+    // SegmentedVector<thingy, 1> if you don't expect a lot of entries.
+    template <typename T, size_t SegmentSize>
     class SegmentedVector {
-        friend class SegmentedVectorIterator<T, SegmentSize, InlineCapacity>;
+        friend class SegmentedVectorIterator<T, SegmentSize>;
         WTF_MAKE_NONCOPYABLE(SegmentedVector);
+        WTF_MAKE_FAST_ALLOCATED;
 
     public:
-        typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
+        typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
 
-        SegmentedVector()
-            : m_size(0)
-        {
-        }
+        SegmentedVector() = default;
 
         ~SegmentedVector()
         {
@@ -125,12 +108,13 @@ namespace WTF {
 
         T& at(size_t index)
         {
-            return segmentFor(index)->at(subscriptFor(index));
+            ASSERT_WITH_SECURITY_IMPLICATION(index < m_size);
+            return segmentFor(index)->entries[subscriptFor(index)];
         }
 
         const T& at(size_t index) const
         {
-            return const_cast<SegmentedVector<T, SegmentSize, InlineCapacity>*>(this)->at(index);
+            return const_cast<SegmentedVector<T, SegmentSize>*>(this)->at(index);
         }
 
         T& operator[](size_t index)
@@ -143,29 +127,54 @@ namespace WTF {
             return at(index);
         }
 
+        T& first()
+        {
+            ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
+            return at(0);
+        }
+        const T& first() const
+        {
+            ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
+            return at(0);
+        }
         T& last()
         {
+            ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
+            return at(size() - 1);
+        }
+        const T& last() const
+        {
+            ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
             return at(size() - 1);
         }
 
-        template <typename U> void append(const U& value)
+        T takeLast()
         {
-            ++m_size;
+            ASSERT_WITH_SECURITY_IMPLICATION(!isEmpty());
+            T result = WTFMove(last());
+            --m_size;
+            return result;
+        }
 
+        template<typename... Args>
+        void append(Args&&... args)
+        {
+            ++m_size;
             if (!segmentExistsFor(m_size - 1))
-                m_segments.append(new Segment);
-            segmentFor(m_size - 1)->uncheckedAppend(value);
+                allocateSegment();
+            new (NotNull, &last()) T(std::forward<Args>(args)...);
         }
 
-        T& alloc()
+        template<typename... Args>
+        T& alloc(Args&&... args)
         {
-            append<T>(T());
+            append(std::forward<Args>(args)...);
             return last();
         }
 
         void removeLast()
         {
-            segmentFor(m_size - 1)->removeLast();
+            last().~T();
             --m_size;
         }
 
@@ -173,7 +182,10 @@ namespace WTF {
         {
             ASSERT(size > m_size);
             ensureSegmentsFor(size);
+            size_t oldSize = m_size;
             m_size = size;
+            for (size_t i = oldSize; i < m_size; ++i)
+                new (NotNull, &at(i)) T();
         }
 
         void clear()
@@ -185,12 +197,12 @@ namespace WTF {
 
         Iterator begin()
         {
-            return Iterator(*this, 0, m_size ? 0 : SegmentSize);
+            return Iterator(*this, 0);
         }
 
         Iterator end()
         {
-            return Iterator(*this, 0, SegmentSize);
+            return Iterator(*this, m_size);
         }
         
         void shrinkToFit()
@@ -199,12 +211,23 @@ namespace WTF {
         }
 
     private:
-        typedef Vector<T, SegmentSize> Segment;
+        struct Segment {
+#if COMPILER(MSVC)
+#pragma warning(push)
+#pragma warning(disable: 4200)
+#endif
+            T entries[0];
+#if COMPILER(MSVC)
+#pragma warning(pop)
+#endif
+        };
 
         void deleteAllSegments()
         {
-            for (size_t i = 0; i < m_segments.size(); i++)
-                delete m_segments[i];
+            for (size_t i = 0; i < m_size; ++i)
+                at(i).~T();
+            for (size_t i = 0; i < m_segments.size(); ++i)
+                fastFree(m_segments[i]);
         }
 
         bool segmentExistsFor(size_t index)
@@ -227,24 +250,23 @@ namespace WTF {
             size_t segmentCount = (m_size + SegmentSize - 1) / SegmentSize;
             size_t neededSegmentCount = (size + SegmentSize - 1) / SegmentSize;
 
-            // Fill up to N - 1 segments.
-            size_t end = neededSegmentCount - 1;
-            for (size_t i = segmentCount ? segmentCount - 1 : 0; i < end; ++i)
-                ensureSegment(i, SegmentSize);
-
-            // Grow segment N to accomodate the remainder.
-            ensureSegment(end, subscriptFor(size - 1) + 1);
+            for (size_t i = segmentCount ? segmentCount - 1 : 0; i < neededSegmentCount; ++i)
+                ensureSegment(i);
         }
 
-        void ensureSegment(size_t segmentIndex, size_t size)
+        void ensureSegment(size_t segmentIndex)
         {
             ASSERT_WITH_SECURITY_IMPLICATION(segmentIndex <= m_segments.size());
             if (segmentIndex == m_segments.size())
-                m_segments.append(new Segment);
-            m_segments[segmentIndex]->grow(size);
+                allocateSegment();
+        }
+
+        void allocateSegment()
+        {
+            m_segments.append(static_cast<Segment*>(fastMalloc(sizeof(T) * SegmentSize)));
         }
 
-        size_t m_size;
+        size_t m_size { 0 };
         Vector<Segment*> m_segments;
     };