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