e2eff4d87804330e9bd19d1f8fdfc9d46e49dcaa
[WebKit-https.git] / Source / JavaScriptCore / heap / GCSegmentedArrayInlines.h
1 /*
2  * Copyright (C) 2014 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  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef GCSegmentedArrayInlines_h
27 #define GCSegmentedArrayInlines_h
28
29 #include "BlockAllocator.h"
30 #include "GCSegmentedArray.h"
31
32 namespace JSC {
33
34 template <typename T>
35 GCSegmentedArray<T>::GCSegmentedArray(BlockAllocator& blockAllocator)
36     : m_blockAllocator(blockAllocator)
37     , m_top(0)
38     , m_numberOfSegments(0)
39 {
40     m_segments.push(GCArraySegment<T>::create(m_blockAllocator.allocate<GCArraySegment<T>>()));
41     m_numberOfSegments++;
42 }
43
44 template <typename T>
45 GCSegmentedArray<T>::~GCSegmentedArray()
46 {
47     ASSERT(m_numberOfSegments == 1);
48     ASSERT(m_segments.size() == 1);
49     m_blockAllocator.deallocate(GCArraySegment<T>::destroy(m_segments.removeHead()));
50     m_numberOfSegments--;
51     ASSERT(!m_numberOfSegments);
52     ASSERT(!m_segments.size());
53 }
54
55 template <typename T>
56 void GCSegmentedArray<T>::clear()
57 {
58     if (!m_segments.head())
59         return;
60     GCArraySegment<T>* next;
61     for (GCArraySegment<T>* current = m_segments.head(); current->next(); current = next) {
62         next = current->next();
63         m_segments.remove(current);
64         m_blockAllocator.deallocate(GCArraySegment<T>::destroy(current));
65     }
66     m_top = 0;
67     m_numberOfSegments = 1;
68 #if !ASSERT_DISABLED
69     m_segments.head()->m_top = 0;
70 #endif
71 }
72
73 template <typename T>
74 void GCSegmentedArray<T>::expand()
75 {
76     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
77     
78     GCArraySegment<T>* nextSegment = GCArraySegment<T>::create(m_blockAllocator.allocate<GCArraySegment<T>>());
79     m_numberOfSegments++;
80     
81 #if !ASSERT_DISABLED
82     nextSegment->m_top = 0;
83 #endif
84
85     m_segments.push(nextSegment);
86     setTopForEmptySegment();
87     validatePrevious();
88 }
89
90 template <typename T>
91 bool GCSegmentedArray<T>::refill()
92 {
93     validatePrevious();
94     if (top())
95         return true;
96     m_blockAllocator.deallocate(GCArraySegment<T>::destroy(m_segments.removeHead()));
97     ASSERT(m_numberOfSegments > 1);
98     m_numberOfSegments--;
99     setTopForFullSegment();
100     validatePrevious();
101     return true;
102 }
103
104 template <typename T>
105 void GCSegmentedArray<T>::fillVector(Vector<T>& vector)
106 {
107     ASSERT(vector.size() == size());
108
109     GCArraySegment<T>* currentSegment = m_segments.head();
110     if (!currentSegment)
111         return;
112
113     unsigned count = 0;
114     for (unsigned i = 0; i < m_top; ++i) {
115         ASSERT(currentSegment->data()[i]);
116         vector[count++] = currentSegment->data()[i];
117     }
118
119     currentSegment = currentSegment->next();
120     while (currentSegment) {
121         for (unsigned i = 0; i < s_segmentCapacity; ++i) {
122             ASSERT(currentSegment->data()[i]);
123             vector[count++] = currentSegment->data()[i];
124         }
125         currentSegment = currentSegment->next();
126     }
127 }
128
129 template <typename T>
130 inline GCArraySegment<T>* GCArraySegment<T>::create(DeadBlock* block)
131 {
132     return new (NotNull, block) GCArraySegment<T>(block->region());
133 }
134
135 template <typename T>
136 inline size_t GCSegmentedArray<T>::postIncTop()
137 {
138     size_t result = m_top++;
139     ASSERT(result == m_segments.head()->m_top++);
140     return result;
141 }
142
143 template <typename T>
144 inline size_t GCSegmentedArray<T>::preDecTop()
145 {
146     size_t result = --m_top;
147     ASSERT(result == --m_segments.head()->m_top);
148     return result;
149 }
150
151 template <typename T>
152 inline void GCSegmentedArray<T>::setTopForFullSegment()
153 {
154     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
155     m_top = s_segmentCapacity;
156 }
157
158 template <typename T>
159 inline void GCSegmentedArray<T>::setTopForEmptySegment()
160 {
161     ASSERT(!m_segments.head()->m_top);
162     m_top = 0;
163 }
164
165 template <typename T>
166 inline size_t GCSegmentedArray<T>::top()
167 {
168     ASSERT(m_top == m_segments.head()->m_top);
169     return m_top;
170 }
171
172 template <typename T>
173 #if ASSERT_DISABLED
174 inline void GCSegmentedArray<T>::validatePrevious() { }
175 #else
176 inline void GCSegmentedArray<T>::validatePrevious()
177 {
178     unsigned count = 0;
179     for (GCArraySegment<T>* current = m_segments.head(); current; current = current->next())
180         count++;
181     ASSERT(m_segments.size() == m_numberOfSegments);
182 }
183 #endif
184
185 template <typename T>
186 inline void GCSegmentedArray<T>::append(T value)
187 {
188     if (m_top == s_segmentCapacity)
189         expand();
190     m_segments.head()->data()[postIncTop()] = value;
191 }
192
193 template <typename T>
194 inline bool GCSegmentedArray<T>::canRemoveLast()
195 {
196     return !!m_top;
197 }
198
199 template <typename T>
200 inline const T GCSegmentedArray<T>::removeLast()
201 {
202     return m_segments.head()->data()[preDecTop()];
203 }
204
205 template <typename T>
206 inline bool GCSegmentedArray<T>::isEmpty()
207 {
208     if (m_top)
209         return false;
210     if (m_segments.head()->next()) {
211         ASSERT(m_segments.head()->next()->m_top == s_segmentCapacity);
212         return false;
213     }
214     return true;
215 }
216
217 template <typename T>
218 inline size_t GCSegmentedArray<T>::size()
219 {
220     return m_top + s_segmentCapacity * (m_numberOfSegments - 1);
221 }
222
223 } // namespace JSC
224
225 #endif // GCSegmentedArrayInlines_h