1/*
2 * Copyright (C) 2012, 2013 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 CopyWorkList_h
27#define CopyWorkList_h
28
29#include "CopyToken.h"
30#include <wtf/DoublyLinkedList.h>
31
32namespace JSC {
33
34class JSCell;
35
36class CopyWorklistItem {
37public:
38 CopyWorklistItem()
39 : m_value(0)
40 {
41 }
42
43 CopyWorklistItem(JSCell* cell, CopyToken token)
44 : m_value(bitwise_cast<uintptr_t>(cell) | static_cast<uintptr_t>(token))
45 {
46 ASSERT(!(bitwise_cast<uintptr_t>(cell) & static_cast<uintptr_t>(mask)));
47 ASSERT(static_cast<uintptr_t>(token) <= mask);
48 }
49
50 JSCell* cell() const { return bitwise_cast<JSCell*>(m_value & ~static_cast<uintptr_t>(mask)); }
51 CopyToken token() const { return static_cast<CopyToken>(m_value & mask); }
52
53private:
54 static const unsigned requiredAlignment = 8;
55 static const unsigned mask = requiredAlignment - 1;
56
57 uintptr_t m_value;
58};
59
60class CopyWorkListSegment : public DoublyLinkedListNode<CopyWorkListSegment> {
61 friend class WTF::DoublyLinkedListNode<CopyWorkListSegment>;
62public:
63 static CopyWorkListSegment* create()
64 {
65 return new (NotNull, fastMalloc(blockSize)) CopyWorkListSegment();
66 }
67
68 static void destroy(CopyWorkListSegment* segment)
69 {
70 segment->~CopyWorkListSegment();
71 fastFree(segment);
72 }
73
74 size_t size() { return m_size; }
75 bool isFull() { return reinterpret_cast<char*>(&data()[size()]) >= endOfBlock(); }
76 CopyWorklistItem get(size_t index) { return data()[index]; }
77
78 void append(CopyWorklistItem item)
79 {
80 ASSERT(!isFull());
81 data()[m_size] = item;
82 m_size += 1;
83 }
84
85 static const size_t blockSize = 512;
86
87private:
88 CopyWorkListSegment()
89 : DoublyLinkedListNode<CopyWorkListSegment>()
90 , m_size(0)
91 {
92 }
93
94 CopyWorklistItem* data() { return reinterpret_cast<CopyWorklistItem*>(this + 1); }
95 char* endOfBlock() { return reinterpret_cast<char*>(this) + blockSize; }
96
97 CopyWorkListSegment* m_prev;
98 CopyWorkListSegment* m_next;
99 size_t m_size;
100};
101
102class CopyWorkListIterator {
103 friend class CopyWorkList;
104public:
105 CopyWorklistItem get() { return m_currentSegment->get(m_currentIndex); }
106 CopyWorklistItem operator*() { return get(); }
107 CopyWorklistItem operator->() { return get(); }
108
109 CopyWorkListIterator& operator++()
110 {
111 m_currentIndex++;
112
113 if (m_currentIndex >= m_currentSegment->size()) {
114 m_currentIndex = 0;
115 m_currentSegment = m_currentSegment->next();
116
117 ASSERT(!m_currentSegment || m_currentSegment->size());
118 }
119
120 return *this;
121 }
122
123 bool operator==(const CopyWorkListIterator& other) const
124 {
125 return m_currentSegment == other.m_currentSegment && m_currentIndex == other.m_currentIndex;
126 }
127
128 bool operator!=(const CopyWorkListIterator& other) const
129 {
130 return !(*this == other);
131 }
132
133 CopyWorkListIterator()
134 : m_currentSegment(0)
135 , m_currentIndex(0)
136 {
137 }
138
139private:
140 CopyWorkListIterator(CopyWorkListSegment* startSegment, size_t startIndex)
141 : m_currentSegment(startSegment)
142 , m_currentIndex(startIndex)
143 {
144 }
145
146 CopyWorkListSegment* m_currentSegment;
147 size_t m_currentIndex;
148};
149
150class CopyWorkList {
151 WTF_MAKE_FAST_ALLOCATED;
152public:
153 typedef CopyWorkListIterator iterator;
154
155 CopyWorkList();
156 ~CopyWorkList();
157
158 void append(CopyWorklistItem);
159 iterator begin();
160 iterator end();
161
162private:
163 DoublyLinkedList<CopyWorkListSegment> m_segments;
164};
165
166inline CopyWorkList::CopyWorkList()
167{
168}
169
170inline CopyWorkList::~CopyWorkList()
171{
172 while (!m_segments.isEmpty())
173 CopyWorkListSegment::destroy(m_segments.removeHead());
174}
175
176inline void CopyWorkList::append(CopyWorklistItem item)
177{
178 if (m_segments.isEmpty() || m_segments.tail()->isFull())
179 m_segments.append(CopyWorkListSegment::create());
180
181 ASSERT(!m_segments.tail()->isFull());
182
183 m_segments.tail()->append(item);
184}
185
186inline CopyWorkList::iterator CopyWorkList::begin()
187{
188 return CopyWorkListIterator(m_segments.head(), 0);
189}
190
191inline CopyWorkList::iterator CopyWorkList::end()
192{
193 return CopyWorkListIterator();
194}
195
196} // namespace JSC
197
198#endif // CopyWorkList_h
199