l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.5/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 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 <bits/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
  50 namespace std
  51 {
  52 namespace __profile
  53 {
  54   /// Class std::unordered_map wrapper with performance instrumentation.
  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;
  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       {
 133         // NB: DR 1204.
 134         // NB: DR 675.
 135         this->clear();
 136         this->swap(__x);
 137         return *this;
 138       }
 139
 140       unordered_map&
 141       operator=(initializer_list<value_type> __l)
 142       {
 143         this->clear();
 144         this->insert(__l);
 145         return *this;
 146       }
 147
 148       ~unordered_map()
 149       {
 150         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 151                                      _Base::size());
 152         _M_profile_destruct();
 153       }
 154
 155       _Base&
 156       _M_base()       { return *this; }
 157
 158       const _Base&
 159       _M_base() const { return *this; }
 160
 161
 162       void
 163       clear()
 164       {
 165         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 166                                      _Base::size());
 167         _M_profile_destruct();
 168         _Base::clear();
 169       }
 170
 171       void
 172       insert(std::initializer_list<value_type> __l)
 173       {
 174         size_type __old_size = _Base::bucket_count();
 175         _Base::insert(__l);
 176         _M_profile_resize(__old_size, _Base::bucket_count());
 177       }
 178
 179       std::pair<iterator, bool>
 180       insert(const value_type& __obj)
 181       {
 182         size_type __old_size =  _Base::bucket_count();
 183         std::pair<iterator, bool> __res = _Base::insert(__obj);
 184         _M_profile_resize(__old_size, _Base::bucket_count());
 185         return __res;
 186       }
 187
 188       iterator
 189       insert(const_iterator __iter, const value_type& __v)
 190       {
 191         size_type __old_size = _Base::bucket_count();
 192         iterator __res = _Base::insert(__iter, __v);
 193         _M_profile_resize(__old_size, _Base::bucket_count());
 194         return __res;
 195       }
 196
 197       template<typename _InputIter>
 198         void
 199         insert(_InputIter __first, _InputIter __last)
 200         {
 201           size_type __old_size = _Base::bucket_count();
 202           _Base::insert(__first.base(), __last.base());
 203           _M_profile_resize(__old_size, _Base::bucket_count());
 204         }
 205
 206       void
 207       insert(const value_type* __first, const value_type* __last)
 208       {
 209         size_type __old_size = _Base::bucket_count();
 210         _Base::insert(__first, __last);
 211         _M_profile_resize(__old_size, _Base::bucket_count());
 212       }
 213
 214       // operator []
 215       mapped_type&
 216       operator[](const _Key& _k)
 217       {
 218         size_type __old_size =  _Base::bucket_count();
 219         mapped_type& __res = _M_base()[_k];
 220         size_type __new_size =  _Base::bucket_count();
 221         _M_profile_resize(__old_size, _Base::bucket_count());
 222         return __res;
 223       }
 224
 225       void
 226       swap(unordered_map& __x)
 227       { _Base::swap(__x); }
 228
 229       void rehash(size_type __n)
 230       {
 231         size_type __old_size =  _Base::bucket_count();
 232         _Base::rehash(__n);
 233         _M_profile_resize(__old_size, _Base::bucket_count());
 234       }
 235
 236     private:
 237       void
 238       _M_profile_resize(size_type __old_size, size_type __new_size)
 239       {
 240         if (__old_size != __new_size)
 241           __profcxx_hashtable_resize(this, __old_size, __new_size);
 242       }
 243
 244       void
 245       _M_profile_destruct()
 246       {
 247         size_type __hops = 0, __lc = 0, __chain = 0;
 248         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 249              ++__it)
 250           {
 251             while (__it._M_cur_node->_M_next)
 252               {
 253                 ++__chain;
 254                 ++__it;
 255               }
 256             if (__chain)
 257               {
 258                 ++__chain;
 259                 __lc = __lc > __chain ? __lc : __chain;
 260                 __hops += __chain * (__chain - 1) / 2;
 261                 __chain = 0;
 262               }
 263           }
 264         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 265       }
 266    };
 267
 268   template<typename _Key, typename _Tp, typename _Hash,
 269            typename _Pred, typename _Alloc>
 270     inline void
 271     swap(unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 272          unordered_map<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 273     { __x.swap(__y); }
 274
 275 #undef _GLIBCXX_BASE
 276 #undef _GLIBCXX_STD_BASE
 277 #define _GLIBCXX_BASE unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>
 278 #define _GLIBCXX_STD_BASE _GLIBCXX_STD_PR::_GLIBCXX_BASE
 279
 280   /// Class std::unordered_multimap wrapper with performance instrumentation.
 281   template<typename _Key, typename _Tp,
 282            typename _Hash  = std::hash<_Key>,
 283            typename _Pred = std::equal_to<_Key>,
 284            typename _Alloc =  std::allocator<_Key> >
 285     class unordered_multimap
 286     : public _GLIBCXX_STD_BASE
 287     {
 288       typedef typename _GLIBCXX_STD_BASE _Base;
 289
 290     public:
 291       typedef typename _Base::size_type       size_type;
 292       typedef typename _Base::hasher          hasher;
 293       typedef typename _Base::key_equal       key_equal;
 294       typedef typename _Base::allocator_type  allocator_type;
 295       typedef typename _Base::key_type        key_type;
 296       typedef typename _Base::value_type      value_type;
 297       typedef typename _Base::difference_type difference_type;
 298       typedef typename _Base::reference       reference;
 299       typedef typename _Base::const_reference const_reference;
 300
 301       typedef typename _Base::iterator iterator;
 302       typedef typename _Base::const_iterator const_iterator;
 303
 304       explicit
 305       unordered_multimap(size_type __n = 10,
 306                     const hasher& __hf = hasher(),
 307                     const key_equal& __eql = key_equal(),
 308                     const allocator_type& __a = allocator_type())
 309       : _Base(__n, __hf, __eql, __a)
 310       {
 311         __profcxx_hashtable_construct(this, _Base::bucket_count());
 312       }
 313       template<typename _InputIterator>
 314         unordered_multimap(_InputIterator __f, _InputIterator __l,
 315               size_type __n = 10,
 316               const hasher& __hf = hasher(),
 317               const key_equal& __eql = key_equal(),
 318               const allocator_type& __a = allocator_type())
 319       : _Base(__f, __l, __n, __hf, __eql, __a)
 320       {
 321         __profcxx_hashtable_construct(this, _Base::bucket_count());
 322       }
 323
 324       unordered_multimap(const _Base& __x)
 325       : _Base(__x)
 326       {
 327         __profcxx_hashtable_construct(this, _Base::bucket_count());
 328       }
 329
 330       unordered_multimap(unordered_multimap&& __x)
 331       : _Base(std::forward<_Base>(__x))
 332       {
 333         __profcxx_hashtable_construct(this, _Base::bucket_count());
 334       }
 335
 336       unordered_multimap(initializer_list<value_type> __l,
 337                          size_type __n = 10,
 338                          const hasher& __hf = hasher(),
 339                          const key_equal& __eql = key_equal(),
 340                          const allocator_type& __a = allocator_type())
 341       : _Base(__l, __n, __hf, __eql, __a) { }
 342
 343       unordered_multimap&
 344       operator=(const unordered_multimap& __x)
 345       {
 346         *static_cast<_Base*>(this) = __x;
 347         return *this;
 348       }
 349
 350       unordered_multimap&
 351       operator=(unordered_multimap&& __x)
 352       {
 353         // NB: DR 1204.
 354         // NB: DR 675.
 355         this->clear();
 356         this->swap(__x);
 357         return *this;
 358       }
 359
 360       unordered_multimap&
 361       operator=(initializer_list<value_type> __l)
 362       {
 363         this->clear();
 364         this->insert(__l);
 365         return *this;
 366       }
 367
 368       ~unordered_multimap()
 369       {
 370         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 371                                      _Base::size());
 372         _M_profile_destruct();
 373       }
 374
 375       _Base&
 376       _M_base()       { return *this; }
 377
 378       const _Base&
 379       _M_base() const { return *this; }
 380
 381
 382       void
 383       clear()
 384       {
 385         __profcxx_hashtable_destruct(this, _Base::bucket_count(),
 386                                      _Base::size());
 387         _M_profile_destruct();
 388         _Base::clear();
 389       }
 390
 391       void
 392       insert(std::initializer_list<value_type> __l)
 393       {
 394         size_type __old_size =  _Base::bucket_count();
 395         _Base::insert(__l);
 396         _M_profile_resize(__old_size, _Base::bucket_count());
 397       }
 398
 399       iterator
 400       insert(const value_type& __obj)
 401       {
 402         size_type __old_size =  _Base::bucket_count();
 403         iterator __res = _Base::insert(__obj);
 404         _M_profile_resize(__old_size, _Base::bucket_count());
 405         return __res;
 406       }
 407
 408       iterator
 409       insert(const_iterator __iter, const value_type& __v)
 410       {
 411         size_type __old_size = _Base::bucket_count();
 412         iterator __res =_Base::insert(__iter, __v);
 413         _M_profile_resize(__old_size, _Base::bucket_count());
 414         return __res;
 415       }
 416
 417       template<typename _InputIter>
 418         void
 419         insert(_InputIter __first, _InputIter __last)
 420         {
 421           size_type __old_size = _Base::bucket_count();
 422           _Base::insert(__first.base(), __last.base());
 423           _M_profile_resize(__old_size, _Base::bucket_count());
 424         }
 425
 426       void
 427       insert(const value_type* __first, const value_type* __last)
 428       {
 429         size_type __old_size = _Base::bucket_count();
 430         _Base::insert(__first, __last);
 431         _M_profile_resize(__old_size, _Base::bucket_count());
 432       }
 433
 434       void
 435       swap(unordered_multimap& __x)
 436       { _Base::swap(__x); }
 437
 438       void rehash(size_type __n)
 439       {
 440         size_type __old_size =  _Base::bucket_count();
 441         _Base::rehash(__n);
 442         _M_profile_resize(__old_size, _Base::bucket_count());
 443       }
 444
 445     private:
 446       void
 447       _M_profile_resize(size_type __old_size, size_type __new_size)
 448       {
 449         if (__old_size != __new_size)
 450           __profcxx_hashtable_resize(this, __old_size, __new_size);
 451       }
 452
 453       void
 454       _M_profile_destruct()
 455       {
 456         size_type __hops = 0, __lc = 0, __chain = 0;
 457         for (iterator __it = _M_base().begin(); __it != _M_base().end();
 458              ++__it)
 459           {
 460             while (__it._M_cur_node->_M_next)
 461               {
 462                 ++__chain;
 463                 ++__it;
 464               }
 465             if (__chain)
 466               {
 467                 ++__chain;
 468                 __lc = __lc > __chain ? __lc : __chain;
 469                 __hops += __chain * (__chain - 1) / 2;
 470                 __chain = 0;
 471               }
 472           }
 473         __profcxx_hashtable_destruct2(this, __lc,  _Base::size(), __hops);
 474       }
 475
 476     };
 477
 478   template<typename _Key, typename _Tp, typename _Hash,
 479            typename _Pred, typename _Alloc>
 480     inline void
 481     swap(unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __x,
 482          unordered_multimap<_Key, _Tp, _Hash, _Pred, _Alloc>& __y)
 483     { __x.swap(__y); }
 484
 485 } // namespace __profile
 486 } // namespace std
 487
 488 #undef _GLIBCXX_BASE
 489 #undef _GLIBCXX_STD_BASE
 490
 491 #endif