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