heap/CopyWorkList.h

   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
  32 namespace JSC {
  33
  34 class JSCell;
  35
  36 class CopyWorklistItem {
  37 public:
  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
  53 private:
  54     static const unsigned requiredAlignment = 8;
  55     static const unsigned mask = requiredAlignment - 1;
  56
  57     uintptr_t m_value;
  58 };
  59
  60 class CopyWorkListSegment : public HeapBlock<CopyWorkListSegment> {
  61 public:
  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
  80 private:
  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
  93 class CopyWorkListIterator {
  94     friend class CopyWorkList;
  95 public:
  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
 130 private:
 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
 141 class CopyWorkList {
 142     WTF_MAKE_FAST_ALLOCATED;
 143 public:
 144     typedef CopyWorkListIterator iterator;
 145
 146     CopyWorkList(BlockAllocator&);
 147     ~CopyWorkList();
 148
 149     void append(CopyWorklistItem);
 150     iterator begin();
 151     iterator end();
 152
 153 private:
 154     DoublyLinkedList<CopyWorkListSegment> m_segments;
 155     BlockAllocator& m_blockAllocator;
 156 };
 157
 158 inline CopyWorkList::CopyWorkList(BlockAllocator& blockAllocator)
 159     : m_blockAllocator(blockAllocator)
 160 {
 161 }
 162
 163 inline CopyWorkList::~CopyWorkList()
 164 {
 165     while (!m_segments.isEmpty())
 166         m_blockAllocator.deallocate(CopyWorkListSegment::destroy(m_segments.removeHead()));
 167 }
 168
 169 inline 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
 179 inline CopyWorkList::iterator CopyWorkList::begin()
 180 {
 181     return CopyWorkListIterator(m_segments.head(), 0);
 182 }
 183
 184 inline CopyWorkList::iterator CopyWorkList::end()
 185 {
 186     return CopyWorkListIterator();
 187 }
 188
 189 } // namespace JSC
 190
 191 #endif // CopyWorkList_h