src/INTERP_KERNEL/Bases/InterpKernelHashTable.hxx

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