heap/GCSegmentedArray.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 GCSegmentedArray_h
  27 #define GCSegmentedArray_h
  28
  29 #include "HeapBlock.h"
  30 #include <wtf/Vector.h>
  31
  32 namespace JSC {
  33
  34 class BlockAllocator;
  35 class DeadBlock;
  36
  37 template <typename T>
  38 class GCArraySegment : public HeapBlock<GCArraySegment<T>> {
  39 public:
  40     GCArraySegment(Region* region)
  41         : HeapBlock<GCArraySegment>(region)
  42 #if !ASSERT_DISABLED
  43         , m_top(0)
  44 #endif
  45     {
  46     }
  47
  48     static GCArraySegment* create(DeadBlock*);
  49
  50     T* data()
  51     {
  52         return bitwise_cast<T*>(this + 1);
  53     }
  54
  55     static const size_t blockSize = 4 * KB;
  56
  57 #if !ASSERT_DISABLED
  58     size_t m_top;
  59 #endif
  60 };
  61
  62 template <typename T> class GCSegmentedArrayIterator;
  63
  64 template <typename T>
  65 class GCSegmentedArray {
  66     friend class GCSegmentedArrayIterator<T>;
  67     friend class GCSegmentedArrayIterator<const T>;
  68 public:
  69     GCSegmentedArray(BlockAllocator&);
  70     ~GCSegmentedArray();
  71
  72     void append(T);
  73
  74     bool canRemoveLast();
  75     const T removeLast();
  76     bool refill();
  77
  78     size_t size();
  79     bool isEmpty();
  80
  81     void fillVector(Vector<T>&);
  82     void clear();
  83
  84     typedef GCSegmentedArrayIterator<T> iterator;
  85     iterator begin() const { return GCSegmentedArrayIterator<T>(m_segments.head(), m_top); }
  86     iterator end() const { return GCSegmentedArrayIterator<T>(); }
  87
  88 protected:
  89     template <size_t size> struct CapacityFromSize {
  90         static const size_t value = (size - sizeof(GCArraySegment<T>)) / sizeof(T);
  91     };
  92
  93     void expand();
  94
  95     size_t postIncTop();
  96     size_t preDecTop();
  97     void setTopForFullSegment();
  98     void setTopForEmptySegment();
  99     size_t top();
 100
 101     void validatePrevious();
 102
 103     DoublyLinkedList<GCArraySegment<T>> m_segments;
 104     BlockAllocator& m_blockAllocator;
 105
 106     JS_EXPORT_PRIVATE static const size_t s_segmentCapacity = CapacityFromSize<GCArraySegment<T>::blockSize>::value;
 107     size_t m_top;
 108     size_t m_numberOfSegments;
 109 };
 110
 111 template <typename T>
 112 class GCSegmentedArrayIterator {
 113     friend class GCSegmentedArray<T>;
 114 public:
 115     GCSegmentedArrayIterator()
 116         : m_currentSegment(0)
 117         , m_currentOffset(0)
 118     {
 119     }
 120
 121     T& get() { return m_currentSegment->data()[m_currentOffset]; }
 122     T& operator*() { return get(); }
 123     T& operator->() { return get(); }
 124
 125     bool operator==(const GCSegmentedArrayIterator& other)
 126     {
 127         return m_currentSegment == other.m_currentSegment && m_currentOffset == other.m_currentOffset;
 128     }
 129
 130     bool operator!=(const GCSegmentedArrayIterator& other)
 131     {
 132         return !(*this == other);
 133     }
 134
 135     GCSegmentedArrayIterator& operator++()
 136     {
 137         ASSERT(m_currentSegment);
 138
 139         m_currentOffset++;
 140
 141         if (m_currentOffset >= m_offsetLimit) {
 142             m_currentSegment = m_currentSegment->next();
 143             m_currentOffset = 0;
 144             m_offsetLimit = GCSegmentedArray<T>::s_segmentCapacity;
 145         }
 146
 147         return *this;
 148     }
 149
 150 private:
 151     GCSegmentedArrayIterator(GCArraySegment<T>* start, size_t top)
 152         : m_currentSegment(start)
 153         , m_currentOffset(0)
 154         , m_offsetLimit(top)
 155     {
 156         if (!m_offsetLimit)
 157             m_currentSegment = nullptr;
 158     }
 159
 160     GCArraySegment<T>* m_currentSegment;
 161     size_t m_currentOffset;
 162     size_t m_offsetLimit;
 163 };
 164
 165 } // namespace JSC
 166
 167 #endif // GCSegmentedArray_h