1/*
2 * Copyright (C) 2016 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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#if ENABLE(DFG_JIT)
29
30#include <wtf/StdLibExtras.h>
31#include <wtf/Vector.h>
32
33namespace JSC { namespace B3 {
34
35// B3::Procedure and Air::Code have a lot of collections of indexed things. This has all of the
36// logic.
37
38template<typename T>
39class SparseCollection {
40 typedef Vector<std::unique_ptr<T>> VectorType;
41
42public:
43 SparseCollection()
44 {
45 }
46
47 T* add(std::unique_ptr<T> value)
48 {
49 T* result = value.get();
50
51 size_t index;
52 if (m_indexFreeList.isEmpty()) {
53 index = m_vector.size();
54 m_vector.append(nullptr);
55 } else
56 index = m_indexFreeList.takeLast();
57
58 value->m_index = index;
59 ASSERT(!m_vector[index]);
60 new (NotNull, &m_vector[index]) std::unique_ptr<T>(WTFMove(value));
61
62 return result;
63 }
64
65 template<typename... Arguments>
66 T* addNew(Arguments&&... arguments)
67 {
68 return add(std::unique_ptr<T>(new T(std::forward<Arguments>(arguments)...)));
69 }
70
71 void remove(T* value)
72 {
73 RELEASE_ASSERT(m_vector[value->m_index].get() == value);
74 m_indexFreeList.append(value->m_index);
75 m_vector[value->m_index] = nullptr;
76 }
77
78 void packIndices()
79 {
80 if (m_indexFreeList.isEmpty())
81 return;
82
83 unsigned holeIndex = 0;
84 unsigned endIndex = m_vector.size();
85
86 while (true) {
87 while (holeIndex < endIndex && m_vector[holeIndex])
88 ++holeIndex;
89
90 if (holeIndex == endIndex)
91 break;
92 ASSERT(holeIndex < m_vector.size());
93 ASSERT(!m_vector[holeIndex]);
94
95 do {
96 --endIndex;
97 } while (!m_vector[endIndex] && endIndex > holeIndex);
98
99 if (holeIndex == endIndex)
100 break;
101 ASSERT(endIndex > holeIndex);
102 ASSERT(m_vector[endIndex]);
103
104 auto& value = m_vector[endIndex];
105 value->m_index = holeIndex;
106 m_vector[holeIndex] = WTFMove(value);
107 ++holeIndex;
108 }
109
110 m_indexFreeList.shrink(0);
111 m_vector.shrink(endIndex);
112 }
113
114 unsigned size() const { return m_vector.size(); }
115 bool isEmpty() const { return m_vector.isEmpty(); }
116
117 T* at(unsigned index) const { return m_vector[index].get(); }
118 T* operator[](unsigned index) const { return at(index); }
119
120 class iterator {
121 public:
122 iterator()
123 : m_collection(nullptr)
124 , m_index(0)
125 {
126 }
127
128 iterator(const SparseCollection& collection, unsigned index)
129 : m_collection(&collection)
130 , m_index(findNext(index))
131 {
132 }
133
134 T* operator*()
135 {
136 return m_collection->at(m_index);
137 }
138
139 iterator& operator++()
140 {
141 m_index = findNext(m_index + 1);
142 return *this;
143 }
144
145 bool operator==(const iterator& other) const
146 {
147 ASSERT(m_collection == other.m_collection);
148 return m_index == other.m_index;
149 }
150
151 bool operator!=(const iterator& other) const
152 {
153 return !(*this == other);
154 }
155
156 private:
157 unsigned findNext(unsigned index)
158 {
159 while (index < m_collection->size() && !m_collection->at(index))
160 index++;
161 return index;
162 }
163
164 const SparseCollection* m_collection;
165 unsigned m_index;
166 };
167
168 iterator begin() const { return iterator(*this, 0); }
169 iterator end() const { return iterator(*this, size()); }
170
171private:
172 Vector<std::unique_ptr<T>, 0, UnsafeVectorOverflow> m_vector;
173 Vector<size_t, 0, UnsafeVectorOverflow> m_indexFreeList;
174};
175
176} } // namespace JSC::B3
177
178#endif // ENABLE(DFG_JIT)
179