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