19aca9bb03e78a5f95256380b6a19ec3405b80e8
[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 #pragma once
27
28 #include "GCSegmentedArray.h"
29
30 namespace JSC {
31
32 template <typename T>
33 GCSegmentedArray<T>::GCSegmentedArray()
34     : m_top(0)
35     , m_numberOfSegments(0)
36 {
37     m_segments.push(GCArraySegment<T>::create());
38     m_numberOfSegments++;
39 }
40
41 template <typename T>
42 GCSegmentedArray<T>::~GCSegmentedArray()
43 {
44     ASSERT(m_numberOfSegments == 1);
45     ASSERT(m_segments.size() == 1);
46     GCArraySegment<T>::destroy(m_segments.removeHead());
47     m_numberOfSegments--;
48     ASSERT(!m_numberOfSegments);
49     ASSERT(!m_segments.size());
50 }
51
52 template <typename T>
53 void GCSegmentedArray<T>::clear()
54 {
55     if (!m_segments.head())
56         return;
57     GCArraySegment<T>* next;
58     for (GCArraySegment<T>* current = m_segments.head(); current->next(); current = next) {
59         next = current->next();
60         m_segments.remove(current);
61         GCArraySegment<T>::destroy(current);
62     }
63     m_top = 0;
64     m_numberOfSegments = 1;
65 #if !ASSERT_DISABLED
66     m_segments.head()->m_top = 0;
67 #endif
68 }
69
70 template <typename T>
71 void GCSegmentedArray<T>::expand()
72 {
73     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
74     
75     GCArraySegment<T>* nextSegment = GCArraySegment<T>::create();
76     m_numberOfSegments++;
77     
78 #if !ASSERT_DISABLED
79     nextSegment->m_top = 0;
80 #endif
81
82     m_segments.push(nextSegment);
83     setTopForEmptySegment();
84     validatePrevious();
85 }
86
87 template <typename T>
88 bool GCSegmentedArray<T>::refill()
89 {
90     validatePrevious();
91     if (top())
92         return true;
93     GCArraySegment<T>::destroy(m_segments.removeHead());
94     ASSERT(m_numberOfSegments > 1);
95     m_numberOfSegments--;
96     setTopForFullSegment();
97     validatePrevious();
98     return true;
99 }
100
101 template <typename T>
102 void GCSegmentedArray<T>::fillVector(Vector<T>& vector)
103 {
104     ASSERT(vector.size() == size());
105
106     GCArraySegment<T>* currentSegment = m_segments.head();
107     if (!currentSegment)
108         return;
109
110     unsigned count = 0;
111     for (unsigned i = 0; i < m_top; ++i) {
112         ASSERT(currentSegment->data()[i]);
113         vector[count++] = currentSegment->data()[i];
114     }
115
116     currentSegment = currentSegment->next();
117     while (currentSegment) {
118         for (unsigned i = 0; i < s_segmentCapacity; ++i) {
119             ASSERT(currentSegment->data()[i]);
120             vector[count++] = currentSegment->data()[i];
121         }
122         currentSegment = currentSegment->next();
123     }
124 }
125
126 template <typename T>
127 inline GCArraySegment<T>* GCArraySegment<T>::create()
128 {
129     return new (NotNull, fastMalloc(blockSize)) GCArraySegment<T>();
130 }
131
132 template <typename T>
133 inline void GCArraySegment<T>::destroy(GCArraySegment* segment)
134 {
135     segment->~GCArraySegment();
136     fastFree(segment);
137 }
138
139 template <typename T>
140 inline size_t GCSegmentedArray<T>::postIncTop()
141 {
142     size_t result = m_top++;
143     ASSERT(result == m_segments.head()->m_top++);
144     return result;
145 }
146
147 template <typename T>
148 inline size_t GCSegmentedArray<T>::preDecTop()
149 {
150     size_t result = --m_top;
151     ASSERT(result == --m_segments.head()->m_top);
152     return result;
153 }
154
155 template <typename T>
156 inline void GCSegmentedArray<T>::setTopForFullSegment()
157 {
158     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
159     m_top = s_segmentCapacity;
160 }
161
162 template <typename T>
163 inline void GCSegmentedArray<T>::setTopForEmptySegment()
164 {
165     ASSERT(!m_segments.head()->m_top);
166     m_top = 0;
167 }
168
169 template <typename T>
170 inline size_t GCSegmentedArray<T>::top()
171 {
172     ASSERT(m_top == m_segments.head()->m_top);
173     return m_top;
174 }
175
176 template <typename T>
177 #if ASSERT_DISABLED
178 inline void GCSegmentedArray<T>::validatePrevious() { }
179 #else
180 inline void GCSegmentedArray<T>::validatePrevious()
181 {
182     unsigned count = 0;
183     for (GCArraySegment<T>* current = m_segments.head(); current; current = current->next())
184         count++;
185     ASSERT(m_segments.size() == m_numberOfSegments);
186 }
187 #endif
188
189 template <typename T>
190 inline void GCSegmentedArray<T>::append(T value)
191 {
192     if (m_top == s_segmentCapacity)
193         expand();
194     m_segments.head()->data()[postIncTop()] = value;
195 }
196
197 template <typename T>
198 inline bool GCSegmentedArray<T>::canRemoveLast()
199 {
200     return !!m_top;
201 }
202
203 template <typename T>
204 inline const T GCSegmentedArray<T>::removeLast()
205 {
206     return m_segments.head()->data()[preDecTop()];
207 }
208
209 template <typename T>
210 inline bool GCSegmentedArray<T>::isEmpty()
211 {
212     if (m_top)
213         return false;
214     if (m_segments.head()->next()) {
215         ASSERT(m_segments.head()->next()->m_top == s_segmentCapacity);
216         return false;
217     }
218     return true;
219 }
220
221 template <typename T>
222 inline size_t GCSegmentedArray<T>::size()
223 {
224     return m_top + s_segmentCapacity * (m_numberOfSegments - 1);
225 }
226
227 } // namespace JSC