1/*
2 * Copyright (C) 2014-2016 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 <wtf/DoublyLinkedList.h>
29#include <wtf/Forward.h>
30#include <wtf/Noncopyable.h>
31
32namespace JSC {
33
34template <typename T>
35class GCArraySegment : public DoublyLinkedListNode<GCArraySegment<T>> {
36 friend class WTF::DoublyLinkedListNode<GCArraySegment<T>>;
37public:
38 GCArraySegment()
39 : DoublyLinkedListNode<GCArraySegment<T>>()
40#if !ASSERT_DISABLED
41 , m_top(0)
42#endif
43 {
44 }
45
46 static GCArraySegment* create();
47 static void destroy(GCArraySegment*);
48
49 T* data()
50 {
51 return bitwise_cast<T*>(this + 1);
52 }
53
54 static const size_t blockSize = 4 * KB;
55
56 GCArraySegment* m_prev;
57 GCArraySegment* m_next;
58#if !ASSERT_DISABLED
59 size_t m_top;
60#endif
61};
62
63template <typename T> class GCSegmentedArrayIterator;
64
65template <typename T>
66class GCSegmentedArray {
67 WTF_MAKE_FAST_ALLOCATED;
68 WTF_MAKE_NONCOPYABLE(GCSegmentedArray);
69 friend class GCSegmentedArrayIterator<T>;
70 friend class GCSegmentedArrayIterator<const T>;
71public:
72 GCSegmentedArray();
73 ~GCSegmentedArray();
74
75 void append(T);
76
77 bool canRemoveLast();
78 const T removeLast();
79 bool refill();
80
81 size_t size();
82 bool isEmpty();
83
84 void fillVector(Vector<T>&);
85 void clear();
86
87 typedef GCSegmentedArrayIterator<T> iterator;
88 iterator begin() const { return GCSegmentedArrayIterator<T>(m_segments.head(), m_top); }
89 iterator end() const { return GCSegmentedArrayIterator<T>(); }
90
91protected:
92 template <size_t size> struct CapacityFromSize {
93 static const size_t value = (size - sizeof(GCArraySegment<T>)) / sizeof(T);
94 };
95
96 void expand();
97
98 size_t postIncTop();
99 size_t preDecTop();
100 void setTopForFullSegment();
101 void setTopForEmptySegment();
102 size_t top();
103
104 void validatePrevious();
105
106 DoublyLinkedList<GCArraySegment<T>> m_segments;
107
108 JS_EXPORT_PRIVATE static const size_t s_segmentCapacity = CapacityFromSize<GCArraySegment<T>::blockSize>::value;
109 size_t m_top;
110 size_t m_numberOfSegments;
111};
112
113template <typename T>
114class GCSegmentedArrayIterator {
115 friend class GCSegmentedArray<T>;
116public:
117 GCSegmentedArrayIterator()
118 : m_currentSegment(0)
119 , m_currentOffset(0)
120 {
121 }
122
123 T& get() { return m_currentSegment->data()[m_currentOffset]; }
124 T& operator*() { return get(); }
125 T& operator->() { return get(); }
126
127 bool operator==(const GCSegmentedArrayIterator& other)
128 {
129 return m_currentSegment == other.m_currentSegment && m_currentOffset == other.m_currentOffset;
130 }
131
132 bool operator!=(const GCSegmentedArrayIterator& other)
133 {
134 return !(*this == other);
135 }
136
137 GCSegmentedArrayIterator& operator++()
138 {
139 ASSERT(m_currentSegment);
140
141 m_currentOffset++;
142
143 if (m_currentOffset >= m_offsetLimit) {
144 m_currentSegment = m_currentSegment->next();
145 m_currentOffset = 0;
146 m_offsetLimit = GCSegmentedArray<T>::s_segmentCapacity;
147 }
148
149 return *this;
150 }
151
152private:
153 GCSegmentedArrayIterator(GCArraySegment<T>* start, size_t top)
154 : m_currentSegment(start)
155 , m_currentOffset(0)
156 , m_offsetLimit(top)
157 {
158 if (!m_offsetLimit)
159 m_currentSegment = nullptr;
160 }
161
162 GCArraySegment<T>* m_currentSegment;
163 size_t m_currentOffset;
164 size_t m_offsetLimit;
165};
166
167} // namespace JSC
168
169