src/INTERP_KERNEL/Bases/InterpKernelHashTable.hxx

   1 // Copyright (C) 2001-2013  CEA/DEN, EDF R&D
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 // This library is distributed in the hope that it will be useful,
  21 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  22 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23 // GNU General Public License for more details.
  24
  25 // Under Section 7 of GPL version 3, you are granted additional
  26 // permissions described in the GCC Runtime Library Exception, version
  27 // 3.1, as published by the Free Software Foundation.
  28
  29 // You should have received a copy of the GNU General Public License and
  30 // a copy of the GCC Runtime Library Exception along with this program;
  31 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  32 // <http://www.gnu.org/licenses/>.
  33
  34 /*
  35  * Copyright (c) 1996,1997
  36  * Silicon Graphics Computer Systems, Inc.
  37  *
  38  * Permission to use, copy, modify, distribute and sell this software
  39  * and its documentation for any purpose is hereby granted without fee,
  40  * provided that the above copyright notice appear in all copies and
  41  * that both that copyright notice and this permission notice appear
  42  * in supporting documentation.  Silicon Graphics makes no
  43  * representations about the suitability of this software for any
  44  * purpose.  It is provided "as is" without express or implied warranty.
  45  *
  46  *
  47  * Copyright (c) 1994
  48  * Hewlett-Packard Company
  49  *
  50  * Permission to use, copy, modify, distribute and sell this software
  51  * and its documentation for any purpose is hereby granted without fee,
  52  * provided that the above copyright notice appear in all copies and
  53  * that both that copyright notice and this permission notice appear
  54  * in supporting documentation.  Hewlett-Packard Company makes no
  55  * representations about the suitability of this software for any
  56  * purpose.  It is provided "as is" without express or implied warranty.
  57  *
  58  */
  59 #ifndef __INTERPKERNELHASHTABLE_HXX__
  60 #define __INTERPKERNELHASHTABLE_HXX__
  61
  62 #include "InterpKernelStlExt.hxx"
  63 #include "InterpKernelHashFun.hxx"
  64
  65 #include <vector>
  66 #include <iterator>
  67 #include <algorithm>
  68 #include <functional>
  69
  70 namespace INTERP_KERNEL
  71 {
  72   template<class _Val>
  73   struct _Hashtable_node
  74   {
  75     _Hashtable_node* _M_next;
  76     _Val _M_val;
  77   };
  78
  79   template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
  80            class _EqualKey, class _Alloc = std::allocator<_Val> >
  81   class hashtable;
  82
  83   template<class _Val, class _Key, class _HashFcn,
  84            class _ExtractKey, class _EqualKey, class _Alloc>
  85   struct _Hashtable_iterator;
  86
  87   template<class _Val, class _Key, class _HashFcn,
  88            class _ExtractKey, class _EqualKey, class _Alloc>
  89   struct _Hashtable_const_iterator;
  90
  91   template<class _Val, class _Key, class _HashFcn,
  92            class _ExtractKey, class _EqualKey, class _Alloc>
  93   struct _Hashtable_iterator
  94   {
  95     typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
  96     _Hashtable;
  97     typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
  98                                 _ExtractKey, _EqualKey, _Alloc>
  99     iterator;
 100     typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 101                                       _ExtractKey, _EqualKey, _Alloc>
 102     const_iterator;
 103     typedef _Hashtable_node<_Val> _Node;
 104     typedef std::forward_iterator_tag iterator_category;
 105     typedef _Val value_type;
 106     typedef std::ptrdiff_t difference_type;
 107     typedef std::size_t size_type;
 108     typedef _Val& reference;
 109     typedef _Val* pointer;
 110
 111     _Node* _M_cur;
 112     _Hashtable* _M_ht;
 113
 114     _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
 115       : _M_cur(__n), _M_ht(__tab) { }
 116
 117     _Hashtable_iterator() { }
 118
 119     reference
 120     operator*() const
 121     { return _M_cur->_M_val; }
 122
 123     pointer
 124     operator->() const
 125     { return &(operator*()); }
 126
 127     iterator&
 128     operator++();
 129
 130     iterator
 131     operator++(int);
 132
 133     bool
 134     operator==(const iterator& __it) const
 135     { return _M_cur == __it._M_cur; }
 136
 137     bool
 138     operator!=(const iterator& __it) const
 139     { return _M_cur != __it._M_cur; }
 140   };
 141
 142   template<class _Val, class _Key, class _HashFcn,
 143            class _ExtractKey, class _EqualKey, class _Alloc>
 144   struct _Hashtable_const_iterator
 145   {
 146     typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
 147     _Hashtable;
 148     typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
 149                                 _ExtractKey,_EqualKey,_Alloc>
 150     iterator;
 151     typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 152                                       _ExtractKey, _EqualKey, _Alloc>
 153     const_iterator;
 154     typedef _Hashtable_node<_Val> _Node;
 155
 156     typedef std::forward_iterator_tag iterator_category;
 157     typedef _Val value_type;
 158     typedef std::ptrdiff_t difference_type;
 159     typedef std::size_t size_type;
 160     typedef const _Val& reference;
 161     typedef const _Val* pointer;
 162
 163     const _Node* _M_cur;
 164     const _Hashtable* _M_ht;
 165
 166     _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
 167       : _M_cur(__n), _M_ht(__tab) { }
 168
 169     _Hashtable_const_iterator() { }
 170
 171     _Hashtable_const_iterator(const iterator& __it)
 172       : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
 173
 174     reference  operator*() const { return _M_cur->_M_val; }
 175
 176     pointer operator->() const { return &(operator*()); }
 177
 178     const_iterator& operator++();
 179
 180     const_iterator operator++(int);
 181
 182     bool operator==(const const_iterator& __it) const { return _M_cur == __it._M_cur; }
 183
 184     bool operator!=(const const_iterator& __it) const { return _M_cur != __it._M_cur; }
 185   };
 186
 187   // Note: assumes long is at least 32 bits.
 188   enum { _S_num_primes = 28 };
 189
 190   static const unsigned long __stl_prime_list[_S_num_primes] =
 191     {
 192       53ul,         97ul,         193ul,       389ul,       769ul,
 193       1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
 194       49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
 195       1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
 196       50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
 197       1610612741ul, 3221225473ul, 4294967291ul
 198     };
 199
 200   inline unsigned long
 201   __stl_next_prime(unsigned long __n)
 202   {
 203     const unsigned long* __first = __stl_prime_list;
 204     const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
 205     const unsigned long* pos = std::lower_bound(__first, __last, __n);
 206     return pos == __last ? *(__last - 1) : *pos;
 207   }
 208
 209   // Forward declaration of operator==.
 210   template<class _Val, class _Key, class _HF, class _Ex,
 211            class _Eq, class _All>
 212   class hashtable;
 213
 214   template<class _Val, class _Key, class _HF, class _Ex,
 215            class _Eq, class _All>
 216   bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
 217                   const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
 218
 219   // Hashtables handle allocators a bit differently than other
 220   // containers do.  If we're using standard-conforming allocators, then
 221   // a hashtable unconditionally has a member variable to hold its
 222   // allocator, even if it so happens that all instances of the
 223   // allocator type are identical.  This is because, for hashtables,
 224   // this extra storage is negligible.  Additionally, a base class
 225   // wouldn't serve any other purposes; it wouldn't, for example,
 226   // simplify the exception-handling code.
 227   template<class _Val, class _Key, class _HashFcn,
 228            class _ExtractKey, class _EqualKey, class _Alloc>
 229   class hashtable
 230   {
 231   public:
 232     typedef _Key key_type;
 233     typedef _Val value_type;
 234     typedef _HashFcn hasher;
 235     typedef _EqualKey key_equal;
 236
 237     typedef std::size_t            size_type;
 238     typedef std::ptrdiff_t         difference_type;
 239     typedef value_type*       pointer;
 240     typedef const value_type* const_pointer;
 241     typedef value_type&       reference;
 242     typedef const value_type& const_reference;
 243
 244     hasher hash_funct() const { return _M_hash; }
 245
 246     key_equal key_eq() const { return _M_equals; }
 247
 248   private:
 249     typedef _Hashtable_node<_Val> _Node;
 250
 251   public:
 252     typedef typename _Alloc::template rebind<value_type>::other allocator_type;
 253     allocator_type get_allocator() const { return _M_node_allocator; }
 254
 255   private:
 256     typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
 257     typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
 258     typedef std::vector<_Node*, _Nodeptr_Alloc> _Vector_type;
 259
 260     _Node_Alloc _M_node_allocator;
 261
 262     _Node *_M_get_node() { return _M_node_allocator.allocate(1); }
 263
 264     void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
 265
 266   private:
 267     hasher                _M_hash;
 268     key_equal             _M_equals;
 269     _ExtractKey           _M_get_key;
 270     _Vector_type          _M_buckets;
 271     size_type             _M_num_elements;
 272
 273   public:
 274     typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 275                                 _EqualKey, _Alloc>
 276     iterator;
 277     typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 278                                       _EqualKey, _Alloc>
 279     const_iterator;
 280
 281     friend struct
 282     _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
 283
 284     friend struct
 285     _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
 286                               _EqualKey, _Alloc>;
 287
 288   public:
 289     hashtable(size_type __n, const _HashFcn& __hf,
 290               const _EqualKey& __eql, const _ExtractKey& __ext,
 291               const allocator_type& __a = allocator_type())
 292       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
 293         _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
 294     { _M_initialize_buckets(__n); }
 295
 296     hashtable(size_type __n, const _HashFcn& __hf,
 297               const _EqualKey& __eql,
 298               const allocator_type& __a = allocator_type())
 299       : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
 300         _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
 301     { _M_initialize_buckets(__n); }
 302
 303     hashtable(const hashtable& __ht)
 304       : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
 305         _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
 306         _M_buckets(__ht.get_allocator()), _M_num_elements(0)
 307     { _M_copy_from(__ht); }
 308
 309     hashtable& operator= (const hashtable& __ht)
 310     {
 311       if (&__ht != this)
 312         {
 313           clear();
 314           _M_hash = __ht._M_hash;
 315           _M_equals = __ht._M_equals;
 316           _M_get_key = __ht._M_get_key;
 317           _M_copy_from(__ht);
 318         }
 319       return *this;
 320     }
 321
 322     ~hashtable()
 323     { clear(); }
 324
 325     size_type size() const { return _M_num_elements; }
 326
 327     size_type max_size() const { return size_type(-1); }
 328
 329     bool empty() const { return size() == 0; }
 330
 331     void swap(hashtable& __ht)
 332     {
 333       std::swap(_M_hash, __ht._M_hash);
 334       std::swap(_M_equals, __ht._M_equals);
 335       std::swap(_M_get_key, __ht._M_get_key);
 336       _M_buckets.swap(__ht._M_buckets);
 337       std::swap(_M_num_elements, __ht._M_num_elements);
 338     }
 339
 340     iterator begin()
 341     {
 342       for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 343         if (_M_buckets[__n])
 344           return iterator(_M_buckets[__n], this);
 345       return end();
 346     }
 347
 348     iterator end() { return iterator(0, this); }
 349
 350     const_iterator begin() const
 351     {
 352       for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 353         if (_M_buckets[__n])
 354           return const_iterator(_M_buckets[__n], this);
 355       return end();
 356     }
 357
 358     const_iterator end() const { return const_iterator(0, this); }
 359
 360     template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al>
 361     friend bool operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
 362                            const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
 363
 364   public:
 365     size_type bucket_count() const { return _M_buckets.size(); }
 366
 367     size_type max_bucket_count() const { return __stl_prime_list[(int)_S_num_primes - 1]; }
 368
 369     size_type elems_in_bucket(size_type __bucket) const
 370     {
 371       size_type __result = 0;
 372       for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
 373         __result += 1;
 374       return __result;
 375     }
 376
 377     std::pair<iterator, bool> insert_unique(const value_type& __obj)
 378     {
 379       resize(_M_num_elements + 1);
 380       return insert_unique_noresize(__obj);
 381     }
 382
 383     iterator insert_equal(const value_type& __obj)
 384     {
 385       resize(_M_num_elements + 1);
 386       return insert_equal_noresize(__obj);
 387     }
 388
 389     std::pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
 390
 391     iterator insert_equal_noresize(const value_type& __obj);
 392
 393     template<class _InputIterator>
 394     void insert_unique(_InputIterator __f, _InputIterator __l)
 395     { insert_unique(__f, __l, __iterator_category(__f)); }
 396
 397     template<class _InputIterator>
 398     void insert_equal(_InputIterator __f, _InputIterator __l)
 399     { insert_equal(__f, __l, __iterator_category(__f)); }
 400
 401     template<class _InputIterator>
 402     void insert_unique(_InputIterator __f, _InputIterator __l,
 403                        std::input_iterator_tag)
 404     {
 405       for ( ; __f != __l; ++__f)
 406         insert_unique(*__f);
 407     }
 408
 409     template<class _InputIterator>
 410     void insert_equal(_InputIterator __f, _InputIterator __l,
 411                       std::input_iterator_tag)
 412     {
 413       for ( ; __f != __l; ++__f)
 414         insert_equal(*__f);
 415     }
 416
 417     template<class _ForwardIterator>
 418     void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
 419                        std::forward_iterator_tag)
 420     {
 421       size_type __n = std::distance(__f, __l);
 422       resize(_M_num_elements + __n);
 423       for ( ; __n > 0; --__n, ++__f)
 424         insert_unique_noresize(*__f);
 425     }
 426
 427     template<class _ForwardIterator>
 428     void
 429     insert_equal(_ForwardIterator __f, _ForwardIterator __l,
 430                  std::forward_iterator_tag)
 431     {
 432       size_type __n = std::distance(__f, __l);
 433       resize(_M_num_elements + __n);
 434       for ( ; __n > 0; --__n, ++__f)
 435         insert_equal_noresize(*__f);
 436     }
 437
 438     reference find_or_insert(const value_type& __obj);
 439
 440     iterator find(const key_type& __key)
 441     {
 442       size_type __n = _M_bkt_num_key(__key);
 443       _Node* __first;
 444       for (__first = _M_buckets[__n];
 445            __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 446            __first = __first->_M_next)
 447         { }
 448       return iterator(__first, this);
 449     }
 450
 451     const_iterator find(const key_type& __key) const
 452     {
 453       size_type __n = _M_bkt_num_key(__key);
 454       const _Node* __first;
 455       for (__first = _M_buckets[__n];
 456            __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 457            __first = __first->_M_next)
 458         { }
 459       return const_iterator(__first, this);
 460     }
 461
 462     size_type count(const key_type& __key) const
 463     {
 464       const size_type __n = _M_bkt_num_key(__key);
 465       size_type __result = 0;
 466       for (const _Node* __cur = _M_buckets[__n]; __cur;
 467            __cur = __cur->_M_next)
 468         if (_M_equals(_M_get_key(__cur->_M_val), __key))
 469           ++__result;
 470       return __result;
 471     }
 472
 473     std::pair<iterator, iterator> equal_range(const key_type& __key);
 474
 475     std::pair<const_iterator, const_iterator> equal_range(const key_type& __key) const;
 476
 477     size_type erase(const key_type& __key);
 478
 479     void erase(const iterator& __it);
 480
 481     void erase(iterator __first, iterator __last);
 482
 483     void erase(const const_iterator& __it);
 484
 485     void erase(const_iterator __first, const_iterator __last);
 486
 487     void resize(size_type __num_elements_hint);
 488
 489     void clear();
 490
 491   private:
 492     size_type _M_next_size(size_type __n) const { return __stl_next_prime(__n); }
 493
 494     void _M_initialize_buckets(size_type __n)
 495     {
 496       const size_type __n_buckets = _M_next_size(__n);
 497       _M_buckets.reserve(__n_buckets);
 498       _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
 499       _M_num_elements = 0;
 500     }
 501
 502     size_type _M_bkt_num_key(const key_type& __key) const
 503     { return _M_bkt_num_key(__key, _M_buckets.size()); }
 504
 505     size_type _M_bkt_num(const value_type& __obj) const
 506     { return _M_bkt_num_key(_M_get_key(__obj)); }
 507
 508     size_type _M_bkt_num_key(const key_type& __key, std::size_t __n) const
 509     { return _M_hash(__key) % __n; }
 510
 511     size_type _M_bkt_num(const value_type& __obj, std::size_t __n) const
 512     { return _M_bkt_num_key(_M_get_key(__obj), __n); }
 513
 514     _Node* _M_new_node(const value_type& __obj)
 515     {
 516       _Node* __n = _M_get_node();
 517       __n->_M_next = 0;
 518       try
 519         {
 520           this->get_allocator().construct(&__n->_M_val, __obj);
 521           return __n;
 522         }
 523       catch(...)
 524         {
 525           _M_put_node(__n);
 526           throw;
 527         }
 528     }
 529
 530     void _M_delete_node(_Node* __n)
 531     {
 532       this->get_allocator().destroy(&__n->_M_val);
 533       _M_put_node(__n);
 534     }
 535
 536     void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
 537
 538     void _M_erase_bucket(const size_type __n, _Node* __last);
 539
 540     void _M_copy_from(const hashtable& __ht);
 541   };
 542
 543   template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
 544   _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
 545   _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 546   operator++()
 547   {
 548     const _Node* __old = _M_cur;
 549     _M_cur = _M_cur->_M_next;
 550     if (!_M_cur)
 551       {
 552         size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 553         while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 554           _M_cur = _M_ht->_M_buckets[__bucket];
 555       }
 556     return *this;
 557   }
 558
 559   template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
 560   inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
 561   _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 562   operator++(int)
 563   {
 564     iterator __tmp = *this;
 565     ++*this;
 566     return __tmp;
 567   }
 568
 569   template<class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
 570   _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
 571   _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 572   operator++()
 573   {
 574     const _Node* __old = _M_cur;
 575     _M_cur = _M_cur->_M_next;
 576     if (!_M_cur)
 577       {
 578         size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 579         while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 580           _M_cur = _M_ht->_M_buckets[__bucket];
 581       }
 582     return *this;
 583   }
 584
 585   template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
 586            class _All>
 587   inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
 588   _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
 589   operator++(int)
 590   {
 591     const_iterator __tmp = *this;
 592     ++*this;
 593     return __tmp;
 594   }
 595
 596   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 597   bool operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
 598                   const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
 599   {
 600     typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
 601
 602     if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
 603       return false;
 604
 605     for (std::size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
 606       {
 607         _Node* __cur1 = __ht1._M_buckets[__n];
 608         _Node* __cur2 = __ht2._M_buckets[__n];
 609         // Check same length of lists
 610         for (; __cur1 && __cur2;
 611              __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
 612           { }
 613         if (__cur1 || __cur2)
 614           return false;
 615         // Now check one's elements are in the other
 616         for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
 617              __cur1 = __cur1->_M_next)
 618           {
 619             bool _found__cur1 = false;
 620             for (__cur2 = __ht2._M_buckets[__n];
 621                  __cur2; __cur2 = __cur2->_M_next)
 622               {
 623                 if (__cur1->_M_val == __cur2->_M_val)
 624                   {
 625                     _found__cur1 = true;
 626                     break;
 627                   }
 628               }
 629             if (!_found__cur1)
 630               return false;
 631           }
 632       }
 633     return true;
 634   }
 635
 636   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 637   inline bool operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
 638                          const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
 639   { return !(__ht1 == __ht2); }
 640
 641   template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, class _All>
 642   inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
 643                    hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
 644   { __ht1.swap(__ht2); }
 645
 646   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 647   std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
 648   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 649   insert_unique_noresize(const value_type& __obj)
 650   {
 651     const size_type __n = _M_bkt_num(__obj);
 652     _Node* __first = _M_buckets[__n];
 653
 654     for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 655       if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 656         return std::pair<iterator, bool>(iterator(__cur, this), false);
 657
 658     _Node* __tmp = _M_new_node(__obj);
 659     __tmp->_M_next = __first;
 660     _M_buckets[__n] = __tmp;
 661     ++_M_num_elements;
 662     return std::pair<iterator, bool>(iterator(__tmp, this), true);
 663   }
 664
 665   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 666   typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
 667   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 668   insert_equal_noresize(const value_type& __obj)
 669   {
 670     const size_type __n = _M_bkt_num(__obj);
 671     _Node* __first = _M_buckets[__n];
 672
 673     for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 674       if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 675         {
 676           _Node* __tmp = _M_new_node(__obj);
 677           __tmp->_M_next = __cur->_M_next;
 678           __cur->_M_next = __tmp;
 679           ++_M_num_elements;
 680           return iterator(__tmp, this);
 681         }
 682
 683     _Node* __tmp = _M_new_node(__obj);
 684     __tmp->_M_next = __first;
 685     _M_buckets[__n] = __tmp;
 686     ++_M_num_elements;
 687     return iterator(__tmp, this);
 688   }
 689
 690   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 691   typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
 692   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 693   find_or_insert(const value_type& __obj)
 694   {
 695     resize(_M_num_elements + 1);
 696
 697     size_type __n = _M_bkt_num(__obj);
 698     _Node* __first = _M_buckets[__n];
 699
 700     for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 701       if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 702         return __cur->_M_val;
 703
 704     _Node* __tmp = _M_new_node(__obj);
 705     __tmp->_M_next = __first;
 706     _M_buckets[__n] = __tmp;
 707     ++_M_num_elements;
 708     return __tmp->_M_val;
 709   }
 710
 711   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 712   std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
 713             typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
 714   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key)
 715   {
 716     typedef std::pair<iterator, iterator> _Pii;
 717     const size_type __n = _M_bkt_num_key(__key);
 718
 719     for (_Node* __first = _M_buckets[__n]; __first;
 720          __first = __first->_M_next)
 721       if (_M_equals(_M_get_key(__first->_M_val), __key))
 722         {
 723           for (_Node* __cur = __first->_M_next; __cur;
 724                __cur = __cur->_M_next)
 725             if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 726               return _Pii(iterator(__first, this), iterator(__cur, this));
 727           for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 728             if (_M_buckets[__m])
 729               return _Pii(iterator(__first, this),
 730                           iterator(_M_buckets[__m], this));
 731           return _Pii(iterator(__first, this), end());
 732         }
 733     return _Pii(end(), end());
 734   }
 735
 736   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 737   std::pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
 738             typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
 739   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::equal_range(const key_type& __key) const
 740   {
 741     typedef std::pair<const_iterator, const_iterator> _Pii;
 742     const size_type __n = _M_bkt_num_key(__key);
 743
 744     for (const _Node* __first = _M_buckets[__n]; __first;
 745          __first = __first->_M_next)
 746       {
 747         if (_M_equals(_M_get_key(__first->_M_val), __key))
 748           {
 749             for (const _Node* __cur = __first->_M_next; __cur;
 750                  __cur = __cur->_M_next)
 751               if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 752                 return _Pii(const_iterator(__first, this),
 753                           const_iterator(__cur, this));
 754             for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 755               if (_M_buckets[__m])
 756                 return _Pii(const_iterator(__first, this),
 757                             const_iterator(_M_buckets[__m], this));
 758             return _Pii(const_iterator(__first, this), end());
 759           }
 760       }
 761     return _Pii(end(), end());
 762   }
 763
 764   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 765   typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
 766   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const key_type& __key)
 767   {
 768     const size_type __n = _M_bkt_num_key(__key);
 769     _Node* __first = _M_buckets[__n];
 770     size_type __erased = 0;
 771
 772     if (__first)
 773       {
 774         _Node* __cur = __first;
 775         _Node* __next = __cur->_M_next;
 776         while (__next)
 777           {
 778             if (_M_equals(_M_get_key(__next->_M_val), __key))
 779               {
 780                 __cur->_M_next = __next->_M_next;
 781                 _M_delete_node(__next);
 782                 __next = __cur->_M_next;
 783                 ++__erased;
 784                 --_M_num_elements;
 785               }
 786             else
 787               {
 788                 __cur = __next;
 789                 __next = __cur->_M_next;
 790               }
 791           }
 792         if (_M_equals(_M_get_key(__first->_M_val), __key))
 793           {
 794             _M_buckets[__n] = __first->_M_next;
 795             _M_delete_node(__first);
 796             ++__erased;
 797             --_M_num_elements;
 798           }
 799       }
 800     return __erased;
 801   }
 802
 803   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 804   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const iterator& __it)
 805   {
 806     _Node* __p = __it._M_cur;
 807     if (__p)
 808       {
 809         const size_type __n = _M_bkt_num(__p->_M_val);
 810         _Node* __cur = _M_buckets[__n];
 811         if (__cur == __p)
 812           {
 813             _M_buckets[__n] = __cur->_M_next;
 814             _M_delete_node(__cur);
 815             --_M_num_elements;
 816           }
 817         else
 818           {
 819             _Node* __next = __cur->_M_next;
 820             while (__next)
 821               {
 822                 if (__next == __p)
 823                   {
 824                     __cur->_M_next = __next->_M_next;
 825                     _M_delete_node(__next);
 826                     --_M_num_elements;
 827                     break;
 828                   }
 829                 else
 830                   {
 831                     __cur = __next;
 832                     __next = __cur->_M_next;
 833                   }
 834               }
 835           }
 836       }
 837   }
 838
 839   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 840   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(iterator __first, iterator __last)
 841   {
 842     size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
 843
 844     size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
 845
 846     if (__first._M_cur == __last._M_cur)
 847       return;
 848     else if (__f_bucket == __l_bucket)
 849       _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
 850     else
 851       {
 852         _M_erase_bucket(__f_bucket, __first._M_cur, 0);
 853         for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
 854           _M_erase_bucket(__n, 0);
 855         if (__l_bucket != _M_buckets.size())
 856           _M_erase_bucket(__l_bucket, __last._M_cur);
 857       }
 858   }
 859
 860   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 861   inline void
 862   hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
 863   erase(const_iterator __first, const_iterator __last)
 864   {
 865     erase(iterator(const_cast<_Node*>(__first._M_cur),
 866                    const_cast<hashtable*>(__first._M_ht)),
 867           iterator(const_cast<_Node*>(__last._M_cur),
 868                    const_cast<hashtable*>(__last._M_ht)));
 869   }
 870
 871   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 872   inline void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::erase(const const_iterator& __it)
 873   { erase(iterator(const_cast<_Node*>(__it._M_cur), const_cast<hashtable*>(__it._M_ht))); }
 874
 875   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 876   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::resize(size_type __num_elements_hint)
 877   {
 878     const size_type __old_n = _M_buckets.size();
 879     if (__num_elements_hint > __old_n)
 880       {
 881         const size_type __n = _M_next_size(__num_elements_hint);
 882         if (__n > __old_n)
 883           {
 884             _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
 885             try
 886               {
 887                 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
 888                   {
 889                     _Node* __first = _M_buckets[__bucket];
 890                     while (__first)
 891                       {
 892                         size_type __new_bucket = _M_bkt_num(__first->_M_val,__n);
 893                         _M_buckets[__bucket] = __first->_M_next;
 894                         __first->_M_next = __tmp[__new_bucket];
 895                         __tmp[__new_bucket] = __first;
 896                         __first = _M_buckets[__bucket];
 897                       }
 898                   }
 899                 _M_buckets.swap(__tmp);
 900               }
 901             catch(...)
 902               {
 903                 for (size_type __bucket = 0; __bucket < __tmp.size();++__bucket)
 904                   {
 905                     while (__tmp[__bucket])
 906                       {
 907                         _Node* __next = __tmp[__bucket]->_M_next;
 908                         _M_delete_node(__tmp[__bucket]);
 909                         __tmp[__bucket] = __next;
 910                       }
 911                   }
 912                 throw;
 913               }
 914           }
 915       }
 916   }
 917
 918   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 919   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
 920   {
 921     _Node* __cur = _M_buckets[__n];
 922     if (__cur == __first)
 923       _M_erase_bucket(__n, __last);
 924     else
 925       {
 926         _Node* __next;
 927         for (__next = __cur->_M_next;
 928              __next != __first;
 929              __cur = __next, __next = __cur->_M_next)
 930           ;
 931         while (__next != __last)
 932           {
 933             __cur->_M_next = __next->_M_next;
 934             _M_delete_node(__next);
 935             __next = __cur->_M_next;
 936             --_M_num_elements;
 937           }
 938       }
 939   }
 940
 941   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 942   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_erase_bucket(const size_type __n, _Node* __last)
 943   {
 944     _Node* __cur = _M_buckets[__n];
 945     while (__cur != __last)
 946       {
 947         _Node* __next = __cur->_M_next;
 948         _M_delete_node(__cur);
 949         __cur = __next;
 950         _M_buckets[__n] = __cur;
 951         --_M_num_elements;
 952       }
 953   }
 954
 955   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 956   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::clear()
 957   {
 958     for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
 959       {
 960         _Node* __cur = _M_buckets[__i];
 961         while (__cur != 0)
 962           {
 963             _Node* __next = __cur->_M_next;
 964             _M_delete_node(__cur);
 965             __cur = __next;
 966           }
 967         _M_buckets[__i] = 0;
 968       }
 969     _M_num_elements = 0;
 970   }
 971
 972   template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 973   void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_M_copy_from(const hashtable& __ht)
 974   {
 975     _M_buckets.clear();
 976     _M_buckets.reserve(__ht._M_buckets.size());
 977     _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
 978     try
 979       {
 980         for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
 981           const _Node* __cur = __ht._M_buckets[__i];
 982           if (__cur)
 983             {
 984               _Node* __local_copy = _M_new_node(__cur->_M_val);
 985               _M_buckets[__i] = __local_copy;
 986               for (_Node* __next = __cur->_M_next;
 987                    __next;
 988                    __cur = __next, __next = __cur->_M_next)
 989                 {
 990                   __local_copy->_M_next = _M_new_node(__next->_M_val);
 991                   __local_copy = __local_copy->_M_next;
 992                 }
 993             }
 994         }
 995         _M_num_elements = __ht._M_num_elements;
 996       }
 997     catch(...)
 998       {
 999         clear();
1000         throw;
1001       }
1002   }
1003 }
1004
1005 #endif