include/c++/stl/stl/_hashtable.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Copyright (c) 1996,1997
   7  * Silicon Graphics Computer Systems, Inc.
   8  *
   9  * Copyright (c) 1997
  10  * Moscow Center for SPARC Technology
  11  *
  12  * Copyright (c) 1999
  13  * Boris Fomitchev
  14  *
  15  * This material is provided "as is", with absolutely no warranty expressed
  16  * or implied. Any use is at your own risk.
  17  *
  18  * Permission to use or copy this software for any purpose is hereby granted
  19  * without fee, provided the above notices are retained on all copies.
  20  * Permission to modify the code and to distribute modified code is granted,
  21  * provided the above notices are retained, and a notice that the code was
  22  * modified is included with the above copyright notice.
  23  *
  24  */
  25
  26 /* NOTE: This is an internal header file, included by other STL headers.
  27  *   You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _STLP_INTERNAL_HASHTABLE_H
  31 #define _STLP_INTERNAL_HASHTABLE_H
  32
  33 #ifndef _STLP_INTERNAL_VECTOR_H
  34 #  include <stl/_vector.h>
  35 #endif
  36
  37 #ifndef _STLP_INTERNAL_SLIST_H
  38 #  include <stl/_slist.h>
  39 #endif
  40
  41 #ifndef _STLP_INTERNAL_ITERATOR_H
  42 #  include <stl/_iterator.h>
  43 #endif
  44
  45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
  46 #  include <stl/_function_base.h>
  47 #endif
  48
  49 #ifndef _STLP_INTERNAL_ALGOBASE_H
  50 #  include <stl/_algobase.h>
  51 #endif
  52
  53 #ifndef _STLP_HASH_FUN_H
  54 #  include <stl/_hash_fun.h>
  55 #endif
  56
  57 /*
  58  * Hashtable class, used to implement the hashed associative containers
  59  * hash_set, hash_map, hash_multiset, hash_multimap,
  60  * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
  61  */
  62
  63 _STLP_BEGIN_NAMESPACE
  64
  65 #if defined (_STLP_USE_TEMPLATE_EXPORT)
  66 //Export of the classes used to represent buckets in the hashtable implementation.
  67 #  if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
  68 //If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
  69 //storage type for which internal classes have already been exported.
  70 _STLP_EXPORT_TEMPLATE_CLASS allocator<_STLP_PRIV _Slist_node_base*>;
  71
  72 _STLP_MOVE_TO_PRIV_NAMESPACE
  73 _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Slist_node_base**, _Slist_node_base*,
  74                                               allocator<_Slist_node_base*> >;
  75 _STLP_EXPORT_TEMPLATE_CLASS _Vector_base<_Slist_node_base*,
  76                                          allocator<_Slist_node_base*> >;
  77 _STLP_MOVE_TO_STD_NAMESPACE
  78 #  endif
  79
  80 #  if defined (_STLP_DEBUG)
  81 _STLP_MOVE_TO_PRIV_NAMESPACE
  82 #    define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
  83 _STLP_EXPORT_TEMPLATE_CLASS __construct_checker<_STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> > >;
  84 _STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
  85 #    undef _STLP_NON_DBG_VECTOR
  86 _STLP_MOVE_TO_STD_NAMESPACE
  87 #  endif
  88
  89 _STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*,
  90                                    allocator<_STLP_PRIV _Slist_node_base*> >;
  91 #endif
  92
  93 #if defined (_STLP_DEBUG)
  94 #  define hashtable _STLP_NON_DBG_NAME(hashtable)
  95 _STLP_MOVE_TO_PRIV_NAMESPACE
  96 #endif
  97
  98 // some compilers require the names of template parameters to be the same
  99 template <class _Val, class _Key, class _HF,
 100           class _Traits, class _ExK, class _EqK, class _All>
 101 class hashtable;
 102
 103 #if !defined (_STLP_DEBUG)
 104 _STLP_MOVE_TO_PRIV_NAMESPACE
 105 #endif
 106
 107 template <class _BaseIte, class _Traits>
 108 struct _Ht_iterator {
 109   typedef typename _Traits::_ConstTraits _ConstTraits;
 110   typedef typename _Traits::_NonConstTraits _NonConstTraits;
 111
 112   typedef _Ht_iterator<_BaseIte,_Traits> _Self;
 113
 114   typedef typename _Traits::value_type value_type;
 115   typedef typename _Traits::pointer pointer;
 116   typedef typename _Traits::reference reference;
 117   typedef forward_iterator_tag iterator_category;
 118   typedef ptrdiff_t difference_type;
 119   typedef size_t size_type;
 120
 121   typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator;
 122   typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator;
 123
 124   _Ht_iterator() {}
 125   //copy constructor for iterator and constructor from iterator for const_iterator
 126   _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {}
 127   _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
 128
 129   reference operator*() const {
 130     return *_M_ite;
 131   }
 132   _STLP_DEFINE_ARROW_OPERATOR
 133
 134   _Self& operator++() {
 135     ++_M_ite;
 136     return *this;
 137   }
 138   _Self operator++(int) {
 139     _Self __tmp = *this;
 140     ++*this;
 141     return __tmp;
 142   }
 143
 144   bool operator == (const_iterator __rhs) const {
 145     return _M_ite == __rhs._M_ite;
 146   }
 147   bool operator != (const_iterator __rhs) const {
 148     return _M_ite != __rhs._M_ite;
 149   }
 150
 151   _BaseIte _M_ite;
 152 };
 153
 154 _STLP_MOVE_TO_STD_NAMESPACE
 155
 156 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 157 template <class _BaseIte, class _Traits>
 158 struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
 159   typedef __false_type   has_trivial_default_constructor;
 160   typedef __true_type    has_trivial_copy_constructor;
 161   typedef __true_type    has_trivial_assignment_operator;
 162   typedef __true_type    has_trivial_destructor;
 163   typedef __false_type   is_POD_type;
 164 };
 165 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 166
 167 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
 168 template <class _BaseIte, class _Traits>
 169 inline
 170 #  if defined (_STLP_NESTED_TYPE_PARAM_BUG)
 171 _STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
 172 #  else
 173 _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type *
 174 #  endif
 175 value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
 176   typedef typename _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val;
 177   return (_Val*) 0;
 178 }
 179 template <class _BaseIte, class _Traits>
 180 inline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
 181 { return forward_iterator_tag(); }
 182 template <class _BaseIte, class _Traits>
 183 inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
 184 { return (ptrdiff_t*) 0; }
 185 #endif
 186
 187 _STLP_MOVE_TO_PRIV_NAMESPACE
 188
 189 template <class _Dummy>
 190 class _Stl_prime {
 191 public:
 192   //Returns the maximum number of buckets handled by the hashtable implementation
 193   static size_t _STLP_CALL _S_max_nb_buckets();
 194
 195   //Returns the bucket size next to a required size
 196   static size_t _STLP_CALL _S_next_size(size_t);
 197 };
 198
 199 #if defined (_STLP_USE_TEMPLATE_EXPORT)
 200 _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
 201 #endif
 202
 203 typedef _Stl_prime<bool> _Stl_prime_type;
 204
 205 #if !defined (_STLP_DEBUG)
 206 _STLP_MOVE_TO_STD_NAMESPACE
 207 #endif
 208
 209 /*
 210  * Hashtables handle allocators a bit differently than other containers
 211  * do. If we're using standard-conforming allocators, then a hashtable
 212  * unconditionally has a member variable to hold its allocator, even if
 213  * it so happens that all instances of the allocator type are identical.
 214  * This is because, for hashtables, this extra storage is negligible.
 215  * Additionally, a base class wouldn't serve any other purposes; it
 216  * wouldn't, for example, simplify the exception-handling code.
 217  */
 218 template <class _Val, class _Key, class _HF,
 219           class _Traits, class _ExK, class _EqK, class _All>
 220 class hashtable {
 221   typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
 222   typedef typename _Traits::_NonConstTraits _NonConstTraits;
 223   typedef typename _Traits::_ConstTraits _ConstTraits;
 224   typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
 225   typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
 226
 227 public:
 228   typedef _Key key_type;
 229   typedef _Val value_type;
 230   typedef _HF hasher;
 231   typedef _EqK key_equal;
 232
 233   typedef size_t            size_type;
 234   typedef ptrdiff_t         difference_type;
 235   typedef typename _NonConstTraits::pointer pointer;
 236   typedef const value_type* const_pointer;
 237   typedef typename _NonConstTraits::reference reference;
 238   typedef const value_type& const_reference;
 239   typedef forward_iterator_tag _Iterator_category;
 240
 241   hasher hash_funct() const { return _M_hash; }
 242   key_equal key_eq() const { return _M_equals; }
 243
 244 private:
 245   _STLP_FORCE_ALLOCATORS(_Val, _All)
 246 #if defined (_STLP_DEBUG)
 247   typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
 248 #else
 249   typedef slist<value_type, _All> _ElemsCont;
 250 #endif
 251   typedef typename _ElemsCont::iterator _ElemsIte;
 252   typedef typename _ElemsCont::const_iterator _ElemsConstIte;
 253   typedef _STLP_PRIV _Slist_node_base _BucketType;
 254   typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _M_bucket_allocator_type;
 255   /*
 256    * We are going to use vector of _Slist_node_base pointers for 2 reasons:
 257    *  - limit code bloat, all hashtable instanciation use the same buckets representation.
 258    *  - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
 259    *    method would be too slow because the slist::splice_after method become linear on
 260    *    the number of iterators in the buckets rather than constant in time as the iterator
 261    *    has to be move from a slist to the other.
 262    */
 263 #if defined (_STLP_DEBUG)
 264   typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _M_bucket_allocator_type> _BucketVector;
 265 #else
 266   typedef vector<_BucketType*, _M_bucket_allocator_type> _BucketVector;
 267 #endif
 268
 269   hasher                _M_hash;
 270   key_equal             _M_equals;
 271   _ExK                  _M_get_key;
 272   _ElemsCont            _M_elems;
 273   _BucketVector         _M_buckets;
 274   size_type             _M_num_elements;
 275   float                 _M_max_load_factor;
 276   _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
 277
 278 public:
 279   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator;
 280   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator;
 281   //TODO: Avoids this debug check and make the local_iterator different from
 282   //iterator in debug mode too.
 283 #if !defined (_STLP_DEBUG)
 284   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator;
 285   typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator;
 286 #else
 287   typedef iterator       local_iterator;
 288   typedef const_iterator const_local_iterator;
 289 #endif
 290
 291   typedef typename _Alloc_traits<_Val, _All>::allocator_type allocator_type;
 292   allocator_type get_allocator() const { return _M_elems.get_allocator(); }
 293
 294 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 295   hashtable(size_type __n,
 296             const _HF&  __hf,
 297             const _EqK& __eql,
 298             const _ExK& __ext,
 299             const allocator_type& __a = allocator_type())
 300 #else
 301   hashtable(size_type __n,
 302             const _HF&  __hf,
 303             const _EqK& __eql,
 304             const _ExK& __ext)
 305     : _M_hash(__hf),
 306       _M_equals(__eql),
 307       _M_get_key(__ext),
 308       _M_elems(allocator_type()),
 309       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
 310       _M_num_elements(0),
 311       _M_max_load_factor(1.0f)
 312   { _M_initialize_buckets(__n); }
 313
 314   hashtable(size_type __n,
 315             const _HF&  __hf,
 316             const _EqK& __eql,
 317             const _ExK& __ext,
 318             const allocator_type& __a)
 319 #endif
 320     : _M_hash(__hf),
 321       _M_equals(__eql),
 322       _M_get_key(__ext),
 323       _M_elems(__a),
 324       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
 325       _M_num_elements(0),
 326       _M_max_load_factor(1.0f)
 327   { _M_initialize_buckets(__n); }
 328
 329 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
 330   hashtable(size_type __n,
 331             const _HF&    __hf,
 332             const _EqK&   __eql,
 333             const allocator_type& __a = allocator_type())
 334 #else
 335   hashtable(size_type __n,
 336             const _HF&    __hf,
 337             const _EqK&   __eql)
 338     : _M_hash(__hf),
 339       _M_equals(__eql),
 340       _M_get_key(_ExK()),
 341       _M_elems(allocator_type()),
 342       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
 343       _M_num_elements(0),
 344       _M_max_load_factor(1.0f)
 345   { _M_initialize_buckets(__n); }
 346
 347   hashtable(size_type __n,
 348             const _HF&    __hf,
 349             const _EqK&   __eql,
 350             const allocator_type& __a)
 351 #endif
 352     : _M_hash(__hf),
 353       _M_equals(__eql),
 354       _M_get_key(_ExK()),
 355       _M_elems(__a),
 356       _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
 357       _M_num_elements(0),
 358       _M_max_load_factor(1.0f)
 359   { _M_initialize_buckets(__n); }
 360
 361   hashtable(const _Self& __ht)
 362     : _M_hash(__ht._M_hash),
 363       _M_equals(__ht._M_equals),
 364       _M_get_key(__ht._M_get_key),
 365       _M_elems(__ht.get_allocator()),
 366       _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
 367       _M_num_elements(0),
 368       _M_max_load_factor(1.0f)
 369   { _M_copy_from(__ht); }
 370
 371   hashtable(__move_source<_Self> src)
 372     : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
 373       _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
 374       _M_get_key(_STLP_PRIV _AsMoveSource(src.get()._M_get_key)),
 375       _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
 376       _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
 377       _M_num_elements(src.get()._M_num_elements),
 378       _M_max_load_factor(src.get()._M_max_load_factor) {}
 379
 380   _Self& operator= (const _Self& __ht) {
 381     if (&__ht != this) {
 382       clear();
 383       _M_hash = __ht._M_hash;
 384       _M_equals = __ht._M_equals;
 385       _M_get_key = __ht._M_get_key;
 386       _M_copy_from(__ht);
 387     }
 388     return *this;
 389   }
 390
 391   ~hashtable() { clear(); }
 392
 393   size_type size() const { return _M_num_elements; }
 394   size_type max_size() const { return size_type(-1); }
 395   bool empty() const { return size() == 0; }
 396
 397   void swap(_Self& __ht) {
 398     _STLP_STD::swap(_M_hash, __ht._M_hash);
 399     _STLP_STD::swap(_M_equals, __ht._M_equals);
 400     _STLP_STD::swap(_M_get_key, __ht._M_get_key);
 401     _M_elems.swap(__ht._M_elems);
 402     _M_buckets.swap(__ht._M_buckets);
 403     _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
 404     _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
 405   }
 406
 407   iterator begin() { return _M_elems.begin(); }
 408   iterator end() { return _M_elems.end(); }
 409   local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
 410   local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }
 411
 412   const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
 413   const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
 414   const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
 415   const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }
 416
 417   //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
 418
 419 public:
 420   //The number of buckets is size() - 1 because the last bucket always contains
 421   //_M_elems.end() to make algo easier to implement.
 422   size_type bucket_count() const { return _M_buckets.size() - 1; }
 423   size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
 424   size_type elems_in_bucket(size_type __bucket) const
 425   { return distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
 426
 427   _STLP_TEMPLATE_FOR_CONT_EXT
 428   size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
 429
 430   // hash policy
 431   float load_factor() const { return (float)size() / (float)bucket_count(); }
 432   float max_load_factor() const { return _M_max_load_factor; }
 433   void max_load_factor(float __z) { _M_max_load_factor = __z;}
 434
 435   pair<iterator, bool> insert_unique(const value_type& __obj) {
 436     resize(_M_num_elements + 1);
 437     return insert_unique_noresize(__obj);
 438   }
 439
 440   iterator insert_equal(const value_type& __obj) {
 441     resize(_M_num_elements + 1);
 442     return insert_equal_noresize(__obj);
 443   }
 444
 445 protected:
 446   iterator _M_insert_noresize(size_type __n, const value_type& __obj);
 447 public:
 448   pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
 449   iterator insert_equal_noresize(const value_type& __obj);
 450
 451 #if defined (_STLP_MEMBER_TEMPLATES)
 452   template <class _InputIterator>
 453   void insert_unique(_InputIterator __f, _InputIterator __l)
 454   { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
 455
 456   template <class _InputIterator>
 457   void insert_equal(_InputIterator __f, _InputIterator __l)
 458   { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
 459
 460   template <class _InputIterator>
 461   void insert_unique(_InputIterator __f, _InputIterator __l,
 462                      const input_iterator_tag &) {
 463     for ( ; __f != __l; ++__f)
 464       insert_unique(*__f);
 465   }
 466
 467   template <class _InputIterator>
 468   void insert_equal(_InputIterator __f, _InputIterator __l,
 469                     const input_iterator_tag &) {
 470     for ( ; __f != __l; ++__f)
 471       insert_equal(*__f);
 472   }
 473
 474   template <class _ForwardIterator>
 475   void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
 476                      const forward_iterator_tag &) {
 477     size_type __n = distance(__f, __l);
 478     resize(_M_num_elements + __n);
 479     for ( ; __n > 0; --__n, ++__f)
 480       insert_unique_noresize(*__f);
 481   }
 482
 483   template <class _ForwardIterator>
 484   void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
 485                     const forward_iterator_tag &) {
 486     size_type __n = distance(__f, __l);
 487     resize(_M_num_elements + __n);
 488     for ( ; __n > 0; --__n, ++__f)
 489       insert_equal_noresize(*__f);
 490   }
 491
 492 #else /* _STLP_MEMBER_TEMPLATES */
 493   void insert_unique(const value_type* __f, const value_type* __l) {
 494     size_type __n = __l - __f;
 495     resize(_M_num_elements + __n);
 496     for ( ; __n > 0; --__n, ++__f)
 497       insert_unique_noresize(*__f);
 498   }
 499
 500   void insert_equal(const value_type* __f, const value_type* __l) {
 501     size_type __n = __l - __f;
 502     resize(_M_num_elements + __n);
 503     for ( ; __n > 0; --__n, ++__f)
 504       insert_equal_noresize(*__f);
 505   }
 506
 507   void insert_unique(const_iterator __f, const_iterator __l) {
 508     size_type __n = distance(__f, __l);
 509     resize(_M_num_elements + __n);
 510     for ( ; __n > 0; --__n, ++__f)
 511       insert_unique_noresize(*__f);
 512   }
 513
 514   void insert_equal(const_iterator __f, const_iterator __l) {
 515     size_type __n = distance(__f, __l);
 516     resize(_M_num_elements + __n);
 517     for ( ; __n > 0; --__n, ++__f)
 518       insert_equal_noresize(*__f);
 519   }
 520 #endif /*_STLP_MEMBER_TEMPLATES */
 521
 522   //reference find_or_insert(const value_type& __obj);
 523
 524 private:
 525   _STLP_TEMPLATE_FOR_CONT_EXT
 526   _ElemsIte _M_find(const _KT& __key) const {
 527     size_type __n = _M_bkt_num_key(__key);
 528     _ElemsIte __first(_M_buckets[__n]);
 529     _ElemsIte __last(_M_buckets[__n + 1]);
 530     for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
 531     if (__first != __last)
 532       return __first;
 533     else
 534       return __CONST_CAST(_ElemsCont&, _M_elems).end();
 535   }
 536
 537 public:
 538   _STLP_TEMPLATE_FOR_CONT_EXT
 539   iterator find(const _KT& __key) { return _M_find(__key); }
 540   _STLP_TEMPLATE_FOR_CONT_EXT
 541   const_iterator find(const _KT& __key) const { return _M_find(__key); }
 542
 543   _STLP_TEMPLATE_FOR_CONT_EXT
 544   size_type count(const _KT& __key) const {
 545     const size_type __n = _M_bkt_num_key(__key);
 546
 547     _ElemsIte __cur(_M_buckets[__n]);
 548     _ElemsIte __last(_M_buckets[__n + 1]);
 549     for (; __cur != __last; ++__cur) {
 550       if (_M_equals(_M_get_key(*__cur), __key)) {
 551         size_type __result = 1;
 552         for (++__cur;
 553              __cur != __last && _M_equals(_M_get_key(*__cur), __key);
 554              ++__result, ++__cur);
 555         return __result;
 556       }
 557     }
 558     return 0;
 559   }
 560
 561   _STLP_TEMPLATE_FOR_CONT_EXT
 562   pair<iterator, iterator> equal_range(const _KT& __key) {
 563     typedef pair<iterator, iterator> _Pii;
 564     const size_type __n = _M_bkt_num_key(__key);
 565
 566     for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
 567          __first != __last; ++__first) {
 568       if (_M_equals(_M_get_key(*__first), __key)) {
 569         _ElemsIte __cur(__first);
 570         for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
 571         return _Pii(__first, __cur);
 572       }
 573     }
 574     return _Pii(end(), end());
 575   }
 576
 577   _STLP_TEMPLATE_FOR_CONT_EXT
 578   pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
 579     typedef pair<const_iterator, const_iterator> _Pii;
 580     const size_type __n = _M_bkt_num_key(__key);
 581
 582     for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
 583          __first != __last; ++__first) {
 584       if (_M_equals(_M_get_key(*__first), __key)) {
 585         _ElemsIte __cur(__first);
 586         for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
 587         return _Pii(__first, __cur);
 588       }
 589     }
 590     return _Pii(end(), end());
 591   }
 592
 593   size_type erase(const key_type& __key);
 594   void erase(const_iterator __it);
 595   void erase(const_iterator __first, const_iterator __last);
 596
 597 private:
 598   void _M_rehash(size_type __num_buckets);
 599 #if defined (_STLP_DEBUG)
 600   void _M_check() const;
 601 #endif
 602
 603 public:
 604   void rehash(size_type __num_buckets_hint);
 605   void resize(size_type __num_elements_hint);
 606   void clear();
 607
 608   // this is for hash_map::operator[]
 609   reference _M_insert(const value_type& __obj);
 610
 611 private:
 612   //__n is set to the first bucket that has to be modified if any
 613   //erase/insert operation is done after the returned iterator.
 614   iterator _M_before_begin(size_type &__n) const;
 615
 616   static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
 617                                   size_type &__n);
 618
 619   void _M_initialize_buckets(size_type __n) {
 620     const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
 621     _M_buckets.reserve(__n_buckets);
 622     _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
 623   }
 624
 625   _STLP_TEMPLATE_FOR_CONT_EXT
 626   size_type _M_bkt_num_key(const _KT& __key) const
 627   { return _M_bkt_num_key(__key, bucket_count()); }
 628
 629   size_type _M_bkt_num(const value_type& __obj) const
 630   { return _M_bkt_num_key(_M_get_key(__obj)); }
 631
 632   _STLP_TEMPLATE_FOR_CONT_EXT
 633   size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
 634   { return _M_hash(__key) % __n; }
 635
 636   size_type _M_bkt_num(const value_type& __obj, size_t __n) const
 637   { return _M_bkt_num_key(_M_get_key(__obj), __n); }
 638
 639   void _M_copy_from(const _Self& __ht);
 640 };
 641
 642 #if defined (_STLP_DEBUG)
 643 #  undef hashtable
 644 _STLP_MOVE_TO_STD_NAMESPACE
 645 #endif
 646
 647 _STLP_END_NAMESPACE
 648
 649 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
 650 #  include <stl/_hashtable.c>
 651 #endif
 652
 653 #if defined (_STLP_DEBUG)
 654 #  include <stl/debug/_hashtable.h>
 655 #endif
 656
 657 _STLP_BEGIN_NAMESPACE
 658
 659 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
 660 #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
 661 #include <stl/_relops_hash_cont.h>
 662 #undef _STLP_TEMPLATE_CONTAINER
 663 #undef _STLP_TEMPLATE_HEADER
 664
 665 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 666 template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
 667 struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
 668   //Hashtables are movable:
 669   typedef __stlp_movable implemented;
 670
 671   //Completeness depends on many template parameters, for the moment we consider it not complete:
 672   typedef __false_type complete;
 673 };
 674 #endif
 675
 676 _STLP_END_NAMESPACE
 677
 678 #endif /* _STLP_INTERNAL_HASHTABLE_H */
 679
 680 // Local Variables:
 681 // mode:C++
 682 // End: