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
48namespace ue2 {
49
50namespace insertion_ordered_detail {
51
52// Iterator facade that wraps an underlying iterator, so that we get our
53// own iterator types.
54template<class WrappedIter, class Value>
55class iter_wrapper
56 : public boost::iterator_facade<iter_wrapper<WrappedIter, Value>, Value,
57 boost::random_access_traversal_tag> {
58public:
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
74private:
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
90template<class Key, class Element>
91class element_store {
92 std::vector<Element> data;
93 ue2_unordered_map<Key, size_t> map;
94
95public:
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
189template<class Key, class Value>
190class insertion_ordered_map
191 : public totally_ordered<insertion_ordered_map<Key, Value>> {
192public:
193 using key_type = Key;
194 using mapped_type = Value;
195 using value_type = std::pair<const Key, Value>;
196
197private:
198 using store_type = insertion_ordered_detail::element_store<Key, value_type>;
199 store_type store;
200
201public:
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
289template<class Key>
290class insertion_ordered_set
291 : public totally_ordered<insertion_ordered_set<Key>> {
292public:
293 using key_type = Key;
294 using value_type = Key;
295
296private:
297 using store_type = insertion_ordered_detail::element_store<Key, value_type>;
298 store_type store;
299
300public:
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