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