FCL/sf/mw/qtwebkit: comparison JavaScriptCore/wtf/SegmentedVector.h

equal deleted inserted replaced

--1:000000000000
+:4f2f89ce4247
+/*
+* Copyright (C) 2008 Apple Inc. All rights reserved.
+*
+* Redistribution and use in source and binary forms, with or without
+* modification, are permitted provided that the following conditions
+* are met:
+*
+* 1.  Redistributions of source code must retain the above copyright
+*     notice, this list of conditions and the following disclaimer.
+* 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
+*     its contributors may be used to endorse or promote products derived
+*     from this software without specific prior written permission.
+*
+* THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+* DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+#ifndef SegmentedVector_h
+#define SegmentedVector_h
+#include <wtf/Vector.h>
+namespace WTF {
+// An iterator for SegmentedVector. It supports only the pre ++ operator
+template <typename T, size_t SegmentSize> class SegmentedVector;
+template <typename T, size_t SegmentSize> class SegmentedVectorIterator {
+private:
+friend class SegmentedVector<T, SegmentSize>;
+public:
+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); }
+// 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;
+}
+}
+return *this;
+}
+bool operator==(const Iterator& other) const
+{
+return (m_index == other.m_index && m_segment = other.m_segment && &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);
+}
+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>& vector, size_t segment, size_t index)
+: m_vector(vector)
+, m_segment(segment)
+, m_index(index)
+{
+}
+SegmentedVector<T, SegmentSize>& m_vector;
+size_t m_segment;
+size_t m_index;
+};
+// SegmentedVector is just like Vector, but it doesn't move the values
+// stored in its buffer when it grows. Therefore, it is safe to keep
+// pointers into a SegmentedVector.
+template <typename T, size_t SegmentSize> class SegmentedVector {
+friend class SegmentedVectorIterator<T, SegmentSize>;
+public:
+typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
+SegmentedVector()
+: m_size(0)
+{
+m_segments.append(&m_inlineSegment);
+}
+~SegmentedVector()
+{
+deleteAllSegments();
+}
+size_t size() const { return m_size; }
+bool isEmpty() const { return !size(); }
+T& at(size_t index)
+{
+if (index < SegmentSize)
+return m_inlineSegment[index];
+return segmentFor(index)->at(subscriptFor(index));
+}
+T& operator[](size_t index)
+{
+return at(index);
+}
+T& last()
+{
+return at(size() - 1);
+}
+template <typename U> void append(const U& value)
+{
+++m_size;
+if (m_size <= SegmentSize) {
+m_inlineSegment.uncheckedAppend(value);
+return;
+}
+if (!segmentExistsFor(m_size - 1))
+m_segments.append(new Segment);
+segmentFor(m_size - 1)->uncheckedAppend(value);
+}
+T& alloc()
+{
+append<T>(T());
+return last();
+}
+void removeLast()
+{
+if (m_size <= SegmentSize)
+m_inlineSegment.removeLast();
+else
+segmentFor(m_size - 1)->removeLast();
+--m_size;
+}
+void grow(size_t size)
+{
+ASSERT(size > m_size);
+ensureSegmentsFor(size);
+m_size = size;
+}
+void clear()
+{
+deleteAllSegments();
+m_segments.resize(1);
+m_inlineSegment.clear();
+m_size = 0;
+}
+Iterator begin()
+{
+return Iterator(*this, 0, m_size ? 0 : SegmentSize);
+}
+Iterator end()
+{
+return Iterator(*this, 0, SegmentSize);
+}
+private:
+typedef Vector<T, SegmentSize> Segment;
+void deleteAllSegments()
+{
+// Skip the first segment, because it's our inline segment, which was
+// not created by new.
+for (size_t i = 1; i < m_segments.size(); i++)
+delete m_segments[i];
+}
+bool segmentExistsFor(size_t index)
+{
+return index / SegmentSize < m_segments.size();
+}
+Segment* segmentFor(size_t index)
+{
+return m_segments[index / SegmentSize];
+}
+size_t subscriptFor(size_t index)
+{
+return index % SegmentSize;
+}
+void ensureSegmentsFor(size_t size)
+{
+size_t segmentCount = m_size / SegmentSize;
+if (m_size % SegmentSize)
+++segmentCount;
+segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
+size_t neededSegmentCount = size / SegmentSize;
+if (size % SegmentSize)
+++neededSegmentCount;
+// Fill up to N - 1 segments.
+size_t end = neededSegmentCount - 1;
+for (size_t i = segmentCount - 1; i < end; ++i)
+ensureSegment(i, SegmentSize);
+// Grow segment N to accomodate the remainder.
+ensureSegment(end, subscriptFor(size - 1) + 1);
+}
+void ensureSegment(size_t segmentIndex, size_t size)
+{
+ASSERT(segmentIndex <= m_segments.size());
+if (segmentIndex == m_segments.size())
+m_segments.append(new Segment);
+m_segments[segmentIndex]->grow(size);
+}
+size_t m_size;
+Segment m_inlineSegment;
+Vector<Segment*, 32> m_segments;
+};
+} // namespace WTF
+using WTF::SegmentedVector;
+#endif // SegmentedVector_h