1/*
2 * Copyright (C) 2015-2017 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#include <wtf/Vector.h>
29
30namespace WTF {
31
32// IndexSparseSet is an efficient set of integers that can only be valued
33// between zero and size() - 1.
34//
35// The implementation is using Briggs Sparse Set representation. We allocate
36// memory from 0 to size() - 1 to do mapping in O(1), but we never initialize
37// that memory. When adding/removing values to the set, they are added in a list
38// and the corresponding bucket is initialized to the position in the list.
39//
40// The assumption here is that we only need a sparse subset of number live at any
41// time.
42
43template<typename T>
44struct DefaultIndexSparseSetTraits {
45 typedef T EntryType;
46
47 static T create(unsigned entry)
48 {
49 return entry;
50 }
51
52 static unsigned key(const T& entry)
53 {
54 return entry;
55 }
56};
57
58template<typename KeyType, typename ValueType>
59struct DefaultIndexSparseSetTraits<KeyValuePair<KeyType, ValueType>> {
60 typedef KeyValuePair<KeyType, ValueType> EntryType;
61
62 template<typename PassedValueType>
63 static EntryType create(unsigned key, PassedValueType&& value)
64 {
65 return EntryType(key, std::forward<PassedValueType>(value));
66 }
67
68 static unsigned key(const EntryType& entry)
69 {
70 return entry.key;
71 }
72};
73
74template<typename EntryType = unsigned, typename EntryTypeTraits = DefaultIndexSparseSetTraits<EntryType>, typename OverflowHandler = CrashOnOverflow>
75class IndexSparseSet {
76 typedef Vector<EntryType, 0, OverflowHandler> ValueList;
77public:
78 explicit IndexSparseSet(unsigned size);
79
80 template<typename... Arguments>
81 bool add(unsigned, Arguments&&...);
82 template<typename... Arguments>
83 bool set(unsigned, Arguments&&...);
84 bool remove(unsigned);
85 void clear();
86
87 unsigned size() const;
88 bool isEmpty() const;
89 bool contains(unsigned) const;
90 const EntryType* get(unsigned) const;
91 EntryType* get(unsigned);
92
93 typedef typename ValueList::const_iterator const_iterator;
94 const_iterator begin() const;
95 const_iterator end() const;
96
97 void sort();
98
99 const ValueList& values() const { return m_values; }
100
101private:
102 Vector<unsigned, 0, OverflowHandler, 1> m_map;
103 ValueList m_values;
104};
105
106template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
107inline IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::IndexSparseSet(unsigned size)
108{
109 m_map.grow(size);
110}
111
112template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
113template<typename... Arguments>
114inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::add(unsigned value, Arguments&&... arguments)
115{
116 if (contains(value))
117 return false;
118
119 unsigned newPosition = m_values.size();
120 m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
121 m_map[value] = newPosition;
122 return true;
123}
124
125template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
126template<typename... Arguments>
127inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::set(unsigned value, Arguments&&... arguments)
128{
129 if (EntryType* entry = get(value)) {
130 *entry = EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...);
131 return false;
132 }
133
134 unsigned newPosition = m_values.size();
135 m_values.append(EntryTypeTraits::create(value, std::forward<Arguments>(arguments)...));
136 m_map[value] = newPosition;
137 return true;
138}
139
140template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
141inline bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::remove(unsigned value)
142{
143 unsigned position = m_map[value];
144 if (position >= m_values.size())
145 return false;
146
147 if (m_values[position] == value) {
148 EntryType lastValue = m_values.last();
149 m_values[position] = WTFMove(lastValue);
150 m_map[EntryTypeTraits::key(lastValue)] = position;
151 m_values.removeLast();
152 return true;
153 }
154
155 return false;
156}
157
158template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
159void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::clear()
160{
161 m_values.shrink(0);
162}
163
164template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
165unsigned IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::size() const
166{
167 return m_values.size();
168}
169
170template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
171bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::isEmpty() const
172{
173 return !size();
174}
175
176template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
177bool IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::contains(unsigned value) const
178{
179 unsigned position = m_map[value];
180 if (position >= m_values.size())
181 return false;
182
183 return EntryTypeTraits::key(m_values[position]) == value;
184}
185
186template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
187auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) -> EntryType*
188{
189 unsigned position = m_map[value];
190 if (position >= m_values.size())
191 return nullptr;
192
193 EntryType& entry = m_values[position];
194 if (EntryTypeTraits::key(entry) != value)
195 return nullptr;
196
197 return &entry;
198}
199
200template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
201auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::get(unsigned value) const -> const EntryType*
202{
203 return const_cast<IndexSparseSet*>(this)->get(value);
204}
205
206template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
207void IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::sort()
208{
209 std::sort(
210 m_values.begin(), m_values.end(),
211 [&] (const EntryType& a, const EntryType& b) {
212 return EntryTypeTraits::key(a) < EntryTypeTraits::key(b);
213 });
214}
215
216template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
217auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::begin() const -> const_iterator
218{
219 return m_values.begin();
220}
221
222template<typename EntryType, typename EntryTypeTraits, typename OverflowHandler>
223auto IndexSparseSet<EntryType, EntryTypeTraits, OverflowHandler>::end() const -> const_iterator
224{
225 return m_values.end();
226}
227
228} // namespace WTF
229
230using WTF::DefaultIndexSparseSetTraits;
231using WTF::IndexSparseSet;
232