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 44 namespace ue2 { 45 46 namespace flat_detail { 47 48 // Iterator facade that wraps an underlying iterator, so that we get our 49 // own iterator types. 50 template <class WrappedIter, class Value> 51 class iter_wrapper 52 : public boost::iterator_facade<iter_wrapper<WrappedIter, Value>, Value, 53 boost::random_access_traversal_tag> { 54 public: 55 iter_wrapper() = default; iter_wrapper(WrappedIter it_in)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. 60 private: 61 template <class, class> friend class iter_wrapper; 62 63 public: 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 get()70 WrappedIter get() const { return it; } 71 72 private: 73 friend class boost::iterator_core_access; 74 75 WrappedIter it; 76 increment()77 void increment() { ++it; } decrement()78 void decrement() { --it; } advance(size_t n)79 void advance(size_t n) { it += n; } 80 typename std::iterator_traits<WrappedIter>::difference_type distance_to(const iter_wrapper & other)81 distance_to(const iter_wrapper &other) const { 82 return other.it - it; 83 } equal(const iter_wrapper & other)84 bool equal(const iter_wrapper &other) const { return it == other.it; } dereference()85 Value &dereference() const { return *it; } 86 }; 87 88 template <class T, class Compare, class Allocator> 89 class flat_base { 90 protected: 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 flat_base(const Compare & compare,const Allocator & alloc)100 flat_base(const Compare &compare, const Allocator &alloc) 101 : storage(storage_type(storage_alloc_type(alloc)), compare) {} 102 data()103 storage_type &data() { return std::get<0>(this->storage); } data()104 const storage_type &data() const { return std::get<0>(this->storage); } 105 comp()106 Compare &comp() { return std::get<1>(this->storage); } comp()107 const Compare &comp() const { return std::get<1>(this->storage); } 108 109 public: 110 // Common member types. 111 using key_compare = Compare; 112 get_allocator()113 Allocator get_allocator() const { 114 return data().get_allocator(); 115 } 116 key_comp()117 key_compare key_comp() const { 118 return comp(); 119 } 120 121 // Capacity. 122 empty()123 bool empty() const { return data().empty(); } size()124 size_t size() const { return data().size(); } max_size()125 size_t max_size() const { return data().max_size(); } 126 127 // Modifiers. 128 clear()129 void clear() { 130 data().clear(); 131 } 132 swap(flat_base & a)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 */ 150 template <class T, class Compare = std::less<T>, 151 class Allocator = std::allocator<T>> 152 class 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. mutable_iterator(storage_const_iterator it)165 storage_iterator mutable_iterator(storage_const_iterator it) { 166 return data().begin() + std::distance(data().cbegin(), it); 167 } 168 #endif 169 170 public: 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()) base_type(compare,alloc)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()) flat_set(compare,alloc)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()) flat_set(compare,alloc)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 begin()223 iterator begin() { return iterator(data().begin()); } cbegin()224 const_iterator cbegin() const { return const_iterator(data().cbegin()); } begin()225 const_iterator begin() const { return cbegin(); } 226 end()227 iterator end() { return iterator(data().end()); } cend()228 const_iterator cend() const { return const_iterator(data().cend()); } end()229 const_iterator end() const { return cend(); } 230 rbegin()231 reverse_iterator rbegin() { return reverse_iterator(end()); } crbegin()232 const_reverse_iterator crbegin() const { 233 return const_reverse_iterator(cend()); 234 } rbegin()235 const_reverse_iterator rbegin() const { return crbegin(); } 236 rend()237 reverse_iterator rend() { return reverse_iterator(begin()); } crend()238 const_reverse_iterator crend() const { 239 return const_reverse_iterator(cbegin()); 240 } rend()241 const_reverse_iterator rend() const { return crend(); } 242 243 // Modifiers. 244 insert(const value_type & value)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 insert(UNUSED const_iterator hint,const value_type & value)253 iterator insert(UNUSED const_iterator hint, const value_type &value) { 254 return insert(value).first; 255 } 256 insert(value_type && value)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 insert(UNUSED const_iterator hint,value_type && value)266 iterator insert(UNUSED const_iterator hint, value_type &&value) { 267 return insert(value).first; 268 } 269 270 template <class InputIt> insert(InputIt first,InputIt second)271 void insert(InputIt first, InputIt second) { 272 for (; first != second; ++first) { 273 insert(*first); 274 } 275 } 276 insert(std::initializer_list<value_type> ilist)277 void insert(std::initializer_list<value_type> ilist) { 278 insert(ilist.begin(), ilist.end()); 279 } 280 281 template<class...Args> emplace(Args &&...args)282 std::pair<iterator, bool> emplace(Args&&... args) { 283 return insert(value_type(std::forward<Args>(args)...)); 284 } 285 erase(const_iterator pos)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 erase(const_iterator first,const_iterator last)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 erase(const key_type & key)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 count(const value_type & value)319 size_type count(const value_type &value) const { 320 return find(value) != end() ? 1 : 0; 321 } 322 find(const value_type & value)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 find(const value_type & value)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 value_comp()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. swap(flat_set & a,flat_set & b)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 */ 374 template <class Key, class T, class Compare = std::less<Key>, 375 class Allocator = std::allocator<std::pair<Key, T>>> 376 class flat_map 377 : public flat_detail::flat_base<std::pair<Key, T>, Compare, Allocator>, 378 public totally_ordered<flat_map<Key, T, Compare, Allocator>> { 379 public: 380 // Member types. 381 using key_type = Key; 382 using mapped_type = T; 383 using value_type = std::pair<const Key, T>; 384 385 private: 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. mutable_iterator(storage_const_iterator it)398 storage_iterator mutable_iterator(storage_const_iterator it) { 399 return data().begin() + std::distance(data().cbegin(), it); 400 } 401 #endif 402 403 public: 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 415 public: 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()) base_type(compare,alloc)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()) flat_map(compare,alloc)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()) flat_map(compare,alloc)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 cbegin()453 const_iterator cbegin() const { return const_iterator(data().cbegin()); } begin()454 const_iterator begin() const { return cbegin(); } 455 cend()456 const_iterator cend() const { return const_iterator(data().cend()); } end()457 const_iterator end() const { return cend(); } 458 crbegin()459 const_reverse_iterator crbegin() const { 460 return const_reverse_iterator(cend()); 461 } rbegin()462 const_reverse_iterator rbegin() const { return crbegin(); } 463 crend()464 const_reverse_iterator crend() const { 465 return const_reverse_iterator(cbegin()); 466 } rend()467 const_reverse_iterator rend() const { return crend(); } 468 469 private: data_lower_bound(const key_type & key)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 data_lower_bound(const key_type & key)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 data_insert(const value_type & value)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 data_insert(value_type && value)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 data_find(const key_type & key)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 data_find(const key_type & key)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 519 public: 520 // Modifiers. 521 insert(const value_type & value)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 insert(value_type && value)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> insert(InputIt first,InputIt second)533 void insert(InputIt first, InputIt second) { 534 for (; first != second; ++first) { 535 insert(*first); 536 } 537 } 538 insert(std::initializer_list<value_type> ilist)539 void insert(std::initializer_list<value_type> ilist) { 540 insert(ilist.begin(), ilist.end()); 541 } 542 543 template<class...Args> emplace(Args &&...args)544 std::pair<iterator, bool> emplace(Args&&... args) { 545 return insert(value_type(std::forward<Args>(args)...)); 546 } 547 erase(const_iterator pos)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 erase(const_iterator first,const_iterator last)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 erase(const key_type & key)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 count(const key_type & key)581 size_type count(const key_type &key) const { 582 return find(key) != end() ? 1 : 0; 583 } 584 find(const key_type & key)585 const_iterator find(const key_type &key) const { 586 return const_iterator(data_find(key)); 587 } 588 589 // Element access. 590 at(const key_type & key)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 at(const key_type & key)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; value_compare(Compare c_in)618 value_compare(Compare c_in) : c(c_in) {} 619 public: operator()620 bool operator()(const value_type &lhs, const value_type &rhs) { 621 return c(lhs.first, rhs.first); 622 } 623 }; 624 value_comp()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. swap(flat_map & a,flat_map & b)639 friend void swap(flat_map &a, flat_map &b) { 640 a.swap(b); 641 } 642 }; 643 644 } // namespace ue2 645 646 namespace std { 647 648 template<typename T, typename Compare, typename Allocator> 649 struct 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 655 template<typename Key, typename T, typename Compare, typename Allocator> 656 struct 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