DFG should be able to set watchpoints on global variables
[WebKit-https.git] / Source / WTF / wtf / SegmentedVector.h
1 /*
2  * Copyright (C) 2008 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #ifndef SegmentedVector_h
30 #define SegmentedVector_h
31
32 #include <wtf/Vector.h>
33
34 namespace WTF {
35
36     // An iterator for SegmentedVector. It supports only the pre ++ operator
37     template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVector;
38     template <typename T, size_t SegmentSize = 8, size_t InlineCapacity = 32> class SegmentedVectorIterator {
39     private:
40         friend class SegmentedVector<T, SegmentSize, InlineCapacity>;
41     public:
42         typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
43
44         ~SegmentedVectorIterator() { }
45
46         T& operator*() const { return m_vector.m_segments.at(m_segment)->at(m_index); }
47         T* operator->() const { return &m_vector.m_segments.at(m_segment)->at(m_index); }
48
49         // Only prefix ++ operator supported
50         Iterator& operator++()
51         {
52             ASSERT(m_index != SegmentSize);
53             ++m_index;
54             if (m_index >= m_vector.m_segments.at(m_segment)->size())  {
55                 if (m_segment + 1 < m_vector.m_segments.size()) {
56                     ASSERT(m_vector.m_segments.at(m_segment)->size() > 0);
57                     ++m_segment;
58                     m_index = 0;
59                 } else {
60                     // Points to the "end" symbol
61                     m_segment = 0;
62                     m_index = SegmentSize;
63                 }
64             }
65             return *this;
66         }
67
68         bool operator==(const Iterator& other) const
69         {
70             return m_index == other.m_index && m_segment == other.m_segment && &m_vector == &other.m_vector;
71         }
72
73         bool operator!=(const Iterator& other) const
74         {
75             return m_index != other.m_index || m_segment != other.m_segment || &m_vector != &other.m_vector;
76         }
77
78         SegmentedVectorIterator& operator=(const SegmentedVectorIterator<T, SegmentSize, InlineCapacity>& other)
79         {
80             m_vector = other.m_vector;
81             m_segment = other.m_segment;
82             m_index = other.m_index;
83             return *this;
84         }
85
86     private:
87         SegmentedVectorIterator(SegmentedVector<T, SegmentSize, InlineCapacity>& vector, size_t segment, size_t index)
88             : m_vector(vector)
89             , m_segment(segment)
90             , m_index(index)
91         {
92         }
93
94         SegmentedVector<T, SegmentSize, InlineCapacity>& m_vector;
95         size_t m_segment;
96         size_t m_index;
97     };
98
99     // SegmentedVector is just like Vector, but it doesn't move the values
100     // stored in its buffer when it grows. Therefore, it is safe to keep
101     // pointers into a SegmentedVector. The default tuning values are
102     // optimized for segmented vectors that get large; you may want to use
103     // SegmentedVector<thingy, 1, 0> if you don't expect a lot of entries.
104     template <typename T, size_t SegmentSize, size_t InlineCapacity>
105     class SegmentedVector {
106         friend class SegmentedVectorIterator<T, SegmentSize, InlineCapacity>;
107     public:
108         typedef SegmentedVectorIterator<T, SegmentSize, InlineCapacity> Iterator;
109
110         SegmentedVector()
111             : m_size(0)
112         {
113             m_segments.append(&m_inlineSegment);
114         }
115
116         ~SegmentedVector()
117         {
118             deleteAllSegments();
119         }
120
121         size_t size() const { return m_size; }
122         bool isEmpty() const { return !size(); }
123
124         T& at(size_t index)
125         {
126             if (index < SegmentSize)
127                 return m_inlineSegment[index];
128             return segmentFor(index)->at(subscriptFor(index));
129         }
130
131         T& operator[](size_t index)
132         {
133             return at(index);
134         }
135
136         T& last()
137         {
138             return at(size() - 1);
139         }
140
141         template <typename U> void append(const U& value)
142         {
143             ++m_size;
144
145             if (m_size <= SegmentSize) {
146                 m_inlineSegment.uncheckedAppend(value);
147                 return;
148             }
149
150             if (!segmentExistsFor(m_size - 1))
151                 m_segments.append(new Segment);
152             segmentFor(m_size - 1)->uncheckedAppend(value);
153         }
154
155         T& alloc()
156         {
157             append<T>(T());
158             return last();
159         }
160
161         void removeLast()
162         {
163             if (m_size <= SegmentSize)
164                 m_inlineSegment.removeLast();
165             else
166                 segmentFor(m_size - 1)->removeLast();
167             --m_size;
168         }
169
170         void grow(size_t size)
171         {
172             ASSERT(size > m_size);
173             ensureSegmentsFor(size);
174             m_size = size;
175         }
176
177         void clear()
178         {
179             deleteAllSegments();
180             m_segments.resize(1);
181             m_inlineSegment.clear();
182             m_size = 0;
183         }
184
185         Iterator begin()
186         {
187             return Iterator(*this, 0, m_size ? 0 : SegmentSize);
188         }
189
190         Iterator end()
191         {
192             return Iterator(*this, 0, SegmentSize);
193         }
194         
195         void shrinkToFit()
196         {
197             m_segments.shrinkToFit();
198         }
199
200     private:
201         typedef Vector<T, SegmentSize> Segment;
202
203         void deleteAllSegments()
204         {
205             // Skip the first segment, because it's our inline segment, which was
206             // not created by new.
207             for (size_t i = 1; i < m_segments.size(); i++)
208                 delete m_segments[i];
209         }
210
211         bool segmentExistsFor(size_t index)
212         {
213             return index / SegmentSize < m_segments.size();
214         }
215
216         Segment* segmentFor(size_t index)
217         {
218             return m_segments[index / SegmentSize];
219         }
220
221         size_t subscriptFor(size_t index)
222         {
223             return index % SegmentSize;
224         }
225
226         void ensureSegmentsFor(size_t size)
227         {
228             size_t segmentCount = m_size / SegmentSize;
229             if (m_size % SegmentSize)
230                 ++segmentCount;
231             segmentCount = std::max<size_t>(segmentCount, 1); // We always have at least our inline segment.
232
233             size_t neededSegmentCount = size / SegmentSize;
234             if (size % SegmentSize)
235                 ++neededSegmentCount;
236
237             // Fill up to N - 1 segments.
238             size_t end = neededSegmentCount - 1;
239             for (size_t i = segmentCount - 1; i < end; ++i)
240                 ensureSegment(i, SegmentSize);
241
242             // Grow segment N to accomodate the remainder.
243             ensureSegment(end, subscriptFor(size - 1) + 1);
244         }
245
246         void ensureSegment(size_t segmentIndex, size_t size)
247         {
248             ASSERT(segmentIndex <= m_segments.size());
249             if (segmentIndex == m_segments.size())
250                 m_segments.append(new Segment);
251             m_segments[segmentIndex]->grow(size);
252         }
253
254         size_t m_size;
255         Segment m_inlineSegment;
256         Vector<Segment*, InlineCapacity> m_segments;
257     };
258
259 } // namespace WTF
260
261 using WTF::SegmentedVector;
262
263 #endif // SegmentedVector_h