_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_DBG_HASHTABLE_H 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_INTERNAL_DBG_HASHTABLE_H 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Hashtable class, used to implement the hashed associative containers 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// hash_set, hash_map, hash_multiset, and hash_multimap, 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// unordered_set, unordered_map, unordered_multiset, unordered_multimap 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_DBG_ITERATOR_H 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/debug/_iterator.h> 399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_PRIV_NAMESPACE 449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Key, class _Equal> 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _DbgEqual { 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _DbgEqual() {} 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _DbgEqual(const _Equal& __eq) : _M_non_dbg_eq(__eq) {} 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _DbgEqual(const _DbgEqual& __eq) : _M_non_dbg_eq(__eq._M_non_dbg_eq) {} 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_USE_CONTAINERS_EXTENSION) 539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator () (const _Key& __lhs, const _Key& __rhs) const 549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _Kp1, class _Kp2> 569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_USE_CONTAINERS_EXTENSION) 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT(_M_non_dbg_eq(__rhs, __lhs) == _M_non_dbg_eq(__lhs, __rhs), _StlMsg_INVALID_EQUIVALENT_PREDICATE) 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_non_dbg_eq(__lhs, __rhs) ? true : false; 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Equal non_dbg_key_eq() const { return _M_non_dbg_eq; } 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Equal _M_non_dbg_eq; 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_MOVE_TO_STD_NAMESPACE 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_NON_DBG_HT \ 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_PRIV _STLP_NON_DBG_NAME(hashtable) <_Val, _Key, _HF, _Traits, _ExK, _STLP_PRIV _DbgEqual<_Key, _EqK>, _All> 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS) 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _ExK, class _EqK, class _All> 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline _Val* 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvalue_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_HT >&) 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return (_Val*)0; } 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _ExK, class _EqK, class _All> 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline forward_iterator_tag 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockiterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_HT >&) 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ return forward_iterator_tag(); } 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _Val, class _Key, class _HF, 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block class _Traits, class _ExK, class _EqK, class _All> 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass hashtable { 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self; 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_NON_DBG_HT _Base; 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstTraits _NonConstTraits; 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstTraits _ConstTraits; 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits; 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits; 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Base _M_non_dbg_impl; 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __owned_list _M_iter_list; 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Key key_type; 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _HF hasher; 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _EqK key_equal; 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __IMPORT_CONTAINER_TYPEDEFS(_Base) 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstTraits> > iterator; 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstTraits> > const_iterator; 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_NonConstLocalTraits> > local_iterator; 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef iterator local_iterator; 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_ConstLocalTraits> > const_local_iterator; 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef const_iterator const_local_iterator; 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Base::iterator _Base_iterator; 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _Base::const_iterator _Base_const_iterator; 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hasher hash_funct() const { return _M_non_dbg_impl.hash_funct(); } 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block key_equal key_eq() const { return _M_non_dbg_impl.key_eq().non_dbg_key_eq(); } 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _Invalidate_iterator(const const_iterator& __it) 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _STLP_PRIV __invalidate_iterator(&_M_iter_list, __it); } 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void _Invalidate_iterators(const const_iterator& __first, const const_iterator& __last) 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); } 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); } 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _ExK& __ext, 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a = allocator_type()) 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_non_dbg_impl(__n, __hf, __eql, __ext, __a), 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_iter_list(&_M_non_dbg_impl) {} 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(size_type __n, 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _HF& __hf, 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _EqK& __eql, 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const allocator_type& __a = allocator_type()) 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_non_dbg_impl(__n, __hf, __eql, __a), 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_iter_list(&_M_non_dbg_impl) {} 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(const _Self& __ht) 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_non_dbg_impl(__ht._M_non_dbg_impl), 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_iter_list(&_M_non_dbg_impl) {} 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block hashtable(__move_source<_Self> src) 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)), 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_iter_list(&_M_non_dbg_impl) { 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL) 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block src.get()._M_iter_list._Invalidate_all(); 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block src.get()._M_iter_list._Set_owner(_M_iter_list); 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type size() const { return _M_non_dbg_impl.size(); } 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type max_size() const { return _M_non_dbg_impl.max_size(); } 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool empty() const { return _M_non_dbg_impl.empty(); } 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator=(const _Self& __ht) { 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (this != &__ht) { 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //Should not invalidate end iterator 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Invalidate_iterators(begin(), end()); 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl = __ht._M_non_dbg_impl; 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void swap(_Self& __ht) { 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_iter_list._Swap_owners(__ht._M_iter_list); 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.swap(__ht._M_non_dbg_impl); 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block local_iterator begin(size_type __n) { 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT) 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n)); 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block local_iterator end(size_type __n) { 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT) 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n)); 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); } 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); } 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_local_iterator begin(size_type __n) const { 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT) 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n)); 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_local_iterator end(size_type __n) const { 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT) 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n)); 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, bool> insert_unique(const value_type& __obj) { 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__obj); 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second); 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal(const value_type& __obj) 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__obj)); } 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, bool> insert_unique_noresize(const value_type& __obj) { 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique_noresize(__obj); 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second); 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator insert_equal_noresize(const value_type& __obj) 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal_noresize(__obj)); } 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined (_STLP_MEMBER_TEMPLATES) 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(_InputIterator __f, _InputIterator __l) { 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l)) 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__f), _STLP_PRIV _Non_Dbg_iter(__l)); 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block template <class _InputIterator> 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(_InputIterator __f, _InputIterator __l){ 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l)) 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__f), _STLP_PRIV _Non_Dbg_iter(__l)); 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const value_type* __f, const value_type* __l) { 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l)) 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_unique(__f, __l); 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const value_type* __f, const value_type* __l) { 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l)) 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_equal(__f, __l); 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_unique(const_iterator __f, const_iterator __l) { 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l)) 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_unique(__f._M_iterator, __l._M_iterator); 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void insert_equal(const_iterator __f, const_iterator __l) { 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l)) 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.insert_equal(__f._M_iterator, __l._M_iterator); 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator find(const _KT& __key) 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); } 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator find(const _KT& __key) const 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); } 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type count(const _KT& __key) const { return _M_non_dbg_impl.count(__key); } 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<iterator, iterator> equal_range(const _KT& __key) { 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<_Base_iterator, _Base_iterator> __res = _M_non_dbg_impl.equal_range(__key); 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<iterator,iterator> (iterator(&_M_iter_list,__res.first), 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block iterator(&_M_iter_list,__res.second)); 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<const_iterator, const_iterator> equal_range(const _KT& __key) const { 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair <_Base_const_iterator, _Base_const_iterator> __res = _M_non_dbg_impl.equal_range(__key); 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return pair<const_iterator,const_iterator> (const_iterator(&_M_iter_list,__res.first), 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator(&_M_iter_list,__res.second)); 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type erase(const key_type& __key) { 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block pair<_Base_iterator, _Base_iterator> __p = _M_non_dbg_impl.equal_range(__key); 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __n = _STLP_STD::distance(__p.first, __p.second); 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Invalidate_iterators(const_iterator(&_M_iter_list, __p.first), const_iterator(&_M_iter_list, __p.second)); 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.erase(__p.first, __p.second); 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __n; 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(const const_iterator& __it) { 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__it)) 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __it)) 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Invalidate_iterator(__it); 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.erase(__it._M_iterator); 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void erase(const_iterator __first, const_iterator __last) { 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator(begin()), const_iterator(end()))) 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Invalidate_iterators(__first, __last); 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator); 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void rehash(size_type __num_buckets_hint) { _M_non_dbg_impl.rehash(__num_buckets_hint); } 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void resize(size_type __num_elements_hint) { _M_non_dbg_impl.resize(__num_elements_hint); } 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void clear() { 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Invalidate_iterators(begin(), end()); 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.clear(); 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block reference _M_insert(const value_type& __obj) { return _M_non_dbg_impl._M_insert(__obj); } 3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type bucket_count() const { return _M_non_dbg_impl.bucket_count(); } 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type max_bucket_count() const { return _M_non_dbg_impl.max_bucket_count(); } 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type elems_in_bucket(size_type __n) const { 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT) 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _M_non_dbg_impl.elems_in_bucket(__n); 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TEMPLATE_FOR_CONT_EXT 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type bucket(const _KT& __k) const { return _M_non_dbg_impl.bucket(__k); } 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block float load_factor() const { return _M_non_dbg_impl.load_factor(); } 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block float max_load_factor() const { return _M_non_dbg_impl.max_load_factor(); } 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block void max_load_factor(float __z) { 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_VERBOSE_ASSERT((__z > 0.0f), _StlMsg_INVALID_ARGUMENT) 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_non_dbg_impl.max_load_factor(__z); 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#undef _STLP_NON_DBG_HT 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_INTERNAL_HASHTABLE_H */ 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 339