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