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