1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/assembler/wtf/SegmentedVector.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,264 @@
1.4 +/*
1.5 + * Copyright (C) 2008 Apple Inc. All rights reserved.
1.6 + *
1.7 + * Redistribution and use in source and binary forms, with or without
1.8 + * modification, are permitted provided that the following conditions
1.9 + * are met:
1.10 + *
1.11 + * 1. Redistributions of source code must retain the above copyright
1.12 + * notice, this list of conditions and the following disclaimer.
1.13 + * 2. Redistributions in binary form must reproduce the above copyright
1.14 + * notice, this list of conditions and the following disclaimer in the
1.15 + * documentation and/or other materials provided with the distribution.
1.16 + * 3. Neither the name of Apple Computer, Inc. ("Apple") nor the names of
1.17 + * its contributors may be used to endorse or promote products derived
1.18 + * from this software without specific prior written permission.
1.19 + *
1.20 + * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
1.21 + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
1.22 + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
1.23 + * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
1.24 + * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
1.25 + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
1.26 + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
1.27 + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
1.29 + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 + */
1.31 +
1.32 +#ifndef assembler_wtf_SegmentedVector_h
1.33 +#define assembler_wtf_SegmentedVector_h
1.34 +
1.35 +#include "js/Utility.h"
1.36 +#include "js/Vector.h"
1.37 +
1.38 +namespace WTF {
1.39 +
1.40 + // An iterator for SegmentedVector. It supports only the pre ++ operator
1.41 + template <typename T, size_t SegmentSize> class SegmentedVector;
1.42 + template <typename T, size_t SegmentSize> class SegmentedVectorIterator {
1.43 + private:
1.44 + friend class SegmentedVector<T, SegmentSize>;
1.45 + public:
1.46 + typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
1.47 +
1.48 + ~SegmentedVectorIterator() { }
1.49 +
1.50 + T& operator*() const { return (*m_vector.m_segments[m_segment])[m_index]; }
1.51 + T* operator->() const { return &(*m_vector.m_segments[m_segment])[m_index]; }
1.52 +
1.53 + // Only prefix ++ operator supported
1.54 + Iterator& operator++()
1.55 + {
1.56 + ASSERT(m_index != SegmentSize);
1.57 + ++m_index;
1.58 + //if (m_index >= m_vector.m_segments.at(m_segment)->size()) {
1.59 + if (m_index >= m_vector.m_segments[m_segment]->length()) {
1.60 + //if (m_segment + 1 < m_vector.m_segments.size()) {
1.61 + if (m_segment + 1 < m_vector.m_segments.length()) {
1.62 + //ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
1.63 + ASSERT(m_vector.m_segments[m_segment]->length() > 0);
1.64 + ++m_segment;
1.65 + m_index = 0;
1.66 + } else {
1.67 + // Points to the "end" symbol
1.68 + m_segment = 0;
1.69 + m_index = SegmentSize;
1.70 + }
1.71 + }
1.72 + return *this;
1.73 + }
1.74 +
1.75 + bool operator==(const Iterator& other) const
1.76 + {
1.77 + return (m_index == other.m_index && m_segment = other.m_segment && &m_vector == &other.m_vector);
1.78 + }
1.79 +
1.80 + bool operator!=(const Iterator& other) const
1.81 + {
1.82 + return (m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector);
1.83 + }
1.84 +
1.85 + SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize>& other)
1.86 + {
1.87 + m_vector = other.m_vector;
1.88 + m_segment = other.m_segment;
1.89 + m_index = other.m_index;
1.90 + return *this;
1.91 + }
1.92 +
1.93 + private:
1.94 + SegmentedVectorIterator(SegmentedVector<T, SegmentSize>& vector, size_t segment, size_t index)
1.95 + : m_vector(vector)
1.96 + , m_segment(segment)
1.97 + , m_index(index)
1.98 + {
1.99 + }
1.100 +
1.101 + SegmentedVector<T, SegmentSize>& m_vector;
1.102 + size_t m_segment;
1.103 + size_t m_index;
1.104 + };
1.105 +
1.106 + // SegmentedVector is just like Vector, but it doesn't move the values
1.107 + // stored in its buffer when it grows. Therefore, it is safe to keep
1.108 + // pointers into a SegmentedVector.
1.109 + template <typename T, size_t SegmentSize> class SegmentedVector {
1.110 + friend class SegmentedVectorIterator<T, SegmentSize>;
1.111 + public:
1.112 + typedef SegmentedVectorIterator<T, SegmentSize> Iterator;
1.113 +
1.114 + SegmentedVector()
1.115 + : m_size(0)
1.116 + {
1.117 + m_segments.append(&m_inlineSegment);
1.118 + }
1.119 +
1.120 + ~SegmentedVector()
1.121 + {
1.122 + deleteAllSegments();
1.123 + }
1.124 +
1.125 + size_t size() const { return m_size; }
1.126 + bool isEmpty() const { return !size(); }
1.127 +
1.128 + T& at(size_t index)
1.129 + {
1.130 + if (index < SegmentSize)
1.131 + return m_inlineSegment[index];
1.132 + return segmentFor(index)->at(subscriptFor(index));
1.133 + }
1.134 +
1.135 + T& operator[](size_t index)
1.136 + {
1.137 + return at(index);
1.138 + }
1.139 +
1.140 + T& last()
1.141 + {
1.142 + return at(size() - 1);
1.143 + }
1.144 +
1.145 + template <typename U> void append(const U& value)
1.146 + {
1.147 + ++m_size;
1.148 +
1.149 + if (m_size <= SegmentSize) {
1.150 + //m_inlineSegment.uncheckedAppend(value);
1.151 + m_inlineSegment.append(value);
1.152 + return;
1.153 + }
1.154 +
1.155 + if (!segmentExistsFor(m_size - 1))
1.156 + m_segments.append(js_new<Segment>());
1.157 + //segmentFor(m_size - 1)->uncheckedAppend(value);
1.158 + segmentFor(m_size - 1)->append(value);
1.159 + }
1.160 +
1.161 + T& alloc()
1.162 + {
1.163 + append<T>(T());
1.164 + return last();
1.165 + }
1.166 +
1.167 + void removeLast()
1.168 + {
1.169 + if (m_size <= SegmentSize)
1.170 + m_inlineSegment.removeLast();
1.171 + else
1.172 + segmentFor(m_size - 1)->removeLast();
1.173 + --m_size;
1.174 + }
1.175 +
1.176 + void grow(size_t size)
1.177 + {
1.178 + ASSERT(size > m_size);
1.179 + ensureSegmentsFor(size);
1.180 + m_size = size;
1.181 + }
1.182 +
1.183 + void clear()
1.184 + {
1.185 + deleteAllSegments();
1.186 + m_segments.resize(1);
1.187 + m_inlineSegment.clear();
1.188 + m_size = 0;
1.189 + }
1.190 +
1.191 + Iterator begin()
1.192 + {
1.193 + return Iterator(*this, 0, m_size ? 0 : SegmentSize);
1.194 + }
1.195 +
1.196 + Iterator end()
1.197 + {
1.198 + return Iterator(*this, 0, SegmentSize);
1.199 + }
1.200 +
1.201 + private:
1.202 + typedef js::Vector<T, SegmentSize ,js::SystemAllocPolicy > Segment;
1.203 +
1.204 + void deleteAllSegments()
1.205 + {
1.206 + // Skip the first segment, because it's our inline segment, which was
1.207 + // not created by new.
1.208 + //for (size_t i = 1; i < m_segments.size(); i++)
1.209 + for (size_t i = 1; i < m_segments.length(); i++)
1.210 + js_delete<Segment>(m_segments[i]);
1.211 + }
1.212 +
1.213 + bool segmentExistsFor(size_t index)
1.214 + {
1.215 + //return index / SegmentSize < m_segments.size();
1.216 + return index / SegmentSize < m_segments.length();
1.217 + }
1.218 +
1.219 + Segment* segmentFor(size_t index)
1.220 + {
1.221 + return m_segments[index / SegmentSize];
1.222 + }
1.223 +
1.224 + size_t subscriptFor(size_t index)
1.225 + {
1.226 + return index % SegmentSize;
1.227 + }
1.228 +
1.229 + void ensureSegmentsFor(size_t size)
1.230 + {
1.231 + size_t segmentCount = m_size / SegmentSize;
1.232 + if (m_size % SegmentSize)
1.233 + ++segmentCount;
1.234 + //segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
1.235 + segmentCount = segmentCount > 1 ? segmentCount : 1; // We always have at least our inline segment.
1.236 +
1.237 + size_t neededSegmentCount = size / SegmentSize;
1.238 + if (size % SegmentSize)
1.239 + ++neededSegmentCount;
1.240 +
1.241 + // Fill up to N - 1 segments.
1.242 + size_t end = neededSegmentCount - 1;
1.243 + for (size_t i = segmentCount - 1; i < end; ++i)
1.244 + ensureSegment(i, SegmentSize);
1.245 +
1.246 + // Grow segment N to accomodate the remainder.
1.247 + ensureSegment(end, subscriptFor(size - 1) + 1);
1.248 + }
1.249 +
1.250 + void ensureSegment(size_t segmentIndex, size_t size)
1.251 + {
1.252 + ASSERT(segmentIndex <= m_segments.size());
1.253 + if (segmentIndex == m_segments.size())
1.254 + m_segments.append(js_new<Segment>());
1.255 + m_segments[segmentIndex]->grow(size);
1.256 + }
1.257 +
1.258 + size_t m_size;
1.259 + Segment m_inlineSegment;
1.260 + js::Vector<Segment*, 32 ,js::SystemAllocPolicy > m_segments;
1.261 + };
1.262 +
1.263 +} // namespace WTF
1.264 +
1.265 +using WTF::SegmentedVector;
1.266 +
1.267 +#endif /* assembler_wtf_SegmentedVector_h */
