_hashtable.h revision 9720d5f59b9c1f5d1b9ecbc9173dbcb71bd557be
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>&) { 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef 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 { 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Returns the maximum number of buckets handled by the hashtable implementation 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static size_t _STLP_CALL _S_max_nb_buckets(); 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Returns the bucket size next to a required size 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static size_t _STLP_CALL _S_next_size(size_t); 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_USE_TEMPLATE_EXPORT) 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>; 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktypedef _Stl_prime<bool> _Stl_prime_type; 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG) 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Hashtables handle allocators a bit differently than other containers 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * do. If we're using standard-conforming allocators, then a hashtable 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * unconditionally has a member variable to hold its allocator, even if 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * it so happens that all instances of the allocator type are identical. 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This is because, for hashtables, this extra storage is negligible. 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Additionally, a base class wouldn't serve any other purposes; it 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * wouldn't, for example, simplify the exception-handling code. 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass hashtable { 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self; 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstTraits _NonConstTraits; 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstTraits _ConstTraits; 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits; 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits; 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Key key_type; 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Val value_type; 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _HF hasher; 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _EqK key_equal; 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef size_t size_type; 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef ptrdiff_t difference_type; 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _NonConstTraits::pointer pointer; 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const value_type* const_pointer; 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _NonConstTraits::reference reference; 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const value_type& const_reference; 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef forward_iterator_tag _Iterator_category; 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hasher hash_funct() const { return _M_hash; } 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block key_equal key_eq() const { return _M_equals; } 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_FORCE_ALLOCATORS(_Val, _All) 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont; 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef slist<value_type, _All> _ElemsCont; 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _ElemsCont::iterator _ElemsIte; 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _ElemsCont::const_iterator _ElemsConstIte; 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _Slist_node_base _BucketType; 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _M_bucket_allocator_type; 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /* 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * We are going to use vector of _Slist_node_base pointers for 2 reasons: 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * - limit code bloat, all hashtable instanciation use the same buckets representation. 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * method would be too slow because the slist::splice_after method become linear on 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * the number of iterators in the buckets rather than constant in time as the iterator 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * has to be move from a slist to the other. 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _M_bucket_allocator_type> _BucketVector; 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef vector<_BucketType*, _M_bucket_allocator_type> _BucketVector; 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hasher _M_hash; 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block key_equal _M_equals; 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ExK _M_get_key; 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsCont _M_elems; 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _BucketVector _M_buckets; 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_num_elements; 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block float _M_max_load_factor; 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator; 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator; 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //TODO: Avoids this debug check and make the local_iterator different from 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //iterator in debug mode too. 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DEBUG) 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator; 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator; 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef iterator local_iterator; 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const_iterator const_local_iterator; 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Alloc_traits<_Val, _All>::allocator_type allocator_type; 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block allocator_type get_allocator() const { return _M_elems.get_allocator(); } 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _ExK& __ext, 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a = allocator_type()) 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _ExK& __ext) 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(__hf), 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(__eql), 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(__ext), 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(allocator_type()), 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(0), 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(1.0f) 3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _M_initialize_buckets(__n); } 3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _ExK& __ext, 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a) 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(__hf), 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(__eql), 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(__ext), 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(__a), 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(0), 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(1.0f) 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _M_initialize_buckets(__n); } 3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_DONT_SUP_DFLT_PARAM) 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a = allocator_type()) 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql) 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(__hf), 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(__eql), 3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(_ExK()), 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(allocator_type()), 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(0), 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(1.0f) 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _M_initialize_buckets(__n); } 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a) 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(__hf), 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(__eql), 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(_ExK()), 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(__a), 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(0), 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(1.0f) 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _M_initialize_buckets(__n); } 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(const _Self& __ht) 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(__ht._M_hash), 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(__ht._M_equals), 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(__ht._M_get_key), 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(__ht.get_allocator()), 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)), 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(0), 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(1.0f) 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _M_copy_from(__ht); } 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(__move_source<_Self> src) 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)), 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)), 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key(_STLP_PRIV _AsMoveSource(src.get()._M_get_key)), 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)), 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)), 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_num_elements(src.get()._M_num_elements), 3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_max_load_factor(src.get()._M_max_load_factor) {} 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator= (const _Self& __ht) { 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (&__ht != this) { 3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block clear(); 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_hash = __ht._M_hash; 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_equals = __ht._M_equals; 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_get_key = __ht._M_get_key; 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_copy_from(__ht); 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ~hashtable() { clear(); } 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type size() const { return _M_num_elements; } 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type max_size() const { return size_type(-1); } 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool empty() const { return size() == 0; } 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void swap(_Self& __ht) { 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_hash, __ht._M_hash); 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_equals, __ht._M_equals); 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_get_key, __ht._M_get_key); 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_elems.swap(__ht._M_elems); 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.swap(__ht._M_buckets); 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_num_elements, __ht._M_num_elements); 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor); 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator begin() { return _M_elems.begin(); } 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator end() { return _M_elems.end(); } 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); } 4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); } 4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); } 4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); } 4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); } 4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); } 4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //static bool _STLP_CALL _M_equal (const _Self&, const _Self&); 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //The number of buckets is size() - 1 because the last bucket always contains 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //_M_elems.end() to make algo easier to implement. 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type bucket_count() const { return _M_buckets.size() - 1; } 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); } 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type elems_in_bucket(size_type __bucket) const 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); } 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); } 4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // hash policy 4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block float load_factor() const { return (float)size() / (float)bucket_count(); } 4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block float max_load_factor() const { return _M_max_load_factor; } 4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void max_load_factor(float __z) { _M_max_load_factor = __z;} 4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, bool> insert_unique(const value_type& __obj) { 4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + 1); 4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return insert_unique_noresize(__obj); 4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal(const value_type& __obj) { 4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + 1); 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return insert_equal_noresize(__obj); 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprotected: 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator _M_insert_noresize(size_type __n, const value_type& __obj); 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, bool> insert_unique_noresize(const value_type& __obj); 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal_noresize(const value_type& __obj); 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_MEMBER_TEMPLATES) 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(_InputIterator __f, _InputIterator __l) 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); } 4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(_InputIterator __f, _InputIterator __l) 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); } 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(_InputIterator __f, _InputIterator __l, 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const input_iterator_tag &) { 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __f != __l; ++__f) 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique(*__f); 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(_InputIterator __f, _InputIterator __l, 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const input_iterator_tag &) { 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __f != __l; ++__f) 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal(*__f); 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _ForwardIterator> 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(_ForwardIterator __f, _ForwardIterator __l, 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &) { 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = distance(__f, __l); 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique_noresize(*__f); 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _ForwardIterator> 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(_ForwardIterator __f, _ForwardIterator __l, 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const forward_iterator_tag &) { 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = distance(__f, __l); 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal_noresize(*__f); 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else /* _STLP_MEMBER_TEMPLATES */ 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const value_type* __f, const value_type* __l) { 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = __l - __f; 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique_noresize(*__f); 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const value_type* __f, const value_type* __l) { 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = __l - __f; 5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal_noresize(*__f); 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const_iterator __f, const_iterator __l) { 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = distance(__f, __l); 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_unique_noresize(*__f); 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const_iterator __f, const_iterator __l) { 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = distance(__f, __l); 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block resize(_M_num_elements + __n); 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; __n > 0; --__n, ++__f) 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block insert_equal_noresize(*__f); 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /*_STLP_MEMBER_TEMPLATES */ 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //reference find_or_insert(const value_type& __obj); 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte _M_find(const _KT& __key) const { 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = _M_bkt_num_key(__key); 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __first(_M_buckets[__n]); 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first); 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__first != __last) 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __first; 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __CONST_CAST(_ElemsCont&, _M_elems).end(); 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator find(const _KT& __key) { return _M_find(__key); } 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator find(const _KT& __key) const { return _M_find(__key); } 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type count(const _KT& __key) const { 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num_key(__key); 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(_M_buckets[__n]); 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __last(_M_buckets[__n + 1]); 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (; __cur != __last; ++__cur) { 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__cur), __key)) { 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __result = 1; 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (++__cur; 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __cur != __last && _M_equals(_M_get_key(*__cur), __key); 5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__result, ++__cur); 5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, iterator> equal_range(const _KT& __key) { 5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef pair<iterator, iterator> _Pii; 5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num_key(__key); 5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]); 5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first != __last; ++__first) { 5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__first), __key)) { 5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(__first); 5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur); 5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _Pii(__first, __cur); 5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _Pii(end(), end()); 5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> equal_range(const _KT& __key) const { 5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef pair<const_iterator, const_iterator> _Pii; 5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n = _M_bkt_num_key(__key); 5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]); 5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __first != __last; ++__first) { 5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_equals(_M_get_key(*__first), __key)) { 5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _ElemsIte __cur(__first); 5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur); 5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _Pii(__first, __cur); 5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _Pii(end(), end()); 5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type erase(const key_type& __key); 5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(const_iterator __it); 5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(const_iterator __first, const_iterator __last); 5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_rehash(size_type __num_buckets); 5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_check() const; 6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void rehash(size_type __num_buckets_hint); 6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void resize(size_type __num_elements_hint); 6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void clear(); 6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // this is for hash_map::operator[] 6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reference _M_insert(const value_type& __obj); 6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //__n is set to the first bucket that has to be modified if any 6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //erase/insert operation is done after the returned iterator. 6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator _M_before_begin(size_type &__n) const; 6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets, 6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type &__n); 6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_initialize_buckets(size_type __n) { 6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1; 6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.reserve(__n_buckets); 6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0)); 6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_bkt_num_key(const _KT& __key) const 6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _M_bkt_num_key(__key, bucket_count()); } 6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_bkt_num(const value_type& __obj) const 6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _M_bkt_num_key(_M_get_key(__obj)); } 6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_bkt_num_key(const _KT& __key, size_type __n) const 6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _M_hash(__key) % __n; } 6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type _M_bkt_num(const value_type& __obj, size_t __n) const 6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return _M_bkt_num_key(_M_get_key(__obj), __n); } 6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _M_copy_from(const _Self& __ht); 6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef hashtable 6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_LINK_TIME_INSTANTIATION) 6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_hashtable.c> 6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG) 6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/debug/_hashtable.h> 6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All> 6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#include <stl/_relops_hash_cont.h> 6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_CONTAINER 6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_TEMPLATE_HEADER 6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All> 6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockstruct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > { 6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Hashtables are movable: 6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __stlp_movable implemented; 6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Completeness depends on many template parameters, for the moment we consider it not complete: 6729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef __false_type complete; 6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_INTERNAL_HASHTABLE_H */ 6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 683