]> git.ipfire.org Git - thirdparty/gcc.git/blame - libstdc++-v3/include/profile/unordered_map
projects / thirdparty / gcc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
[multiple changes]
[thirdparty/gcc.git] / libstdc++-v3 / include / profile / unordered_map
CommitLineData
1218d701
SR		 1// Profiling unordered_map/unordered_multimap implementation -*- C++ -*-
2
5004040e 3// Copyright (C) 2009, 2010 Free Software Foundation, Inc.
1218d701
SR		 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/unordered_map
31 * This file is a GNU profile extension to the Standard C++ Library.
32 */
33
34#ifndef _GLIBCXX_PROFILE_UNORDERED_MAP
35#define _GLIBCXX_PROFILE_UNORDERED_MAP 1
36
37#include <profile/base.h>
38
39#ifdef __GXX_EXPERIMENTAL_CXX0X__
40# include <unordered_map>
41#else
42# include <c++0x_warning.h>
43#endif
44
45#include <initializer_list>
46
47#define _GLIBCXX_BASE unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>
48#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
49
50namespace std
51{
52namespace __profile
53{
9ee6a740 54 /// Class std::unordered_map wrapper with performance instrumentation.
1218d701
SR		 55 template<typename _Key, typename _Tp,
56 typename _Hash = std::hash<_Key>,
57 typename _Pred = std::equal_to<_Key>,
58 typename _Alloc = std::allocator<_Key> >
59 class unordered_map
60 : public _GLIBCXX_STD_BASE
61 {
62 typedef typename _GLIBCXX_STD_BASE _Base;
63
64 public:
65 typedef typename _Base::size_type size_type;
66 typedef typename _Base::hasher hasher;
67 typedef typename _Base::key_equal key_equal;
68 typedef typename _Base::allocator_type allocator_type;
69 typedef typename _Base::key_type key_type;
70 typedef typename _Base::value_type value_type;
71 typedef typename _Base::difference_type difference_type;
72 typedef typename _Base::reference reference;
73 typedef typename _Base::const_reference const_reference;
74 typedef typename _Base::mapped_type mapped_type;
1218d701
SR		 75
76 typedef typename _Base::iterator iterator;
77 typedef typename _Base::const_iterator const_iterator;
78
79 explicit
80 unordered_map(size_type __n = 10,
81 const hasher& __hf = hasher(),
82 const key_equal& __eql = key_equal(),
83 const allocator_type& __a = allocator_type())
84 : _Base(__n, __hf, __eql, __a)
85 {
86 __profcxx_hashtable_construct(this, _Base::bucket_count());
87 __profcxx_hashtable_construct2(this);
88 }
89
90 template<typename _InputIterator>
91 unordered_map(_InputIterator __f, _InputIterator __l,
92 size_type __n = 10,
93 const hasher& __hf = hasher(),
94 const key_equal& __eql = key_equal(),
95 const allocator_type& __a = allocator_type())
96 : _Base(__f, __l, __n, __hf, __eql, __a)
97 {
98 __profcxx_hashtable_construct(this, _Base::bucket_count());
99 __profcxx_hashtable_construct2(this);
100 }
101
102 unordered_map(const _Base& __x)
103 : _Base(__x)
104 {
105 __profcxx_hashtable_construct(this, _Base::bucket_count());
106 __profcxx_hashtable_construct2(this);
107 }
108
109 unordered_map(unordered_map&& __x)
110 : _Base(std::forward<_Base>(__x))
111 {
112 __profcxx_hashtable_construct(this, _Base::bucket_count());
113 __profcxx_hashtable_construct2(this);
114 }
115
116 unordered_map(initializer_list<value_type> __l,
117 size_type __n = 10,
118 const hasher& __hf = hasher(),
119 const key_equal& __eql = key_equal(),
120 const allocator_type& __a = allocator_type())
121 : _Base(__l, __n, __hf, __eql, __a) { }
122
123 unordered_map&
124 operator=(const unordered_map& __x)
125 {
126 *static_cast<_Base*>(this) = __x;
127 return *this;
128 }
129
130 unordered_map&
131 operator=(unordered_map&& __x)
132 {
6b592ab3
PC		 133 if (this != &__x)
134 {
135 // NB: DR 675.
136 this->clear();
137 this->swap(__x);
138 }
1218d701
SR		 139 return *this;
140 }
141
142 unordered_map&
143 operator=(initializer_list<value_type> __l)
144 {
145 this->clear();
146 this->insert(__l);
147 return *this;
148 }
149
150 ~unordered_map()
151 {
5004040e
PC		 152 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
153 _Base::size());
1218d701
SR		 154 _M_profile_destruct();
155 }
156
157 _Base&
158 _M_base() { return *this; }
159
160 const _Base&
161 _M_base() const { return *this; }
162
163
164 void
165 clear()
166 {
5004040e
PC		 167 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
168 _Base::size());
1218d701
SR		 169 _M_profile_destruct();
170 _Base::clear();
171 }
172
173 void
174 insert(std::initializer_list<value_type> __l)
175 {
176 size_type __old_size = _Base::bucket_count();
177 _Base::insert(__l);
178 _M_profile_resize(__old_size, _Base::bucket_count());
179 }
180
5004040e 181 std::pair<iterator, bool>
1218d701
SR		 182 insert(const value_type& __obj)
183 {
184 size_type __old_size = _Base::bucket_count();
5004040e 185 std::pair<iterator, bool> __res = _Base::insert(__obj);
1218d701
SR		 186 _M_profile_resize(__old_size, _Base::bucket_count());
187 return __res;
188 }
5004040e 189
1218d701
SR		 190 iterator
191 insert(iterator __iter, const value_type& __v)
192 {
193 size_type __old_size = _Base::bucket_count();
194 iterator res = _Base::insert(__iter, __v);
195 _M_profile_resize(__old_size, _Base::bucket_count());
196 return res;
197 }
198
199 const_iterator
200 insert(const_iterator __iter, const value_type& __v)
201 {
202 size_type __old_size = _Base::bucket_count();
203 const_iterator res =_Base::insert(__iter, __v);
204 _M_profile_resize(__old_size, _Base::bucket_count());
205 return res;
206 }
207
208 template<typename _InputIter>
209 void
210 insert(_InputIter __first, _InputIter __last)
211 {
212 size_type __old_size = _Base::bucket_count();
213 _Base::insert(__first.base(), __last.base());
214 _M_profile_resize(__old_size, _Base::bucket_count());
215 }
216
217 void
218 insert(const value_type* __first, const value_type* __last)
219 {
220 size_type __old_size = _Base::bucket_count();
221 _Base::insert(__first, __last);
222 _M_profile_resize(__old_size, _Base::bucket_count());
223 }
224
225 // operator []
226 mapped_type&
227 operator[](const _Key& _k)
228 {
229 size_type __old_size = _Base::bucket_count();
230 mapped_type& __res = _M_base()[_k];
231 size_type __new_size = _Base::bucket_count();
232 _M_profile_resize(__old_size, _Base::bucket_count());
233 return __res;
234 }
235
236 void
237 swap(unordered_map& __x)
238 {
239 _Base::swap(__x);
240 }
241
242 void rehash(size_type __n)
243 {
244 size_type __old_size = _Base::bucket_count();
245 _Base::rehash(__n);
246 _M_profile_resize(__old_size, _Base::bucket_count());
247 }
248 private:
249 void _M_profile_resize(size_type __old_size, size_type __new_size)
250 {
251 if (__old_size != __new_size)
252 {
253 __profcxx_hashtable_resize(this, __old_size, __new_size);
254 }
255 }
256 void _M_profile_destruct()
257 {
258 size_type __hops = 0, __lc = 0, __chain = 0;
259 for (iterator it = _M_base().begin(); it != _M_base().end(); it++)
260 {
261 while (it._M_cur_node->_M_next) {
262 __chain++;
263 it++;
264 }
265 if (__chain) {
266 __chain++;
267 __lc = __lc > __chain ? __lc : __chain;
268 __hops += __chain * (__chain - 1) / 2;
269 __chain = 0;
270 }
271 }
272 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
273 }
274 };
275 template<typename _Key, typename _Tp, typename _Hash,
276 typename _Pred, typename _Alloc>
277 inline void
278 swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
279 unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
280 { __x.swap(__y); }
281
9ee6a740 282
1218d701
SR		 283#undef _GLIBCXX_BASE
284#undef _GLIBCXX_STD_BASE
285#define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
286#define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
287
9ee6a740 288 /// Class std::unordered_multimap wrapper with performance instrumentation.
1218d701
SR		 289 template<typename _Key, typename _Tp,
290 typename _Hash = std::hash<_Key>,
291 typename _Pred = std::equal_to<_Key>,
292 typename _Alloc = std::allocator<_Key> >
293 class unordered_multimap
294 : public _GLIBCXX_STD_BASE
295 {
296 typedef typename _GLIBCXX_STD_BASE _Base;
297
298 public:
299 typedef typename _Base::size_type size_type;
300 typedef typename _Base::hasher hasher;
301 typedef typename _Base::key_equal key_equal;
302 typedef typename _Base::allocator_type allocator_type;
303 typedef typename _Base::key_type key_type;
304 typedef typename _Base::value_type value_type;
305 typedef typename _Base::difference_type difference_type;
306 typedef typename _Base::reference reference;
307 typedef typename _Base::const_reference const_reference;
1218d701
SR		 308
309 typedef typename _Base::iterator iterator;
310 typedef typename _Base::const_iterator const_iterator;
311
312 explicit
313 unordered_multimap(size_type __n = 10,
314 const hasher& __hf = hasher(),
315 const key_equal& __eql = key_equal(),
316 const allocator_type& __a = allocator_type())
317 : _Base(__n, __hf, __eql, __a)
318 {
319 __profcxx_hashtable_construct(this, _Base::bucket_count());
320 }
321 template<typename _InputIterator>
322 unordered_multimap(_InputIterator __f, _InputIterator __l,
323 size_type __n = 10,
324 const hasher& __hf = hasher(),
325 const key_equal& __eql = key_equal(),
326 const allocator_type& __a = allocator_type())
327 : _Base(__f, __l, __n, __hf, __eql, __a)
328 {
329 __profcxx_hashtable_construct(this, _Base::bucket_count());
330 }
331
332 unordered_multimap(const _Base& __x)
333 : _Base(__x)
334 {
335 __profcxx_hashtable_construct(this, _Base::bucket_count());
336 }
337
338 unordered_multimap(unordered_multimap&& __x)
339 : _Base(std::forward<_Base>(__x))
340 {
341 __profcxx_hashtable_construct(this, _Base::bucket_count());
342 }
343
344 unordered_multimap(initializer_list<value_type> __l,
345 size_type __n = 10,
346 const hasher& __hf = hasher(),
347 const key_equal& __eql = key_equal(),
348 const allocator_type& __a = allocator_type())
349 : _Base(__l, __n, __hf, __eql, __a) { }
350
351 unordered_multimap&
352 operator=(const unordered_multimap& __x)
353 {
354 *static_cast<_Base*>(this) = __x;
355 return *this;
356 }
357
358 unordered_multimap&
359 operator=(unordered_multimap&& __x)
360 {
6b592ab3
PC		 361 if (this != &__x)
362 {
363 // NB: DR 675.
364 this->clear();
365 this->swap(__x);
366 }
1218d701
SR		 367 return *this;
368 }
369
370 unordered_multimap&
371 operator=(initializer_list<value_type> __l)
372 {
373 this->clear();
374 this->insert(__l);
375 return *this;
376 }
377
378 ~unordered_multimap()
379 {
9ee6a740
BK		 380 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
381 _Base::size());
1218d701
SR		 382 _M_profile_destruct();
383 }
384
385 _Base&
386 _M_base() { return *this; }
387
388 const _Base&
389 _M_base() const { return *this; }
390
391
392 void
393 clear()
394 {
9ee6a740
BK		 395 __profcxx_hashtable_destruct(this, _Base::bucket_count(),
396 _Base::size());
1218d701
SR		 397 _M_profile_destruct();
398 _Base::clear();
399 }
400
401 void
402 insert(std::initializer_list<value_type> __l)
403 {
404 size_type __old_size = _Base::bucket_count();
405 _Base::insert(__l);
406 _M_profile_resize(__old_size, _Base::bucket_count());
407 }
408
5004040e 409 iterator
1218d701
SR		 410 insert(const value_type& __obj)
411 {
412 size_type __old_size = _Base::bucket_count();
5004040e 413 iterator __res = _Base::insert(__obj);
1218d701
SR		 414 _M_profile_resize(__old_size, _Base::bucket_count());
415 return __res;
416 }
5004040e 417
1218d701
SR		 418 iterator
419 insert(iterator __iter, const value_type& __v)
420 {
421 size_type __old_size = _Base::bucket_count();
422 iterator res = _Base::insert(__iter, __v);
423 _M_profile_resize(__old_size, _Base::bucket_count());
424 return res;
425 }
426
427 const_iterator
428 insert(const_iterator __iter, const value_type& __v)
429 {
430 size_type __old_size = _Base::bucket_count();
431 const_iterator res =_Base::insert(__iter, __v);
432 _M_profile_resize(__old_size, _Base::bucket_count());
433 return res;
434 }
435
436 template<typename _InputIter>
437 void
438 insert(_InputIter __first, _InputIter __last)
439 {
440 size_type __old_size = _Base::bucket_count();
441 _Base::insert(__first.base(), __last.base());
442 _M_profile_resize(__old_size, _Base::bucket_count());
443 }
444
445 void
446 insert(const value_type* __first, const value_type* __last)
447 {
448 size_type __old_size = _Base::bucket_count();
449 _Base::insert(__first, __last);
450 _M_profile_resize(__old_size, _Base::bucket_count());
451 }
452
453 void
454 swap(unordered_multimap& __x)
455 {
456 _Base::swap(__x);
457 }
458
459 void rehash(size_type __n)
460 {
461 size_type __old_size = _Base::bucket_count();
462 _Base::rehash(__n);
463 _M_profile_resize(__old_size, _Base::bucket_count());
464 }
465 private:
466 void _M_profile_resize(size_type __old_size, size_type __new_size)
467 {
468 if (__old_size != __new_size)
469 {
470 __profcxx_hashtable_resize(this, __old_size, __new_size);
471 }
472 }
473
474 void _M_profile_destruct()
475 {
476 size_type __hops = 0, __lc = 0, __chain = 0;
477 for (iterator it = _M_base().begin(); it != _M_base().end(); it++)
478 {
479 while (it._M_cur_node->_M_next) {
480 __chain++;
481 it++;
482 }
483 if (__chain) {
484 __chain++;
485 __lc = __lc > __chain ? __lc : __chain;
486 __hops += __chain * (__chain - 1) / 2;
487 __chain = 0;
488 }
489 }
490 __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
491 }
492
493 };
494 template<typename _Key, typename _Tp, typename _Hash,
495 typename _Pred, typename _Alloc>
496 inline void
497 swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
498 unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
499 { __x.swap(__y); }
500
501} // namespace __profile
502} // namespace std
503
504#undef _GLIBCXX_BASE
505#undef _GLIBCXX_STD_BASE
506
507#endif
Mirror of https://gcc.gnu.org/git/gcc.git