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 GCSegmentedArray_h
27#define GCSegmentedArray_h
28
29#include <wtf/DoublyLinkedList.h>
30#include <wtf/Vector.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 friend class GCSegmentedArrayIterator<T>;
68 friend class GCSegmentedArrayIterator<const T>;
69public:
70 GCSegmentedArray();
71 ~GCSegmentedArray();
72
73 void append(T);
74
75 bool canRemoveLast();
76 const T removeLast();
77 bool refill();
78
79 size_t size();
80 bool isEmpty();
81
82 void fillVector(Vector<T>&);
83 void clear();
84
85 typedef GCSegmentedArrayIterator<T> iterator;
86 iterator begin() const { return GCSegmentedArrayIterator<T>(m_segments.head(), m_top); }
87 iterator end() const { return GCSegmentedArrayIterator<T>(); }
88
89protected:
90 template <size_t size> struct CapacityFromSize {
91 static const size_t value = (size - sizeof(GCArraySegment<T>)) / sizeof(T);
92 };
93
94 void expand();
95
96 size_t postIncTop();
97 size_t preDecTop();
98 void setTopForFullSegment();
99 void setTopForEmptySegment();
100 size_t top();
101
102 void validatePrevious();
103
104 DoublyLinkedList<GCArraySegment<T>> m_segments;
105
106 JS_EXPORT_PRIVATE static const size_t s_segmentCapacity = CapacityFromSize<GCArraySegment<T>::blockSize>::value;
107 size_t m_top;
108 size_t m_numberOfSegments;
109};
110
111template <typename T>
112class GCSegmentedArrayIterator {
113 friend class GCSegmentedArray<T>;
114public:
115 GCSegmentedArrayIterator()
116 : m_currentSegment(0)
117 , m_currentOffset(0)
118 {
119 }
120
121 T& get() { return m_currentSegment->data()[m_currentOffset]; }
122 T& operator*() { return get(); }
123 T& operator->() { return get(); }
124
125 bool operator==(const GCSegmentedArrayIterator& other)
126 {
127 return m_currentSegment == other.m_currentSegment && m_currentOffset == other.m_currentOffset;
128 }
129
130 bool operator!=(const GCSegmentedArrayIterator& other)
131 {
132 return !(*this == other);
133 }
134
135 GCSegmentedArrayIterator& operator++()
136 {
137 ASSERT(m_currentSegment);
138
139 m_currentOffset++;
140
141 if (m_currentOffset >= m_offsetLimit) {
142 m_currentSegment = m_currentSegment->next();
143 m_currentOffset = 0;
144 m_offsetLimit = GCSegmentedArray<T>::s_segmentCapacity;
145 }
146
147 return *this;
148 }
149
150private:
151 GCSegmentedArrayIterator(GCArraySegment<T>* start, size_t top)
152 : m_currentSegment(start)
153 , m_currentOffset(0)
154 , m_offsetLimit(top)
155 {
156 if (!m_offsetLimit)
157 m_currentSegment = nullptr;
158 }
159
160 GCArraySegment<T>* m_currentSegment;
161 size_t m_currentOffset;
162 size_t m_offsetLimit;
163};
164
165} // namespace JSC
166
167#endif // GCSegmentedArray_h
168