1 // Profiling map implementation -*- C++ -*- 2 3 // Copyright (C) 2009-2014 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 <utility> 32 #include <profile/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 { 44 typedef _GLIBCXX_STD_C::map<_Key, _Tp, _Compare, _Allocator> _Base; 45 46 #if __cplusplus >= 201103L 47 typedef __gnu_cxx::__alloc_traits<_Allocator> _Alloc_traits; 48 #endif 49 50 public: 51 // types: 52 typedef _Key key_type; 53 typedef _Tp mapped_type; 54 typedef std::pair<const _Key, _Tp> value_type; 55 typedef _Compare key_compare; 56 typedef _Allocator allocator_type; 57 typedef typename _Base::reference reference; 58 typedef typename _Base::const_reference const_reference; 59 60 typedef typename _Base::iterator iterator; 61 typedef typename _Base::const_iterator const_iterator; 62 typedef typename _Base::size_type size_type; 63 typedef typename _Base::difference_type difference_type; 64 typedef typename _Base::pointer pointer; 65 typedef typename _Base::const_pointer const_pointer; 66 typedef std::reverse_iterator<iterator> reverse_iterator; 67 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 68 69 // 23.3.1.1 construct/copy/destroy: 70 71 map() 72 : _Base() 73 { __profcxx_map_to_unordered_map_construct(this); } 74 75 explicit 76 map(const _Compare& __comp, 77 const _Allocator& __a = _Allocator()) 78 : _Base(__comp, __a) 79 { __profcxx_map_to_unordered_map_construct(this); } 80 81 #if __cplusplus >= 201103L 82 template<typename _InputIterator, 83 typename = std::_RequireInputIter<_InputIterator>> 84 #else 85 template<typename _InputIterator> 86 #endif 87 map(_InputIterator __first, _InputIterator __last, 88 const _Compare& __comp = _Compare(), 89 const _Allocator& __a = _Allocator()) 90 : _Base(__first, __last, __comp, __a) 91 { __profcxx_map_to_unordered_map_construct(this); } 92 93 map(const map& __x) 94 : _Base(__x) 95 { __profcxx_map_to_unordered_map_construct(this); } 96 97 map(const _Base& __x) 98 : _Base(__x) 99 { __profcxx_map_to_unordered_map_construct(this); } 100 101 #if __cplusplus >= 201103L 102 map(map&& __x) 103 noexcept(is_nothrow_copy_constructible<_Compare>::value) 104 : _Base(std::move(__x)) 105 { __profcxx_map_to_unordered_map_construct(this); } 106 107 map(initializer_list<value_type> __l, 108 const _Compare& __c = _Compare(), 109 const allocator_type& __a = allocator_type()) 110 : _Base(__l, __c, __a) 111 { __profcxx_map_to_unordered_map_construct(this); } 112 113 explicit 114 map(const allocator_type& __a) 115 : _Base(__a) 116 { __profcxx_map_to_unordered_map_construct(this); } 117 118 map(const map& __x, const allocator_type& __a) 119 : _Base(__x, __a) 120 { __profcxx_map_to_unordered_map_construct(this); } 121 122 map(map&& __x, const allocator_type& __a) 123 noexcept(is_nothrow_copy_constructible<_Compare>::value 124 && _Alloc_traits::_S_always_equal()) 125 : _Base(std::move(__x), __a) 126 { __profcxx_map_to_unordered_map_construct(this); } 127 128 map(initializer_list<value_type> __l, const allocator_type& __a) 129 : _Base(__l, __a) 130 { __profcxx_map_to_unordered_map_construct(this); } 131 132 template<typename _InputIterator> 133 map(_InputIterator __first, _InputIterator __last, 134 const allocator_type& __a) 135 : _Base(__first, __last, __a) 136 { __profcxx_map_to_unordered_map_construct(this); } 137 #endif 138 139 ~map() _GLIBCXX_NOEXCEPT 140 { __profcxx_map_to_unordered_map_destruct(this); } 141 142 #if __cplusplus < 201103L 143 map& 144 operator=(const map& __x) 145 { 146 _M_base() = __x; 147 return *this; 148 } 149 #else 150 map& 151 operator=(const map&) = default; 152 153 map& 154 operator=(map&&) = default; 155 156 map& 157 operator=(initializer_list<value_type> __l) 158 { 159 _M_base() = __l; 160 return *this; 161 } 162 #endif 163 164 // _GLIBCXX_RESOLVE_LIB_DEFECTS 165 // 133. map missing get_allocator() 166 using _Base::get_allocator; 167 168 // iterators: 169 iterator 170 begin() _GLIBCXX_NOEXCEPT 171 { return _Base::begin(); } 172 173 const_iterator 174 begin() const _GLIBCXX_NOEXCEPT 175 { return _Base::begin(); } 176 177 iterator 178 end() _GLIBCXX_NOEXCEPT 179 { return _Base::end(); } 180 181 const_iterator 182 end() const _GLIBCXX_NOEXCEPT 183 { return _Base::end(); } 184 185 reverse_iterator 186 rbegin() _GLIBCXX_NOEXCEPT 187 { 188 __profcxx_map_to_unordered_map_invalidate(this); 189 return reverse_iterator(end()); 190 } 191 192 const_reverse_iterator 193 rbegin() const _GLIBCXX_NOEXCEPT 194 { 195 __profcxx_map_to_unordered_map_invalidate(this); 196 return const_reverse_iterator(end()); 197 } 198 199 reverse_iterator 200 rend() _GLIBCXX_NOEXCEPT 201 { 202 __profcxx_map_to_unordered_map_invalidate(this); 203 return reverse_iterator(begin()); 204 } 205 206 const_reverse_iterator 207 rend() const _GLIBCXX_NOEXCEPT 208 { 209 __profcxx_map_to_unordered_map_invalidate(this); 210 return const_reverse_iterator(begin()); 211 } 212 213 #if __cplusplus >= 201103L 214 const_iterator 215 cbegin() const noexcept 216 { return const_iterator(_Base::begin()); } 217 218 const_iterator 219 cend() const noexcept 220 { return const_iterator(_Base::end()); } 221 222 const_reverse_iterator 223 crbegin() const noexcept 224 { 225 __profcxx_map_to_unordered_map_invalidate(this); 226 return const_reverse_iterator(end()); 227 } 228 229 const_reverse_iterator 230 crend() const noexcept 231 { 232 __profcxx_map_to_unordered_map_invalidate(this); 233 return const_reverse_iterator(begin()); 234 } 235 #endif 236 237 // capacity: 238 using _Base::empty; 239 using _Base::size; 240 using _Base::max_size; 241 242 // 23.3.1.2 element access: 243 mapped_type& 244 operator[](const key_type& __k) 245 { 246 __profcxx_map_to_unordered_map_find(this, size()); 247 return _Base::operator[](__k); 248 } 249 250 #if __cplusplus >= 201103L 251 mapped_type& 252 operator[](key_type&& __k) 253 { 254 __profcxx_map_to_unordered_map_find(this, size()); 255 return _Base::operator[](std::move(__k)); 256 } 257 #endif 258 259 mapped_type& 260 at(const key_type& __k) 261 { 262 __profcxx_map_to_unordered_map_find(this, size()); 263 return _Base::at(__k); 264 } 265 266 const mapped_type& 267 at(const key_type& __k) const 268 { 269 __profcxx_map_to_unordered_map_find(this, size()); 270 return _Base::at(__k); 271 } 272 273 // modifiers: 274 #if __cplusplus >= 201103L 275 template<typename... _Args> 276 std::pair<iterator, bool> 277 emplace(_Args&&... __args) 278 { 279 __profcxx_map_to_unordered_map_insert(this, size(), 1); 280 auto __res = _Base::emplace(std::forward<_Args>(__args)...); 281 return std::pair<iterator, bool>(iterator(__res.first), 282 __res.second); 283 } 284 285 template<typename... _Args> 286 iterator 287 emplace_hint(const_iterator __pos, _Args&&... __args) 288 { 289 size_type size_before = size(); 290 auto __res = _Base::emplace_hint(__pos, 291 std::forward<_Args>(__args)...); 292 __profcxx_map_to_unordered_map_insert(this, size_before, 293 size() - size_before); 294 return __res; 295 } 296 #endif 297 298 std::pair<iterator, bool> 299 insert(const value_type& __x) 300 { 301 __profcxx_map_to_unordered_map_insert(this, size(), 1); 302 typedef typename _Base::iterator _Base_iterator; 303 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 304 return std::pair<iterator, bool>(iterator(__res.first), 305 __res.second); 306 } 307 308 #if __cplusplus >= 201103L 309 template<typename _Pair, typename = typename 310 std::enable_if<std::is_constructible<value_type, 311 _Pair&&>::value>::type> 312 std::pair<iterator, bool> 313 insert(_Pair&& __x) 314 { 315 __profcxx_map_to_unordered_map_insert(this, size(), 1); 316 typedef typename _Base::iterator _Base_iterator; 317 std::pair<_Base_iterator, bool> __res 318 = _Base::insert(std::forward<_Pair>(__x)); 319 return std::pair<iterator, bool>(iterator(__res.first), 320 __res.second); 321 } 322 #endif 323 324 #if __cplusplus >= 201103L 325 void 326 insert(std::initializer_list<value_type> __list) 327 { 328 size_type size_before = size(); 329 _Base::insert(__list); 330 __profcxx_map_to_unordered_map_insert(this, size_before, 331 size() - size_before); 332 } 333 #endif 334 335 iterator 336 #if __cplusplus >= 201103L 337 insert(const_iterator __position, const value_type& __x) 338 #else 339 insert(iterator __position, const value_type& __x) 340 #endif 341 { 342 size_type size_before = size(); 343 iterator __i = iterator(_Base::insert(__position, __x)); 344 __profcxx_map_to_unordered_map_insert(this, size_before, 345 size() - size_before); 346 return __i; 347 } 348 349 #if __cplusplus >= 201103L 350 template<typename _Pair, typename = typename 351 std::enable_if<std::is_constructible<value_type, 352 _Pair&&>::value>::type> 353 iterator 354 insert(const_iterator __position, _Pair&& __x) 355 { 356 size_type size_before = size(); 357 iterator __i 358 = iterator(_Base::insert(__position, std::forward<_Pair>(__x))); 359 __profcxx_map_to_unordered_map_insert(this, size_before, 360 size() - size_before); 361 return __i; 362 } 363 #endif 364 365 #if __cplusplus >= 201103L 366 template<typename _InputIterator, 367 typename = std::_RequireInputIter<_InputIterator>> 368 #else 369 template<typename _InputIterator> 370 #endif 371 void 372 insert(_InputIterator __first, _InputIterator __last) 373 { 374 size_type size_before = size(); 375 _Base::insert(__first, __last); 376 __profcxx_map_to_unordered_map_insert(this, size_before, 377 size() - size_before); 378 } 379 380 #if __cplusplus >= 201103L 381 iterator 382 erase(const_iterator __position) 383 { 384 iterator __i = _Base::erase(__position); 385 __profcxx_map_to_unordered_map_erase(this, size(), 1); 386 return __i; 387 } 388 389 iterator 390 erase(iterator __position) 391 { return erase(const_iterator(__position)); } 392 #else 393 void 394 erase(iterator __position) 395 { 396 _Base::erase(__position); 397 __profcxx_map_to_unordered_map_erase(this, size(), 1); 398 } 399 #endif 400 401 size_type 402 erase(const key_type& __x) 403 { 404 iterator __victim = find(__x); 405 if (__victim == end()) 406 return 0; 407 else 408 { 409 _Base::erase(__victim); 410 return 1; 411 } 412 } 413 414 #if __cplusplus >= 201103L 415 iterator 416 erase(const_iterator __first, const_iterator __last) 417 { return iterator(_Base::erase(__first, __last)); } 418 #else 419 void 420 erase(iterator __first, iterator __last) 421 { _Base::erase(__first, __last); } 422 #endif 423 424 void 425 swap(map& __x) 426 #if __cplusplus >= 201103L 427 noexcept(_Alloc_traits::_S_nothrow_swap()) 428 #endif 429 { _Base::swap(__x); } 430 431 void 432 clear() _GLIBCXX_NOEXCEPT 433 { this->erase(begin(), end()); } 434 435 // observers: 436 using _Base::key_comp; 437 using _Base::value_comp; 438 439 // 23.3.1.3 map operations: 440 iterator 441 find(const key_type& __x) 442 { 443 __profcxx_map_to_unordered_map_find(this, size()); 444 return iterator(_Base::find(__x)); 445 } 446 447 const_iterator 448 find(const key_type& __x) const 449 { 450 __profcxx_map_to_unordered_map_find(this, size()); 451 return const_iterator(_Base::find(__x)); 452 } 453 454 size_type 455 count(const key_type& __x) const 456 { 457 __profcxx_map_to_unordered_map_find(this, size()); 458 return _Base::count(__x); 459 } 460 461 iterator 462 lower_bound(const key_type& __x) 463 { 464 __profcxx_map_to_unordered_map_invalidate(this); 465 return iterator(_Base::lower_bound(__x)); 466 } 467 468 const_iterator 469 lower_bound(const key_type& __x) const 470 { 471 __profcxx_map_to_unordered_map_invalidate(this); 472 return const_iterator(_Base::lower_bound(__x)); 473 } 474 475 iterator 476 upper_bound(const key_type& __x) 477 { 478 __profcxx_map_to_unordered_map_invalidate(this); 479 return iterator(_Base::upper_bound(__x)); 480 } 481 482 const_iterator 483 upper_bound(const key_type& __x) const 484 { 485 __profcxx_map_to_unordered_map_invalidate(this); 486 return const_iterator(_Base::upper_bound(__x)); 487 } 488 489 std::pair<iterator,iterator> 490 equal_range(const key_type& __x) 491 { 492 typedef typename _Base::iterator _Base_iterator; 493 std::pair<_Base_iterator, _Base_iterator> __res = 494 _Base::equal_range(__x); 495 return std::make_pair(iterator(__res.first), 496 iterator(__res.second)); 497 } 498 499 std::pair<const_iterator,const_iterator> 500 equal_range(const key_type& __x) const 501 { 502 __profcxx_map_to_unordered_map_find(this, size()); 503 typedef typename _Base::const_iterator _Base_const_iterator; 504 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 505 _Base::equal_range(__x); 506 return std::make_pair(const_iterator(__res.first), 507 const_iterator(__res.second)); 508 } 509 510 _Base& 511 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 512 513 const _Base& 514 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 515 516 }; 517 518 template<typename _Key, typename _Tp, 519 typename _Compare, typename _Allocator> 520 inline bool 521 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 522 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 523 { 524 __profcxx_map_to_unordered_map_invalidate(&__lhs); 525 __profcxx_map_to_unordered_map_invalidate(&__rhs); 526 return __lhs._M_base() == __rhs._M_base(); 527 } 528 529 template<typename _Key, typename _Tp, 530 typename _Compare, typename _Allocator> 531 inline bool 532 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 533 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 534 { 535 __profcxx_map_to_unordered_map_invalidate(&__lhs); 536 __profcxx_map_to_unordered_map_invalidate(&__rhs); 537 return __lhs._M_base() != __rhs._M_base(); 538 } 539 540 template<typename _Key, typename _Tp, 541 typename _Compare, typename _Allocator> 542 inline bool 543 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 544 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 545 { 546 __profcxx_map_to_unordered_map_invalidate(&__lhs); 547 __profcxx_map_to_unordered_map_invalidate(&__rhs); 548 return __lhs._M_base() < __rhs._M_base(); 549 } 550 551 template<typename _Key, typename _Tp, 552 typename _Compare, typename _Allocator> 553 inline bool 554 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 555 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 556 { 557 __profcxx_map_to_unordered_map_invalidate(&__lhs); 558 __profcxx_map_to_unordered_map_invalidate(&__rhs); 559 return __lhs._M_base() <= __rhs._M_base(); 560 } 561 562 template<typename _Key, typename _Tp, 563 typename _Compare, typename _Allocator> 564 inline bool 565 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 566 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 567 { 568 __profcxx_map_to_unordered_map_invalidate(&__lhs); 569 __profcxx_map_to_unordered_map_invalidate(&__rhs); 570 return __lhs._M_base() >= __rhs._M_base(); 571 } 572 573 template<typename _Key, typename _Tp, 574 typename _Compare, typename _Allocator> 575 inline bool 576 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 577 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 578 { 579 __profcxx_map_to_unordered_map_invalidate(&__lhs); 580 __profcxx_map_to_unordered_map_invalidate(&__rhs); 581 return __lhs._M_base() > __rhs._M_base(); 582 } 583 584 template<typename _Key, typename _Tp, 585 typename _Compare, typename _Allocator> 586 inline void 587 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 588 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 589 { __lhs.swap(__rhs); } 590 591 } // namespace __profile 592 } // namespace std 593 594 #endif 595
