CMakeLua/Source/kwsys/hashtable.hxx.in

   1 /*=========================================================================
   2
   3   Program:   KWSys - Kitware System Library
   4   Module:    $RCSfile: hashtable.hxx.in,v $
   5
   6   Copyright (c) Kitware, Inc., Insight Consortium.  All rights reserved.
   7   See Copyright.txt or http://www.kitware.com/Copyright.htm for details.
   8
   9      This software is distributed WITHOUT ANY WARRANTY; without even
  10      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  11      PURPOSE.  See the above copyright notices for more information.
  12
  13 =========================================================================*/
  14 /*
  15  * Copyright (c) 1996
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  *
  26  *
  27  * Copyright (c) 1994
  28  * Hewlett-Packard Company
  29  *
  30  * Permission to use, copy, modify, distribute and sell this software
  31  * and its documentation for any purpose is hereby granted without fee,
  32  * provided that the above copyright notice appear in all copies and
  33  * that both that copyright notice and this permission notice appear
  34  * in supporting documentation.  Hewlett-Packard Company makes no
  35  * representations about the suitability of this software for any
  36  * purpose.  It is provided "as is" without express or implied warranty.
  37  *
  38  */
  39 #ifndef @KWSYS_NAMESPACE@_hashtable_hxx
  40 #define @KWSYS_NAMESPACE@_hashtable_hxx
  41
  42 #include <@KWSYS_NAMESPACE@/Configure.hxx>
  43
  44 #include <@KWSYS_NAMESPACE@/cstddef>        // size_t
  45 #include <@KWSYS_NAMESPACE@/stl/algorithm>  // lower_bound
  46 #include <@KWSYS_NAMESPACE@/stl/functional> // unary_function
  47 #include <@KWSYS_NAMESPACE@/stl/iterator>   // iterator_traits
  48 #include <@KWSYS_NAMESPACE@/stl/memory>     // allocator
  49 #include <@KWSYS_NAMESPACE@/stl/utility>    // pair
  50 #include <@KWSYS_NAMESPACE@/stl/vector>     // vector
  51
  52 #if defined(_MSC_VER)
  53 # pragma warning (push)
  54 # pragma warning (disable:4284)
  55 # pragma warning (disable:4786)
  56 # pragma warning (disable:4512) /* no assignment operator for class */
  57 #endif
  58
  59 #if @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_TEMPLATE
  60 # define @KWSYS_NAMESPACE@_HASH_DEFAULT_ALLOCATOR(T) @KWSYS_NAMESPACE@_stl::allocator< T >
  61 #elif @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_NONTEMPLATE
  62 # define @KWSYS_NAMESPACE@_HASH_DEFAULT_ALLOCATOR(T) @KWSYS_NAMESPACE@_stl::allocator
  63 #else
  64 # define @KWSYS_NAMESPACE@_HASH_DEFAULT_ALLOCATOR(T) @KWSYS_NAMESPACE@_stl::alloc
  65 #endif
  66
  67 #if @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_OBJECTS
  68 # define @KWSYS_NAMESPACE@_HASH_BUCKETS_INIT(__a) _M_buckets(__a)
  69 # define @KWSYS_NAMESPACE@_HASH_BUCKETS_GET_ALLOCATOR(__b) , __b.get_allocator()
  70 #else
  71 # define @KWSYS_NAMESPACE@_HASH_BUCKETS_INIT(__a) _M_buckets()
  72 # define @KWSYS_NAMESPACE@_HASH_BUCKETS_GET_ALLOCATOR(__b)
  73 #endif
  74
  75 namespace @KWSYS_NAMESPACE@
  76 {
  77
  78 //----------------------------------------------------------------------------
  79 // Define an allocator adaptor for platforms that do not provide an
  80 // allocator with the rebind member.
  81 #if !@KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_REBIND
  82
  83 // Utility functions to convert item counts.
  84 inline size_t hash_sizeof(void*) { return sizeof(char); }
  85 inline size_t hash_sizeof(const void*) { return sizeof(char); }
  86 template <class TPtr> inline size_t hash_sizeof(TPtr p)
  87 {
  88   static_cast<void>(p);
  89   return sizeof(*p);
  90 }
  91 template <class POut, class PIn, class TSize>
  92 inline TSize hash_allocator_n(POut out, PIn in, TSize n)
  93 {
  94   return n*(hash_sizeof(out)/hash_sizeof(in) +
  95             (hash_sizeof(out)%hash_sizeof(in)>0));
  96 }
  97
  98 // Define an allocation method to use the native allocator with
  99 // the proper signature.  The following signatures of the allocate
 100 // method are used on various STL implementations:
 101 //   pointer allocate(size_type, const void* hint)
 102 //   pointer allocate(size_type)
 103 //   static pointer allocate(size_type, const void* hint)
 104 //   static pointer allocate(size_type)
 105 // Where pointer might be a real type or void*.
 106 // This set of overloads decodes the signature for a particular STL.
 107 // The extra three int/long arguments will favor certain signatures
 108 // over others in the case that multiple are present to avoid
 109 // ambiguity errors.
 110 template <class TAlloc, class PIn, class TSize, class THint, class POut>
 111 inline void hash_allocate(TAlloc* a, PIn (TAlloc::*allocate)(TSize, THint),
 112                           TSize n_out, const void* hint, POut& out,
 113                           int, int, int)
 114 {
 115   TSize n_in = hash_allocator_n(POut(), PIn(), n_out);
 116   void* vout = (a->*allocate)(n_in, const_cast<THint>(hint));
 117   out = static_cast<POut>(vout);
 118 }
 119
 120 template <class TAlloc, class PIn, class TSize, class POut>
 121 inline void hash_allocate(TAlloc* a, PIn (TAlloc::*allocate)(TSize),
 122                           TSize n_out, const void*, POut& out,
 123                           int, int, long)
 124 {
 125   TSize n_in = hash_allocator_n(POut(), PIn(), n_out);
 126   void* vout = (a->*allocate)(n_in);
 127   out = static_cast<POut>(vout);
 128 }
 129
 130 template <class PIn, class TSize, class THint, class POut>
 131 inline void hash_allocate(void*, PIn (*allocate)(TSize, THint),
 132                           TSize n_out, const void* hint, POut& out,
 133                           int, long, long)
 134 {
 135   TSize n_in = hash_allocator_n(POut(), PIn(), n_out);
 136   void* vout = allocate(n_in, const_cast<THint>(hint));
 137   out = static_cast<POut>(vout);
 138 }
 139
 140 template <class PIn, class TSize, class POut>
 141 inline void hash_allocate(void*, PIn (*allocate)(TSize),
 142                           TSize n_out, const void*, POut& out,
 143                           long, long, long)
 144 {
 145   TSize n_in = hash_allocator_n(POut(), PIn(), n_out);
 146   void* vout = allocate(n_in);
 147   out = static_cast<POut>(vout);
 148 }
 149
 150 // Define a deallocation method to use the native allocator with
 151 // the proper signature.  The following signatures of the deallocate
 152 // method are used on various STL implementations:
 153 //   void deallocate(pointer, size_type)
 154 //   void deallocate(pointer)
 155 //   static void deallocate(pointer, size_type)
 156 //   static void deallocate(pointer)
 157 // Where pointer might be a real type or void*.
 158 // This set of overloads decodes the signature for a particular STL.
 159 // The extra three int/long arguments will favor certain signatures
 160 // over others in the case that multiple are present to avoid
 161 // ambiguity errors.
 162 template <class TAlloc, class PIn, class TSize, class PInReal, class POut>
 163 inline void hash_deallocate(TAlloc* a, void (TAlloc::*deallocate)(PIn, TSize),
 164                             PInReal, POut p, TSize n_out, int, int, int)
 165 {
 166   TSize n_in = hash_allocator_n(POut(), PInReal(), n_out);
 167   void* vout = p;
 168   (a->*deallocate)(static_cast<PIn>(vout), n_in);
 169 }
 170
 171 template <class TAlloc, class PIn, class TSize, class PInReal, class POut>
 172 inline void hash_deallocate(TAlloc* a, void (TAlloc::*deallocate)(PIn),
 173                             PInReal, POut p, TSize, int, int, long)
 174 {
 175   void* vout = p;
 176   (a->*deallocate)(static_cast<PIn>(vout));
 177 }
 178
 179 template <class PIn, class TSize, class PInReal, class POut>
 180 inline void hash_deallocate(void*, void (*deallocate)(PIn, TSize),
 181                             PInReal, POut p, TSize n_out, int, long, long)
 182 {
 183   TSize n_in = hash_allocator_n(POut(), PInReal(), n_out);
 184   void* vout = p;
 185   deallocate(static_cast<PIn>(vout), n_in);
 186 }
 187
 188 template <class PIn, class TSize, class PInReal, class POut>
 189 inline void hash_deallocate(void*, void (*deallocate)(PIn),
 190                             PInReal, POut p, TSize, long, long, long)
 191 {
 192   void* vout = p;
 193   deallocate(static_cast<PIn>(vout));
 194 }
 195
 196 // Use the same four overloads as hash_allocate to decode the type
 197 // really used for allocation.  This is passed as PInReal to the
 198 // deallocate functions so that hash_allocator_n has the proper size.
 199 template <class TAlloc, class PIn, class TSize, class THint>
 200 inline PIn hash_allocate_type(PIn (TAlloc::*)(TSize, THint),
 201                               int, int, int) { return 0; }
 202 template <class TAlloc, class PIn, class TSize>
 203 inline PIn hash_allocate_type(PIn (TAlloc::*)(TSize),
 204                               int, int, long) { return 0; }
 205 template <class PIn, class TSize, class THint>
 206 inline PIn hash_allocate_type(PIn (*)(TSize, THint),
 207                               int, long, long) { return 0; }
 208 template <class PIn, class TSize>
 209 inline PIn hash_allocate_type(PIn (*)(TSize),
 210                               long, long, long) { return 0; }
 211
 212 // Define the comparison operators in terms of a base type to avoid
 213 // needing templated versions.
 214 class hash_allocator_base {};
 215 bool operator==(const hash_allocator_base&,
 216                 const hash_allocator_base&) throw() { return true; }
 217 bool operator!=(const hash_allocator_base&,
 218                 const hash_allocator_base&) throw() { return false; }
 219
 220 // Define the allocator template.
 221 template <class T, class Alloc>
 222 class hash_allocator: public hash_allocator_base
 223 {
 224 private:
 225   // Store the real allocator privately.
 226   typedef Alloc alloc_type;
 227   alloc_type alloc_;
 228
 229 public:
 230   // Standard allocator interface.
 231   typedef size_t size_type;
 232   typedef ptrdiff_t difference_type;
 233   typedef T* pointer;
 234   typedef const T* const_pointer;
 235   typedef T& reference;
 236   typedef const T& const_reference;
 237   typedef T value_type;
 238
 239   hash_allocator() throw(): alloc_() {}
 240   hash_allocator(const hash_allocator_base&) throw() : alloc_() {}
 241   hash_allocator(const hash_allocator& a) throw() : alloc_(a.alloc_) {}
 242   hash_allocator(const alloc_type& a) throw() : alloc_(a) {}
 243   ~hash_allocator() throw() {}
 244 # if @KWSYS_NAMESPACE@_CXX_HAS_MEMBER_TEMPLATES
 245   template <class U>
 246   struct rebind { typedef hash_allocator<U, alloc_type> other; };
 247 # endif
 248   pointer address(reference x) const { return &x; }
 249   const_pointer address(const_reference x) const { return &x; }
 250   typedef void* void_pointer;
 251   typedef const void* const_void_pointer;
 252   pointer allocate(size_type n=1, const_void_pointer hint = 0)
 253     {
 254     if(n)
 255       {
 256       pointer p;
 257       hash_allocate(&alloc_, &alloc_type::allocate, n, hint, p, 1, 1, 1);
 258       return p;
 259       }
 260     else
 261       {
 262       return 0;
 263       }
 264     }
 265   void deallocate(pointer p, size_type n=1)
 266     {
 267     if(n)
 268       {
 269       hash_deallocate(&alloc_, &alloc_type::deallocate,
 270                       hash_allocate_type(&alloc_type::allocate, 1, 1, 1),
 271                       p, n, 1, 1, 1);
 272       }
 273     }
 274 #if @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_MAX_SIZE_ARGUMENT
 275   size_type max_size(size_type s) const throw()
 276     {
 277     return alloc_.max_size(s);
 278     }
 279 #else
 280   size_type max_size() const throw()
 281     {
 282     size_type n = alloc_.max_size() / sizeof(value_type);
 283     return n>0? n:1;
 284     }
 285 #endif
 286   void construct(pointer p, const value_type& val) { new (p) value_type(val); }
 287   void destroy(pointer p) { (void)p; p->~value_type(); }
 288 };
 289 #endif
 290
 291 template <class _Val>
 292 struct _Hashtable_node
 293 {
 294   _Hashtable_node* _M_next;
 295   _Val _M_val;
 296 };
 297
 298 template <class _Val, class _Key, class _HashFcn,
 299           class _ExtractKey, class _EqualKey,
 300           class _Alloc = @KWSYS_NAMESPACE@_HASH_DEFAULT_ALLOCATOR(char) >
 301 class hashtable;
 302
 303 template <class _Val, class _Key, class _HashFcn,
 304           class _ExtractKey, class _EqualKey, class _Alloc>
 305 struct _Hashtable_iterator;
 306
 307 template <class _Val, class _Key, class _HashFcn,
 308           class _ExtractKey, class _EqualKey, class _Alloc>
 309 struct _Hashtable_const_iterator;
 310
 311 template <class _Val, class _Key, class _HashFcn,
 312           class _ExtractKey, class _EqualKey, class _Alloc>
 313 struct _Hashtable_iterator {
 314   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
 315           _Hashtable;
 316   typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
 317                               _ExtractKey, _EqualKey, _Alloc>
 318           iterator;
 319   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 320                                     _ExtractKey, _EqualKey, _Alloc>
 321           const_iterator;
 322   typedef _Hashtable_node<_Val> _Node;
 323
 324   typedef @KWSYS_NAMESPACE@_stl::forward_iterator_tag iterator_category;
 325   typedef _Val value_type;
 326   typedef ptrdiff_t difference_type;
 327   typedef size_t size_type;
 328   typedef _Val& reference;
 329   typedef _Val* pointer;
 330
 331   _Node* _M_cur;
 332   _Hashtable* _M_ht;
 333
 334   _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
 335     : _M_cur(__n), _M_ht(__tab) {}
 336   _Hashtable_iterator() {}
 337   reference operator*() const { return _M_cur->_M_val; }
 338   pointer operator->() const { return &(operator*()); }
 339   iterator& operator++();
 340   iterator operator++(int);
 341   bool operator==(const iterator& __it) const
 342     { return _M_cur == __it._M_cur; }
 343   bool operator!=(const iterator& __it) const
 344     { return _M_cur != __it._M_cur; }
 345 };
 346
 347
 348 template <class _Val, class _Key, class _HashFcn,
 349           class _ExtractKey, class _EqualKey, class _Alloc>
 350 struct _Hashtable_const_iterator {
 351   typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
 352           _Hashtable;
 353   typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
 354                               _ExtractKey,_EqualKey,_Alloc>
 355           iterator;
 356   typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
 357                                     _ExtractKey, _EqualKey, _Alloc>
 358           const_iterator;
 359   typedef _Hashtable_node<_Val> _Node;
 360
 361   typedef @KWSYS_NAMESPACE@_stl::forward_iterator_tag iterator_category;
 362   typedef _Val value_type;
 363   typedef ptrdiff_t difference_type;
 364   typedef size_t size_type;
 365   typedef const _Val& reference;
 366   typedef const _Val* pointer;
 367
 368   const _Node* _M_cur;
 369   const _Hashtable* _M_ht;
 370
 371   _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
 372     : _M_cur(__n), _M_ht(__tab) {}
 373   _Hashtable_const_iterator() {}
 374   _Hashtable_const_iterator(const iterator& __it)
 375     : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {}
 376   reference operator*() const { return _M_cur->_M_val; }
 377   pointer operator->() const { return &(operator*()); }
 378   const_iterator& operator++();
 379   const_iterator operator++(int);
 380   bool operator==(const const_iterator& __it) const
 381     { return _M_cur == __it._M_cur; }
 382   bool operator!=(const const_iterator& __it) const
 383     { return _M_cur != __it._M_cur; }
 384 };
 385
 386 // Note: assumes long is at least 32 bits.
 387 enum { _stl_num_primes = 31 };
 388
 389 static const unsigned long _stl_prime_list[_stl_num_primes] =
 390 {
 391   5ul,          11ul,         23ul,
 392   53ul,         97ul,         193ul,       389ul,       769ul,
 393   1543ul,       3079ul,       6151ul,      12289ul,     24593ul,
 394   49157ul,      98317ul,      196613ul,    393241ul,    786433ul,
 395   1572869ul,    3145739ul,    6291469ul,   12582917ul,  25165843ul,
 396   50331653ul,   100663319ul,  201326611ul, 402653189ul, 805306457ul,
 397   1610612741ul, 3221225473ul, 4294967291ul
 398 };
 399
 400 inline size_t _stl_next_prime(size_t __n)
 401 {
 402   const unsigned long* __first = _stl_prime_list;
 403   const unsigned long* __last = _stl_prime_list + (int)_stl_num_primes;
 404   const unsigned long* pos = @KWSYS_NAMESPACE@_stl::lower_bound(__first, __last, __n);
 405   return pos == __last ? *(__last - 1) : *pos;
 406 }
 407
 408 // Forward declaration of operator==.
 409
 410 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 411 class hashtable;
 412
 413 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 414 bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
 415                 const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2);
 416
 417 // Hashtables handle allocators a bit differently than other containers
 418 //  do.  If we're using standard-conforming allocators, then a hashtable
 419 //  unconditionally has a member variable to hold its allocator, even if
 420 //  it so happens that all instances of the allocator type are identical.
 421 // This is because, for hashtables, this extra storage is negligible.
 422 //  Additionally, a base class wouldn't serve any other purposes; it
 423 //  wouldn't, for example, simplify the exception-handling code.
 424
 425 template <class _Val, class _Key, class _HashFcn,
 426           class _ExtractKey, class _EqualKey, class _Alloc>
 427 class hashtable {
 428 public:
 429   typedef _Key key_type;
 430   typedef _Val value_type;
 431   typedef _HashFcn hasher;
 432   typedef _EqualKey key_equal;
 433
 434   typedef size_t            size_type;
 435   typedef ptrdiff_t         difference_type;
 436   typedef value_type*       pointer;
 437   typedef const value_type* const_pointer;
 438   typedef value_type&       reference;
 439   typedef const value_type& const_reference;
 440
 441   hasher hash_funct() const { return _M_hash; }
 442   key_equal key_eq() const { return _M_equals; }
 443
 444 private:
 445   typedef _Hashtable_node<_Val> _Node;
 446
 447 #if @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_REBIND
 448 public:
 449   typedef typename _Alloc::template rebind<_Val>::other allocator_type;
 450   allocator_type get_allocator() const { return _M_node_allocator; }
 451 private:
 452   typedef typename _Alloc::template rebind<_Node>::other _M_node_allocator_type;
 453   typedef typename _Alloc::template rebind<_Node*>::other _M_node_ptr_allocator_type;
 454   typedef @KWSYS_NAMESPACE@_stl::vector<_Node*,_M_node_ptr_allocator_type> _M_buckets_type;
 455 #else
 456 public:
 457   typedef hash_allocator<_Val, _Alloc> allocator_type;
 458   allocator_type get_allocator() const { return allocator_type(); }
 459 private:
 460   typedef hash_allocator<_Node, _Alloc> _M_node_allocator_type;
 461 # if @KWSYS_NAMESPACE@_STL_HAS_ALLOCATOR_OBJECTS
 462   typedef hash_allocator<_Node*, _Alloc> _M_node_ptr_allocator_type;
 463 # else
 464   typedef _Alloc _M_node_ptr_allocator_type;
 465 # endif
 466   typedef @KWSYS_NAMESPACE@_stl::vector<_Node*,_M_node_ptr_allocator_type> _M_buckets_type;
 467 #endif
 468
 469 private:
 470   _M_node_allocator_type _M_node_allocator;
 471   hasher                 _M_hash;
 472   key_equal              _M_equals;
 473   _ExtractKey            _M_get_key;
 474   _M_buckets_type        _M_buckets;
 475   size_type              _M_num_elements;
 476
 477   _Node* _M_get_node() { return _M_node_allocator.allocate(1); }
 478   void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); }
 479
 480 public:
 481   typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
 482           iterator;
 483   typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,
 484                                     _Alloc>
 485           const_iterator;
 486
 487   friend struct
 488   _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>;
 489   friend struct
 490   _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>;
 491
 492 public:
 493   hashtable(size_type __n,
 494             const _HashFcn&    __hf,
 495             const _EqualKey&   __eql,
 496             const _ExtractKey& __ext,
 497             const allocator_type& __a = allocator_type())
 498     : _M_node_allocator(__a),
 499       _M_hash(__hf),
 500       _M_equals(__eql),
 501       _M_get_key(__ext),
 502       @KWSYS_NAMESPACE@_HASH_BUCKETS_INIT(__a),
 503       _M_num_elements(0)
 504   {
 505     _M_initialize_buckets(__n);
 506   }
 507
 508   hashtable(size_type __n,
 509             const _HashFcn&    __hf,
 510             const _EqualKey&   __eql,
 511             const allocator_type& __a = allocator_type())
 512     : _M_node_allocator(__a),
 513       _M_hash(__hf),
 514       _M_equals(__eql),
 515       _M_get_key(_ExtractKey()),
 516       @KWSYS_NAMESPACE@_HASH_BUCKETS_INIT(__a),
 517       _M_num_elements(0)
 518   {
 519     _M_initialize_buckets(__n);
 520   }
 521
 522   hashtable(const hashtable& __ht)
 523     : _M_node_allocator(__ht.get_allocator()),
 524       _M_hash(__ht._M_hash),
 525       _M_equals(__ht._M_equals),
 526       _M_get_key(__ht._M_get_key),
 527       @KWSYS_NAMESPACE@_HASH_BUCKETS_INIT(__ht.get_allocator()),
 528       _M_num_elements(0)
 529   {
 530     _M_copy_from(__ht);
 531   }
 532
 533   hashtable& operator= (const hashtable& __ht)
 534   {
 535     if (&__ht != this) {
 536       clear();
 537       _M_hash = __ht._M_hash;
 538       _M_equals = __ht._M_equals;
 539       _M_get_key = __ht._M_get_key;
 540       _M_copy_from(__ht);
 541     }
 542     return *this;
 543   }
 544
 545   ~hashtable() { clear(); }
 546
 547   size_type size() const { return _M_num_elements; }
 548   size_type max_size() const { return size_type(-1); }
 549   bool empty() const { return size() == 0; }
 550
 551   void swap(hashtable& __ht)
 552   {
 553     @KWSYS_NAMESPACE@_stl::swap(_M_hash, __ht._M_hash);
 554     @KWSYS_NAMESPACE@_stl::swap(_M_equals, __ht._M_equals);
 555     @KWSYS_NAMESPACE@_stl::swap(_M_get_key, __ht._M_get_key);
 556     _M_buckets.swap(__ht._M_buckets);
 557     @KWSYS_NAMESPACE@_stl::swap(_M_num_elements, __ht._M_num_elements);
 558   }
 559
 560   iterator begin()
 561   {
 562     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 563       if (_M_buckets[__n])
 564         return iterator(_M_buckets[__n], this);
 565     return end();
 566   }
 567
 568   iterator end() { return iterator(0, this); }
 569
 570   const_iterator begin() const
 571   {
 572     for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
 573       if (_M_buckets[__n])
 574         return const_iterator(_M_buckets[__n], this);
 575     return end();
 576   }
 577
 578   const_iterator end() const { return const_iterator(0, this); }
 579
 580   friend bool operator==@KWSYS_NAMESPACE@_CXX_NULL_TEMPLATE_ARGS(const hashtable&,
 581                                                                  const hashtable&);
 582
 583 public:
 584
 585   size_type bucket_count() const { return _M_buckets.size(); }
 586
 587   size_type max_bucket_count() const
 588     { return _stl_prime_list[(int)_stl_num_primes - 1]; }
 589
 590   size_type elems_in_bucket(size_type __bucket) const
 591   {
 592     size_type __result = 0;
 593     for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
 594       __result += 1;
 595     return __result;
 596   }
 597
 598   @KWSYS_NAMESPACE@_stl::pair<iterator, bool> insert_unique(const value_type& __obj)
 599   {
 600     resize(_M_num_elements + 1);
 601     return insert_unique_noresize(__obj);
 602   }
 603
 604   iterator insert_equal(const value_type& __obj)
 605   {
 606     resize(_M_num_elements + 1);
 607     return insert_equal_noresize(__obj);
 608   }
 609
 610   @KWSYS_NAMESPACE@_stl::pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
 611   iterator insert_equal_noresize(const value_type& __obj);
 612
 613 #if @KWSYS_NAMESPACE@_STL_HAS_ITERATOR_TRAITS
 614 # define @KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY(T,I) \
 615   typename @KWSYS_NAMESPACE@_stl::iterator_traits< T >::iterator_category()
 616 #elif @KWSYS_NAMESPACE@_STL_HAS_ITERATOR_CATEGORY
 617 # define @KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY(T,I) \
 618   @KWSYS_NAMESPACE@_stl::iterator_category( I )
 619 #elif @KWSYS_NAMESPACE@_STL_HAS___ITERATOR_CATEGORY
 620 # define @KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY(T,I) \
 621   @KWSYS_NAMESPACE@_stl::__iterator_category( I )
 622 #endif
 623
 624 #if @KWSYS_NAMESPACE@_CXX_HAS_MEMBER_TEMPLATES && defined(@KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY)
 625   template <class _InputIterator>
 626   void insert_unique(_InputIterator __f, _InputIterator __l)
 627   {
 628     insert_unique(__f, __l,
 629       @KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY(_InputIterator, __f));
 630   }
 631
 632   template <class _InputIterator>
 633   void insert_equal(_InputIterator __f, _InputIterator __l)
 634   {
 635     insert_equal(__f, __l,
 636       @KWSYS_NAMESPACE@_HASH_ITERATOR_CATEGORY(_InputIterator, __f));
 637   }
 638
 639   template <class _InputIterator>
 640   void insert_unique(_InputIterator __f, _InputIterator __l,
 641                      @KWSYS_NAMESPACE@_stl::input_iterator_tag)
 642   {
 643     for ( ; __f != __l; ++__f)
 644       insert_unique(*__f);
 645   }
 646
 647   template <class _InputIterator>
 648   void insert_equal(_InputIterator __f, _InputIterator __l,
 649                     @KWSYS_NAMESPACE@_stl::input_iterator_tag)
 650   {
 651     for ( ; __f != __l; ++__f)
 652       insert_equal(*__f);
 653   }
 654
 655   template <class _ForwardIterator>
 656   void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
 657                      @KWSYS_NAMESPACE@_stl::forward_iterator_tag)
 658   {
 659     size_type __n = 0;
 660     @KWSYS_NAMESPACE@_stl::distance(__f, __l, __n);
 661     resize(_M_num_elements + __n);
 662     for ( ; __n > 0; --__n, ++__f)
 663       insert_unique_noresize(*__f);
 664   }
 665
 666   template <class _ForwardIterator>
 667   void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
 668                     @KWSYS_NAMESPACE@_stl::forward_iterator_tag)
 669   {
 670     size_type __n = 0;
 671     @KWSYS_NAMESPACE@_stl::distance(__f, __l, __n);
 672     resize(_M_num_elements + __n);
 673     for ( ; __n > 0; --__n, ++__f)
 674       insert_equal_noresize(*__f);
 675   }
 676
 677 #else
 678   void insert_unique(const value_type* __f, const value_type* __l)
 679   {
 680     size_type __n = __l - __f;
 681     resize(_M_num_elements + __n);
 682     for ( ; __n > 0; --__n, ++__f)
 683       insert_unique_noresize(*__f);
 684   }
 685
 686   void insert_equal(const value_type* __f, const value_type* __l)
 687   {
 688     size_type __n = __l - __f;
 689     resize(_M_num_elements + __n);
 690     for ( ; __n > 0; --__n, ++__f)
 691       insert_equal_noresize(*__f);
 692   }
 693
 694   void insert_unique(const_iterator __f, const_iterator __l)
 695   {
 696     size_type __n = 0;
 697     @KWSYS_NAMESPACE@_stl::distance(__f, __l, __n);
 698     resize(_M_num_elements + __n);
 699     for ( ; __n > 0; --__n, ++__f)
 700       insert_unique_noresize(*__f);
 701   }
 702
 703   void insert_equal(const_iterator __f, const_iterator __l)
 704   {
 705     size_type __n = 0;
 706     @KWSYS_NAMESPACE@_stl::distance(__f, __l, __n);
 707     resize(_M_num_elements + __n);
 708     for ( ; __n > 0; --__n, ++__f)
 709       insert_equal_noresize(*__f);
 710   }
 711 #endif
 712
 713   reference find_or_insert(const value_type& __obj);
 714
 715   iterator find(const key_type& __key)
 716   {
 717     size_type __n = _M_bkt_num_key(__key);
 718     _Node* __first;
 719     for ( __first = _M_buckets[__n];
 720           __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 721           __first = __first->_M_next)
 722       {}
 723     return iterator(__first, this);
 724   }
 725
 726   const_iterator find(const key_type& __key) const
 727   {
 728     size_type __n = _M_bkt_num_key(__key);
 729     const _Node* __first;
 730     for ( __first = _M_buckets[__n];
 731           __first && !_M_equals(_M_get_key(__first->_M_val), __key);
 732           __first = __first->_M_next)
 733       {}
 734     return const_iterator(__first, this);
 735   }
 736
 737   size_type count(const key_type& __key) const
 738   {
 739     const size_type __n = _M_bkt_num_key(__key);
 740     size_type __result = 0;
 741
 742     for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next)
 743       if (_M_equals(_M_get_key(__cur->_M_val), __key))
 744         ++__result;
 745     return __result;
 746   }
 747
 748   @KWSYS_NAMESPACE@_stl::pair<iterator, iterator>
 749   equal_range(const key_type& __key);
 750
 751   @KWSYS_NAMESPACE@_stl::pair<const_iterator, const_iterator>
 752   equal_range(const key_type& __key) const;
 753
 754   size_type erase(const key_type& __key);
 755   void erase(const iterator& __it);
 756   void erase(iterator __first, iterator __last);
 757
 758   void erase(const const_iterator& __it);
 759   void erase(const_iterator __first, const_iterator __last);
 760
 761   void resize(size_type __num_elements_hint);
 762   void clear();
 763
 764 private:
 765   size_type _M_next_size(size_type __n) const
 766     { return _stl_next_prime(__n); }
 767
 768   void _M_initialize_buckets(size_type __n)
 769   {
 770     const size_type __n_buckets = _M_next_size(__n);
 771     _M_buckets.reserve(__n_buckets);
 772     _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
 773     _M_num_elements = 0;
 774   }
 775
 776   size_type _M_bkt_num_key(const key_type& __key) const
 777   {
 778     return _M_bkt_num_key(__key, _M_buckets.size());
 779   }
 780
 781   size_type _M_bkt_num(const value_type& __obj) const
 782   {
 783     return _M_bkt_num_key(_M_get_key(__obj));
 784   }
 785
 786   size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
 787   {
 788     return _M_hash(__key) % __n;
 789   }
 790
 791   size_type _M_bkt_num(const value_type& __obj, size_t __n) const
 792   {
 793     return _M_bkt_num_key(_M_get_key(__obj), __n);
 794   }
 795
 796   void construct(_Val* p, const _Val& v)
 797     {
 798     new (p) _Val(v);
 799     }
 800   void destroy(_Val* p)
 801     {
 802     (void)p;
 803     p->~_Val();
 804     }
 805
 806   _Node* _M_new_node(const value_type& __obj)
 807   {
 808     _Node* __n = _M_get_node();
 809     __n->_M_next = 0;
 810     try {
 811       construct(&__n->_M_val, __obj);
 812       return __n;
 813     }
 814     catch(...) {_M_put_node(__n); throw;}
 815   }
 816
 817   void _M_delete_node(_Node* __n)
 818   {
 819     destroy(&__n->_M_val);
 820     _M_put_node(__n);
 821   }
 822
 823   void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
 824   void _M_erase_bucket(const size_type __n, _Node* __last);
 825
 826   void _M_copy_from(const hashtable& __ht);
 827
 828 };
 829
 830 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 831           class _All>
 832 _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
 833 _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
 834 {
 835   const _Node* __old = _M_cur;
 836   _M_cur = _M_cur->_M_next;
 837   if (!_M_cur) {
 838     size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 839     while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 840       _M_cur = _M_ht->_M_buckets[__bucket];
 841   }
 842   return *this;
 843 }
 844
 845 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 846           class _All>
 847 inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>
 848 _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
 849 {
 850   iterator __tmp = *this;
 851   ++*this;
 852   return __tmp;
 853 }
 854
 855 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 856           class _All>
 857 _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>&
 858 _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++()
 859 {
 860   const _Node* __old = _M_cur;
 861   _M_cur = _M_cur->_M_next;
 862   if (!_M_cur) {
 863     size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
 864     while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
 865       _M_cur = _M_ht->_M_buckets[__bucket];
 866   }
 867   return *this;
 868 }
 869
 870 template <class _Val, class _Key, class _HF, class _ExK, class _EqK,
 871           class _All>
 872 inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>
 873 _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int)
 874 {
 875   const_iterator __tmp = *this;
 876   ++*this;
 877   return __tmp;
 878 }
 879
 880 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 881 bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
 882                 const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2)
 883 {
 884   typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node;
 885   if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
 886     return false;
 887   for (int __n = 0; __n < __ht1._M_buckets.size(); ++__n) {
 888     _Node* __cur1 = __ht1._M_buckets[__n];
 889     _Node* __cur2 = __ht2._M_buckets[__n];
 890     for ( ; __cur1 && __cur2 && __cur1->_M_val == __cur2->_M_val;
 891           __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
 892       {}
 893     if (__cur1 || __cur2)
 894       return false;
 895   }
 896   return true;
 897 }
 898
 899 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 900 inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1,
 901                        const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) {
 902   return !(__ht1 == __ht2);
 903 }
 904
 905 template <class _Val, class _Key, class _HF, class _Extract, class _EqKey,
 906           class _All>
 907 inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
 908                  hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) {
 909   __ht1.swap(__ht2);
 910 }
 911
 912 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 913 @KWSYS_NAMESPACE@_stl::pair<@KWSYS_NAMESPACE@_CXX_DECL_TYPENAME hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
 914 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 915   ::insert_unique_noresize(const value_type& __obj)
 916 {
 917   const size_type __n = _M_bkt_num(__obj);
 918   _Node* __first = _M_buckets[__n];
 919
 920   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 921     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 922       return @KWSYS_NAMESPACE@_stl::pair<iterator, bool>(iterator(__cur, this), false);
 923
 924   _Node* __tmp = _M_new_node(__obj);
 925   __tmp->_M_next = __first;
 926   _M_buckets[__n] = __tmp;
 927   ++_M_num_elements;
 928   return @KWSYS_NAMESPACE@_stl::pair<iterator, bool>(iterator(__tmp, this), true);
 929 }
 930
 931 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 932 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
 933 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
 934   ::insert_equal_noresize(const value_type& __obj)
 935 {
 936   const size_type __n = _M_bkt_num(__obj);
 937   _Node* __first = _M_buckets[__n];
 938
 939   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 940     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
 941       _Node* __tmp = _M_new_node(__obj);
 942       __tmp->_M_next = __cur->_M_next;
 943       __cur->_M_next = __tmp;
 944       ++_M_num_elements;
 945       return iterator(__tmp, this);
 946     }
 947
 948   _Node* __tmp = _M_new_node(__obj);
 949   __tmp->_M_next = __first;
 950   _M_buckets[__n] = __tmp;
 951   ++_M_num_elements;
 952   return iterator(__tmp, this);
 953 }
 954
 955 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 956 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference
 957 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj)
 958 {
 959   resize(_M_num_elements + 1);
 960
 961   size_type __n = _M_bkt_num(__obj);
 962   _Node* __first = _M_buckets[__n];
 963
 964   for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
 965     if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
 966       return __cur->_M_val;
 967
 968   _Node* __tmp = _M_new_node(__obj);
 969   __tmp->_M_next = __first;
 970   _M_buckets[__n] = __tmp;
 971   ++_M_num_elements;
 972   return __tmp->_M_val;
 973 }
 974
 975 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 976 @KWSYS_NAMESPACE@_stl::pair<@KWSYS_NAMESPACE@_CXX_DECL_TYPENAME hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator,
 977      @KWSYS_NAMESPACE@_CXX_DECL_TYPENAME hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator>
 978 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key)
 979 {
 980   typedef @KWSYS_NAMESPACE@_stl::pair<iterator, iterator> _Pii;
 981   const size_type __n = _M_bkt_num_key(__key);
 982
 983   for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next)
 984     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
 985       for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next)
 986         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
 987           return _Pii(iterator(__first, this), iterator(__cur, this));
 988       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
 989         if (_M_buckets[__m])
 990           return _Pii(iterator(__first, this),
 991                      iterator(_M_buckets[__m], this));
 992       return _Pii(iterator(__first, this), end());
 993     }
 994   return _Pii(end(), end());
 995 }
 996
 997 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
 998 @KWSYS_NAMESPACE@_stl::pair<@KWSYS_NAMESPACE@_CXX_DECL_TYPENAME hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator,
 999      @KWSYS_NAMESPACE@_CXX_DECL_TYPENAME hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator>
