libstdc++-v3/include/ext/stl_hashtable.h

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