1 | /* |
2 | * Copyright (c) 2017, Intel Corporation |
3 | * |
4 | * Redistribution and use in source and binary forms, with or without |
5 | * modification, are permitted provided that the following conditions are met: |
6 | * |
7 | * * Redistributions of source code must retain the above copyright notice, |
8 | * this list of conditions and the following disclaimer. |
9 | * * 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 | * * Neither the name of Intel Corporation nor the names of its contributors |
13 | * may be used to endorse or promote products derived from this software |
14 | * without specific prior written permission. |
15 | * |
16 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
17 | * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
18 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
19 | * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE |
20 | * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR |
21 | * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF |
22 | * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS |
23 | * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN |
24 | * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
25 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE |
26 | * POSSIBILITY OF SUCH DAMAGE. |
27 | */ |
28 | |
29 | #ifndef UTIL_INSERTION_ORDERED_H |
30 | #define UTIL_INSERTION_ORDERED_H |
31 | |
32 | /** |
33 | * \file |
34 | * \brief Insertion-ordered associative containers (set, map). |
35 | */ |
36 | |
37 | #include "util/operators.h" |
38 | #include "util/unordered.h" |
39 | |
40 | #include <cassert> |
41 | #include <iterator> |
42 | #include <type_traits> |
43 | #include <utility> |
44 | #include <vector> |
45 | |
46 | #include <boost/iterator/iterator_facade.hpp> |
47 | |
48 | namespace ue2 { |
49 | |
50 | namespace insertion_ordered_detail { |
51 | |
52 | // Iterator facade that wraps an underlying iterator, so that we get our |
53 | // own iterator types. |
54 | template<class WrappedIter, class Value> |
55 | class iter_wrapper |
56 | : public boost::iterator_facade<iter_wrapper<WrappedIter, Value>, Value, |
57 | boost::random_access_traversal_tag> { |
58 | public: |
59 | iter_wrapper() = default; |
60 | explicit iter_wrapper(WrappedIter it_in) : it(std::move(it_in)) {} |
61 | |
62 | // Templated copy-constructor to allow for interoperable iterator and |
63 | // const_iterator. |
64 | template<class, class> friend class iter_wrapper; |
65 | |
66 | template<class OtherIter, class OtherValue> |
67 | iter_wrapper(iter_wrapper<OtherIter, OtherValue> other, |
68 | typename std::enable_if<std::is_convertible< |
69 | OtherIter, WrappedIter>::value>::type * = nullptr) |
70 | : it(std::move(other.it)) {} |
71 | |
72 | WrappedIter get() const { return it; } |
73 | |
74 | private: |
75 | friend class boost::iterator_core_access; |
76 | |
77 | WrappedIter it; |
78 | |
79 | void increment() { ++it; } |
80 | void decrement() { --it; } |
81 | void advance(size_t n) { it += n; } |
82 | typename std::iterator_traits<WrappedIter>::difference_type |
83 | distance_to(const iter_wrapper &other) const { |
84 | return other.it - it; |
85 | } |
86 | bool equal(const iter_wrapper &other) const { return it == other.it; } |
87 | Value &dereference() const { return *it; } |
88 | }; |
89 | |
90 | template<class Key, class Element> |
91 | class element_store { |
92 | std::vector<Element> data; |
93 | ue2_unordered_map<Key, size_t> map; |
94 | |
95 | public: |
96 | bool empty() const { |
97 | return data.empty(); |
98 | } |
99 | |
100 | size_t size() const { |
101 | assert(data.size() == map.size()); |
102 | return data.size(); |
103 | } |
104 | |
105 | void clear() { |
106 | data.clear(); |
107 | map.clear(); |
108 | } |
109 | |
110 | void reserve(size_t n) { |
111 | data.reserve(n); |
112 | map.reserve(n); |
113 | } |
114 | |
115 | // Iteration. |
116 | |
117 | using const_iterator = |
118 | iter_wrapper<typename std::vector<Element>::const_iterator, |
119 | const Element>; |
120 | using iterator = |
121 | iter_wrapper<typename std::vector<Element>::iterator, Element>; |
122 | |
123 | const_iterator begin() const { |
124 | return const_iterator(data.begin()); |
125 | } |
126 | |
127 | const_iterator end() const { |
128 | return const_iterator(data.end()); |
129 | } |
130 | |
131 | iterator begin() { |
132 | return iterator(data.begin()); |
133 | } |
134 | |
135 | iterator end() { |
136 | return iterator(data.end()); |
137 | } |
138 | |
139 | // Search. |
140 | |
141 | const_iterator find(const Key &key) const { |
142 | auto map_it = map.find(key); |
143 | if (map_it == map.end()) { |
144 | return end(); |
145 | } |
146 | auto idx = map_it->second; |
147 | assert(idx < data.size()); |
148 | return begin() + idx; |
149 | } |
150 | |
151 | iterator find(const Key &key) { |
152 | auto map_it = map.find(key); |
153 | if (map_it == map.end()) { |
154 | return end(); |
155 | } |
156 | auto idx = map_it->second; |
157 | assert(idx < data.size()); |
158 | return begin() + idx; |
159 | } |
160 | |
161 | // Insert. |
162 | |
163 | std::pair<iterator, bool> insert(const Key &key, const Element &element) { |
164 | const auto idx = data.size(); |
165 | if (map.emplace(key, idx).second) { |
166 | data.push_back(element); |
167 | return {begin() + idx, true}; |
168 | } |
169 | return {end(), false}; |
170 | } |
171 | |
172 | bool operator==(const element_store &a) const { |
173 | return data == a.data; |
174 | } |
175 | |
176 | bool operator<(const element_store &a) const { |
177 | return data < a.data; |
178 | } |
179 | |
180 | void swap(element_store &a) { |
181 | using std::swap; |
182 | swap(data, a.data); |
183 | swap(map, a.map); |
184 | } |
185 | }; |
186 | |
187 | } // namespace insertion_ordered_detail |
188 | |
189 | template<class Key, class Value> |
190 | class insertion_ordered_map |
191 | : public totally_ordered<insertion_ordered_map<Key, Value>> { |
192 | public: |
193 | using key_type = Key; |
194 | using mapped_type = Value; |
195 | using value_type = std::pair<const Key, Value>; |
196 | |
197 | private: |
198 | using store_type = insertion_ordered_detail::element_store<Key, value_type>; |
199 | store_type store; |
200 | |
201 | public: |
202 | using const_iterator = typename store_type::const_iterator; |
203 | using iterator = typename store_type::iterator; |
204 | |
205 | insertion_ordered_map() = default; |
206 | |
207 | template<class Iter> |
208 | insertion_ordered_map(Iter it, Iter it_end) { |
209 | insert(it, it_end); |
210 | } |
211 | |
212 | explicit insertion_ordered_map(std::initializer_list<value_type> init) { |
213 | insert(init.begin(), init.end()); |
214 | } |
215 | |
216 | const_iterator begin() const { return store.begin(); } |
217 | const_iterator end() const { return store.end(); } |
218 | iterator begin() { return store.begin(); } |
219 | iterator end() { return store.end(); } |
220 | |
221 | const_iterator find(const Key &key) const { |
222 | return store.find(key); |
223 | } |
224 | |
225 | iterator find(const Key &key) { |
226 | return store.find(key); |
227 | } |
228 | |
229 | std::pair<iterator, bool> insert(const std::pair<const Key, Value> &p) { |
230 | return store.insert(p.first, p); |
231 | } |
232 | |
233 | template<class Iter> |
234 | void insert(Iter it, Iter it_end) { |
235 | for (; it != it_end; ++it) { |
236 | insert(*it); |
237 | } |
238 | } |
239 | |
240 | Value &operator[](const Key &key) { |
241 | auto it = find(key); |
242 | if (it == end()) { |
243 | it = insert({key, Value{}}).first; |
244 | } |
245 | return it->second; |
246 | } |
247 | |
248 | const Value &at(const Key &key) const { |
249 | return find(key)->second; |
250 | } |
251 | |
252 | Value &at(const Key &key) { |
253 | return find(key)->second; |
254 | } |
255 | |
256 | bool empty() const { |
257 | return store.empty(); |
258 | } |
259 | |
260 | size_t size() const { |
261 | return store.size(); |
262 | } |
263 | |
264 | void clear() { |
265 | store.clear(); |
266 | } |
267 | |
268 | void reserve(size_t n) { |
269 | store.reserve(n); |
270 | } |
271 | |
272 | bool operator==(const insertion_ordered_map &a) const { |
273 | return store == a.store; |
274 | } |
275 | |
276 | bool operator<(const insertion_ordered_map &a) const { |
277 | return store < a.store; |
278 | } |
279 | |
280 | void swap(insertion_ordered_map &a) { |
281 | store.swap(a.store); |
282 | } |
283 | |
284 | friend void swap(insertion_ordered_map &a, insertion_ordered_map &b) { |
285 | a.swap(b); |
286 | } |
287 | }; |
288 | |
289 | template<class Key> |
290 | class insertion_ordered_set |
291 | : public totally_ordered<insertion_ordered_set<Key>> { |
292 | public: |
293 | using key_type = Key; |
294 | using value_type = Key; |
295 | |
296 | private: |
297 | using store_type = insertion_ordered_detail::element_store<Key, value_type>; |
298 | store_type store; |
299 | |
300 | public: |
301 | using const_iterator = typename store_type::const_iterator; |
302 | using iterator = typename store_type::iterator; |
303 | |
304 | insertion_ordered_set() = default; |
305 | |
306 | template<class Iter> |
307 | insertion_ordered_set(Iter it, Iter it_end) { |
308 | insert(it, it_end); |
309 | } |
310 | |
311 | explicit insertion_ordered_set(std::initializer_list<value_type> init) { |
312 | insert(init.begin(), init.end()); |
313 | } |
314 | |
315 | const_iterator begin() const { return store.begin(); } |
316 | const_iterator end() const { return store.end(); } |
317 | |
318 | const_iterator find(const Key &key) const { |
319 | return store.find(key); |
320 | } |
321 | |
322 | std::pair<iterator, bool> insert(const Key &key) { |
323 | return store.insert(key, key); |
324 | } |
325 | |
326 | template<class Iter> |
327 | void insert(Iter it, Iter it_end) { |
328 | for (; it != it_end; ++it) { |
329 | insert(*it); |
330 | } |
331 | } |
332 | |
333 | bool empty() const { |
334 | return store.empty(); |
335 | } |
336 | |
337 | size_t size() const { |
338 | return store.size(); |
339 | } |
340 | |
341 | void clear() { |
342 | store.clear(); |
343 | } |
344 | |
345 | void reserve(size_t n) { |
346 | store.reserve(n); |
347 | } |
348 | |
349 | bool operator==(const insertion_ordered_set &a) const { |
350 | return store == a.store; |
351 | } |
352 | |
353 | bool operator<(const insertion_ordered_set &a) const { |
354 | return store < a.store; |
355 | } |
356 | |
357 | void swap(insertion_ordered_set &a) { |
358 | store.swap(a.store); |
359 | } |
360 | |
361 | friend void swap(insertion_ordered_set &a, insertion_ordered_set &b) { |
362 | a.swap(b); |
363 | } |
364 | }; |
365 | |
366 | } // namespace ue2 |
367 | |
368 | #endif // UTIL_INSERTION_ORDERED_H |
369 | |