1// Profiling map implementation -*- C++ -*- 2 3// Copyright (C) 2009, 2010 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 2, 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// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/** @file profile/map.h 31 * This file is a GNU profile extension to the Standard C++ Library. 32 */ 33 34#ifndef _GLIBCXX_PROFILE_MAP_H 35#define _GLIBCXX_PROFILE_MAP_H 1 36 37#include <utility> 38#include <profile/base.h> 39 40namespace std 41{ 42namespace __profile 43{ 44 /// Class std::map wrapper with performance instrumentation. 45 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 46 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 47 class map 48 : public _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> 49 { 50 typedef _GLIBCXX_STD_D::map<_Key, _Tp, _Compare, _Allocator> _Base; 51 52 public: 53 // types: 54 typedef _Key key_type; 55 typedef _Tp mapped_type; 56 typedef std::pair<const _Key, _Tp> value_type; 57 typedef _Compare key_compare; 58 typedef _Allocator allocator_type; 59 typedef typename _Base::reference reference; 60 typedef typename _Base::const_reference const_reference; 61 62 typedef typename _Base::iterator iterator; 63 typedef typename _Base::const_iterator const_iterator; 64 typedef typename _Base::size_type size_type; 65 typedef typename _Base::difference_type difference_type; 66 typedef typename _Base::pointer pointer; 67 typedef typename _Base::const_pointer const_pointer; 68 typedef std::reverse_iterator<iterator> reverse_iterator; 69 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 70 71 using _Base::value_compare; 72 73 // 23.3.1.1 construct/copy/destroy: 74 explicit map(const _Compare& __comp = _Compare(), 75 const _Allocator& __a = _Allocator()) 76 : _Base(__comp, __a) { 77 __profcxx_map_to_unordered_map_construct(this); 78 } 79 80 template<typename _InputIterator> 81 map(_InputIterator __first, _InputIterator __last, 82 const _Compare& __comp = _Compare(), 83 const _Allocator& __a = _Allocator()) 84 : _Base(__first, __last, __comp, __a) { 85 __profcxx_map_to_unordered_map_construct(this); 86 } 87 88 map(const map& __x) 89 : _Base(__x) { 90 __profcxx_map_to_unordered_map_construct(this); 91 } 92 93 map(const _Base& __x) 94 : _Base(__x) { 95 __profcxx_map_to_unordered_map_construct(this); 96 } 97 98#ifdef __GXX_EXPERIMENTAL_CXX0X__ 99 map(map&& __x) 100 : _Base(std::forward<map>(__x)) 101 { } 102 103 map(initializer_list<value_type> __l, 104 const _Compare& __c = _Compare(), 105 const allocator_type& __a = allocator_type()) 106 : _Base(__l, __c, __a) { } 107#endif 108 109 ~map() { 110 __profcxx_map_to_unordered_map_destruct(this); 111 } 112 113 map& 114 operator=(const map& __x) 115 { 116 *static_cast<_Base*>(this) = __x; 117 return *this; 118 } 119 120#ifdef __GXX_EXPERIMENTAL_CXX0X__ 121 map& 122 operator=(map&& __x) 123 { 124 // NB: DR 1204. 125 // NB: DR 675. 126 this->clear(); 127 this->swap(__x); 128 return *this; 129 } 130 131 map& 132 operator=(initializer_list<value_type> __l) 133 { 134 this->clear(); 135 this->insert(__l); 136 return *this; 137 } 138#endif 139 140 // _GLIBCXX_RESOLVE_LIB_DEFECTS 141 // 133. map missing get_allocator() 142 using _Base::get_allocator; 143 144 // iterators: 145 iterator 146 begin() 147 { return _Base::begin(); } 148 149 const_iterator 150 begin() const 151 { return _Base::begin(); } 152 153 iterator 154 end() 155 { return _Base::end(); } 156 157 const_iterator 158 end() const 159 { return _Base::end(); } 160 161 reverse_iterator 162 rbegin() 163 { 164 __profcxx_map_to_unordered_map_invalidate(this); 165 return reverse_iterator(end()); 166 } 167 168 const_reverse_iterator 169 rbegin() const 170 { 171 __profcxx_map_to_unordered_map_invalidate(this); 172 return const_reverse_iterator(end()); 173 } 174 175 reverse_iterator 176 rend() 177 { 178 __profcxx_map_to_unordered_map_invalidate(this); 179 return reverse_iterator(begin()); 180 } 181 182 const_reverse_iterator 183 rend() const 184 { 185 __profcxx_map_to_unordered_map_invalidate(this); 186 return const_reverse_iterator(begin()); 187 } 188 189#ifdef __GXX_EXPERIMENTAL_CXX0X__ 190 const_iterator 191 cbegin() const 192 { return const_iterator(_Base::begin()); } 193 194 const_iterator 195 cend() const 196 { return const_iterator(_Base::end()); } 197 198 const_reverse_iterator 199 crbegin() const 200 { 201 __profcxx_map_to_unordered_map_invalidate(this); 202 return const_reverse_iterator(end()); 203 } 204 205 const_reverse_iterator 206 crend() const 207 { 208 __profcxx_map_to_unordered_map_invalidate(this); 209 return const_reverse_iterator(begin()); 210 } 211#endif 212 213 // capacity: 214 using _Base::empty; 215 using _Base::size; 216 using _Base::max_size; 217 218 // 23.3.1.2 element access: 219 mapped_type& 220 operator[](const key_type& __k) 221 { 222 __profcxx_map_to_unordered_map_find(this, size()); 223 return _Base::operator[](__k); 224 } 225 226 mapped_type& 227 at(const key_type& __k) 228 { 229 __profcxx_map_to_unordered_map_find(this, size()); 230 return _Base::at(__k); 231 } 232 233 const mapped_type& 234 at(const key_type& __k) const 235 { 236 __profcxx_map_to_unordered_map_find(this, size()); 237 return _Base::at(__k); 238 } 239 240 // modifiers: 241 std::pair<iterator, bool> 242 insert(const value_type& __x) 243 { 244 __profcxx_map_to_unordered_map_insert(this, size(), 1); 245 typedef typename _Base::iterator _Base_iterator; 246 std::pair<_Base_iterator, bool> __res = _Base::insert(__x); 247 return std::pair<iterator, bool>(iterator(__res.first), 248 __res.second); 249 } 250 251#ifdef __GXX_EXPERIMENTAL_CXX0X__ 252 void 253 insert(std::initializer_list<value_type> __list) 254 { 255 size_type size_before = size(); 256 _Base::insert(__list); 257 __profcxx_map_to_unordered_map_insert(this, size_before, 258 size() - size_before); 259 } 260#endif 261 262 iterator 263 insert(iterator __position, const value_type& __x) 264 { 265 size_type size_before = size(); 266 return iterator(_Base::insert(__position, __x)); 267 __profcxx_map_to_unordered_map_insert(this, size_before, 268 size() - size_before); 269 } 270 271 template<typename _InputIterator> 272 void 273 insert(_InputIterator __first, _InputIterator __last) 274 { 275 size_type size_before = size(); 276 _Base::insert(__first, __last); 277 __profcxx_map_to_unordered_map_insert(this, size_before, 278 size() - size_before); 279 } 280 281#ifdef __GXX_EXPERIMENTAL_CXX0X__ 282 iterator 283 erase(iterator __position) 284 { 285 iterator __i = _Base::erase(__position); 286 __profcxx_map_to_unordered_map_erase(this, size(), 1); 287 return __i; 288 } 289#else 290 void 291 erase(iterator __position) 292 { 293 _Base::erase(__position); 294 __profcxx_map_to_unordered_map_erase(this, size(), 1); 295 } 296#endif 297 298 size_type 299 erase(const key_type& __x) 300 { 301 iterator __victim = find(__x); 302 if (__victim == end()) 303 return 0; 304 else 305 { 306 _Base::erase(__victim); 307 return 1; 308 } 309 } 310 311#ifdef __GXX_EXPERIMENTAL_CXX0X__ 312 iterator 313 erase(iterator __first, iterator __last) 314 { 315 // _GLIBCXX_RESOLVE_LIB_DEFECTS 316 // 151. can't currently clear() empty container 317 while (__first != __last) 318 this->erase(__first++); 319 return __last; 320 } 321#else 322 void 323 erase(iterator __first, iterator __last) 324 { 325 // _GLIBCXX_RESOLVE_LIB_DEFECTS 326 // 151. can't currently clear() empty container 327 while (__first != __last) 328 this->erase(__first++); 329 } 330#endif 331 332 void 333 334 swap(map& __x) 335 { 336 _Base::swap(__x); 337 } 338 339 void 340 clear() 341 { this->erase(begin(), end()); } 342 343 // observers: 344 using _Base::key_comp; 345 using _Base::value_comp; 346 347 // 23.3.1.3 map operations: 348 iterator 349 find(const key_type& __x) 350 { 351 __profcxx_map_to_unordered_map_find(this, size()); 352 return iterator(_Base::find(__x)); 353 } 354 355 const_iterator 356 find(const key_type& __x) const 357 { 358 __profcxx_map_to_unordered_map_find(this, size()); 359 return const_iterator(_Base::find(__x)); 360 } 361 362 size_type 363 count(const key_type& __x) const 364 { 365 __profcxx_map_to_unordered_map_find(this, size()); 366 return _Base::count(__x); 367 } 368 369 iterator 370 lower_bound(const key_type& __x) 371 { 372 __profcxx_map_to_unordered_map_invalidate(this); 373 return iterator(_Base::lower_bound(__x)); 374 } 375 376 const_iterator 377 lower_bound(const key_type& __x) const 378 { 379 __profcxx_map_to_unordered_map_invalidate(this); 380 return const_iterator(_Base::lower_bound(__x)); 381 } 382 383 iterator 384 upper_bound(const key_type& __x) 385 { 386 __profcxx_map_to_unordered_map_invalidate(this); 387 return iterator(_Base::upper_bound(__x)); 388 } 389 390 const_iterator 391 upper_bound(const key_type& __x) const 392 { 393 __profcxx_map_to_unordered_map_invalidate(this); 394 return const_iterator(_Base::upper_bound(__x)); 395 } 396 397 std::pair<iterator,iterator> 398 equal_range(const key_type& __x) 399 { 400 typedef typename _Base::iterator _Base_iterator; 401 std::pair<_Base_iterator, _Base_iterator> __res = 402 _Base::equal_range(__x); 403 return std::make_pair(iterator(__res.first), 404 iterator(__res.second)); 405 } 406 407 std::pair<const_iterator,const_iterator> 408 equal_range(const key_type& __x) const 409 { 410 __profcxx_map_to_unordered_map_find(this, size()); 411 typedef typename _Base::const_iterator _Base_const_iterator; 412 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 413 _Base::equal_range(__x); 414 return std::make_pair(const_iterator(__res.first), 415 const_iterator(__res.second)); 416 } 417 418 _Base& 419 _M_base() { return *this; } 420 421 const _Base& 422 _M_base() const { return *this; } 423 424 }; 425 426 template<typename _Key, typename _Tp, 427 typename _Compare, typename _Allocator> 428 inline bool 429 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 430 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 431 { 432 __profcxx_map_to_unordered_map_invalidate(&__lhs); 433 __profcxx_map_to_unordered_map_invalidate(&__rhs); 434 return __lhs._M_base() == __rhs._M_base(); 435 } 436 437 template<typename _Key, typename _Tp, 438 typename _Compare, typename _Allocator> 439 inline bool 440 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 441 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 442 { 443 __profcxx_map_to_unordered_map_invalidate(&__lhs); 444 __profcxx_map_to_unordered_map_invalidate(&__rhs); 445 return __lhs._M_base() != __rhs._M_base(); 446 } 447 448 template<typename _Key, typename _Tp, 449 typename _Compare, typename _Allocator> 450 inline bool 451 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 452 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 453 { 454 __profcxx_map_to_unordered_map_invalidate(&__lhs); 455 __profcxx_map_to_unordered_map_invalidate(&__rhs); 456 return __lhs._M_base() < __rhs._M_base(); 457 } 458 459 template<typename _Key, typename _Tp, 460 typename _Compare, typename _Allocator> 461 inline bool 462 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 463 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 464 { 465 __profcxx_map_to_unordered_map_invalidate(&__lhs); 466 __profcxx_map_to_unordered_map_invalidate(&__rhs); 467 return __lhs._M_base() <= __rhs._M_base(); 468 } 469 470 template<typename _Key, typename _Tp, 471 typename _Compare, typename _Allocator> 472 inline bool 473 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 474 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 475 { 476 __profcxx_map_to_unordered_map_invalidate(&__lhs); 477 __profcxx_map_to_unordered_map_invalidate(&__rhs); 478 return __lhs._M_base() >= __rhs._M_base(); 479 } 480 481 template<typename _Key, typename _Tp, 482 typename _Compare, typename _Allocator> 483 inline bool 484 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __lhs, 485 const map<_Key, _Tp, _Compare, _Allocator>& __rhs) 486 { 487 __profcxx_map_to_unordered_map_invalidate(&__lhs); 488 __profcxx_map_to_unordered_map_invalidate(&__rhs); 489 return __lhs._M_base() > __rhs._M_base(); 490 } 491 492 template<typename _Key, typename _Tp, 493 typename _Compare, typename _Allocator> 494 inline void 495 swap(map<_Key, _Tp, _Compare, _Allocator>& __lhs, 496 map<_Key, _Tp, _Compare, _Allocator>& __rhs) 497 { __lhs.swap(__rhs); } 498 499} // namespace __profile 500} // namespace std 501 502#endif 503