contrib/gcc-4.7/libstdc++-v3/include/profile/unordered_set

   1 // Profiling unordered_set/unordered_multiset implementation -*- C++ -*-
   2
   3 // Copyright (C) 2009, 2010, 2011 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/unordered_set
  25  *  This file is a GNU profile extension to the Standard C++ Library.
  26  */
  27
  28 #ifndef _GLIBCXX_PROFILE_UNORDERED_SET
  29 #define _GLIBCXX_PROFILE_UNORDERED_SET 1
  30
  31 #ifndef __GXX_EXPERIMENTAL_CXX0X__
  32 # include <bits/c++0x_warning.h>
  33 #else
  34 # include <unordered_set>
  35
  36 #include <profile/base.h>
  37
  38 #define _GLIBCXX_BASE unordered_set<_Key, _Hash, _Pred, _Alloc>
  39 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
  40
  41 namespace std _GLIBCXX_VISIBILITY(default)
  42 {
  43 namespace __profile
  44 {
  45   /** @brief Unordered_set wrapper with performance instrumentation.  */
  46   template<typename _Key,
  47            typename _Hash  = std::hash<_Key>,
  48            typename _Pred = std::equal_to<_Key>,
  49            typename _Alloc =  std::allocator<_Key> >
  50     class unordered_set
  51     : public _GLIBCXX_STD_BASE
  52     {
  53       typedef typename _GLIBCXX_STD_BASE _Base;
  54
  55     public:
  56       typedef typename _Base::size_type       size_type;
  57       typedef typename _Base::hasher          hasher;
  58       typedef typename _Base::key_equal       key_equal;
  59       typedef typename _Base::allocator_type  allocator_type;
  60       typedef typename _Base::key_type        key_type;
  61       typedef typename _Base::value_type      value_type;
  62       typedef typename _Base::difference_type difference_type;
  63       typedef typename _Base::reference       reference;
  64       typedef typename _Base::const_reference const_reference;
  65
  66       typedef typename _Base::iterator iterator;
  67       typedef typename _Base::const_iterator const_iterator;
  68
  69       explicit
  70       unordered_set(size_type __n = 10,
  71                     const hasher& __hf = hasher(),
  72                     const key_equal& __eql = key_equal(),
  73                     const allocator_type& __a = allocator_type())
  74       : _Base(__n, __hf, __eql, __a)
  75       {
  76         __profcxx_hashtable_construct(this, _Base::bucket_count());
  77         __profcxx_hashtable_construct2(this);
  78       }
  79
  80       template<typename _InputIterator>
  81         unordered_set(_InputIterator __f, _InputIterator __l,
  82                       size_type __n = 0,
  83                       const hasher& __hf = hasher(),
  84                       const key_equal& __eql = key_equal(),
  85                       const allocator_type& __a = allocator_type())
  86       : _Base(__f, __l, __n, __hf, __eql, __a)
  87       {
  88         __profcxx_hashtable_construct(this, _Base::bucket_count());
  89         __profcxx_hashtable_construct2(this);
  90       }
  91
  92       unordered_set(const unordered_set& __x)
  93       : _Base(__x)
  94       {
  95         __profcxx_hashtable_construct(this, _Base::bucket_count());
  96         __profcxx_hashtable_construct2(this);
  97       }
  98
  99       unordered_set(const _Base& __x)
 100       : _Base(__x)
 101       {
 102         __profcxx_hashtable_construct(this, _Base::bucket_count());
 103         __profcxx_hashtable_construct2(this);
 104       }
 105
 106       unordered_set(unordered_set&& __x)
 107       : _Base(std::move(__x))
 108       {
 109         __profcxx_hashtable_construct(this, _Base::bucket_count());
 110         __profcxx_hashtable_construct2(this);
 111       }
 112
 113       unordered_set(initializer_list<value_type> __l,
 114                     size_type __n = 0,
 115                     const hasher& __hf = hasher(),
 116                     const key_equal& __eql = key_equal(),
 117                     const allocator_type& __a = allocator_type())
 118       : _Base(__l, __n, __hf, __eql, __a) { }
 119
 120       unordered_set&
 121       operator=(const unordered_set& __x)
 122       {
 123         *static_cast<_Base*>(this) = __x;
 124         return *this;
 125       }
 126
 127       unordered_set&
 128       operator=(unordered_set&& __x)
 129       {
 130         // NB: DR 1204.
 131         // NB: DR 675.
 132         this->clear();
 133         this->swap(__x);
 134         return *this;
 135       }
 136
 137       unordered_set&
 138       operator=(initializer_list<value_type> __l)
 139       {
 140         this->clear();
 141         this->insert(__l);
 142         return *this;
 143       }
 144
 145       ~unordered_set() noexcept
 146       {
 147         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 148                                      _Base::size());
 149         _M_profile_destruct();
 150       }
 151
 152       void
 153       swap(unordered_set& __x)
 154       {
 155         _Base::swap(__x);
 156       }
 157
 158       void
 159       clear() noexcept
 160       {
 161         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 162                                      _Base::size());
 163         _M_profile_destruct();
 164         _Base::clear();
 165       }
 166
 167       template<typename... _Args>
 168         std::pair<iterator, bool>
 169         emplace(_Args&&... __args)
 170         {
 171           size_type __old_size = _Base::bucket_count();
 172           std::pair<iterator, bool> __res
 173             = _Base::emplace(std::forward<_Args>(__args)...);
 174           _M_profile_resize(__old_size);
 175           return __res;
 176         }
 177
 178       template<typename... _Args>
 179         iterator
 180         emplace_hint(const_iterator __it, _Args&&... __args)
 181         {
 182           size_type __old_size = _Base::bucket_count();
 183           iterator __res
 184             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
 185           _M_profile_resize(__old_size);
 186           return __res;
 187         }
 188
 189       void
 190       insert(std::initializer_list<value_type> __l)
 191       {
 192         size_type __old_size = _Base::bucket_count();
 193         _Base::insert(__l);
 194         _M_profile_resize(__old_size);
 195       }
 196
 197       std::pair<iterator, bool>
 198       insert(const value_type& __obj)
 199       {
 200         size_type __old_size = _Base::bucket_count();
 201         std::pair<iterator, bool> __res = _Base::insert(__obj);
 202         _M_profile_resize(__old_size);
 203         return __res;
 204       }
 205
 206       iterator
 207       insert(const_iterator __iter, const value_type& __v)
 208       {
 209         size_type __old_size = _Base::bucket_count();
 210         iterator __res = _Base::insert(__iter, __v);
 211         _M_profile_resize(__old_size);
 212         return __res;
 213       }
 214
 215       std::pair<iterator, bool>
 216       insert(value_type&& __obj)
 217       {
 218         size_type __old_size = _Base::bucket_count();
 219         std::pair<iterator, bool> __res = _Base::insert(std::move(__obj));
 220         _M_profile_resize(__old_size);
 221         return __res;
 222       }
 223
 224       iterator
 225       insert(const_iterator __iter, value_type&& __v)
 226       {
 227         size_type __old_size = _Base::bucket_count();
 228         iterator __res = _Base::insert(__iter, std::move(__v));
 229         _M_profile_resize(__old_size);
 230         return __res;
 231       }
 232
 233       template<typename _InputIter>
 234         void
 235         insert(_InputIter __first, _InputIter __last)
 236         {
 237           size_type __old_size = _Base::bucket_count();
 238           _Base::insert(__first, __last);
 239           _M_profile_resize(__old_size);
 240         }
 241
 242       void
 243       insert(const value_type* __first, const value_type* __last)
 244       {
 245         size_type __old_size = _Base::bucket_count();
 246         _Base::insert(__first, __last);
 247         _M_profile_resize(__old_size);
 248       }
 249
 250       void rehash(size_type __n)
 251       {
 252         size_type __old_size = _Base::bucket_count();
 253         _Base::rehash(__n);
 254         _M_profile_resize(__old_size);
 255       }
 256
 257     private:
 258       void
 259       _M_profile_resize(size_type __old_size)
 260       {
 261         size_type __new_size = _Base::bucket_count();
 262         if (__old_size != __new_size)
 263           __profcxx_hashtable_resize(this, __old_size, __new_size);
 264       }
 265
 266       void
 267       _M_profile_destruct()
 268       {
 269         size_type __hops = 0, __lc = 0, __chain = 0;
 270         iterator __it = this->begin();
 271         while (__it != this->end())
 272           {
 273             size_type __bkt = this->bucket(*__it);
 274             auto __lit = this->begin(__bkt);
 275             auto __lend = this->end(__bkt);
 276             for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 277               ++__chain;
 278             if (__chain)
 279               {
 280                 ++__chain;
 281                 __lc = __lc > __chain ? __lc : __chain;
 282                 __hops += __chain * (__chain - 1) / 2;
 283                 __chain = 0;
 284               }
 285           }
 286         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
 287       }
 288   };
 289
 290   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 291     inline void
 292     swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 293          unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 294     { __x.swap(__y); }
 295
 296   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 297     inline bool
 298     operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 299                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 300     { return __x._M_equal(__y); }
 301
 302   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 303     inline bool
 304     operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
 305                const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
 306     { return !(__x == __y); }
 307
 308 #undef _GLIBCXX_BASE
 309 #undef _GLIBCXX_STD_BASE
 310 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_C::_GLIBCXX_BASE
 311 #define _GLIBCXX_BASE unordered_multiset<_Value, _Hash, _Pred, _Alloc>
 312
 313   /** @brief Unordered_multiset wrapper with performance instrumentation.  */
 314   template<typename _Value,
 315        typename _Hash  = std::hash<_Value>,
 316        typename _Pred = std::equal_to<_Value>,
 317        typename _Alloc =  std::allocator<_Value> >
 318     class unordered_multiset
 319     : public _GLIBCXX_STD_BASE
 320     {
 321       typedef typename _GLIBCXX_STD_BASE _Base;
 322
 323     public:
 324       typedef typename _Base::size_type       size_type;
 325       typedef typename _Base::hasher          hasher;
 326       typedef typename _Base::key_equal       key_equal;
 327       typedef typename _Base::allocator_type  allocator_type;
 328       typedef typename _Base::key_type        key_type;
 329       typedef typename _Base::value_type      value_type;
 330       typedef typename _Base::difference_type difference_type;
 331       typedef typename _Base::reference       reference;
 332       typedef typename _Base::const_reference const_reference;
 333
 334       typedef typename _Base::iterator iterator;
 335       typedef typename _Base::const_iterator const_iterator;
 336
 337       explicit
 338       unordered_multiset(size_type __n = 10,
 339                          const hasher& __hf = hasher(),
 340                          const key_equal& __eql = key_equal(),
 341                          const allocator_type& __a = allocator_type())
 342       : _Base(__n, __hf, __eql, __a)
 343       {
 344         __profcxx_hashtable_construct(this, _Base::bucket_count());
 345       }
 346
 347       template<typename _InputIterator>
 348         unordered_multiset(_InputIterator __f, _InputIterator __l,
 349                            size_type __n = 0,
 350                            const hasher& __hf = hasher(),
 351                            const key_equal& __eql = key_equal(),
 352                            const allocator_type& __a = allocator_type())
 353       : _Base(__f, __l, __n, __hf, __eql, __a)
 354       {
 355         __profcxx_hashtable_construct(this, _Base::bucket_count());
 356       }
 357
 358       unordered_multiset(const unordered_multiset& __x)
 359       : _Base(__x)
 360       {
 361         __profcxx_hashtable_construct(this, _Base::bucket_count());
 362       }
 363
 364       unordered_multiset(const _Base& __x)
 365       : _Base(__x)
 366       {
 367         __profcxx_hashtable_construct(this, _Base::bucket_count());
 368       }
 369
 370       unordered_multiset(unordered_multiset&& __x)
 371       : _Base(std::move(__x))
 372       {
 373         __profcxx_hashtable_construct(this, _Base::bucket_count());
 374       }
 375
 376       unordered_multiset(initializer_list<value_type> __l,
 377                          size_type __n = 0,
 378                          const hasher& __hf = hasher(),
 379                          const key_equal& __eql = key_equal(),
 380                          const allocator_type& __a = allocator_type())
 381       : _Base(__l, __n, __hf, __eql, __a) { }
 382
 383       unordered_multiset&
 384       operator=(const unordered_multiset& __x)
 385       {
 386         *static_cast<_Base*>(this) = __x;
 387         return *this;
 388       }
 389
 390       unordered_multiset&
 391       operator=(unordered_multiset&& __x)
 392       {
 393         // NB: DR 1204.
 394         // NB: DR 675.
 395         this->clear();
 396         this->swap(__x);
 397         return *this;
 398       }
 399
 400       unordered_multiset&
 401       operator=(initializer_list<value_type> __l)
 402       {
 403         this->clear();
 404         this->insert(__l);
 405         return *this;
 406       }
 407
 408       ~unordered_multiset() noexcept
 409       {
 410         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 411                                      _Base::size());
 412         _M_profile_destruct();
 413       }
 414
 415       void
 416       swap(unordered_multiset& __x)
 417       {
 418         _Base::swap(__x);
 419       }
 420
 421       void
 422       clear() noexcept
 423       {
 424         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 425                                      _Base::size());
 426         _M_profile_destruct();
 427         _Base::clear();
 428       }
 429
 430       template<typename... _Args>
 431         iterator
 432         emplace(_Args&&... __args)
 433         {
 434           size_type __old_size = _Base::bucket_count();
 435           iterator __res = _Base::emplace(std::forward<_Args>(__args)...);
 436           _M_profile_resize(__old_size);
 437           return __res;
 438         }
 439
 440       template<typename... _Args>
 441         iterator
 442         emplace_hint(const_iterator __it, _Args&&... __args)
 443         {
 444           size_type __old_size = _Base::bucket_count();
 445           iterator __res
 446             = _Base::emplace_hint(__it, std::forward<_Args>(__args)...);
 447           _M_profile_resize(__old_size);
 448           return __res;
 449         }
 450
 451       void
 452       insert(std::initializer_list<value_type> __l)
 453       {
 454         size_type __old_size = _Base::bucket_count();
 455         _Base::insert(__l);
 456         _M_profile_resize(__old_size);
 457       }
 458
 459       iterator
 460       insert(const value_type& __obj)
 461       {
 462         size_type __old_size = _Base::bucket_count();
 463         iterator __res = _Base::insert(__obj);
 464         _M_profile_resize(__old_size);
 465         return __res;
 466       }
 467
 468       iterator
 469       insert(const_iterator __iter, const value_type& __v)
 470       {
 471         size_type __old_size = _Base::bucket_count();
 472         iterator __res = _Base::insert(__iter, __v);
 473         _M_profile_resize(__old_size);
 474         return __res;
 475       }
 476
 477       iterator
 478       insert(value_type&& __obj)
 479       {
 480         size_type __old_size = _Base::bucket_count();
 481         iterator __res = _Base::insert(std::move(__obj));
 482         _M_profile_resize(__old_size);
 483         return __res;
 484       }
 485
 486       iterator
 487       insert(const_iterator __iter, value_type&& __v)
 488       {
 489         size_type __old_size = _Base::bucket_count();
 490         iterator __res = _Base::insert(__iter, std::move(__v));
 491         _M_profile_resize(__old_size);
 492         return __res;
 493       }
 494
 495       template<typename _InputIter>
 496         void
 497         insert(_InputIter __first, _InputIter __last)
 498         {
 499           size_type __old_size = _Base::bucket_count();
 500           _Base::insert(__first, __last);
 501           _M_profile_resize(__old_size);
 502         }
 503
 504       void
 505       insert(const value_type* __first, const value_type* __last)
 506       {
 507         size_type __old_size = _Base::bucket_count();
 508         _Base::insert(__first, __last);
 509         _M_profile_resize(__old_size);
 510       }
 511
 512       void rehash(size_type __n)
 513       {
 514         size_type __old_size = _Base::bucket_count();
 515         _Base::rehash(__n);
 516         _M_profile_resize(__old_size);
 517       }
 518
 519     private:
 520       void
 521       _M_profile_resize(size_type __old_size)
 522       {
 523         size_type __new_size = _Base::bucket_count();
 524         if (__old_size != __new_size)
 525           __profcxx_hashtable_resize(this, __old_size, __new_size);
 526       }
 527
 528       void
 529       _M_profile_destruct()
 530       {
 531         size_type __hops = 0, __lc = 0, __chain = 0;
 532         iterator __it = this->begin();
 533         while (__it != this->end())
 534           {
 535             size_type __bkt = this->bucket(*__it);
 536             auto __lit = this->begin(__bkt);
 537             auto __lend = this->end(__bkt);
 538             for (++__it, ++__lit; __lit != __lend; ++__it, ++__lit)
 539               ++__chain;
 540             if (__chain)
 541               {
 542                 ++__chain;
 543                 __lc = __lc > __chain ? __lc : __chain;
 544                 __hops += __chain * (__chain - 1) / 2;
 545                 __chain = 0;
 546               }
 547           }
 548         __profcxx_hashtable_destruct2(this, __lc, _Base::size(), __hops);
 549       }
 550    };
 551
 552   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 553     inline void
 554     swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 555          unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 556     { __x.swap(__y); }
 557
 558   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 559     inline bool
 560     operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 561                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 562     { return __x._M_equal(__y); }
 563
 564   template<typename _Value, typename _Hash, typename _Pred, typename _Alloc>
 565     inline bool
 566     operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
 567                const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
 568     { return !(__x == __y); }
 569
 570 } // namespace __profile
 571 } // namespace std
 572
 573 #undef _GLIBCXX_BASE
 574 #undef _GLIBCXX_STD_BASE
 575
 576 #endif // __GXX_EXPERIMENTAL_CXX0X__
 577
 578 #endif