boost/intrusive/detail/ihashtable.hpp

   1 /////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 // (C) Copyright Ion Gaztañaga  2006-2007\r
   4 //\r
   5 // Distributed under the Boost Software License, Version 1.0.\r
   6 //    (See accompanying file LICENSE_1_0.txt or copy at\r
   7 //          http://www.boost.org/LICENSE_1_0.txt)\r
   8 //\r
   9 // See http://www.boost.org/libs/intrusive for documentation.\r
  10 //\r
  11 /////////////////////////////////////////////////////////////////////////////\r
  12 #ifndef BOOST_INTRUSIVE_IHASHTABLE_HPP\r
  13 #define BOOST_INTRUSIVE_IHASHTABLE_HPP\r
  14 \r
  15 #include "config_begin.hpp"\r
  16 //std C++\r
  17 #include <functional>\r
  18 #include <iterator>\r
  19 #include <utility>\r
  20 #include <algorithm>\r
  21 //boost\r
  22 #include <boost/utility.hpp>\r
  23 #include <boost/compressed_pair.hpp>\r
  24 #include <boost/assert.hpp>\r
  25 #include <boost/static_assert.hpp>\r
  26 #include <boost/functional/hash.hpp>\r
  27 //General intrusive utilities\r
  28 #include "pointer_type.hpp"\r
  29 #include "pointer_to_other.hpp"\r
  30 #include "../linking_policy.hpp"\r
  31 //Implementation utilities\r
  32 #include "../iunordered_set_hook.hpp"\r
  33 #include "../islist.hpp"\r
  34 #include <cstddef>\r
  35 #include <iterator>\r
  36 \r
  37 namespace boost {\r
  38 namespace intrusive {\r
  39 namespace detail {\r
  40 \r
  41 template<int Dummy = 0>\r
  42 struct prime_list_holder\r
  43 {\r
  44    static const std::size_t prime_list[];\r
  45    static const std::size_t prime_list_size;\r
  46 };\r
  47 \r
  48 template<int Dummy>\r
  49 const std::size_t prime_list_holder<Dummy>::prime_list[] = {\r
  50    53ul, 97ul, 193ul, 389ul, 769ul,\r
  51    1543ul, 3079ul, 6151ul, 12289ul, 24593ul,\r
  52    49157ul, 98317ul, 196613ul, 393241ul, 786433ul,\r
  53    1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,\r
  54    50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,\r
  55    1610612741ul, 3221225473ul, 4294967291ul };\r
  56 \r
  57 template<int Dummy>\r
  58 const std::size_t prime_list_holder<Dummy>::prime_list_size\r
  59    = sizeof(prime_list)/sizeof(std::size_t);\r
  60 \r
  61 //! The class template ihashtable is an intrusive hash table container, that\r
  62 //! is used to construct intrusive unordered_set and unordered_multiset containers. The\r
  63 //! no-throw guarantee holds only, if the Equal object and Hasher don't throw.\r
  64 template< class ValueTraits\r
  65         , class Hash             = boost::hash<typename ValueTraits::value_type>\r
  66         , class Equal            = std::equal_to<typename ValueTraits::value_type>\r
  67         , bool  ConstantTimeSize = true\r
  68         , class SizeType         = std::size_t\r
  69         >\r
  70 class ihashtable\r
  71    :  private detail::size_holder<ConstantTimeSize, SizeType>\r
  72 {\r
  73    private:\r
  74    template<class T, class Self, class NodeTraits>\r
  75    class hashtable_iterator;\r
  76 \r
  77    typedef islist<ValueTraits, false, SizeType> islist_impl;\r
  78 \r
  79    struct bucket_type_impl\r
  80       :  private islist_impl\r
  81    {\r
  82       friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>;\r
  83 \r
  84       bucket_type_impl()\r
  85       {}\r
  86 \r
  87       bucket_type_impl(const bucket_type_impl &)\r
  88       {}\r
  89 \r
  90       bucket_type_impl &operator=(const bucket_type_impl&)\r
  91       {  islist_impl::clear();   }\r
  92    };\r
  93 \r
  94    static islist_impl &islist_from_bucket(bucket_type_impl &b)\r
  95    {  return static_cast<islist_impl&>(b);   }\r
  96 \r
  97    static const islist_impl &islist_from_bucket(const bucket_type_impl &b)\r
  98    {  return static_cast<const islist_impl&>(b);   }\r
  99 \r
 100    typedef ihashtable<ValueTraits, Hash, Equal\r
 101                      ,ConstantTimeSize, SizeType>           this_type; \r
 102    typedef typename ValueTraits::node_traits                node_traits;\r
 103    typedef detail::size_holder<ConstantTimeSize, SizeType>  size_traits;\r
 104 \r
 105    //noncopyable\r
 106    ihashtable (const ihashtable&);\r
 107    ihashtable operator =(const ihashtable&);\r
 108 \r
 109    public:\r
 110    typedef typename ValueTraits::value_type        value_type;\r
 111    typedef typename ValueTraits::pointer           pointer;\r
 112    typedef typename ValueTraits::const_pointer     const_pointer;\r
 113    typedef value_type&                             reference;\r
 114    typedef const value_type&                       const_reference;\r
 115    typedef SizeType                                size_type;\r
 116    typedef typename std::iterator_traits\r
 117       <pointer>::difference_type                   difference_type;\r
 118    typedef value_type                              key_type;\r
 119    typedef Hash                                    hasher;\r
 120    typedef Equal                                   key_equal;\r
 121    typedef bucket_type_impl                        bucket_type;\r
 122    typedef typename boost::pointer_to_other\r
 123       <pointer, bucket_type>::type                 bucket_ptr;\r
 124    typedef typename islist_impl::iterator          local_iterator;\r
 125    typedef typename islist_impl::const_iterator    const_local_iterator;\r
 126 \r
 127    class const_iterator;\r
 128    class iterator;\r
 129 \r
 130    private:\r
 131    typedef typename node_traits::node              node;\r
 132    typedef typename boost::pointer_to_other\r
 133       <pointer, node>::type                        node_ptr;\r
 134    typedef typename boost::pointer_to_other\r
 135       <node_ptr, const node>::type                 const_node_ptr;\r
 136    //typedef hashtable_algorithms<node_traits>       node_algorithms;\r
 137    typedef slist_algorithms<node_traits>           node_algorithms;\r
 138    enum { safemode_or_autounlink  = \r
 139             (int)ValueTraits::linking_policy == (int)auto_unlink   ||\r
 140             (int)ValueTraits::linking_policy == (int)safe_mode_link     };\r
 141 \r
 142    //Constant-time size is incompatible with auto-unlink hooks!\r
 143    BOOST_STATIC_ASSERT(!(ConstantTimeSize && ((int)ValueTraits::linking_policy == (int)auto_unlink)));\r
 144 \r
 145    struct bucket_info_t\r
 146    {\r
 147       bucket_ptr  buckets_;\r
 148       size_type   buckets_len_;\r
 149    } ;\r
 150 \r
 151    typedef typename boost::pointer_to_other\r
 152       <pointer, bucket_info_t>::type               bucket_info_ptr;\r
 153 \r
 154    typedef typename boost::pointer_to_other\r
 155       <pointer, const bucket_info_t>::type         const_bucket_info_ptr;\r
 156 \r
 157    //User scattered boost::compressed pair to get EBO all compilers\r
 158    boost::compressed_pair\r
 159       <boost::compressed_pair<bucket_info_t, Hash>\r
 160       ,Equal> members_;\r
 161 \r
 162    const Equal &priv_equal() const\r
 163    {  return members_.second();  }\r
 164 \r
 165    Equal &priv_equal()\r
 166    {  return members_.second();  }\r
 167 \r
 168    const_bucket_info_ptr priv_bucket_info() const\r
 169    {  return &members_.first().first();  }\r
 170 \r
 171    bucket_info_ptr priv_bucket_info()\r
 172    {  return &members_.first().first();  }\r
 173 \r
 174    const Hash &priv_hasher() const\r
 175    {  return members_.first().second();  }\r
 176 \r
 177    Hash &priv_hasher()\r
 178    {  return members_.first().second();  }\r
 179 \r
 180    const bucket_ptr &priv_buckets() const\r
 181    {  return members_.first().first().buckets_;  }\r
 182 \r
 183    bucket_ptr &priv_buckets()\r
 184    {  return members_.first().first().buckets_;  }\r
 185 \r
 186    const size_type &priv_buckets_len() const\r
 187    {  return members_.first().first().buckets_len_;  }\r
 188 \r
 189    size_type &priv_buckets_len()\r
 190    {  return members_.first().first().buckets_len_;  }\r
 191 \r
 192    static node_ptr uncast(const_node_ptr ptr)\r
 193    {\r
 194       using boost::get_pointer;\r
 195       return node_ptr(const_cast<node*>(get_pointer(ptr)));\r
 196    }\r
 197 \r
 198    static bucket_info_ptr uncast(const_bucket_info_ptr ptr)\r
 199    {\r
 200       using boost::get_pointer;\r
 201       return bucket_info_ptr(const_cast<bucket_info_t*>(get_pointer(ptr)));\r
 202    }\r
 203 \r
 204    template<class T, class Self, class NodeTraits>\r
 205    class hashtable_iterator\r
 206       :  public std::iterator<std::forward_iterator_tag, T>\r
 207    {\r
 208       protected:\r
 209       explicit hashtable_iterator\r
 210          (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
 211          :  local_it_ (ptr),   bucket_info_ (bucket_info),   n_bucket_ (n_bucket)\r
 212       {}\r
 213 \r
 214       public:\r
 215       hashtable_iterator ()\r
 216       {}\r
 217 \r
 218       Self& operator++()\r
 219       {\r
 220          using boost::get_pointer;\r
 221          ++local_it_;\r
 222          size_type   buckets_len = bucket_info_->buckets_len_;\r
 223          bucket_ptr  buckets     = bucket_info_->buckets_;\r
 224                         while (local_it_ == islist_from_bucket(buckets[n_bucket_]).end()){\r
 225                                 if (++n_bucket_ == buckets_len){\r
 226                                         local_it_ = invalid_local_it(*bucket_info_);\r
 227                break;\r
 228             }\r
 229             local_it_ = islist_from_bucket(buckets[n_bucket_]).begin();\r
 230                         }\r
 231          return static_cast<Self&> (*this);\r
 232       }\r
 233 \r
 234       Self operator++(int)\r
 235       {\r
 236          Self result(local_it_, bucket_info_, n_bucket_);\r
 237          ++(*this);\r
 238          return result;\r
 239       }\r
 240 \r
 241       bool operator== (const Self& i) const\r
 242       { return local_it_ == i.local(); }\r
 243 \r
 244       bool operator!= (const Self& i) const\r
 245       { return !operator== (i); }\r
 246 \r
 247       Self &set_internals\r
 248          (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
 249       {\r
 250          local_it_ = ptr;  bucket_info_ = bucket_info;  n_bucket_ = n_bucket;\r
 251          return static_cast<Self&>(*this);\r
 252       }\r
 253 \r
 254       local_iterator local() const\r
 255       { return local_it_; }\r
 256 \r
 257       bucket_info_ptr priv_bucket_info() const\r
 258       { return bucket_info_; }\r
 259 \r
 260       size_type bucket_num() const\r
 261       { return n_bucket_; }\r
 262 \r
 263       private:\r
 264       local_iterator    local_it_;\r
 265       bucket_info_ptr   bucket_info_;\r
 266       size_type         n_bucket_;\r
 267    };\r
 268 \r
 269    public:\r
 270 \r
 271    class iterator\r
 272       :  public hashtable_iterator <value_type, iterator, node_traits>\r
 273     {\r
 274       private:\r
 275       typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type   private_vt;\r
 276       typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::pointer      private_pointer;\r
 277       typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::reference    private_reference;\r
 278       typedef hashtable_iterator<private_vt, iterator, node_traits>   inherited;\r
 279 \r
 280       public:\r
 281       iterator()\r
 282       {}\r
 283 \r
 284       private_pointer operator->() const\r
 285       { return &*this->local(); }\r
 286 \r
 287       private_reference operator*() const\r
 288       { return *this->local(); }\r
 289 \r
 290       private:\r
 291       explicit iterator\r
 292          (local_iterator local_it, bucket_info_ptr bucket_info, size_type n_bucket)\r
 293          :  inherited(local_it, bucket_info, n_bucket)\r
 294       {}\r
 295 \r
 296       friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>; \r
 297       friend class hashtable_iterator<private_vt, iterator, node_traits>;\r
 298       friend class const_iterator;\r
 299    };\r
 300 \r
 301    class const_iterator\r
 302       :  public hashtable_iterator<const value_type, const_iterator, node_traits>\r
 303    {\r
 304       private:\r
 305       typedef const typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::value_type private_vt;\r
 306       typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_pointer    private_pointer;\r
 307       typedef typename ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>::const_reference  private_reference;\r
 308       typedef hashtable_iterator<private_vt, const_iterator, node_traits>   inherited;\r
 309 \r
 310       public:\r
 311       const_iterator()\r
 312       {}\r
 313 \r
 314       const_iterator(const typename ihashtable::iterator& it)\r
 315          :  inherited (it.local(), it.priv_bucket_info(), it.bucket_num())\r
 316       {}\r
 317 \r
 318       const_iterator & operator=(const typename ihashtable::iterator& it)\r
 319       {  return inherited::set_internals(it.local(), it.priv_bucket_info(), it.bucket_num());  }\r
 320 \r
 321       private_pointer operator->() const\r
 322       { return &*this->local(); }\r
 323 \r
 324       private_reference operator*() const\r
 325       { return *this->local(); }\r
 326 \r
 327       private:\r
 328       explicit const_iterator\r
 329          (local_iterator ptr, bucket_info_ptr bucket_info, size_type n_bucket)\r
 330          :  inherited(ptr, bucket_info, n_bucket)\r
 331       {}\r
 332 \r
 333       friend class ihashtable<ValueTraits, Hash, Equal, ConstantTimeSize, SizeType>; \r
 334       friend class hashtable_iterator<private_vt, const_iterator, node_traits>;\r
 335    };\r
 336 \r
 337    //typedef typename node_algorithms::insert_commit_data insert_commit_data;\r
 338    struct insert_commit_data\r
 339    {\r
 340       local_iterator prev_pos;\r
 341       size_type   bucket_num;\r
 342    };\r
 343 \r
 344    ihashtable( bucket_ptr buckets\r
 345              , size_type buckets_len\r
 346              , const Hash & hasher = Hash()\r
 347              , const Equal &equal = Equal()) \r
 348       :  members_(boost::compressed_pair<bucket_info_t, Hash>(hasher)/*hasher*/, equal)\r
 349    {\r
 350       \r
 351       BOOST_ASSERT(buckets_len != 0);\r
 352       priv_buckets()       = buckets;\r
 353       priv_buckets_len()   = buckets_len;\r
 354       priv_clear_buckets();\r
 355       size_traits::set_size(size_type(0));\r
 356    }\r
 357 \r
 358    ~ihashtable() \r
 359    {  this->clear(); }\r
 360 \r
 361    iterator begin()\r
 362    {\r
 363       size_type bucket_num;\r
 364       local_iterator local_it = priv_begin(bucket_num);\r
 365       return iterator( local_it\r
 366                      , this->priv_bucket_info()\r
 367                      , bucket_num);\r
 368    }\r
 369 \r
 370    const_iterator begin() const\r
 371    {\r
 372       size_type bucket_num;\r
 373       local_iterator local_it = priv_begin(bucket_num);\r
 374       return const_iterator( local_it\r
 375                            , uncast(this->priv_bucket_info())\r
 376                            , bucket_num);\r
 377    }\r
 378 \r
 379    iterator end()\r
 380    {\r
 381       using boost::get_pointer;\r
 382       bucket_info_t *info = get_pointer(this->priv_bucket_info());\r
 383       return iterator(invalid_local_it(*info), 0, info->buckets_len_);\r
 384    }\r
 385 \r
 386    const_iterator end() const\r
 387    {\r
 388       using boost::get_pointer;\r
 389       const bucket_info_t *info = get_pointer(this->priv_bucket_info());\r
 390       return const_iterator(invalid_local_it(*info), 0, info->buckets_len_);\r
 391    }\r
 392 \r
 393    hasher hash_function() const\r
 394    {  return this->priv_hasher();  }\r
 395 \r
 396    key_equal key_eq() const\r
 397    {  return this->priv_equal();   }\r
 398 \r
 399    bool empty() const\r
 400    {\r
 401       if(ConstantTimeSize){\r
 402          return !size();\r
 403       }\r
 404       else{\r
 405          using boost::get_pointer;\r
 406          size_type buckets_len = this->priv_buckets_len();\r
 407          const bucket_type *b = get_pointer(this->priv_buckets());\r
 408          for (size_type n = 0; n < buckets_len; ++n, ++b){\r
 409             if(!b->empty()){\r
 410                return false;\r
 411             }\r
 412          }\r
 413          return true;\r
 414       }\r
 415    }\r
 416 \r
 417    size_type size() const\r
 418    {\r
 419       if(ConstantTimeSize)\r
 420          return size_traits::get_size();\r
 421       else{\r
 422          size_type len = 0;\r
 423          using boost::get_pointer;\r
 424          size_type buckets_len = this->priv_buckets_len();\r
 425          const bucket_type *b = get_pointer(this->priv_buckets());\r
 426          for (size_type n = 0; n < buckets_len; ++n, ++b){\r
 427             len += b->size();\r
 428          }\r
 429          return len;\r
 430       }\r
 431    }\r
 432 \r
 433    void swap(ihashtable& other)\r
 434    {\r
 435       using std::swap;\r
 436       //These can throw\r
 437       swap(this->priv_equal(), other.priv_equal());\r
 438       swap(this->priv_hasher(), other.priv_hasher());\r
 439       //These can't throw\r
 440       swap(this->priv_buckets(), other.priv_buckets());\r
 441       swap(this->priv_buckets_len(), other.priv_buckets_len());\r
 442       if(ConstantTimeSize){\r
 443          size_type backup = size_traits::get_size();\r
 444          size_traits::set_size(other.get_size());\r
 445          other.set_size(backup);\r
 446       }\r
 447    }\r
 448 \r
 449    template <class Cloner, class Destroyer>\r
 450    void clone_from(const ihashtable &src, Cloner cloner, Destroyer destroyer)\r
 451    {\r
 452       this->clear_and_destroy(destroyer);\r
 453       if(!ConstantTimeSize || !src.empty()){\r
 454          const size_type src_bucket_count = src.bucket_count();\r
 455          const size_type dst_bucket_count = this->bucket_count();\r
 456 \r
 457          //If src bucket count is bigger or equal, structural copy is possible\r
 458          if(src_bucket_count >= dst_bucket_count){\r
 459             //First clone the first ones\r
 460             const bucket_ptr src_buckets = src.priv_buckets();\r
 461             const bucket_ptr dst_buckets = this->priv_buckets();\r
 462             size_type constructed;\r
 463             try{\r
 464                for( constructed = 0\r
 465                   ; constructed < dst_bucket_count\r
 466                   ; ++constructed){\r
 467                   dst_buckets[constructed].clone_and_reverse_from(src_buckets[constructed], cloner, destroyer);\r
 468                }\r
 469                if(src_bucket_count != dst_bucket_count){\r
 470                   //Now insert the remaining ones using the modulo trick\r
 471                   for(//"constructed" comes from the previous loop\r
 472                      ; constructed < src_bucket_count\r
 473                      ; ++constructed){\r
 474                      bucket_type &dst_b = dst_buckets[constructed % dst_bucket_count];\r
 475                      bucket_type &src_b = src_buckets[constructed];\r
 476                      for( local_iterator b(src_b.begin()), e(src_b.end())\r
 477                         ; b != e\r
 478                         ; ++b){\r
 479                         dst_b.push_front(*cloner(*b));\r
 480                      }\r
 481                   }\r
 482                }\r
 483             }\r
 484             catch(...){\r
 485                while(constructed--){\r
 486                   dst_buckets[constructed].clear_and_destroy(destroyer);\r
 487                }\r
 488                throw;\r
 489             }\r
 490             size_traits::set_size(src.get_size());\r
 491          }\r
 492          else{\r
 493             //Unlike previous cloning algorithm, this can throw\r
 494             //if cloner, the hasher or comparison functor throw\r
 495             const_iterator b(src.begin()), e(src.end());\r
 496             try{\r
 497                for(; b != e; ++b){\r
 498                   this->insert_equal(*cloner(*b));\r
 499                }\r
 500             }\r
 501             catch(...){\r
 502                this->clear_and_destroy(destroyer);\r
 503                throw;\r
 504             }\r
 505          }\r
 506       }\r
 507    }\r
 508 \r
 509    iterator insert_equal(value_type &value)\r
 510    {\r
 511       size_type bucket_num;\r
 512       local_iterator it = priv_find(value, this->priv_hasher(), this->priv_equal(), bucket_num);\r
 513       bucket_type &b = this->priv_buckets()[bucket_num];\r
 514       if(it == invalid_local_it(*this->priv_bucket_info())){\r
 515          it = b.before_begin();\r
 516       }\r
 517       size_traits::increment();\r
 518       return iterator(b.insert_after(it, value), this->priv_bucket_info(), bucket_num);\r
 519    }\r
 520 \r
 521    template<class Iterator>\r
 522    void insert_equal(Iterator b, Iterator e)\r
 523    {\r
 524       for (; b != e; ++b)\r
 525          this->insert_equal(*b);\r
 526    }\r
 527 \r
 528    std::pair<iterator, bool> insert_unique(value_type &value)\r
 529    {\r
 530       insert_commit_data commit_data;\r
 531       std::pair<iterator, bool> ret = insert_unique_check(value, commit_data);\r
 532       if(!ret.second)\r
 533          return ret;\r
 534       return std::pair<iterator, bool> (insert_unique_commit(value, commit_data), true);\r
 535    }\r
 536 \r
 537    template<class Iterator>\r
 538    void insert_unique(Iterator b, Iterator e)\r
 539    {\r
 540       for (; b != e; ++b)\r
 541          this->insert_unique(*b);\r
 542    }\r
 543 \r
 544    std::pair<iterator, bool> insert_unique_check\r
 545       (const value_type &value, insert_commit_data &commit_data)\r
 546    {  return insert_unique_check(value, this->priv_hasher(), this->priv_equal(), commit_data); }\r
 547 \r
 548    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 549    std::pair<iterator, bool> insert_unique_check\r
 550       ( const KeyType &key\r
 551       , KeyHasher hasher\r
 552       , KeyValueEqual key_value_eq\r
 553       , insert_commit_data &commit_data)\r
 554    {\r
 555       commit_data.prev_pos = \r
 556          priv_find(key, hasher, key_value_eq, commit_data.bucket_num);\r
 557       bool success = commit_data.prev_pos == invalid_local_it(*this->priv_bucket_info());\r
 558       if(success){\r
 559          commit_data.prev_pos = this->priv_buckets()[commit_data.bucket_num].before_begin();\r
 560       }\r
 561       return std::pair<iterator, bool>\r
 562          (iterator(commit_data.prev_pos, this->priv_bucket_info(), commit_data.bucket_num)\r
 563          ,success);\r
 564    }\r
 565 \r
 566    iterator insert_unique_commit(value_type &value, const insert_commit_data &commit_data)\r
 567    {\r
 568       bucket_type &b = this->priv_buckets()[commit_data.bucket_num];\r
 569       size_traits::increment();\r
 570       return iterator( b.insert_after(commit_data.prev_pos, value)\r
 571                      , this->priv_bucket_info()\r
 572                      , commit_data.bucket_num);\r
 573    }\r
 574 \r
 575    void erase(const_iterator i)\r
 576    {  erase_and_destroy(i, detail::null_destroyer());  }\r
 577 \r
 578    void erase(const_iterator b, const_iterator e)\r
 579    {  erase_and_destroy(b, e, detail::null_destroyer());  }\r
 580 \r
 581    size_type erase(const value_type &value)\r
 582    {  return this->erase(value, this->priv_hasher(), this->priv_equal());  }\r
 583 \r
 584    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 585    size_type erase(const KeyType& key, KeyHasher hasher, KeyValueEqual equal)\r
 586    {  return erase_and_destroy(key, hasher, equal, detail::null_destroyer()); }\r
 587 \r
 588    template<class Destroyer>\r
 589    void erase_and_destroy(const_iterator i, Destroyer destroyer)\r
 590    {\r
 591       local_iterator to_erase(i.local());\r
 592       size_type n_bucket = i.bucket_num();\r
 593       bucket_type &b = this->priv_buckets()[n_bucket];\r
 594       b.erase_after_and_destroy(b.previous(to_erase), destroyer);\r
 595       size_traits::decrement();\r
 596    }\r
 597 \r
 598    template<class Destroyer>\r
 599    void erase_and_destroy(const_iterator b, const_iterator e, Destroyer destroyer)\r
 600    {\r
 601       if(b == e)  return;\r
 602 \r
 603       //Get the bucket number and local iterator for both iterators\r
 604       size_type first_bucket_num\r
 605          = b.bucket_num();\r
 606       local_iterator before_first_local_it\r
 607          = priv_buckets()[first_bucket_num].previous(b.local());\r
 608       size_type last_bucket_num;\r
 609       local_iterator last_local_it;\r
 610 \r
 611       //For the end iterator, we will assign the end iterator\r
 612       //of the last bucket\r
 613       if(e == end()){\r
 614          last_bucket_num   = this->bucket_count() - 1;\r
 615          last_local_it     = priv_buckets()[last_bucket_num].end();\r
 616       }\r
 617       else{\r
 618          last_bucket_num   = e.bucket_num();\r
 619          last_local_it     = e.local();\r
 620       }\r
 621 \r
 622       const bucket_ptr buckets = priv_buckets();\r
 623       //First erase the nodes of the first bucket\r
 624       {\r
 625          bucket_type &first_b = buckets[first_bucket_num];\r
 626          local_iterator nxt(before_first_local_it); ++nxt;\r
 627          local_iterator end = first_b.end();\r
 628          while(nxt != end){\r
 629             nxt = first_b.erase_after_and_destroy(before_first_local_it, destroyer);\r
 630             size_traits::decrement();\r
 631          }\r
 632       }\r
 633 \r
 634       //Now fully clear the intermediate buckets\r
 635       for(size_type i = first_bucket_num+1; i < last_bucket_num; ++i){\r
 636          bucket_type &b = buckets[i];\r
 637          if(b.empty())\r
 638             continue;\r
 639          local_iterator b_begin(b.before_begin());\r
 640          local_iterator nxt(b_begin); ++nxt;\r
 641          local_iterator end = b.end();\r
 642          while(nxt != end){\r
 643             nxt = b.erase_after_and_destroy(b_begin, destroyer);\r
 644             size_traits::decrement();\r
 645          }\r
 646       }\r
 647 \r
 648       //Now erase nodes from the last bucket\r
 649       {\r
 650          bucket_type &last_b = buckets[last_bucket_num];\r
 651          local_iterator b_begin(last_b.before_begin());\r
 652          local_iterator nxt(b_begin); ++nxt;\r
 653          while(nxt != last_local_it){\r
 654             nxt = last_b.erase_after_and_destroy(b_begin, destroyer);\r
 655             size_traits::decrement();\r
 656          }\r
 657       }\r
 658    }\r
 659 \r
 660    template<class Destroyer>\r
 661    size_type erase_and_destroy(const value_type &value, Destroyer destroyer)\r
 662    {  return erase_and_destroy(value, priv_hasher(), priv_equal(), destroyer);   }\r
 663 \r
 664    template<class KeyType, class KeyHasher, class KeyValueEqual, class Destroyer>\r
 665    size_type erase_and_destroy(const KeyType& key, KeyHasher hasher\r
 666                   ,KeyValueEqual equal, Destroyer destroyer)\r
 667    {\r
 668       size_type count(0);\r
 669 \r
 670       if(ConstantTimeSize && this->empty()){\r
 671          return 0;\r
 672       }\r
 673 \r
 674       bucket_type &b = this->priv_buckets()[hasher(key) % this->priv_buckets_len()];\r
 675       local_iterator it    = b.begin();\r
 676       local_iterator prev  = b.before_begin();\r
 677 \r
 678       bool found = false;\r
 679       //Find equal value\r
 680       while(it != b.end()){\r
 681          if(equal(key, *it)){\r
 682             found = true;\r
 683             break;\r
 684          }\r
 685          ++prev;\r
 686          ++it;\r
 687       }\r
 688    \r
 689       if(!found)\r
 690          return 0;\r
 691 \r
 692       //If found erase all equal values\r
 693       for(local_iterator end = b.end(); it != end && equal(key, *it); ++count){\r
 694          it = b.erase_after_and_destroy(prev, destroyer);\r
 695          size_traits::decrement();\r
 696       }\r
 697       return count;\r
 698    }\r
 699 \r
 700    void clear()\r
 701    {\r
 702       if(safemode_or_autounlink){\r
 703          priv_clear_buckets();\r
 704       }\r
 705       size_traits::set_size(size_type(0));\r
 706    }\r
 707 \r
 708    template<class Destroyer>\r
 709    void clear_and_destroy(Destroyer destroyer)\r
 710    {\r
 711       if(!ConstantTimeSize || !this->empty()){\r
 712          size_type num_buckets = this->bucket_count();\r
 713          bucket_ptr b = this->priv_buckets();\r
 714          for(; num_buckets--; ++b){\r
 715             b->clear_and_destroy(destroyer);\r
 716          }\r
 717          size_traits::set_size(size_type(0));\r
 718       }\r
 719    }\r
 720 \r
 721    size_type count(const value_type &value) const\r
 722    {  return this->count(value, this->priv_hasher(), this->priv_equal());  }\r
 723 \r
 724    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 725    size_type count(const KeyType &key, const KeyHasher &hasher, const KeyValueEqual &equal) const\r
 726    {\r
 727       size_type bucket_n1, bucket_n2, count;\r
 728       priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
 729       return count;\r
 730    }\r
 731 \r
 732    iterator find(const value_type &value)\r
 733    {  return find(value, this->priv_hasher(), this->priv_equal());   }\r
 734 \r
 735    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 736    iterator find(const KeyType &key, KeyHasher hasher, KeyValueEqual equal)\r
 737    {\r
 738       size_type bucket_n;\r
 739       local_iterator local_it = priv_find(key, hasher, equal, bucket_n);\r
 740       return iterator( local_it\r
 741                       , this->priv_bucket_info()\r
 742                       , bucket_n);\r
 743    }\r
 744 \r
 745    const_iterator find(const value_type &value) const\r
 746    {  return find(value, this->priv_hasher(), this->priv_equal());   }\r
 747 \r
 748    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 749    const_iterator find\r
 750       (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const\r
 751    {\r
 752       size_type bucket_n;\r
 753       local_iterator local_it = priv_find(key, hasher, equal, bucket_n);\r
 754       return const_iterator( local_it\r
 755                            , uncast(this->priv_bucket_info())\r
 756                            , bucket_n);\r
 757    }\r
 758 \r
 759    std::pair<iterator,iterator> equal_range(const value_type &value)\r
 760    {  return this->equal_range(value, this->priv_hasher(), this->priv_equal());  }\r
 761 \r
 762    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 763    std::pair<iterator,iterator> equal_range\r
 764       (const KeyType &key, KeyHasher hasher, KeyValueEqual equal)\r
 765    {\r
 766       size_type bucket_n1, bucket_n2, count;\r
 767       std::pair<local_iterator, local_iterator> ret\r
 768          = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
 769       return std::pair<iterator, iterator>\r
 770          (  iterator( ret.first, this->priv_bucket_info(), bucket_n1)\r
 771          ,  iterator( ret.second, this->priv_bucket_info(), bucket_n2) );\r
 772    }\r
 773 \r
 774    std::pair<const_iterator, const_iterator>\r
 775       equal_range(const value_type &value) const\r
 776    {  return this->equal_range(value, this->priv_hasher(), this->priv_equal());  }\r
 777 \r
 778    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 779    std::pair<const_iterator,const_iterator> equal_range\r
 780       (const KeyType &key, KeyHasher hasher, KeyValueEqual equal) const\r
 781    {\r
 782       size_type bucket_n1, bucket_n2, count;\r
 783       std::pair<local_iterator, local_iterator> ret\r
 784          = priv_equal_range(key, hasher, equal, bucket_n1, bucket_n2, count);\r
 785       return std::pair<const_iterator, const_iterator>\r
 786          (  const_iterator( ret.first, uncast(this->priv_bucket_info()), bucket_n1)\r
 787          ,  const_iterator( ret.second, uncast(this->priv_bucket_info()), bucket_n2)  );\r
 788    }\r
 789 \r
 790    size_type bucket_count() const\r
 791    {  return this->priv_buckets_len();   }\r
 792 \r
 793    size_type bucket_size(size_type n)\r
 794    {  return this->priv_buckets()[n].size();   }\r
 795 \r
 796    size_type bucket(const key_type& k)\r
 797    {  return this->bucket(k, this->priv_hasher());   }\r
 798 \r
 799    template<class KeyType, class KeyHasher>\r
 800    size_type bucket(const KeyType& k, const KeyHasher &hasher)\r
 801    {  return hasher(k) % this->priv_buckets_len();   }\r
 802 \r
 803    bucket_ptr bucket_pointer() const\r
 804    {  return this->priv_buckets();   }\r
 805 \r
 806    local_iterator begin(size_type n)\r
 807    {  return this->priv_buckets()[n].begin();  }\r
 808 \r
 809    const_local_iterator begin(size_type n) const\r
 810    {  return const_cast<const bucket_type&>(this->priv_buckets()[n]).begin();  }\r
 811 \r
 812    local_iterator end(size_type n)\r
 813    {  return this->priv_buckets()[n].end();  }\r
 814 \r
 815    const_local_iterator end(size_type n) const\r
 816    {  return const_cast<const bucket_type&>(this->priv_buckets()[n]).end();  }\r
 817 \r
 818    void rehash(bucket_ptr new_buckets, size_type new_buckets_len)\r
 819    {\r
 820       bucket_ptr old_buckets     = this->priv_buckets();\r
 821       size_type  old_buckets_len = this->priv_buckets_len();\r
 822 \r
 823       try{\r
 824          size_type n = 0;\r
 825          bool same_buffer = old_buckets == new_buckets;\r
 826          //If we are shrinking the bucket array, just rehash the last nodes\r
 827          if(same_buffer && (old_buckets_len > new_buckets_len)){\r
 828             n = new_buckets_len;\r
 829          }\r
 830 \r
 831          //Iterate through nodes\r
 832          for(; n < old_buckets_len; ++n){\r
 833             bucket_type &old_bucket = old_buckets[n];\r
 834             local_iterator before_i(old_bucket.before_begin());\r
 835             local_iterator end(old_bucket.end());\r
 836             local_iterator i(old_bucket.begin());\r
 837             for(;i != end; ++i){\r
 838                size_type new_n = this->priv_hasher()(*i) % new_buckets_len;\r
 839                //If this is a buffer expansion don't move if it's not necessary\r
 840                if(same_buffer && new_n == n){\r
 841                   ++before_i;\r
 842                }\r
 843                else{\r
 844                   bucket_type &new_b = new_buckets[new_n];\r
 845                   new_b.splice_after(new_b.before_begin(), old_bucket, before_i);\r
 846                   i = before_i;\r
 847                }\r
 848             }\r
 849          }\r
 850 \r
 851          this->priv_buckets()      = new_buckets;\r
 852          this->priv_buckets_len()  = new_buckets_len;\r
 853       }\r
 854       catch(...){\r
 855          for(size_type n = 0; n < new_buckets_len; ++n){\r
 856             new_buckets[n].clear();\r
 857             old_buckets[n].clear();\r
 858          }\r
 859          size_traits::set_size(size_type(0));\r
 860          throw;\r
 861       }\r
 862    }\r
 863 \r
 864    iterator current(value_type &value)\r
 865    {\r
 866       return iterator( bucket_type::current(value)\r
 867                      , this->priv_bucket_info()\r
 868                      , this->priv_hasher()(value) % this->priv_buckets_len());\r
 869    }\r
 870 \r
 871    const_iterator current(const value_type &value) const\r
 872    {\r
 873       return const_iterator( bucket_type::current(const_cast<value_type&>(value))\r
 874                      , uncast(this->priv_bucket_info())\r
 875                      , this->priv_hasher()(value) % this->priv_buckets_len());\r
 876    }\r
 877 \r
 878    static local_iterator current_local(value_type &value)\r
 879    {  return bucket_type::current(value);  }\r
 880 \r
 881    static const_local_iterator current_local(const value_type &value)\r
 882    {  return bucket_type::current(value);  }\r
 883 \r
 884    // no throw\r
 885    static size_type suggested_upper_bucket_count(size_type n)\r
 886    {\r
 887       const std::size_t *primes     = &prime_list_holder<0>::prime_list[0];\r
 888       const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;\r
 889       size_type const* bound =\r
 890             std::lower_bound(primes, primes_end, n);\r
 891       if(bound == primes_end)\r
 892             bound--;\r
 893       return size_type(*bound);\r
 894    }\r
 895 \r
 896    // no throw\r
 897    static size_type suggested_lower_bucket_count(size_type n)\r
 898    {\r
 899       const std::size_t *primes     = &prime_list_holder<0>::prime_list[0];\r
 900       const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size;\r
 901       size_type const* bound =\r
 902             std::upper_bound(primes, primes_end, n);\r
 903       if(bound != primes_end)\r
 904             bound--;\r
 905       return size_type(*bound);\r
 906    }\r
 907 \r
 908    private:\r
 909 \r
 910    static local_iterator invalid_local_it(const bucket_info_t &b)\r
 911    {  return b.buckets_->end();  }\r
 912 \r
 913    local_iterator priv_begin(size_type &bucket_num) const\r
 914    {\r
 915       size_type buckets_len = this->priv_buckets_len();\r
 916       for (bucket_num = 0; bucket_num < buckets_len; ++bucket_num){\r
 917          bucket_type &b = this->priv_buckets()[bucket_num];\r
 918          if(!b.empty())\r
 919             return b.begin();\r
 920       }\r
 921       return invalid_local_it(*this->priv_bucket_info());\r
 922    }\r
 923 \r
 924    void priv_clear_buckets()\r
 925    {  priv_clear_buckets(this->priv_buckets(), this->priv_buckets_len());  }\r
 926 \r
 927    static void priv_clear_buckets(bucket_ptr buckets_ptr, size_type buckets_len)\r
 928    {\r
 929       for(; buckets_len--; ++buckets_ptr){\r
 930          buckets_ptr->clear();\r
 931       }\r
 932    }\r
 933 \r
 934    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 935    local_iterator priv_find\r
 936       ( const KeyType &key,  KeyHasher hasher\r
 937       , KeyValueEqual equal, size_type &bucket_number) const\r
 938    {\r
 939       size_type b_len(this->priv_buckets_len());\r
 940       bucket_number = hasher(key) % b_len;\r
 941 \r
 942       if(ConstantTimeSize && this->empty()){\r
 943          return invalid_local_it(*this->priv_bucket_info());\r
 944       }\r
 945       \r
 946       bucket_type &b = this->priv_buckets()[bucket_number];\r
 947       local_iterator it = b.begin();\r
 948 \r
 949       while(it != b.end()){\r
 950          if(equal(key, *it)){\r
 951             return it;\r
 952          }\r
 953          ++it;\r
 954       }\r
 955 \r
 956       return invalid_local_it(*this->priv_bucket_info());\r
 957    }\r
 958 \r
 959    template<class KeyType, class KeyHasher, class KeyValueEqual>\r
 960    std::pair<local_iterator, local_iterator> priv_equal_range\r
 961       ( const KeyType &key\r
 962       , KeyHasher hasher\r
 963       , KeyValueEqual equal\r
 964       , size_type &bucket_number_first\r
 965       , size_type &bucket_number_second\r
 966       , size_type &count) const\r
 967    {\r
 968       count = 0;\r
 969       //Let's see if the element is present\r
 970       std::pair<local_iterator, local_iterator> to_return\r
 971          ( priv_find(key, hasher, equal, bucket_number_first)\r
 972          , invalid_local_it(*this->priv_bucket_info()));\r
 973       if(to_return.first == to_return.second){\r
 974          bucket_number_second = bucket_number_first;\r
 975          return to_return;\r
 976       }\r
 977       ++count;\r
 978       //If it's present, find the first that it's not equal in\r
 979       //the same bucket\r
 980       bucket_type &b = this->priv_buckets()[bucket_number_first];\r
 981       local_iterator it = to_return.first;\r
 982       ++it;\r
 983 \r
 984       while(it != b.end()){\r
 985          if(!equal(key, *it)){\r
 986             to_return.second = it;\r
 987             bucket_number_second = bucket_number_first;\r
 988             return to_return;\r
 989          }\r
 990          ++it;\r
 991          ++count;\r
 992       }\r
 993    \r
 994       //If we reached the end, find the first, non-empty bucket\r
 995       for(bucket_number_second = bucket_number_first+1\r
 996          ; bucket_number_second != this->priv_buckets_len()\r
 997          ; ++bucket_number_second){\r
 998          bucket_type &b = this->priv_buckets()[bucket_number_second];\r
 999          if(!b.empty()){\r
1000             to_return.second = b.begin();\r
1001             return to_return;\r
1002          }\r
1003       }\r
1004 \r
1005       //Otherwise, return the end node\r
1006       to_return.second = invalid_local_it(*this->priv_bucket_info());\r
1007       return to_return;\r
1008    }\r
1009 };\r
1010 \r
1011 } //namespace detail\r
1012 } //namespace intrusive \r
1013 } //namespace boost \r
1014 \r
1015 #include "config_end.hpp"\r
1016 \r
1017 #endif //BOOST_INTRUSIVE_IHASHTABLE_HPP\r