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