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