1// Profiling set implementation -*- C++ -*- 2 3// Copyright (C) 2009-2015 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 35namespace std _GLIBCXX_VISIBILITY(default) 36{ 37namespace __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#if __cplusplus >= 201103L 227 noexcept( noexcept(declval<_Base>().swap(__x)) ) 228#endif 229 { 230 _Base::swap(__x); 231 this->_M_swap(__x); 232 } 233 234 // modifiers: 235#if __cplusplus >= 201103L 236 template<typename... _Args> 237 std::pair<iterator, bool> 238 emplace(_Args&&... __args) 239 { 240 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 241 auto __base_ret = _Base::emplace(std::forward<_Args>(__args)...); 242 return std::make_pair(iterator(__base_ret.first, this), 243 __base_ret.second); 244 } 245 246 template<typename... _Args> 247 iterator 248 emplace_hint(const_iterator __pos, _Args&&... __args) 249 { 250 auto size_before = this->size(); 251 auto __res 252 = _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...); 253 __profcxx_map2umap_insert(this->_M_map2umap_info, 254 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 255 return iterator(__res, this); 256 } 257#endif 258 259 std::pair<iterator, bool> 260 insert(const value_type& __x) 261 { 262 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 263 std::pair<_Base_iterator, bool> __base_ret = _Base::insert(__x); 264 return std::make_pair(iterator(__base_ret.first, this), 265 __base_ret.second); 266 } 267 268#if __cplusplus >= 201103L 269 std::pair<iterator, bool> 270 insert(value_type&& __x) 271 { 272 __profcxx_map2umap_insert(this->_M_map2umap_info, this->size(), 1); 273 std::pair<_Base_iterator, bool> __base_ret 274 = _Base::insert(std::move(__x)); 275 return std::make_pair(iterator(__base_ret.first, this), 276 __base_ret.second); 277 } 278#endif 279 280 iterator 281 insert(const_iterator __pos, const value_type& __x) 282 { 283 size_type size_before = this->size(); 284 _Base_iterator __res = _Base::insert(__pos.base(), __x); 285 __profcxx_map2umap_insert(this->_M_map2umap_info, 286 size_before, _M_hint_used(__pos.base(), __res) ? 0 : 1); 287 return iterator(__res, this); 288 } 289 290#if __cplusplus >= 201103L 291 iterator 292 insert(const_iterator __pos, value_type&& __x) 293 { return iterator(_Base::insert(__pos.base(), std::move(__x)), this); } 294#endif 295 296 template<typename _InputIterator> 297 void 298 insert(_InputIterator __first, _InputIterator __last) 299 { 300 for (; __first != __last; ++__first) 301 insert(*__first); 302 } 303 304#if __cplusplus >= 201103L 305 void 306 insert(initializer_list<value_type> __l) 307 { insert(__l.begin(), __l.end()); } 308#endif 309 310#if __cplusplus >= 201103L 311 iterator 312 erase(const_iterator __pos) 313 { 314 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 315 return iterator(_Base::erase(__pos.base()), this); 316 } 317#else 318 void 319 erase(iterator __pos) 320 { 321 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 322 _Base::erase(__pos.base()); 323 } 324#endif 325 326 size_type 327 erase(const key_type& __x) 328 { 329 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 330 __profcxx_map2umap_erase(this->_M_map2umap_info, this->size(), 1); 331 return _Base::erase(__x); 332 } 333 334#if __cplusplus >= 201103L 335 iterator 336 erase(const_iterator __first, const_iterator __last) 337 { 338 if (__first != __last) 339 { 340 iterator __ret; 341 for (; __first != __last;) 342 __ret = erase(__first++); 343 return __ret; 344 } 345 346 return iterator(_Base::erase(__first.base(), __last.base()), this); 347 } 348#else 349 void 350 erase(iterator __first, iterator __last) 351 { 352 for (; __first != __last;) 353 erase(__first++); 354 } 355#endif 356 357 void 358 clear() _GLIBCXX_NOEXCEPT 359 { 360 this->_M_profile_destruct(); 361 _Base::clear(); 362 this->_M_profile_construct(); 363 } 364 365 size_type 366 count(const key_type& __x) const 367 { 368 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 369 return _Base::count(__x); 370 } 371 372 // set operations: 373 iterator 374 find(const key_type& __x) 375 { 376 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 377 return iterator(_Base::find(__x), this); 378 } 379 380 const_iterator 381 find(const key_type& __x) const 382 { 383 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 384 return const_iterator(_Base::find(__x), this); 385 } 386 387 iterator 388 lower_bound(const key_type& __x) 389 { 390 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 391 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 392 return iterator(_Base::lower_bound(__x), this); 393 } 394 395 const_iterator 396 lower_bound(const key_type& __x) const 397 { 398 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 399 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 400 return const_iterator(_Base::lower_bound(__x), this); 401 } 402 403 iterator 404 upper_bound(const key_type& __x) 405 { 406 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 407 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 408 return iterator(_Base::upper_bound(__x), this); 409 } 410 411 const_iterator 412 upper_bound(const key_type& __x) const 413 { 414 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 415 __profcxx_map2umap_invalidate(this->_M_map2umap_info); 416 return const_iterator(_Base::upper_bound(__x), this); 417 } 418 419 std::pair<iterator, iterator> 420 equal_range(const key_type& __x) 421 { 422 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 423 std::pair<_Base_iterator, _Base_iterator> __base_ret 424 = _Base::equal_range(__x); 425 return std::make_pair(iterator(__base_ret.first, this), 426 iterator(__base_ret.second, this)); 427 } 428 429 std::pair<const_iterator, const_iterator> 430 equal_range(const key_type& __x) const 431 { 432 __profcxx_map2umap_find(this->_M_map2umap_info, this->size()); 433 std::pair<_Base_const_iterator, _Base_const_iterator> __base_ret 434 = _Base::equal_range(__x); 435 return std::make_pair(const_iterator(__base_ret.first, this), 436 const_iterator(__base_ret.second, this)); 437 } 438 439 _Base& 440 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 441 442 const _Base& 443 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 444 445 private: 446 /** If hint is used we consider that the map and unordered_map 447 * operations have equivalent insertion cost so we do not update metrics 448 * about it. 449 * Note that to find out if hint has been used is libstdc++ 450 * implementation dependent. 451 */ 452 bool 453 _M_hint_used(_Base_const_iterator __hint, _Base_iterator __res) 454 { 455 return (__hint == __res 456 || (__hint == _M_base().end() && ++__res == _M_base().end()) 457 || (__hint != _M_base().end() && (++__hint == __res 458 || ++__res == --__hint))); 459 } 460 461 template<typename _K1, typename _C1, typename _A1> 462 friend bool 463 operator==(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 464 465 template<typename _K1, typename _C1, typename _A1> 466 friend bool 467 operator<(const set<_K1, _C1, _A1>&, const set<_K1, _C1, _A1>&); 468 }; 469 470 template<typename _Key, typename _Compare, typename _Allocator> 471 inline bool 472 operator==(const set<_Key, _Compare, _Allocator>& __lhs, 473 const set<_Key, _Compare, _Allocator>& __rhs) 474 { 475 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 476 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 477 return __lhs._M_base() == __rhs._M_base(); 478 } 479 480 template<typename _Key, typename _Compare, typename _Allocator> 481 inline bool 482 operator<(const set<_Key, _Compare, _Allocator>& __lhs, 483 const set<_Key, _Compare, _Allocator>& __rhs) 484 { 485 __profcxx_map2umap_invalidate(__lhs._M_map2umap_info); 486 __profcxx_map2umap_invalidate(__rhs._M_map2umap_info); 487 return __lhs._M_base() < __rhs._M_base(); 488 } 489 490 template<typename _Key, typename _Compare, typename _Allocator> 491 inline bool 492 operator!=(const set<_Key, _Compare, _Allocator>& __lhs, 493 const set<_Key, _Compare, _Allocator>& __rhs) 494 { return !(__lhs == __rhs); } 495 496 template<typename _Key, typename _Compare, typename _Allocator> 497 inline bool 498 operator<=(const set<_Key, _Compare, _Allocator>& __lhs, 499 const set<_Key, _Compare, _Allocator>& __rhs) 500 { return !(__rhs < __lhs); } 501 502 template<typename _Key, typename _Compare, typename _Allocator> 503 inline bool 504 operator>=(const set<_Key, _Compare, _Allocator>& __lhs, 505 const set<_Key, _Compare, _Allocator>& __rhs) 506 { return !(__lhs < __rhs); } 507 508 template<typename _Key, typename _Compare, typename _Allocator> 509 inline bool 510 operator>(const set<_Key, _Compare, _Allocator>& __lhs, 511 const set<_Key, _Compare, _Allocator>& __rhs) 512 { return __rhs < __lhs; } 513 514 template<typename _Key, typename _Compare, typename _Allocator> 515 void 516 swap(set<_Key, _Compare, _Allocator>& __x, 517 set<_Key, _Compare, _Allocator>& __y) 518 { return __x.swap(__y); } 519 520} // namespace __profile 521} // namespace std 522 523#endif 524