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/Vector.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 HeapBlock<CopyWorkListSegment> {
61public:
62    static CopyWorkListSegment* create(DeadBlock* block)
63    {
64        return new (NotNull, block) CopyWorkListSegment(block->region());
65    }
66
67    size_t size() { return m_size; }
68    bool isFull() { return reinterpret_cast<char*>(&data()[size()]) >= endOfBlock(); }
69    CopyWorklistItem get(size_t index) { return data()[index]; }
70
71    void append(CopyWorklistItem item)
72    {
73        ASSERT(!isFull());
74        data()[m_size] = item;
75        m_size += 1;
76    }
77
78    static const size_t blockSize = 512;
79
80private:
81    CopyWorkListSegment(Region* region)
82        : HeapBlock<CopyWorkListSegment>(region)
83        , m_size(0)
84    {
85    }
86
87    CopyWorklistItem* data() { return reinterpret_cast<CopyWorklistItem*>(this + 1); }
88    char* endOfBlock() { return reinterpret_cast<char*>(this) + blockSize; }
89
90    size_t m_size;
91};
92
93class CopyWorkListIterator {
94    friend class CopyWorkList;
95public:
96    CopyWorklistItem get() { return m_currentSegment->get(m_currentIndex); }
97    CopyWorklistItem operator*() { return get(); }
98    CopyWorklistItem operator->() { return get(); }
99
100    CopyWorkListIterator& operator++()
101    {
102        m_currentIndex++;
103
104        if (m_currentIndex >= m_currentSegment->size()) {
105            m_currentIndex = 0;
106            m_currentSegment = m_currentSegment->next();
107
108            ASSERT(!m_currentSegment || m_currentSegment->size());
109        }
110
111        return *this;
112    }
113
114    bool operator==(const CopyWorkListIterator& other) const
115    {
116        return m_currentSegment == other.m_currentSegment && m_currentIndex == other.m_currentIndex;
117    }
118
119    bool operator!=(const CopyWorkListIterator& other) const
120    {
121        return !(*this == other);
122    }
123
124    CopyWorkListIterator()
125        : m_currentSegment(0)
126        , m_currentIndex(0)
127    {
128    }
129
130private:
131    CopyWorkListIterator(CopyWorkListSegment* startSegment, size_t startIndex)
132        : m_currentSegment(startSegment)
133        , m_currentIndex(startIndex)
134    {
135    }
136
137    CopyWorkListSegment* m_currentSegment;
138    size_t m_currentIndex;
139};
140
141class CopyWorkList {
142    WTF_MAKE_FAST_ALLOCATED;
143public:
144    typedef CopyWorkListIterator iterator;
145
146    CopyWorkList(BlockAllocator&);
147    ~CopyWorkList();
148
149    void append(CopyWorklistItem);
150    iterator begin();
151    iterator end();
152
153private:
154    DoublyLinkedList<CopyWorkListSegment> m_segments;
155    BlockAllocator& m_blockAllocator;
156};
157
158inline CopyWorkList::CopyWorkList(BlockAllocator& blockAllocator)
159    : m_blockAllocator(blockAllocator)
160{
161}
162
163inline CopyWorkList::~CopyWorkList()
164{
165    while (!m_segments.isEmpty())
166        m_blockAllocator.deallocate(CopyWorkListSegment::destroy(m_segments.removeHead()));
167}
168
169inline void CopyWorkList::append(CopyWorklistItem item)
170{
171    if (m_segments.isEmpty() || m_segments.tail()->isFull())
172        m_segments.append(CopyWorkListSegment::create(m_blockAllocator.allocate<CopyWorkListSegment>()));
173
174    ASSERT(!m_segments.tail()->isFull());
175
176    m_segments.tail()->append(item);
177}
178
179inline CopyWorkList::iterator CopyWorkList::begin()
180{
181    return CopyWorkListIterator(m_segments.head(), 0);
182}
183
184inline CopyWorkList::iterator CopyWorkList::end()
185{
186    return CopyWorkListIterator();
187}
188
189} // namespace JSC
190
191#endif // CopyWorkList_h
192