1000 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1001   ::equal_range(const key_type& __key) const
1002 {
1003   typedef @KWSYS_NAMESPACE@_stl::pair<const_iterator, const_iterator> _Pii;
1004   const size_type __n = _M_bkt_num_key(__key);
1005
1006   for (const _Node* __first = _M_buckets[__n] ;
1007        __first;
1008        __first = __first->_M_next) {
1009     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1010       for (const _Node* __cur = __first->_M_next;
1011            __cur;
1012            __cur = __cur->_M_next)
1013         if (!_M_equals(_M_get_key(__cur->_M_val), __key))
1014           return _Pii(const_iterator(__first, this),
1015                       const_iterator(__cur, this));
1016       for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
1017         if (_M_buckets[__m])
1018           return _Pii(const_iterator(__first, this),
1019                       const_iterator(_M_buckets[__m], this));
1020       return _Pii(const_iterator(__first, this), end());
1021     }
1022   }
1023   return _Pii(end(), end());
1024 }
1025
1026 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1027 typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
1028 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
1029 {
1030   const size_type __n = _M_bkt_num_key(__key);
1031   _Node* __first = _M_buckets[__n];
1032   size_type __erased = 0;
1033
1034   if (__first) {
1035     _Node* __cur = __first;
1036     _Node* __next = __cur->_M_next;
1037     while (__next) {
1038       if (_M_equals(_M_get_key(__next->_M_val), __key)) {
1039         __cur->_M_next = __next->_M_next;
1040         _M_delete_node(__next);
1041         __next = __cur->_M_next;
1042         ++__erased;
1043         --_M_num_elements;
1044       }
1045       else {
1046         __cur = __next;
1047         __next = __cur->_M_next;
1048       }
1049     }
1050     if (_M_equals(_M_get_key(__first->_M_val), __key)) {
1051       _M_buckets[__n] = __first->_M_next;
1052       _M_delete_node(__first);
1053       ++__erased;
1054       --_M_num_elements;
1055     }
1056   }
1057   return __erased;
1058 }
1059
1060 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1061 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it)
1062 {
1063   _Node* __p = __it._M_cur;
1064   if (__p) {
1065     const size_type __n = _M_bkt_num(__p->_M_val);
1066     _Node* __cur = _M_buckets[__n];
1067
1068     if (__cur == __p) {
1069       _M_buckets[__n] = __cur->_M_next;
1070       _M_delete_node(__cur);
1071       --_M_num_elements;
1072     }
1073     else {
1074       _Node* __next = __cur->_M_next;
1075       while (__next) {
1076         if (__next == __p) {
1077           __cur->_M_next = __next->_M_next;
1078           _M_delete_node(__next);
1079           --_M_num_elements;
1080           break;
1081         }
1082         else {
1083           __cur = __next;
1084           __next = __cur->_M_next;
1085         }
1086       }
1087     }
1088   }
1089 }
1090
1091 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1092 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1093   ::erase(iterator __first, iterator __last)
1094 {
1095   size_type __f_bucket = __first._M_cur ?
1096     _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size();
1097   size_type __l_bucket = __last._M_cur ?
1098     _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size();
1099
1100   if (__first._M_cur == __last._M_cur)
1101     return;
1102   else if (__f_bucket == __l_bucket)
1103     _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
1104   else {
1105     _M_erase_bucket(__f_bucket, __first._M_cur, 0);
1106     for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
1107       _M_erase_bucket(__n, 0);
1108     if (__l_bucket != _M_buckets.size())
1109       _M_erase_bucket(__l_bucket, __last._M_cur);
1110   }
1111 }
1112
1113 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1114 inline void
1115 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first,
1116                                              const_iterator __last)
1117 {
1118   erase(iterator(const_cast<_Node*>(__first._M_cur),
1119                  const_cast<hashtable*>(__first._M_ht)),
1120         iterator(const_cast<_Node*>(__last._M_cur),
1121                  const_cast<hashtable*>(__last._M_ht)));
1122 }
1123
1124 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1125 inline void
1126 hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it)
1127 {
1128   erase(iterator(const_cast<_Node*>(__it._M_cur),
1129                  const_cast<hashtable*>(__it._M_ht)));
1130 }
1131
1132 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1133 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1134   ::resize(size_type __num_elements_hint)
1135 {
1136   const size_type __old_n = _M_buckets.size();
1137   if (__num_elements_hint > __old_n) {
1138     const size_type __n = _M_next_size(__num_elements_hint);
1139     if (__n > __old_n) {
1140       _M_buckets_type __tmp(
1141         __n, (_Node*)(0)
1142         @KWSYS_NAMESPACE@_HASH_BUCKETS_GET_ALLOCATOR(_M_buckets));
1143       try {
1144         for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
1145           _Node* __first = _M_buckets[__bucket];
1146           while (__first) {
1147             size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
1148             _M_buckets[__bucket] = __first->_M_next;
1149             __first->_M_next = __tmp[__new_bucket];
1150             __tmp[__new_bucket] = __first;
1151             __first = _M_buckets[__bucket];
1152           }
1153         }
1154         _M_buckets.swap(__tmp);
1155       }
1156       catch(...) {
1157         for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) {
1158           while (__tmp[__bucket]) {
1159             _Node* __next = __tmp[__bucket]->_M_next;
1160             _M_delete_node(__tmp[__bucket]);
1161             __tmp[__bucket] = __next;
1162           }
1163         }
1164         throw;
1165       }
1166     }
1167   }
1168 }
1169
1170 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1171 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1172   ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
1173 {
1174   _Node* __cur = _M_buckets[__n];
1175   if (__cur == __first)
1176     _M_erase_bucket(__n, __last);
1177   else {
1178     _Node* __next;
1179     for (__next = __cur->_M_next;
1180          __next != __first;
1181          __cur = __next, __next = __cur->_M_next)
1182       ;
1183     while (__next != __last) {
1184       __cur->_M_next = __next->_M_next;
1185       _M_delete_node(__next);
1186       __next = __cur->_M_next;
1187       --_M_num_elements;
1188     }
1189   }
1190 }
1191
1192 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1193 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1194   ::_M_erase_bucket(const size_type __n, _Node* __last)
1195 {
1196   _Node* __cur = _M_buckets[__n];
1197   while (__cur != __last) {
1198     _Node* __next = __cur->_M_next;
1199     _M_delete_node(__cur);
1200     __cur = __next;
1201     _M_buckets[__n] = __cur;
1202     --_M_num_elements;
1203   }
1204 }
1205
1206 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1207 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear()
1208 {
1209   for (size_type __i = 0; __i < _M_buckets.size(); ++__i) {
1210     _Node* __cur = _M_buckets[__i];
1211     while (__cur != 0) {
1212       _Node* __next = __cur->_M_next;
1213       _M_delete_node(__cur);
1214       __cur = __next;
1215     }
1216     _M_buckets[__i] = 0;
1217   }
1218   _M_num_elements = 0;
1219 }
1220
1221
1222 template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
1223 void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
1224   ::_M_copy_from(const hashtable& __ht)
1225 {
1226   _M_buckets.clear();
1227   _M_buckets.reserve(__ht._M_buckets.size());
1228   _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
1229   try {
1230     for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
1231       const _Node* __cur = __ht._M_buckets[__i];
1232       if (__cur) {
1233         _Node* __copy = _M_new_node(__cur->_M_val);
1234         _M_buckets[__i] = __copy;
1235
1236         for (_Node* __next = __cur->_M_next;
1237              __next;
1238              __cur = __next, __next = __cur->_M_next) {
1239           __copy->_M_next = _M_new_node(__next->_M_val);
1240           __copy = __copy->_M_next;
1241         }
1242       }
1243     }
1244     _M_num_elements = __ht._M_num_elements;
1245   }
1246   catch(...) {clear(); throw;}
1247 }
1248
1249 } // namespace @KWSYS_NAMESPACE@
1250
1251 // Normally the comparison operators should be found in the @KWSYS_NAMESPACE@
1252 // namespace by argument dependent lookup.  For compilers that do not
1253 // support it we must bring them into the global namespace now.
1254 #if !@KWSYS_NAMESPACE@_CXX_HAS_ARGUMENT_DEPENDENT_LOOKUP
1255 using @KWSYS_NAMESPACE@::operator==;
1256 using @KWSYS_NAMESPACE@::operator!=;
1257 #endif
1258
1259 #if defined(_MSC_VER)
1260 # pragma warning (pop)
1261 #endif
1262
1263 #endif