1/*
2 * Copyright (c) 2015-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_FLAT_CONTAINERS_H
30#define UTIL_FLAT_CONTAINERS_H
31
32#include "ue2common.h"
33#include "util/hash.h"
34#include "util/operators.h"
35#include "util/small_vector.h"
36
37#include <algorithm>
38#include <iterator>
39#include <type_traits>
40#include <utility>
41
42#include <boost/iterator/iterator_facade.hpp>
43
44namespace ue2 {
45
46namespace flat_detail {
47
48// Iterator facade that wraps an underlying iterator, so that we get our
49// own iterator types.
50template <class WrappedIter, class Value>
51class iter_wrapper
52 : public boost::iterator_facade<iter_wrapper<WrappedIter, Value>, Value,
53 boost::random_access_traversal_tag> {
54public:
55 iter_wrapper() = default;
56 explicit iter_wrapper(WrappedIter it_in) : it(std::move(it_in)) {}
57
58 // Templated copy-constructor to allow for interoperable iterator and
59 // const_iterator.
60private:
61 template <class, class> friend class iter_wrapper;
62
63public:
64 template <class OtherIter, class OtherValue>
65 iter_wrapper(iter_wrapper<OtherIter, OtherValue> other,
66 typename std::enable_if<std::is_convertible<
67 OtherIter, WrappedIter>::value>::type * = nullptr)
68 : it(std::move(other.it)) {}
69
70 WrappedIter get() const { return it; }
71
72private:
73 friend class boost::iterator_core_access;
74
75 WrappedIter it;
76
77 void increment() { ++it; }
78 void decrement() { --it; }
79 void advance(size_t n) { it += n; }
80 typename std::iterator_traits<WrappedIter>::difference_type
81 distance_to(const iter_wrapper &other) const {
82 return other.it - it;
83 }
84 bool equal(const iter_wrapper &other) const { return it == other.it; }
85 Value &dereference() const { return *it; }
86};
87
88template <class T, class Compare, class Allocator>
89class flat_base {
90protected:
91 // Underlying storage is a small vector with local space for one element.
92 using storage_type = small_vector<T, 1, Allocator>;
93 using storage_alloc_type = typename storage_type::allocator_type;
94
95 // Putting our storage and comparator in a tuple allows us to make use of
96 // the empty base class optimization (if this STL implements it for
97 // std::tuple).
98 std::tuple<storage_type, Compare> storage;
99
100 flat_base(const Compare &compare, const Allocator &alloc)
101 : storage(storage_type(storage_alloc_type(alloc)), compare) {}
102
103 storage_type &data() { return std::get<0>(this->storage); }
104 const storage_type &data() const { return std::get<0>(this->storage); }
105
106 Compare &comp() { return std::get<1>(this->storage); }
107 const Compare &comp() const { return std::get<1>(this->storage); }
108
109public:
110 // Common member types.
111 using key_compare = Compare;
112
113 Allocator get_allocator() const {
114 return data().get_allocator();
115 }
116
117 key_compare key_comp() const {
118 return comp();
119 }
120
121 // Capacity.
122
123 bool empty() const { return data().empty(); }
124 size_t size() const { return data().size(); }
125 size_t max_size() const { return data().max_size(); }
126
127 // Modifiers.
128
129 void clear() {
130 data().clear();
131 }
132
133 void swap(flat_base &a) {
134 using std::swap;
135 swap(comp(), a.comp());
136 swap(data(), a.data());
137 }
138};
139
140} // namespace flat_detail
141
142/**
143 * \brief Set container implemented internally as a sorted vector. Use this
144 * rather than std::set for small sets as it's faster, uses less memory and
145 * incurs less malloc time.
146 *
147 * Note: we used to use boost::flat_set, but have run into problems with all
148 * the extra machinery it instantiates.
149 */
150template <class T, class Compare = std::less<T>,
151 class Allocator = std::allocator<T>>
152class flat_set
153 : public flat_detail::flat_base<T, Compare, Allocator>,
154 public totally_ordered<flat_set<T, Compare, Allocator>> {
155 using base_type = flat_detail::flat_base<T, Compare, Allocator>;
156 using storage_type = typename base_type::storage_type;
157 using storage_iterator = typename storage_type::iterator;
158 using storage_const_iterator = typename storage_type::const_iterator;
159 using base_type::data;
160 using base_type::comp;
161
162#if defined(SMALL_VECTOR_IS_STL_VECTOR)
163 // Construct a non-const iterator from a const iterator. Used in flat_map
164 // and flat_set erase() calls to work around g++-4.8 compatibility issues.
165 storage_iterator mutable_iterator(storage_const_iterator it) {
166 return data().begin() + std::distance(data().cbegin(), it);
167 }
168#endif
169
170public:
171 // Member types.
172 using key_type = T;
173 using value_type = T;
174 using size_type = typename storage_type::size_type;
175 using difference_type = typename storage_type::difference_type;
176 using key_compare = typename base_type::key_compare;
177 using value_compare = Compare;
178 using allocator_type = Allocator;
179 using reference = value_type &;
180 using const_reference = const value_type &;
181 using allocator_traits_type = typename std::allocator_traits<Allocator>;
182 using pointer = typename allocator_traits_type::pointer;
183 using const_pointer = typename allocator_traits_type::const_pointer;
184
185 // Iterator types.
186
187 using iterator = flat_detail::iter_wrapper<typename storage_type::iterator,
188 const value_type>;
189 using const_iterator =
190 flat_detail::iter_wrapper<typename storage_type::const_iterator,
191 const value_type>;
192
193 using reverse_iterator = std::reverse_iterator<iterator>;
194 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
195
196 // Constructors.
197
198 flat_set(const Compare &compare = Compare(),
199 const Allocator &alloc = Allocator())
200 : base_type(compare, alloc) {}
201
202 template <class InputIt>
203 flat_set(InputIt first, InputIt last, const Compare &compare = Compare(),
204 const Allocator &alloc = Allocator())
205 : flat_set(compare, alloc) {
206 insert(first, last);
207 }
208
209 flat_set(std::initializer_list<value_type> init,
210 const Compare &compare = Compare(),
211 const Allocator &alloc = Allocator())
212 : flat_set(compare, alloc) {
213 insert(init.begin(), init.end());
214 }
215
216 flat_set(const flat_set &) = default;
217 flat_set(flat_set &&) = default;
218 flat_set &operator=(const flat_set &) = default;
219 flat_set &operator=(flat_set &&) = default;
220
221 // Iterators.
222
223 iterator begin() { return iterator(data().begin()); }
224 const_iterator cbegin() const { return const_iterator(data().cbegin()); }
225 const_iterator begin() const { return cbegin(); }
226
227 iterator end() { return iterator(data().end()); }
228 const_iterator cend() const { return const_iterator(data().cend()); }
229 const_iterator end() const { return cend(); }
230
231 reverse_iterator rbegin() { return reverse_iterator(end()); }
232 const_reverse_iterator crbegin() const {
233 return const_reverse_iterator(cend());
234 }
235 const_reverse_iterator rbegin() const { return crbegin(); }
236
237 reverse_iterator rend() { return reverse_iterator(begin()); }
238 const_reverse_iterator crend() const {
239 return const_reverse_iterator(cbegin());
240 }
241 const_reverse_iterator rend() const { return crend(); }
242
243 // Modifiers.
244
245 std::pair<iterator, bool> insert(const value_type &value) {
246 auto it = std::lower_bound(data().begin(), data().end(), value, comp());
247 if (it == data().end() || comp()(value, *it)) {
248 return std::make_pair(iterator(data().insert(it, value)), true);
249 }
250 return std::make_pair(iterator(it), false);
251 }
252
253 iterator insert(UNUSED const_iterator hint, const value_type &value) {
254 return insert(value).first;
255 }
256
257 std::pair<iterator, bool> insert(value_type &&value) {
258 auto it = std::lower_bound(data().begin(), data().end(), value, comp());
259 if (it == data().end() || comp()(value, *it)) {
260 return std::make_pair(iterator(data().insert(it, std::move(value))),
261 true);
262 }
263 return std::make_pair(iterator(it), false);
264 }
265
266 iterator insert(UNUSED const_iterator hint, value_type &&value) {
267 return insert(value).first;
268 }
269
270 template <class InputIt>
271 void insert(InputIt first, InputIt second) {
272 for (; first != second; ++first) {
273 insert(*first);
274 }
275 }
276
277 void insert(std::initializer_list<value_type> ilist) {
278 insert(ilist.begin(), ilist.end());
279 }
280
281 template<class...Args>
282 std::pair<iterator, bool> emplace(Args&&... args) {
283 return insert(value_type(std::forward<Args>(args)...));
284 }
285
286 void erase(const_iterator pos) {
287#if defined(SMALL_VECTOR_IS_STL_VECTOR)
288 // Cope with libstdc++ 4.8's incomplete STL (it's missing C++11
289 // vector::erase(const_iterator)) by explicitly using a non-const
290 // iterator.
291 auto pos_it = mutable_iterator(pos.get());
292#else
293 auto pos_it = pos.get();
294#endif
295 data().erase(pos_it);
296 }
297
298 void erase(const_iterator first, const_iterator last) {
299#if defined(SMALL_VECTOR_IS_STL_VECTOR)
300 // As above, work around libstdc++ 4.8's incomplete C++11 support.
301 auto first_it = mutable_iterator(first.get());
302 auto last_it = mutable_iterator(last.get());
303#else
304 auto first_it = first.get();
305 auto last_it = last.get();
306#endif
307 data().erase(first_it, last_it);
308 }
309
310 void erase(const key_type &key) {
311 auto it = find(key);
312 if (it != end()) {
313 erase(it);
314 }
315 }
316
317 // Lookup.
318
319 size_type count(const value_type &value) const {
320 return find(value) != end() ? 1 : 0;
321 }
322
323 iterator find(const value_type &value) {
324 auto it = std::lower_bound(data().begin(), data().end(), value, comp());
325 if (it != data().end() && comp()(value, *it)) {
326 it = data().end();
327 }
328 return iterator(it);
329 }
330
331 const_iterator find(const value_type &value) const {
332 auto it = std::lower_bound(data().begin(), data().end(), value, comp());
333 if (it != data().end() && comp()(value, *it)) {
334 it = data().end();
335 }
336 return const_iterator(it);
337 }
338
339 // Observers.
340
341 value_compare value_comp() const {
342 return comp();
343 }
344
345 // Operators. All others provided by ue2::totally_ordered.
346
347 bool operator==(const flat_set &a) const {
348 return data() == a.data();
349 }
350 bool operator<(const flat_set &a) const {
351 return data() < a.data();
352 }
353
354 // Free swap function for ADL.
355 friend void swap(flat_set &a, flat_set &b) {
356 a.swap(b);
357 }
358};
359
360/**
361 * \brief Map container implemented internally as a sorted vector. Use this
362 * rather than std::map for small maps as it's faster, uses less memory and
363 * incurs less malloc time.
364 *
365 * Note: we used to use boost::flat_map, but have run into problems with all
366 * the extra machinery it instantiates.
367 *
368 * Note: ue2::flat_map does NOT provide mutable iterators, as (given the way
369 * the data is stored) it is difficult to provide a real mutable iterator that
370 * wraps std::pair<const Key, T>. Instead, all iterators are const, and you
371 * should use flat_map::at() or flat_map::operator[] to mutate the contents of
372 * the container.
373 */
374template <class Key, class T, class Compare = std::less<Key>,
375 class Allocator = std::allocator<std::pair<Key, T>>>
376class flat_map
377 : public flat_detail::flat_base<std::pair<Key, T>, Compare, Allocator>,
378 public totally_ordered<flat_map<Key, T, Compare, Allocator>> {
379public:
380 // Member types.
381 using key_type = Key;
382 using mapped_type = T;
383 using value_type = std::pair<const Key, T>;
384
385private:
386 using base_type =
387 flat_detail::flat_base<std::pair<Key, T>, Compare, Allocator>;
388 using keyval_storage_type = std::pair<key_type, mapped_type>;
389 using storage_type = typename base_type::storage_type;
390 using storage_iterator = typename storage_type::iterator;
391 using storage_const_iterator = typename storage_type::const_iterator;
392 using base_type::data;
393 using base_type::comp;
394
395#if defined(SMALL_VECTOR_IS_STL_VECTOR)
396 // Construct a non-const iterator from a const iterator. Used in flat_map
397 // and flat_set erase() calls to work around g++-4.8 compatibility issues.
398 storage_iterator mutable_iterator(storage_const_iterator it) {
399 return data().begin() + std::distance(data().cbegin(), it);
400 }
401#endif
402
403public:
404 // More Member types.
405 using size_type = typename storage_type::size_type;
406 using difference_type = typename storage_type::difference_type;
407 using key_compare = typename base_type::key_compare;
408 using allocator_type = Allocator;
409 using reference = value_type &;
410 using const_reference = const value_type &;
411 using allocator_traits_type = typename std::allocator_traits<Allocator>;
412 using pointer = typename allocator_traits_type::pointer;
413 using const_pointer = typename allocator_traits_type::const_pointer;
414
415public:
416 using const_iterator =
417 flat_detail::iter_wrapper<typename storage_type::const_iterator,
418 const keyval_storage_type>;
419
420 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
421
422 // All iterators are const for flat_map.
423 using iterator = const_iterator;
424 using reverse_iterator = const_reverse_iterator;
425
426 // Constructors.
427
428 flat_map(const Compare &compare = Compare(),
429 const Allocator &alloc = Allocator())
430 : base_type(compare, alloc) {}
431
432 template <class InputIt>
433 flat_map(InputIt first, InputIt last, const Compare &compare = Compare(),
434 const Allocator &alloc = Allocator())
435 : flat_map(compare, alloc) {
436 insert(first, last);
437 }
438
439 flat_map(std::initializer_list<value_type> init,
440 const Compare &compare = Compare(),
441 const Allocator &alloc = Allocator())
442 : flat_map(compare, alloc) {
443 insert(init.begin(), init.end());
444 }
445
446 flat_map(const flat_map &) = default;
447 flat_map(flat_map &&) = default;
448 flat_map &operator=(const flat_map &) = default;
449 flat_map &operator=(flat_map &&) = default;
450
451 // Iterators.
452
453 const_iterator cbegin() const { return const_iterator(data().cbegin()); }
454 const_iterator begin() const { return cbegin(); }
455
456 const_iterator cend() const { return const_iterator(data().cend()); }
457 const_iterator end() const { return cend(); }
458
459 const_reverse_iterator crbegin() const {
460 return const_reverse_iterator(cend());
461 }
462 const_reverse_iterator rbegin() const { return crbegin(); }
463
464 const_reverse_iterator crend() const {
465 return const_reverse_iterator(cbegin());
466 }
467 const_reverse_iterator rend() const { return crend(); }
468
469private:
470 storage_iterator data_lower_bound(const key_type &key) {
471 return std::lower_bound(
472 data().begin(), data().end(), key,
473 [&](const keyval_storage_type &elem, const key_type &k) {
474 return comp()(elem.first, k);
475 });
476 }
477
478 storage_const_iterator
479 data_lower_bound(const key_type &key) const {
480 return std::lower_bound(
481 data().begin(), data().end(), key,
482 [&](const keyval_storage_type &elem, const key_type &k) {
483 return comp()(elem.first, k);
484 });
485 }
486
487 std::pair<storage_iterator, bool> data_insert(const value_type &value) {
488 auto it = data_lower_bound(value.first);
489 if (it == data().end() || comp()(value.first, it->first)) {
490 return std::make_pair(data().insert(it, value), true);
491 }
492 return std::make_pair(it, false);
493 }
494
495 std::pair<storage_iterator, bool> data_insert(value_type &&value) {
496 auto it = data_lower_bound(value.first);
497 if (it == data().end() || comp()(value.first, it->first)) {
498 return std::make_pair(data().insert(it, std::move(value)), true);
499 }
500 return std::make_pair(it, false);
501 }
502
503 storage_iterator data_find(const key_type &key) {
504 auto it = data_lower_bound(key);
505 if (it != data().end() && comp()(key, it->first)) {
506 it = data().end();
507 }
508 return it;
509 }
510
511 storage_const_iterator data_find(const key_type &key) const {
512 auto it = data_lower_bound(key);
513 if (it != data().end() && comp()(key, it->first)) {
514 it = data().end();
515 }
516 return it;
517 }
518
519public:
520 // Modifiers.
521
522 std::pair<iterator, bool> insert(const value_type &value) {
523 auto rv = data_insert(value);
524 return std::make_pair(iterator(rv.first), rv.second);
525 }
526
527 std::pair<iterator, bool> insert(value_type &&value) {
528 auto rv = data_insert(std::move(value));
529 return std::make_pair(iterator(rv.first), rv.second);
530 }
531
532 template <class InputIt>
533 void insert(InputIt first, InputIt second) {
534 for (; first != second; ++first) {
535 insert(*first);
536 }
537 }
538
539 void insert(std::initializer_list<value_type> ilist) {
540 insert(ilist.begin(), ilist.end());
541 }
542
543 template<class...Args>
544 std::pair<iterator, bool> emplace(Args&&... args) {
545 return insert(value_type(std::forward<Args>(args)...));
546 }
547
548 void erase(const_iterator pos) {
549#if defined(SMALL_VECTOR_IS_STL_VECTOR)
550 // Cope with libstdc++ 4.8's incomplete STL (it's missing C++11
551 // vector::erase(const_iterator)) by explicitly using a non-const
552 // iterator.
553 auto pos_it = mutable_iterator(pos.get());
554#else
555 auto pos_it = pos.get();
556#endif
557 data().erase(pos_it);
558 }
559
560 void erase(const_iterator first, const_iterator last) {
561#if defined(SMALL_VECTOR_IS_STL_VECTOR)
562 // As above, work around libstdc++ 4.8's incomplete C++11 support.
563 auto first_it = mutable_iterator(first.get());
564 auto last_it = mutable_iterator(last.get());
565#else
566 auto first_it = first.get();
567 auto last_it = last.get();
568#endif
569 data().erase(first_it, last_it);
570 }
571
572 void erase(const key_type &key) {
573 auto it = find(key);
574 if (it != end()) {
575 erase(it);
576 }
577 }
578
579 // Lookup.
580
581 size_type count(const key_type &key) const {
582 return find(key) != end() ? 1 : 0;
583 }
584
585 const_iterator find(const key_type &key) const {
586 return const_iterator(data_find(key));
587 }
588
589 // Element access.
590
591 mapped_type &at(const key_type &key) {
592 auto it = data_find(key);
593 if (it == data().end()) {
594 throw std::out_of_range("element not found");
595 }
596 return it->second;
597 }
598
599 const mapped_type &at(const key_type &key) const {
600 auto it = data_find(key);
601 if (it == data().end()) {
602 throw std::out_of_range("element not found");
603 }
604 return it->second;
605 }
606
607 mapped_type &operator[](const key_type &key) {
608 auto p = data_insert(value_type(key, mapped_type()));
609 return p.first->second;
610 }
611
612 // Observers.
613
614 class value_compare {
615 friend class flat_map;
616 protected:
617 Compare c;
618 value_compare(Compare c_in) : c(c_in) {}
619 public:
620 bool operator()(const value_type &lhs, const value_type &rhs) {
621 return c(lhs.first, rhs.first);
622 }
623 };
624
625 value_compare value_comp() const {
626 return value_compare(comp());
627 }
628
629 // Operators. All others provided by ue2::totally_ordered.
630
631 bool operator==(const flat_map &a) const {
632 return data() == a.data();
633 }
634 bool operator<(const flat_map &a) const {
635 return data() < a.data();
636 }
637
638 // Free swap function for ADL.
639 friend void swap(flat_map &a, flat_map &b) {
640 a.swap(b);
641 }
642};
643
644} // namespace ue2
645
646namespace std {
647
648template<typename T, typename Compare, typename Allocator>
649struct hash<ue2::flat_set<T, Compare, Allocator>> {
650 size_t operator()(const ue2::flat_set<T, Compare, Allocator> &f) {
651 return ue2::ue2_hasher()(f);
652 }
653};
654
655template<typename Key, typename T, typename Compare, typename Allocator>
656struct hash<ue2::flat_map<Key, T, Compare, Allocator>> {
657 size_t operator()(const ue2::flat_map<Key, T, Compare, Allocator> &f) {
658 return ue2::ue2_hasher()(f);
659 }
660};
661
662} // namespace std
663
664#endif // UTIL_FLAT_CONTAINERS_H
665