heap/GCSegmentedArrayInlines.h

   1 /*
   2  * Copyright (C) 2014 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 GCSegmentedArrayInlines_h
  27 #define GCSegmentedArrayInlines_h
  28
  29 #include "BlockAllocator.h"
  30 #include "GCSegmentedArray.h"
  31
  32 namespace JSC {
  33
  34 template <typename T>
  35 GCSegmentedArray<T>::GCSegmentedArray(BlockAllocator& blockAllocator)
  36     : m_blockAllocator(blockAllocator)
  37     , m_top(0)
  38     , m_numberOfSegments(0)
  39 {
  40     m_segments.push(GCArraySegment<T>::create(m_blockAllocator.allocate<GCArraySegment<T>>()));
  41     m_numberOfSegments++;
  42 }
  43
  44 template <typename T>
  45 GCSegmentedArray<T>::~GCSegmentedArray()
  46 {
  47     ASSERT(m_numberOfSegments == 1);
  48     ASSERT(m_segments.size() == 1);
  49     m_blockAllocator.deallocate(GCArraySegment<T>::destroy(m_segments.removeHead()));
  50     m_numberOfSegments--;
  51     ASSERT(!m_numberOfSegments);
  52     ASSERT(!m_segments.size());
  53 }
  54
  55 template <typename T>
  56 void GCSegmentedArray<T>::clear()
  57 {
  58     if (!m_segments.head())
  59         return;
  60     GCArraySegment<T>* next;
  61     for (GCArraySegment<T>* current = m_segments.head(); current->next(); current = next) {
  62         next = current->next();
  63         m_segments.remove(current);
  64         m_blockAllocator.deallocate(GCArraySegment<T>::destroy(current));
  65     }
  66     m_top = 0;
  67     m_numberOfSegments = 1;
  68 #if !ASSERT_DISABLED
  69     m_segments.head()->m_top = 0;
  70 #endif
  71 }
  72
  73 template <typename T>
  74 void GCSegmentedArray<T>::expand()
  75 {
  76     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
  77
  78     GCArraySegment<T>* nextSegment = GCArraySegment<T>::create(m_blockAllocator.allocate<GCArraySegment<T>>());
  79     m_numberOfSegments++;
  80
  81 #if !ASSERT_DISABLED
  82     nextSegment->m_top = 0;
  83 #endif
  84
  85     m_segments.push(nextSegment);
  86     setTopForEmptySegment();
  87     validatePrevious();
  88 }
  89
  90 template <typename T>
  91 bool GCSegmentedArray<T>::refill()
  92 {
  93     validatePrevious();
  94     if (top())
  95         return true;
  96     m_blockAllocator.deallocate(GCArraySegment<T>::destroy(m_segments.removeHead()));
  97     ASSERT(m_numberOfSegments > 1);
  98     m_numberOfSegments--;
  99     setTopForFullSegment();
 100     validatePrevious();
 101     return true;
 102 }
 103
 104 template <typename T>
 105 void GCSegmentedArray<T>::fillVector(Vector<T>& vector)
 106 {
 107     ASSERT(vector.size() == size());
 108
 109     GCArraySegment<T>* currentSegment = m_segments.head();
 110     if (!currentSegment)
 111         return;
 112
 113     unsigned count = 0;
 114     for (unsigned i = 0; i < m_top; ++i) {
 115         ASSERT(currentSegment->data()[i]);
 116         vector[count++] = currentSegment->data()[i];
 117     }
 118
 119     currentSegment = currentSegment->next();
 120     while (currentSegment) {
 121         for (unsigned i = 0; i < s_segmentCapacity; ++i) {
 122             ASSERT(currentSegment->data()[i]);
 123             vector[count++] = currentSegment->data()[i];
 124         }
 125         currentSegment = currentSegment->next();
 126     }
 127 }
 128
 129 template <typename T>
 130 inline GCArraySegment<T>* GCArraySegment<T>::create(DeadBlock* block)
 131 {
 132     return new (NotNull, block) GCArraySegment<T>(block->region());
 133 }
 134
 135 template <typename T>
 136 inline size_t GCSegmentedArray<T>::postIncTop()
 137 {
 138     size_t result = m_top++;
 139     ASSERT(result == m_segments.head()->m_top++);
 140     return result;
 141 }
 142
 143 template <typename T>
 144 inline size_t GCSegmentedArray<T>::preDecTop()
 145 {
 146     size_t result = --m_top;
 147     ASSERT(result == --m_segments.head()->m_top);
 148     return result;
 149 }
 150
 151 template <typename T>
 152 inline void GCSegmentedArray<T>::setTopForFullSegment()
 153 {
 154     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
 155     m_top = s_segmentCapacity;
 156 }
 157
 158 template <typename T>
 159 inline void GCSegmentedArray<T>::setTopForEmptySegment()
 160 {
 161     ASSERT(!m_segments.head()->m_top);
 162     m_top = 0;
 163 }
 164
 165 template <typename T>
 166 inline size_t GCSegmentedArray<T>::top()
 167 {
 168     ASSERT(m_top == m_segments.head()->m_top);
 169     return m_top;
 170 }
 171
 172 template <typename T>
 173 #if ASSERT_DISABLED
 174 inline void GCSegmentedArray<T>::validatePrevious() { }
 175 #else
 176 inline void GCSegmentedArray<T>::validatePrevious()
 177 {
 178     unsigned count = 0;
 179     for (GCArraySegment<T>* current = m_segments.head(); current; current = current->next())
 180         count++;
 181     ASSERT(m_segments.size() == m_numberOfSegments);
 182 }
 183 #endif
 184
 185 template <typename T>
 186 inline void GCSegmentedArray<T>::append(T value)
 187 {
 188     if (m_top == s_segmentCapacity)
 189         expand();
 190     m_segments.head()->data()[postIncTop()] = value;
 191 }
 192
 193 template <typename T>
 194 inline bool GCSegmentedArray<T>::canRemoveLast()
 195 {
 196     return !!m_top;
 197 }
 198
 199 template <typename T>
 200 inline const T GCSegmentedArray<T>::removeLast()
 201 {
 202     return m_segments.head()->data()[preDecTop()];
 203 }
 204
 205 template <typename T>
 206 inline bool GCSegmentedArray<T>::isEmpty()
 207 {
 208     if (m_top)
 209         return false;
 210     if (m_segments.head()->next()) {
 211         ASSERT(m_segments.head()->next()->m_top == s_segmentCapacity);
 212         return false;
 213     }
 214     return true;
 215 }
 216
 217 template <typename T>
 218 inline size_t GCSegmentedArray<T>::size()
 219 {
 220     return m_top + s_segmentCapacity * (m_numberOfSegments - 1);
 221 }
 222
 223 } // namespace JSC
 224
 225 #endif // GCSegmentedArrayInlines_h