src/INTERP_KERNEL/Bases/InterpKernelHashTable.hxx

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