19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1994
49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hewlett-Packard Company
59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997
79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc.
89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1997
109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Moscow Center for SPARC Technology
119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999
139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev
149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed
169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk.
179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted
199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies.
209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted,
219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was
229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice.
239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *
249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* NOTE: This is an internal header file, included by other STL headers.
279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *   You should not attempt to use it directly.
289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_HASHTABLE_H
319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_INTERNAL_HASHTABLE_H
329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_VECTOR_H
349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_vector.h>
359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_SLIST_H
389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_slist.h>
399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ITERATOR_H
429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_iterator.h>
439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_function_base.h>
479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ALGOBASE_H
509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_algobase.h>
519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_HASH_FUN_H
549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_hash_fun.h>
559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hashtable class, used to implement the hashed associative containers
599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * hash_set, hash_map, hash_multiset, hash_multimap,
609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE
649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_TEMPLATE_EXPORT)
669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//Export of the classes used to represent buckets in the hashtable implementation.
679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block//storage type for which internal classes have already been exported.
709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS allocator<_STLP_PRIV _Slist_node_base*>;
719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Slist_node_base**, _Slist_node_base*,
749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                              allocator<_Slist_node_base*> >;
759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _Vector_base<_Slist_node_base*,
769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                         allocator<_Slist_node_base*> >;
779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  endif
799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  if defined (_STLP_DEBUG)
819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#    define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS __construct_checker<_STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> > >;
849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#    undef _STLP_NON_DBG_VECTOR
869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  endif
889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*,
909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                   allocator<_STLP_PRIV _Slist_node_base*> >;
919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  define hashtable _STLP_NON_DBG_NAME(hashtable)
959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// some compilers require the names of template parameters to be the same
999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF,
1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          class _Traits, class _ExK, class _EqK, class _All>
1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass hashtable;
1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG)
1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BaseIte, class _Traits>
1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct _Ht_iterator {
1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_ConstTraits _ConstTraits;
1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_NonConstTraits _NonConstTraits;
1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Ht_iterator<_BaseIte,_Traits> _Self;
1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::value_type value_type;
1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::pointer pointer;
1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::reference reference;
1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef forward_iterator_tag iterator_category;
1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef ptrdiff_t difference_type;
1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef size_t size_type;
1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator;
1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator;
1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Ht_iterator() {}
1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //copy constructor for iterator and constructor from iterator for const_iterator
1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {}
1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference operator*() const {
1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *_M_ite;
1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_DEFINE_ARROW_OPERATOR
1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator++() {
1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    ++_M_ite;
1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self operator++(int) {
1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _Self __tmp = *this;
1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    ++*this;
1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return __tmp;
1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool operator == (const_iterator __rhs) const {
1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _M_ite == __rhs._M_ite;
1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool operator != (const_iterator __rhs) const {
1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _M_ite != __rhs._M_ite;
1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _BaseIte _M_ite;
1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BaseIte, class _Traits>
1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __false_type   has_trivial_default_constructor;
1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __true_type    has_trivial_copy_constructor;
1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __true_type    has_trivial_assignment_operator;
1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __true_type    has_trivial_destructor;
1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __false_type   is_POD_type;
1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BaseIte, class _Traits>
1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline
1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  else
1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type *
1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  endif
1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvalue_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
176e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _STLP_TYPENAME _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val;
1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  return (_Val*) 0;
1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}
1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BaseIte, class _Traits>
1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return forward_iterator_tag(); }
1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _BaseIte, class _Traits>
1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (ptrdiff_t*) 0; }
1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE
1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Dummy>
1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Stl_prime {
191e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  // Returns begining of primes list and size by reference.
192e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  static const size_t* _S_primes(size_t&);
1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //Returns the maximum number of buckets handled by the hashtable implementation
1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _STLP_CALL _S_max_nb_buckets();
1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //Returns the bucket size next to a required size
1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static size_t _STLP_CALL _S_next_size(size_t);
199e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott
200e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  // Returns the bucket range containing sorted list of prime numbers <= __hint.
201e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end);
2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_TEMPLATE_EXPORT)
2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktypedef _Stl_prime<bool> _Stl_prime_type;
2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG)
2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/*
2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hashtables handle allocators a bit differently than other containers
2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * do. If we're using standard-conforming allocators, then a hashtable
2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * unconditionally has a member variable to hold its allocator, even if
2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * it so happens that all instances of the allocator type are identical.
2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This is because, for hashtables, this extra storage is negligible.
2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Additionally, a base class wouldn't serve any other purposes; it
2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * wouldn't, for example, simplify the exception-handling code.
2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */
2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF,
2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block          class _Traits, class _ExK, class _EqK, class _All>
2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass hashtable {
2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_NonConstTraits _NonConstTraits;
2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_ConstTraits _ConstTraits;
2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Key key_type;
2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _Val value_type;
2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _HF hasher;
2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _EqK key_equal;
2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef size_t            size_type;
2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef ptrdiff_t         difference_type;
2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _NonConstTraits::pointer pointer;
2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef const value_type* const_pointer;
2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _NonConstTraits::reference reference;
2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef const value_type& const_reference;
2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef forward_iterator_tag _Iterator_category;
2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hasher hash_funct() const { return _M_hash; }
2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  key_equal key_eq() const { return _M_equals; }
2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_FORCE_ALLOCATORS(_Val, _All)
2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef slist<value_type, _All> _ElemsCont;
2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _ElemsCont::iterator _ElemsIte;
2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef typename _ElemsCont::const_iterator _ElemsConstIte;
2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Slist_node_base _BucketType;
259e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _BucketAllocType;
2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  /*
2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   * We are going to use vector of _Slist_node_base pointers for 2 reasons:
2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   *  - limit code bloat, all hashtable instanciation use the same buckets representation.
2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   *  - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   *    method would be too slow because the slist::splice_after method become linear on
2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   *    the number of iterators in the buckets rather than constant in time as the iterator
2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   *    has to be move from a slist to the other.
2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block   */
2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
269e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _BucketAllocType> _BucketVector;
2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
271e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef vector<_BucketType*, _BucketAllocType> _BucketVector;
2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hasher                _M_hash;
2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  key_equal             _M_equals;
2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _ElemsCont            _M_elems;
2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _BucketVector         _M_buckets;
2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type             _M_num_elements;
2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  float                 _M_max_load_factor;
2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
282e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  static const key_type& _M_get_key(const value_type& __val) {
283e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _ExK k;
284e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    return k(__val);
285e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  }
2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator;
2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator;
2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //TODO: Avoids this debug check and make the local_iterator different from
2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //iterator in debug mode too.
2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG)
2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator;
2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator;
2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef iterator       local_iterator;
2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef const_iterator const_local_iterator;
2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
299e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef _All allocator_type;
3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  allocator_type get_allocator() const { return _M_elems.get_allocator(); }
3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hashtable(size_type __n,
3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _HF&    __hf,
3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _EqK&   __eql,
3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const allocator_type& __a = allocator_type())
3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else
3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hashtable(size_type __n,
3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _HF&    __hf,
3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _EqK&   __eql)
3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_hash(__hf),
3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_equals(__eql),
3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_elems(allocator_type()),
3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_num_elements(0),
3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_max_load_factor(1.0f)
3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _M_initialize_buckets(__n); }
3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hashtable(size_type __n,
3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _HF&    __hf,
3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const _EqK&   __eql,
3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block            const allocator_type& __a)
3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_hash(__hf),
3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_equals(__eql),
3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_elems(__a),
3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_num_elements(0),
3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_max_load_factor(1.0f)
3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _M_initialize_buckets(__n); }
3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hashtable(const _Self& __ht)
3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_hash(__ht._M_hash),
3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_equals(__ht._M_equals),
3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_elems(__ht.get_allocator()),
3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_num_elements(0),
3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_max_load_factor(1.0f)
3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { _M_copy_from(__ht); }
3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
341e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_NO_MOVE_SEMANTIC)
3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  hashtable(__move_source<_Self> src)
3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_num_elements(src.get()._M_num_elements),
3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_max_load_factor(src.get()._M_max_load_factor) {}
349e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif
3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _Self& operator= (const _Self& __ht) {
3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (&__ht != this) {
3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      clear();
3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_hash = __ht._M_hash;
3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_equals = __ht._M_equals;
3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      _M_copy_from(__ht);
3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return *this;
3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  ~hashtable() { clear(); }
3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type size() const { return _M_num_elements; }
3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type max_size() const { return size_type(-1); }
3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  bool empty() const { return size() == 0; }
3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void swap(_Self& __ht) {
3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::swap(_M_hash, __ht._M_hash);
3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::swap(_M_equals, __ht._M_equals);
3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_elems.swap(__ht._M_elems);
3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buckets.swap(__ht._M_buckets);
3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator begin() { return _M_elems.begin(); }
3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator end() { return _M_elems.end(); }
3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }
3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }
3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //The number of buckets is size() - 1 because the last bucket always contains
3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //_M_elems.end() to make algo easier to implement.
3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type bucket_count() const { return _M_buckets.size() - 1; }
3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type elems_in_bucket(size_type __bucket) const
394e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  { return _STLP_STD::distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // hash policy
4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  float load_factor() const { return (float)size() / (float)bucket_count(); }
4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  float max_load_factor() const { return _M_max_load_factor; }
402e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void max_load_factor(float __z) {
403e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_max_load_factor = __z;
404e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_resize();
405e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  }
4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  pair<iterator, bool> insert_unique(const value_type& __obj) {
408e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + 1);
4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return insert_unique_noresize(__obj);
4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert_equal(const value_type& __obj) {
413e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + 1);
4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return insert_equal_noresize(__obj);
4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected:
4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator _M_insert_noresize(size_type __n, const value_type& __obj);
4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator insert_equal_noresize(const value_type& __obj);
4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_MEMBER_TEMPLATES)
4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _InputIterator>
4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_unique(_InputIterator __f, _InputIterator __l)
4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _InputIterator>
4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_equal(_InputIterator __f, _InputIterator __l)
4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _InputIterator>
4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_unique(_InputIterator __f, _InputIterator __l,
4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                     const input_iterator_tag &) {
4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __f != __l; ++__f)
4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_unique(*__f);
4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _InputIterator>
4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_equal(_InputIterator __f, _InputIterator __l,
4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                    const input_iterator_tag &) {
4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __f != __l; ++__f)
4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_equal(*__f);
4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _ForwardIterator>
4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                     const forward_iterator_tag &) {
449e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    size_type __n = _STLP_STD::distance(__f, __l);
450e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_unique_noresize(*__f);
4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  template <class _ForwardIterator>
4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                    const forward_iterator_tag &) {
458e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    size_type __n = _STLP_STD::distance(__f, __l);
459e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_equal_noresize(*__f);
4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else /* _STLP_MEMBER_TEMPLATES */
4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_unique(const value_type* __f, const value_type* __l) {
4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_type __n = __l - __f;
467e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_unique_noresize(*__f);
4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_equal(const value_type* __f, const value_type* __l) {
4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_type __n = __l - __f;
474e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_equal_noresize(*__f);
4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_unique(const_iterator __f, const_iterator __l) {
480e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    size_type __n = _STLP_STD::distance(__f, __l);
481e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_unique_noresize(*__f);
4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void insert_equal(const_iterator __f, const_iterator __l) {
487e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    size_type __n = _STLP_STD::distance(__f, __l);
488e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott    _M_enlarge(_M_num_elements + __n);
4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; __n > 0; --__n, ++__f)
4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      insert_equal_noresize(*__f);
4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /*_STLP_MEMBER_TEMPLATES */
4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //reference find_or_insert(const value_type& __obj);
4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _ElemsIte _M_find(const _KT& __key) const {
4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    size_type __n = _M_bkt_num_key(__key);
5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _ElemsIte __first(_M_buckets[__n]);
5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _ElemsIte __last(_M_buckets[__n + 1]);
5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    if (__first != __last)
5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return __first;
5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    else
5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      return __CONST_CAST(_ElemsCont&, _M_elems).end();
5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator find(const _KT& __key) { return _M_find(__key); }
5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  const_iterator find(const _KT& __key) const { return _M_find(__key); }
5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type count(const _KT& __key) const {
5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    const size_type __n = _M_bkt_num_key(__key);
5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _ElemsIte __cur(_M_buckets[__n]);
5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _ElemsIte __last(_M_buckets[__n + 1]);
5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for (; __cur != __last; ++__cur) {
5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      if (_M_equals(_M_get_key(*__cur), __key)) {
5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        size_type __result = 1;
5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        for (++__cur;
5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block             __cur != __last && _M_equals(_M_get_key(*__cur), __key);
5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block             ++__result, ++__cur);
5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        return __result;
5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return 0;
5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  pair<iterator, iterator> equal_range(const _KT& __key) {
5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    typedef pair<iterator, iterator> _Pii;
5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    const size_type __n = _M_bkt_num_key(__key);
5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block         __first != __last; ++__first) {
5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      if (_M_equals(_M_get_key(*__first), __key)) {
5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _ElemsIte __cur(__first);
5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        return _Pii(__first, __cur);
5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Pii(end(), end());
5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    typedef pair<const_iterator, const_iterator> _Pii;
5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    const size_type __n = _M_bkt_num_key(__key);
5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block         __first != __last; ++__first) {
5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      if (_M_equals(_M_get_key(*__first), __key)) {
5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        _ElemsIte __cur(__first);
5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block        return _Pii(__first, __cur);
5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block      }
5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    }
5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    return _Pii(end(), end());
5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type erase(const key_type& __key);
5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void erase(const_iterator __it);
5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void erase(const_iterator __first, const_iterator __last);
5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
570e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void _M_enlarge(size_type __n);
571e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void _M_reduce();
572e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void _M_resize();
5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_rehash(size_type __num_buckets);
5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_check() const;
5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic:
5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void rehash(size_type __num_buckets_hint);
580e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  void resize(size_type __num_buckets_hint)
581e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  { rehash(__num_buckets_hint); }
5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void clear();
5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  // this is for hash_map::operator[]
5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  reference _M_insert(const value_type& __obj);
5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate:
5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //__n is set to the first bucket that has to be modified if any
5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //erase/insert operation is done after the returned iterator.
5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  iterator _M_before_begin(size_type &__n) const;
5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block                                  size_type &__n);
5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_initialize_buckets(size_type __n) {
5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buckets.reserve(__n_buckets);
5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block    _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  }
6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type _M_bkt_num_key(const _KT& __key) const
6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return _M_bkt_num_key(__key, bucket_count()); }
6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type _M_bkt_num(const value_type& __obj) const
6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return _M_bkt_num_key(_M_get_key(__obj)); }
6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  _STLP_TEMPLATE_FOR_CONT_EXT
6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return _M_hash(__key) % __n; }
6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  size_type _M_bkt_num(const value_type& __obj, size_t __n) const
6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  { return _M_bkt_num_key(_M_get_key(__obj), __n); }
6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  void _M_copy_from(const _Self& __ht);
6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  undef hashtable
6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE
6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE
6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_LINK_TIME_INSTANTIATION)
6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/_hashtable.c>
6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG)
6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#  include <stl/debug/_hashtable.h>
6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE
6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#include <stl/_relops_hash_cont.h>
6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_CONTAINER
6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_HEADER
6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
641e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC)
6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //Hashtables are movable:
645e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott  typedef __true_type implemented;
6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  //Completeness depends on many template parameters, for the moment we consider it not complete:
6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block  typedef __false_type complete;
6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block};
6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif
6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE
6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_INTERNAL_HASHTABLE_H */
6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block
6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables:
6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++
6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End:
659