git.saurik.com Git - apple/javascriptcore.git/blob

1 /*

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 */

26 #ifndef GCSegmentedArray_h

27 #define GCSegmentedArray_h

29 #include <wtf/DoublyLinkedList.h>

30 #include <wtf/Vector.h>

32 namespace JSC {

34 template <typename T>

 class GCArraySegment : public DoublyLinkedListNode<GCArraySegment<T>> {

     friend class WTF::DoublyLinkedListNode<GCArraySegment<T>>;

37 public:

38 GCArraySegment()

39 : DoublyLinkedListNode<GCArraySegment<T>>()

40 #if !ASSERT_DISABLED

         , m_top(0)

42 #endif

43 {

44 }

46 static GCArraySegment* create();

47 static void destroy(GCArraySegment*);

49 T* data()

50 {

         return bitwise_cast<T*>(this + 1);

52 }

     static const size_t blockSize = 4 * KB;

56 GCArraySegment* m_prev;

57 GCArraySegment* m_next;

58 #if !ASSERT_DISABLED

59 size_t m_top;

60 #endif

61 };

 template <typename T> class GCSegmentedArrayIterator;

65 template <typename T>

66 class GCSegmentedArray {

67 friend class GCSegmentedArrayIterator<T>;

68 friend class GCSegmentedArrayIterator<const T>;

69 public:

70 GCSegmentedArray();

71 ~GCSegmentedArray();

73 void append(T);

75 bool canRemoveLast();

76 const T removeLast();

77 bool refill();

79 size_t size();

80 bool isEmpty();

     void fillVector(Vector<T>&);

83 void clear();

85 typedef GCSegmentedArrayIterator<T> iterator;

     iterator begin() const { return GCSegmentedArrayIterator<T>(m_segments.head(), m_top); }

     iterator end() const { return GCSegmentedArrayIterator<T>(); }

89 protected:

     template <size_t size> struct CapacityFromSize {

         static const size_t value = (size - sizeof(GCArraySegment<T>)) / sizeof(T);

92 };

94 void expand();

96 size_t postIncTop();

97 size_t preDecTop();

98 void setTopForFullSegment();

99 void setTopForEmptySegment();

100 size_t top();

101

102 void validatePrevious();

103

104 DoublyLinkedList<GCArraySegment<T>> m_segments;

105

     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()

         : m_currentSegment(0)

         , m_currentOffset(0)

118 {

119 }

120

     T& get() { return m_currentSegment->data()[m_currentOffset]; }

     T& operator*() { return get(); }

     T& operator->() { return get(); }

124

     bool operator==(const GCSegmentedArrayIterator& other)

126 {

         return m_currentSegment == other.m_currentSegment && m_currentOffset == other.m_currentOffset;

128 }

129

     bool operator!=(const GCSegmentedArrayIterator& other)

131 {

         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:

     GCSegmentedArrayIterator(GCArraySegment<T>* start, size_t top)

152 : m_currentSegment(start)

         , 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