l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.6/include/profile/unordered_map

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