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