libstdc++
|
00001 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2009-2013 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 // 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License along 00021 // with this library; see the file COPYING3. If not see 00022 // <http://www.gnu.org/licenses/>. 00023 00024 /** @file profile/unordered_set 00025 * This file is a GNU profile extension to the Standard C++ Library. 00026 */ 00027 00028 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET 00029 #define _GLIBCXX_PROFILE_UNORDERED_SET 1 00030 00031 #if __cplusplus < 201103L 00032 # include <bits/c++0x_warning.h> 00033 #else 00034 # include <unordered_set> 00035 00036 #include <profile/base.h> 00037 #include <profile/unordered_base.h> 00038 00039 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc> 00040 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00041 00042 namespace std _GLIBCXX_VISIBILITY(default) 00043 { 00044 namespace __profile 00045 { 00046 /** @brief Unordered_set wrapper with performance instrumentation. */ 00047 template<typename _Key, 00048 typename _Hash = std::hash<_Key>, 00049 typename _Pred = std::equal_to<_Key>, 00050 typename _Alloc = std::allocator<_Key> > 00051 class unordered_set 00052 : public _GLIBCXX_STD_BASE, 00053 public _Unordered_profile<unordered_set<_Key, _Hash, _Pred, _Alloc>, 00054 true> 00055 { 00056 typedef _GLIBCXX_STD_BASE _Base; 00057 00058 _Base& 00059 _M_base() noexcept { return *this; } 00060 00061 const _Base& 00062 _M_base() const noexcept { return *this; } 00063 00064 public: 00065 typedef typename _Base::size_type size_type; 00066 typedef typename _Base::hasher hasher; 00067 typedef typename _Base::key_equal key_equal; 00068 typedef typename _Base::allocator_type allocator_type; 00069 typedef typename _Base::key_type key_type; 00070 typedef typename _Base::value_type value_type; 00071 typedef typename _Base::difference_type difference_type; 00072 typedef typename _Base::reference reference; 00073 typedef typename _Base::const_reference const_reference; 00074 00075 typedef typename _Base::iterator iterator; 00076 typedef typename _Base::const_iterator const_iterator; 00077 00078 explicit 00079 unordered_set(size_type __n = 10, 00080 const hasher& __hf = hasher(), 00081 const key_equal& __eql = key_equal(), 00082 const allocator_type& __a = allocator_type()) 00083 : _Base(__n, __hf, __eql, __a) 00084 { } 00085 00086 template<typename _InputIterator> 00087 unordered_set(_InputIterator __f, _InputIterator __l, 00088 size_type __n = 0, 00089 const hasher& __hf = hasher(), 00090 const key_equal& __eql = key_equal(), 00091 const allocator_type& __a = allocator_type()) 00092 : _Base(__f, __l, __n, __hf, __eql, __a) 00093 { } 00094 00095 unordered_set(const unordered_set&) = default; 00096 00097 unordered_set(const _Base& __x) 00098 : _Base(__x) 00099 { } 00100 00101 unordered_set(unordered_set&&) = default; 00102 00103 unordered_set(initializer_list<value_type> __l, 00104 size_type __n = 0, 00105 const hasher& __hf = hasher(), 00106 const key_equal& __eql = key_equal(), 00107 const allocator_type& __a = allocator_type()) 00108 : _Base(__l, __n, __hf, __eql, __a) 00109 { } 00110 00111 unordered_set& 00112 operator=(const unordered_set&) = default; 00113 00114 unordered_set& 00115 operator=(unordered_set&&) = default; 00116 00117 unordered_set& 00118 operator=(initializer_list<value_type> __l) 00119 { 00120 _M_base() = __l; 00121 return *this; 00122 } 00123 00124 void 00125 swap(unordered_set& __x) 00126 { _Base::swap(__x); } 00127 00128 void 00129 clear() noexcept 00130 { 00131 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00132 _Base::size()); 00133 this->_M_profile_destruct(); 00134 _Base::clear(); 00135 } 00136 00137 template<typename... _Args> 00138 std::pair<iterator, bool> 00139 emplace(_Args&&... __args) 00140 { 00141 size_type __old_size = _Base::bucket_count(); 00142 std::pair<iterator, bool> __res 00143 = _Base::emplace(std::forward<_Args>(__args)...); 00144 _M_profile_resize(__old_size); 00145 return __res; 00146 } 00147 00148 template<typename... _Args> 00149 iterator 00150 emplace_hint(const_iterator __it, _Args&&... __args) 00151 { 00152 size_type __old_size = _Base::bucket_count(); 00153 iterator __res 00154 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00155 _M_profile_resize(__old_size); 00156 return __res; 00157 } 00158 00159 void 00160 insert(std::initializer_list<value_type> __l) 00161 { 00162 size_type __old_size = _Base::bucket_count(); 00163 _Base::insert(__l); 00164 _M_profile_resize(__old_size); 00165 } 00166 00167 std::pair<iterator, bool> 00168 insert(const value_type& __obj) 00169 { 00170 size_type __old_size = _Base::bucket_count(); 00171 std::pair<iterator, bool> __res = _Base::insert(__obj); 00172 _M_profile_resize(__old_size); 00173 return __res; 00174 } 00175 00176 iterator 00177 insert(const_iterator __iter, const value_type& __v) 00178 { 00179 size_type __old_size = _Base::bucket_count(); 00180 iterator __res = _Base::insert(__iter, __v); 00181 _M_profile_resize(__old_size); 00182 return __res; 00183 } 00184 00185 std::pair<iterator, bool> 00186 insert(value_type&& __obj) 00187 { 00188 size_type __old_size = _Base::bucket_count(); 00189 std::pair<iterator, bool> __res = _Base::insert(std::move(__obj)); 00190 _M_profile_resize(__old_size); 00191 return __res; 00192 } 00193 00194 iterator 00195 insert(const_iterator __iter, value_type&& __v) 00196 { 00197 size_type __old_size = _Base::bucket_count(); 00198 iterator __res = _Base::insert(__iter, std::move(__v)); 00199 _M_profile_resize(__old_size); 00200 return __res; 00201 } 00202 00203 template<typename _InputIter> 00204 void 00205 insert(_InputIter __first, _InputIter __last) 00206 { 00207 size_type __old_size = _Base::bucket_count(); 00208 _Base::insert(__first, __last); 00209 _M_profile_resize(__old_size); 00210 } 00211 00212 void 00213 rehash(size_type __n) 00214 { 00215 size_type __old_size = _Base::bucket_count(); 00216 _Base::rehash(__n); 00217 _M_profile_resize(__old_size); 00218 } 00219 00220 private: 00221 void 00222 _M_profile_resize(size_type __old_size) 00223 { 00224 size_type __new_size = _Base::bucket_count(); 00225 if (__old_size != __new_size) 00226 __profcxx_hashtable_resize(this, __old_size, __new_size); 00227 } 00228 }; 00229 00230 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00231 inline void 00232 swap(unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00233 unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00234 { __x.swap(__y); } 00235 00236 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00237 inline bool 00238 operator==(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00239 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00240 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00241 00242 template<typename _Key, typename _Hash, typename _Pred, typename _Alloc> 00243 inline bool 00244 operator!=(const unordered_set<_Key, _Hash, _Pred, _Alloc>& __x, 00245 const unordered_set<_Key, _Hash, _Pred, _Alloc>& __y) 00246 { return !(__x == __y); } 00247 00248 #undef _GLIBCXX_BASE 00249 #undef _GLIBCXX_STD_BASE 00250 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE 00251 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc> 00252 00253 /** @brief Unordered_multiset wrapper with performance instrumentation. */ 00254 template<typename _Value, 00255 typename _Hash = std::hash<_Value>, 00256 typename _Pred = std::equal_to<_Value>, 00257 typename _Alloc = std::allocator<_Value> > 00258 class unordered_multiset 00259 : public _GLIBCXX_STD_BASE, 00260 public _Unordered_profile<unordered_multiset<_Value, 00261 _Hash, _Pred, _Alloc>, 00262 false> 00263 { 00264 typedef _GLIBCXX_STD_BASE _Base; 00265 00266 _Base& 00267 _M_base() noexcept { return *this; } 00268 00269 const _Base& 00270 _M_base() const noexcept { return *this; } 00271 00272 public: 00273 typedef typename _Base::size_type size_type; 00274 typedef typename _Base::hasher hasher; 00275 typedef typename _Base::key_equal key_equal; 00276 typedef typename _Base::allocator_type allocator_type; 00277 typedef typename _Base::key_type key_type; 00278 typedef typename _Base::value_type value_type; 00279 typedef typename _Base::difference_type difference_type; 00280 typedef typename _Base::reference reference; 00281 typedef typename _Base::const_reference const_reference; 00282 00283 typedef typename _Base::iterator iterator; 00284 typedef typename _Base::const_iterator const_iterator; 00285 00286 explicit 00287 unordered_multiset(size_type __n = 10, 00288 const hasher& __hf = hasher(), 00289 const key_equal& __eql = key_equal(), 00290 const allocator_type& __a = allocator_type()) 00291 : _Base(__n, __hf, __eql, __a) 00292 { } 00293 00294 template<typename _InputIterator> 00295 unordered_multiset(_InputIterator __f, _InputIterator __l, 00296 size_type __n = 0, 00297 const hasher& __hf = hasher(), 00298 const key_equal& __eql = key_equal(), 00299 const allocator_type& __a = allocator_type()) 00300 : _Base(__f, __l, __n, __hf, __eql, __a) 00301 { } 00302 00303 unordered_multiset(const unordered_multiset&) = default; 00304 00305 unordered_multiset(const _Base& __x) 00306 : _Base(__x) 00307 { } 00308 00309 unordered_multiset(unordered_multiset&&) = default; 00310 00311 unordered_multiset(initializer_list<value_type> __l, 00312 size_type __n = 0, 00313 const hasher& __hf = hasher(), 00314 const key_equal& __eql = key_equal(), 00315 const allocator_type& __a = allocator_type()) 00316 : _Base(__l, __n, __hf, __eql, __a) 00317 { } 00318 00319 unordered_multiset& 00320 operator=(const unordered_multiset&) = default; 00321 00322 unordered_multiset& 00323 operator=(unordered_multiset&&) = default; 00324 00325 unordered_multiset& 00326 operator=(initializer_list<value_type> __l) 00327 { 00328 _M_base() = __l; 00329 return *this; 00330 } 00331 00332 void 00333 swap(unordered_multiset& __x) 00334 { _Base::swap(__x); } 00335 00336 void 00337 clear() noexcept 00338 { 00339 __profcxx_hashtable_destruct(this, _Base::bucket_count(), 00340 _Base::size()); 00341 this->_M_profile_destruct(); 00342 _Base::clear(); 00343 } 00344 00345 template<typename... _Args> 00346 iterator 00347 emplace(_Args&&... __args) 00348 { 00349 size_type __old_size = _Base::bucket_count(); 00350 iterator __res = _Base::emplace(std::forward<_Args>(__args)...); 00351 _M_profile_resize(__old_size); 00352 return __res; 00353 } 00354 00355 template<typename... _Args> 00356 iterator 00357 emplace_hint(const_iterator __it, _Args&&... __args) 00358 { 00359 size_type __old_size = _Base::bucket_count(); 00360 iterator __res 00361 = _Base::emplace_hint(__it, std::forward<_Args>(__args)...); 00362 _M_profile_resize(__old_size); 00363 return __res; 00364 } 00365 00366 void 00367 insert(std::initializer_list<value_type> __l) 00368 { 00369 size_type __old_size = _Base::bucket_count(); 00370 _Base::insert(__l); 00371 _M_profile_resize(__old_size); 00372 } 00373 00374 iterator 00375 insert(const value_type& __obj) 00376 { 00377 size_type __old_size = _Base::bucket_count(); 00378 iterator __res = _Base::insert(__obj); 00379 _M_profile_resize(__old_size); 00380 return __res; 00381 } 00382 00383 iterator 00384 insert(const_iterator __iter, const value_type& __v) 00385 { 00386 size_type __old_size = _Base::bucket_count(); 00387 iterator __res = _Base::insert(__iter, __v); 00388 _M_profile_resize(__old_size); 00389 return __res; 00390 } 00391 00392 iterator 00393 insert(value_type&& __obj) 00394 { 00395 size_type __old_size = _Base::bucket_count(); 00396 iterator __res = _Base::insert(std::move(__obj)); 00397 _M_profile_resize(__old_size); 00398 return __res; 00399 } 00400 00401 iterator 00402 insert(const_iterator __iter, value_type&& __v) 00403 { 00404 size_type __old_size = _Base::bucket_count(); 00405 iterator __res = _Base::insert(__iter, std::move(__v)); 00406 _M_profile_resize(__old_size); 00407 return __res; 00408 } 00409 00410 template<typename _InputIter> 00411 void 00412 insert(_InputIter __first, _InputIter __last) 00413 { 00414 size_type __old_size = _Base::bucket_count(); 00415 _Base::insert(__first, __last); 00416 _M_profile_resize(__old_size); 00417 } 00418 00419 void 00420 rehash(size_type __n) 00421 { 00422 size_type __old_size = _Base::bucket_count(); 00423 _Base::rehash(__n); 00424 _M_profile_resize(__old_size); 00425 } 00426 00427 private: 00428 void 00429 _M_profile_resize(size_type __old_size) 00430 { 00431 size_type __new_size = _Base::bucket_count(); 00432 if (__old_size != __new_size) 00433 __profcxx_hashtable_resize(this, __old_size, __new_size); 00434 } 00435 }; 00436 00437 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00438 inline void 00439 swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00440 unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00441 { __x.swap(__y); } 00442 00443 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00444 inline bool 00445 operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00446 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00447 { return static_cast<const _GLIBCXX_STD_BASE&>(__x) == __y; } 00448 00449 template<typename _Value, typename _Hash, typename _Pred, typename _Alloc> 00450 inline bool 00451 operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x, 00452 const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y) 00453 { return !(__x == __y); } 00454 00455 } // namespace __profile 00456 } // namespace std 00457 00458 #undef _GLIBCXX_BASE 00459 #undef _GLIBCXX_STD_BASE 00460 00461 #endif // C++11 00462 00463 #endif