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