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
30namespace JSC {
31
32template <typename T>
33GCSegmentedArray<T>::GCSegmentedArray()
34 : m_top(0)
35 , m_numberOfSegments(0)
36{
37 m_segments.push(GCArraySegment<T>::create());
38 m_numberOfSegments++;
39}
40
41template <typename T>
42GCSegmentedArray<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
52template <typename T>
53void 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
70template <typename T>
71void 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
87template <typename T>
88bool 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
101template <typename T>
102void 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
126template <typename T>
127inline GCArraySegment<T>* GCArraySegment<T>::create()
128{
129 return new (NotNull, fastMalloc(blockSize)) GCArraySegment<T>();
130}
131
132template <typename T>
133inline void GCArraySegment<T>::destroy(GCArraySegment* segment)
134{
135 segment->~GCArraySegment();
136 fastFree(segment);
137}
138
139template <typename T>
140inline 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
147template <typename T>
148inline 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
155template <typename T>
156inline void GCSegmentedArray<T>::setTopForFullSegment()
157{
158 ASSERT(m_segments.head()->m_top == s_segmentCapacity);
159 m_top = s_segmentCapacity;
160}
161
162template <typename T>
163inline void GCSegmentedArray<T>::setTopForEmptySegment()
164{
165 ASSERT(!m_segments.head()->m_top);
166 m_top = 0;
167}
168
169template <typename T>
170inline size_t GCSegmentedArray<T>::top()
171{
172 ASSERT(m_top == m_segments.head()->m_top);
173 return m_top;
174}
175
176template <typename T>
177#if ASSERT_DISABLED
178inline void GCSegmentedArray<T>::validatePrevious() { }
179#else
180inline 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
189template <typename T>
190inline void GCSegmentedArray<T>::append(T value)
191{
192 if (m_top == s_segmentCapacity)
193 expand();
194 m_segments.head()->data()[postIncTop()] = value;
195}
196
197template <typename T>
198inline bool GCSegmentedArray<T>::canRemoveLast()
199{
200 return !!m_top;
201}
202
203template <typename T>
204inline const T GCSegmentedArray<T>::removeLast()
205{
206 return m_segments.head()->data()[preDecTop()];
207}
208
209template <typename T>
210inline bool GCSegmentedArray<T>::isEmpty()
211{
212 // This happens to be safe to call concurrently. It's important to preserve that capability.
213 if (m_top)
214 return false;
215 if (m_segments.head()->next())
216 return false;
217 return true;
218}
219
220template <typename T>
221inline size_t GCSegmentedArray<T>::size()
222{
223 return m_top + s_segmentCapacity * (m_numberOfSegments - 1);
224}
225
226} // namespace JSC
227