The Tor Browser / file revision

 /*

  * 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 assembler_wtf_SegmentedVector_h

 #define assembler_wtf_SegmentedVector_h

 #include "js/Utility.h"

 #include "js/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[m_segment])[m_index]; }

         T* operator->() const { return &(*m_vector.m_segments[m_segment])[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_index >= m_vector.m_segments[m_segment]->length())  {

                 //if (m_segment + 1 < m_vector.m_segments.size()) {

                 if (m_segment + 1 < m_vector.m_segments.length()) {

                     //ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);

                     ASSERT(m_vector.m_segments[m_segment]->length() > 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);

                 m_inlineSegment.append(value);

                 return;

             }

             if (!segmentExistsFor(m_size - 1))

                 m_segments.append(js_new<Segment>());

             //segmentFor(m_size - 1)->uncheckedAppend(value);

             segmentFor(m_size - 1)->append(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 js::Vector<T, SegmentSize ,js::SystemAllocPolicy > 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++)

             for (size_t i = 1; i < m_segments.length(); i++)

                 js_delete<Segment>(m_segments[i]);

         }

         bool segmentExistsFor(size_t index)

         {

             //return index / SegmentSize < m_segments.size();

             return index / SegmentSize < m_segments.length();

         }

         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.

             segmentCount = segmentCount > 1 ? 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(js_new<Segment>());

             m_segments[segmentIndex]->grow(size);

         }

         size_t m_size;

         Segment m_inlineSegment;

         js::Vector<Segment*, 32 ,js::SystemAllocPolicy > m_segments;

     };

 } // namespace WTF

 using WTF::SegmentedVector;

 #endif /* assembler_wtf_SegmentedVector_h */