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