1 // Profiling map implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2019 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 // 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License along 21 // with this library; see the file COPYING3. If not see 22 // <http://www.gnu.org/licenses/>. 23 24 /** @file profile/map.h 25 * This file is a GNU profile extension to the Standard C++ Library. 26 */ 27 28 #ifndef _GLIBCXX_PROFILE_MAP_H 29 #define _GLIBCXX_PROFILE_MAP_H 1 30 31 #include <profile/base.h> 32 #include <profile/ordered_base.h> 33 34 namespace std _GLIBCXX_VISIBILITY(default) 35 { 36 namespace __profile 37 { 38 /// Class std::map wrapper with performance instrumentation. 39 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 40 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 41 class map 42 : public _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator>, 43 public _Ordered_profile<map<_Key, _Tp, _Compare, _Allocator> > 44 { 45 typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base; 46 47 typedef typename _Base::iterator _Base_iterator; 48 typedef typename _Base::const_iterator _Base_const_iterator; 49 50 public: 51 // types: 52 typedef _Key key_type; 53 typedef _Tp mapped_type; 54 typedef typename _Base::value_type value_type; 55 typedef _Compare key_compare; 56 typedef typename _Base::reference reference; 57 typedef typename _Base::const_reference const_reference; 58 59 typedef __iterator_tracker<_Base_iterator, map> iterator; 60 typedef __iterator_tracker<_Base_const_iterator, 61 map> const_iterator; 62 typedef std::reverse_iterator<iterator> reverse_iterator; 63 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 64 65 typedef typename _Base::size_type size_type; 66 typedef typename _Base::difference_type difference_type; 67 68 // 23.3.1.1 construct/copy/destroy: 69 70 #if __cplusplus < 201103L 71 map() 72 : _Base() { } 73 map(const map& __x) 74 : _Base(__x) { } 75 ~map() 76 { } 77 #else 78 map() = default; 79 map(const map&) = default; 80 map(map&&) = default; 81 ~map() = default; 82 #endif 83 84 explicit 85 map(const _Compare& __comp, 86 const _Allocator& __a = _Allocator()) 87 : _Base(__comp, __a) { } 88 89 #if __cplusplus >= 201103L 90 template<typename _InputIterator, 91 typename = std::_RequireInputIter<_InputIterator>> 92 #else 93 template<typename _InputIterator> 94 #endif 95 map(_InputIterator __first, _InputIterator __last, 96 const _Compare& __comp = _Compare(), 97 const _Allocator& __a = _Allocator()) 98 : _Base(__first, __last, __comp, __a) { } 99 100 map(const _Base& __x) 101 : _Base(__x) { } 102 103 #if __cplusplus >= 201103L 104 map(initializer_list<value_type> __l, 105 const _Compare& __c = _Compare(), 106 const _Allocator& __a = _Allocator()) 107 : _Base(__l, __c, __a) { } 108 109 explicit 110 map(const _Allocator& __a) 111 : _Base(__a) { } 112 113 map(const map& __x, const _Allocator& __a) 114 : _Base(__x, __a) { } 115 116 map(map&& __x, const _Allocator& __a) 117 noexcept( noexcept(_Base(std::move(__x), __a)) ) 118 : _Base(std::move(__x), __a) { } 119 120 map(initializer_list<value_type> __l, const _Allocator& __a) 121 : _Base(__l, __a) { } 122 123 template<typename _InputIterator> 124 map(_InputIterator __first, _InputIterator __last, 125 const _Allocator& __a) 126 : _Base(__first, __last, __a) { } 127 #endif 128 129 #if __cplusplus < 201103L 130 map& 131 operator=(const map& __x) 132 { 133 this->_M_profile_destruct(); 134 _M_base() = __x; 135 this->_M_profile_construct(); 136 return *this; 137 } 138 #else 139 map& 140 operator=(const map&) = default; 141 142 map& 143 operator=(map&&) = default; 144 145 map& 146 operator=(initializer_list<value_type> __l) 147 { 148 this->_M_profile_destruct(); 149 _M_base() = __l; 150 this->_M_profile_construct(); 151 return *this; 152 } 153 #endif 154 155 // iterators 156 iterator 157 begin() _GLIBCXX_NOEXCEPT 158 { return iterator(_Base::begin(), this); } 159 160 const_iterator 161 begin() const _GLIBCXX_NOEXCEPT 162 { return const_iterator(_Base::begin(), this); } 163 164 iterator 165 end() _GLIBCXX_NOEXCEPT 166 { return iterator(_Base::end(), this); } 167 168 const_iterator 169 end() const _GLIBCXX_NOEXCEPT 170 { return const_iterator(_Base::end(), this); } 171 172 #if __cplusplus >= 201103L 173 const_iterator 174 cbegin() const noexcept 175 { return const_iterator(_Base::cbegin(), this); } 176 177 const_iterator 178 cend() const noexcept 179 { return const_iterator(_Base::cend(), this); } 180 #endif 181 182 reverse_iterator 183 rbegin() _GLIBCXX_NOEXCEPT 184 { 185 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 186 return reverse_iterator(end()); 187 } 188 189 const_reverse_iterator 190 rbegin() const _GLIBCXX_NOEXCEPT 191 { 192 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 193 return const_reverse_iterator(end()); 194 } 195 196 reverse_iterator 197 rend() _GLIBCXX_NOEXCEPT 198 { 199 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 200 return reverse_iterator(begin()); 201 } 202 203 const_reverse_iterator 204 rend() const _GLIBCXX_NOEXCEPT 205 { 206 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 207 return const_reverse_iterator(begin()); 208 } 209 210 #if __cplusplus >= 201103L 211 const_reverse_iterator 212 crbegin() const noexcept 213 { 214 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 215 return const_reverse_iterator(cend()); 216 } 217 218 const_reverse_iterator 219 crend() const noexcept 220 { 221 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 222 return const_reverse_iterator(cbegin()); 223 } 224 #endif 225 226 // 23.3.1.2 element access: 227 mapped_type& 228 operator[](const key_type& __k) 229 { 230 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 231 return _Base::operator[](__k); 232 } 233 234 #if __cplusplus >= 201103L 235 mapped_type& 236 operator[](key_type&& __k) 237 { 238 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 239 return _Base::operator[](std::move(__k)); 240 } 241 #endif 242 243 mapped_type& 244 at(const key_type& __k) 245 { 246 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 247 return _Base::at(__k); 248 } 249 250 const mapped_type& 251 at(const key_type& __k) const 252 { 253 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 254 return _Base::at(__k); 255 } 256 257 // modifiers: 258 #if __cplusplus >= 201103L 259 template<typename... _Args> 260 std::pair<iterator, bool> 261 emplace(_Args&&... __args) 262 { 263 // The cost is the same whether or not the element is inserted so we 264 // always report insertion of 1 element. 265 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 266 auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...); 267 return std::make_pair(iterator(__base_ret.first, this), 268 __base_ret.second); 269 } 270 271 template<typename... _Args> 272 iterator 273 emplace_hint(const_iterator __pos, _Args&&... __args) 274 { 275 auto size_before = this->size(); 276 auto __res 277 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 278 __profcxx_map2umap_insert(this->_M_map2umap_info, 279 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 280 return iterator(__res, this); 281 } 282 #endif 283 284 std::pair<iterator, bool> 285 insert(const value_type& __x) 286 { 287 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 288 std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x); 289 return std::make_pair(iterator(__base_ret.first, this), 290 __base_ret.second); 291 } 292 293 #if __cplusplus >= 201103L 294 template<typename _Pair, typename = typename 295 std::enable_if<std::is_constructible<value_type, 296 _Pair&&>::value>::type> 297 std::pair<iterator, bool> 298 insert(_Pair&& __x) 299 { 300 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 301 auto __base_ret= _Base::insert(std::forward<_Pair>(__x)); 302 return std::make_pair(iterator(__base_ret.first, this), 303 __base_ret.second); 304 } 305 #endif 306 307 #if __cplusplus >= 201103L 308 void 309 insert(std::initializer_list<value_type> __list) 310 { insert(__list.begin(), __list.end()); } 311 #endif 312 313 iterator 314 #if __cplusplus >= 201103L 315 insert(const_iterator __pos, const value_type& __x) 316 #else 317 insert(iterator __pos, const value_type& __x) 318 #endif 319 { 320 size_type size_before = this->size(); 321 _Base_iterator __res = _Base::insert(__pos.base(), __x); 322 323 __profcxx_map2umap_insert(this->_M_map2umap_info, 324 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 325 return iterator(__res, this); 326 } 327 328 #if __cplusplus >= 201103L 329 template<typename _Pair, typename = typename 330 std::enable_if<std::is_constructible<value_type, 331 _Pair&&>::value>::type> 332 iterator 333 insert(const_iterator __pos, _Pair&& __x) 334 { 335 size_type size_before = this->size(); 336 auto __res = _Base::insert(__pos.base(), std::forward<_Pair>(__x)); 337 338 __profcxx_map2umap_insert(this->_M_map2umap_info, 339 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 340 return iterator(__res, this); 341 } 342 #endif 343 344 template<typename _InputIterator> 345 void 346 insert(_InputIterator __first, _InputIterator __last) 347 { 348 for (; __first != __last; ++__first) 349 insert(*__first); 350 } 351 352 #if __cplusplus >= 201103L 353 iterator 354 erase(const_iterator __pos) 355 { 356 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 357 return iterator(_Base::erase(__pos.base()), this); 358 } 359 360 iterator 361 erase(iterator __pos) 362 { 363 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 364 return iterator(_Base::erase(__pos.base()), this); 365 } 366 #else 367 void 368 erase(iterator __pos) 369 { 370 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 371 _Base::erase(__pos.base()); 372 } 373 #endif 374 375 size_type 376 erase(const key_type& __x) 377 { 378 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 379 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 380 return _Base::erase(__x); 381 } 382 383 #if __cplusplus >= 201103L 384 iterator 385 erase(const_iterator __first, const_iterator __last) 386 { 387 if (__first != __last) 388 { 389 iterator __ret; 390 for (; __first != __last;) 391 __ret = erase(__first++); 392 return __ret; 393 } 394 else 395 return iterator(_Base::erase(__first.base(), __last.base()), this); 396 } 397 #else 398 void 399 erase(iterator __first, iterator __last) 400 { 401 for (; __first != __last;) 402 erase(__first++); 403 } 404 #endif 405 406 void 407 swap(map& __x) 408 _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) 409 { 410 _Base::swap(__x); 411 this->_M_swap(__x); 412 } 413 414 void 415 clear() _GLIBCXX_NOEXCEPT 416 { 417 this->_M_profile_destruct(); 418 _Base::clear(); 419 this->_M_profile_construct(); 420 } 421 422 // 23.3.1.3 map operations: 423 iterator 424 find(const key_type& __x) 425 { 426 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 427 return iterator(_Base::find(__x), this); 428 } 429 430 #if __cplusplus > 201103L 431 template<typename _Kt, 432 typename _Req = 433 typename __has_is_transparent<_Compare, _Kt>::type> 434 iterator 435 find(const _Kt& __x) 436 { 437 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 438 return { _Base::find(__x), this }; 439 } 440 #endif 441 442 const_iterator 443 find(const key_type& __x) const 444 { 445 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 446 return const_iterator(_Base::find(__x), this); 447 } 448 449 #if __cplusplus > 201103L 450 template<typename _Kt, 451 typename _Req = 452 typename __has_is_transparent<_Compare, _Kt>::type> 453 const_iterator 454 find(const _Kt& __x) const 455 { 456 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 457 return { _Base::find(__x), this }; 458 } 459 #endif 460 461 size_type 462 count(const key_type& __x) const 463 { 464 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 465 return _Base::count(__x); 466 } 467 468 #if __cplusplus > 201103L 469 template<typename _Kt, 470 typename _Req = 471 typename __has_is_transparent<_Compare, _Kt>::type> 472 size_type 473 count(const _Kt& __x) const 474 { 475 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 476 return _Base::count(__x); 477 } 478 #endif 479 480 iterator 481 lower_bound(const key_type& __x) 482 { 483 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 484 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 485 return iterator(_Base::lower_bound(__x), this); 486 } 487 488 #if __cplusplus > 201103L 489 template<typename _Kt, 490 typename _Req = 491 typename __has_is_transparent<_Compare, _Kt>::type> 492 iterator 493 lower_bound(const _Kt& __x) 494 { 495 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 496 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 497 return { _Base::lower_bound(__x), this }; 498 } 499 #endif 500 501 const_iterator 502 lower_bound(const key_type& __x) const 503 { 504 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 505 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 506 return const_iterator(_Base::lower_bound(__x), this); 507 } 508 509 #if __cplusplus > 201103L 510 template<typename _Kt, 511 typename _Req = 512 typename __has_is_transparent<_Compare, _Kt>::type> 513 const_iterator 514 lower_bound(const _Kt& __x) const 515 { 516 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 517 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 518 return { _Base::lower_bound(__x), this }; 519 } 520 #endif 521 522 iterator 523 upper_bound(const key_type& __x) 524 { 525 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 526 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 527 return iterator(_Base::upper_bound(__x), this); 528 } 529 530 #if __cplusplus > 201103L 531 template<typename _Kt, 532 typename _Req = 533 typename __has_is_transparent<_Compare, _Kt>::type> 534 iterator 535 upper_bound(const _Kt& __x) 536 { 537 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 538 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 539 return { _Base::upper_bound(__x), this }; 540 } 541 #endif 542 543 const_iterator 544 upper_bound(const key_type& __x) const 545 { 546 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 547 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 548 return const_iterator(_Base::upper_bound(__x), this); 549 } 550 551 #if __cplusplus > 201103L 552 template<typename _Kt, 553 typename _Req = 554 typename __has_is_transparent<_Compare, _Kt>::type> 555 const_iterator 556 upper_bound(const _Kt& __x) const 557 { 558 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 559 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 560 return { _Base::upper_bound(__x), this }; 561 } 562 #endif 563 564 std::pair<iterator,iterator> 565 equal_range(const key_type& __x) 566 { 567 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 568 std::pair<_Base_iterator, _Base_iterator> __base_ret 569 = _Base::equal_range(__x); 570 return std::make_pair(iterator(__base_ret.first, this), 571 iterator(__base_ret.second, this)); 572 } 573 574 #if __cplusplus > 201103L 575 template<typename _Kt, 576 typename _Req = 577 typename __has_is_transparent<_Compare, _Kt>::type> 578 std::pair<iterator, iterator> 579 equal_range(const _Kt& __x) 580 { 581 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 582 auto __res = _Base::equal_range(__x); 583 return { { __res.first, this }, { __res.second, this } }; 584 } 585 #endif 586 587 std::pair<const_iterator,const_iterator> 588 equal_range(const key_type& __x) const 589 { 590 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 591 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 592 = _Base::equal_range(__x); 593 return std::make_pair(const_iterator(__base_ret.first, this), 594 const_iterator(__base_ret.second, this)); 595 } 596 597 #if __cplusplus > 201103L 598 template<typename _Kt, 599 typename _Req = 600 typename __has_is_transparent<_Compare, _Kt>::type> 601 std::pair<const_iterator, const_iterator> 602 equal_range(const _Kt& __x) const 603 { 604 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 605 auto __res = _Base::equal_range(__x); 606 return { { __res.first, this }, { __res.second, this } }; 607 } 608 #endif 609 610 _Base& 611 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 612 613 const _Base& 614 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 615 616 private: 617 /** If hint is used we consider that the map and unordered_map 618 * operations have equivalent insertion cost so we do not update metrics 619 * about it. 620 * Note that to find out if hint has been used is libstdc++ 621 * implementation dependent. 622 */ 623 bool 624 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 625 { 626 return (__hint == __res 627 || (__hint == _M_base().end() && ++__res == _M_base().end()) 628 || (__hint != _M_base().end() && (++__hint == __res 629 || ++__res == --__hint))); 630 } 631 632 633 template<typename _K1, typename _T1, typename _C1, typename _A1> 634 friend bool 635 operator==(const map<_K1, _T1, _C1, _A1>&, 636 const map<_K1, _T1, _C1, _A1>&); 637 638 template<typename _K1, typename _T1, typename _C1, typename _A1> 639 friend bool 640 operator<(const map<_K1, _T1, _C1, _A1>&, 641 const map<_K1, _T1, _C1, _A1>&); 642 }; 643 644 template<typename _Key, typename _Tp, 645 typename _Compare, typename _Allocator> 646 inline bool 647 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 648 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 649 { 650 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 651 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 652 return __lhs._M_base() == __rhs._M_base(); 653 } 654 655 template<typename _Key, typename _Tp, 656 typename _Compare, typename _Allocator> 657 inline bool 658 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 659 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 660 { 661 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 662 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 663 return __lhs._M_base() < __rhs._M_base(); 664 } 665 666 template<typename _Key, typename _Tp, 667 typename _Compare, typename _Allocator> 668 inline bool 669 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 670 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 671 { return !(__lhs == __rhs); } 672 673 template<typename _Key, typename _Tp, 674 typename _Compare, typename _Allocator> 675 inline bool 676 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 677 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 678 { return !(__rhs < __lhs); } 679 680 template<typename _Key, typename _Tp, 681 typename _Compare, typename _Allocator> 682 inline bool 683 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 684 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 685 { return !(__lhs < __rhs); } 686 687 template<typename _Key, typename _Tp, 688 typename _Compare, typename _Allocator> 689 inline bool 690 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 691 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 692 { return __rhs < __lhs; } 693 694 template<typename _Key, typename _Tp, 695 typename _Compare, typename _Allocator> 696 inline void 697 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 698 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 699 _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) 700 { __lhs.swap(__rhs); } 701 702 } // namespace __profile 703 } // namespace std 704 705 #endif 706
Indexes created Tue Feb 24 01:34:59 UTC 2026