williamr@2: /* williamr@2: * williamr@2: * Copyright (c) 1994 williamr@2: * Hewlett-Packard Company williamr@2: * williamr@2: * Copyright (c) 1996,1997 williamr@2: * Silicon Graphics Computer Systems, Inc. williamr@2: * williamr@2: * Copyright (c) 1997 williamr@2: * Moscow Center for SPARC Technology williamr@2: * williamr@2: * Copyright (c) 1999 williamr@2: * Boris Fomitchev williamr@2: * williamr@2: * This material is provided "as is", with absolutely no warranty expressed williamr@2: * or implied. Any use is at your own risk. williamr@2: * williamr@2: * Permission to use or copy this software for any purpose is hereby granted williamr@2: * without fee, provided the above notices are retained on all copies. williamr@2: * Permission to modify the code and to distribute modified code is granted, williamr@2: * provided the above notices are retained, and a notice that the code was williamr@2: * modified is included with the above copyright notice. williamr@2: * williamr@2: */ williamr@2: williamr@2: /* NOTE: This is an internal header file, included by other STL headers. williamr@2: * You should not attempt to use it directly. williamr@2: */ williamr@2: williamr@2: #ifndef _STLP_INTERNAL_HASHTABLE_H williamr@2: #define _STLP_INTERNAL_HASHTABLE_H williamr@2: williamr@2: # ifndef _STLP_INTERNAL_VECTOR_H williamr@2: # include <stl/_vector.h> williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_ITERATOR_H williamr@2: # include <stl/_iterator.h> williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_FUNCTION_H williamr@2: # include <stl/_function_base.h> williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_INTERNAL_ALGOBASE_H williamr@2: # include <stl/_algobase.h> williamr@2: # endif williamr@2: williamr@2: # ifndef _STLP_HASH_FUN_H williamr@2: # include <stl/_hash_fun.h> williamr@2: # endif williamr@2: williamr@2: // Hashtable class, used to implement the hashed associative containers williamr@2: // hash_set, hash_map, hash_multiset, and hash_multimap. williamr@2: williamr@2: #ifdef _STLP_DEBUG williamr@2: # define hashtable __WORKAROUND_DBG_RENAME(hashtable) williamr@2: #endif williamr@2: williamr@2: _STLP_BEGIN_NAMESPACE williamr@2: williamr@2: template <class _Val> williamr@2: struct _Hashtable_node williamr@2: { williamr@2: typedef _Hashtable_node<_Val> _Self; williamr@2: _Self* _M_next; williamr@2: _Val _M_val; williamr@2: __TRIVIAL_STUFF(_Hashtable_node) williamr@2: }; williamr@2: williamr@2: // some compilers require the names of template parameters to be the same williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: class hashtable; williamr@2: williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: struct _Hashtable_iterator williamr@2: { williamr@2: typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@2: _Hashtable; williamr@2: typedef _Hashtable_node<_Val> _Node; williamr@2: williamr@2: _Node* _M_cur; williamr@2: _Hashtable* _M_ht; williamr@2: williamr@2: _Hashtable_iterator(_Node* __n, _Hashtable* __tab) williamr@2: : _M_cur(__n), _M_ht(__tab) {} williamr@2: _Hashtable_iterator() {} williamr@2: williamr@2: _Node* _M_skip_to_next(); williamr@2: }; williamr@2: williamr@2: williamr@2: template <class _Val, class _Traits, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: struct _Ht_iterator : public _Hashtable_iterator< _Val, _Key,_HF, _ExK,_EqK,_All> williamr@2: { williamr@2: williamr@2: typedef _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Base; williamr@2: williamr@2: // typedef _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> iterator; williamr@2: // typedef _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> const_iterator; williamr@2: typedef _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All> _Self; williamr@2: williamr@2: typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable; williamr@2: typedef _Hashtable_node<_Val> _Node; williamr@2: williamr@2: typedef _Val value_type; williamr@2: typedef forward_iterator_tag iterator_category; williamr@2: typedef ptrdiff_t difference_type; williamr@2: typedef size_t size_type; williamr@2: typedef typename _Traits::reference reference; williamr@2: typedef typename _Traits::pointer pointer; williamr@2: williamr@2: _Ht_iterator(const _Node* __n, const _Hashtable* __tab) : williamr@2: _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>((_Node*)__n, (_Hashtable*)__tab) {} williamr@2: _Ht_iterator() {} williamr@2: _Ht_iterator(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __it) : williamr@2: _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>(__it) {} williamr@2: williamr@2: reference operator*() const { williamr@2: return this->_M_cur->_M_val; williamr@2: } williamr@2: _STLP_DEFINE_ARROW_OPERATOR williamr@2: williamr@2: _Self& operator++() { williamr@2: _Node* __n = this->_M_cur->_M_next; williamr@2: this->_M_cur = (__n !=0 ? __n : this->_M_skip_to_next()); williamr@2: return *this; williamr@2: } williamr@2: inline _Self operator++(int) { williamr@2: _Self __tmp = *this; williamr@2: ++*this; williamr@2: return __tmp; williamr@2: } williamr@2: }; williamr@2: williamr@2: template <class _Val, class _Traits, class _Traits1, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: inline bool williamr@2: operator==(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>& __x, williamr@2: const _Ht_iterator<_Val, _Traits1,_Key,_HF,_ExK,_EqK,_All>& __y) { williamr@2: return __x._M_cur == __y._M_cur; williamr@2: } williamr@2: williamr@2: #ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: inline bool williamr@2: operator!=(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __x, williamr@2: const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __y) { williamr@2: return __x._M_cur != __y._M_cur; williamr@2: } williamr@2: #else williamr@2: williamr@2: # if (defined (__GNUC__) && (__GNUC_MINOR__ < 8)) williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: inline bool williamr@2: operator!=(const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x, williamr@2: const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) { williamr@2: return __x._M_cur != __y._M_cur; williamr@2: } williamr@2: # endif williamr@2: williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: inline bool williamr@2: operator!=(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x, williamr@2: const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) { williamr@2: return __x._M_cur != __y._M_cur; williamr@2: } williamr@2: #endif williamr@2: williamr@2: # ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES williamr@2: template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All> williamr@2: inline _Val* value_type(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (_Val*) 0; } williamr@2: template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All> williamr@2: inline forward_iterator_tag iterator_category(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return forward_iterator_tag(); } williamr@2: template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All> williamr@2: inline ptrdiff_t* distance_type(const _Ht_iterator<_Val,_Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (ptrdiff_t*) 0; } williamr@2: #endif williamr@2: williamr@2: #define __stl_num_primes 28 williamr@2: template <class _Tp> williamr@2: class _Stl_prime { williamr@2: public: williamr@2: static const size_t _M_list[__stl_num_primes]; williamr@2: }; williamr@2: williamr@2: # if defined (_STLP_USE_TEMPLATE_EXPORT) williamr@2: _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>; williamr@2: # endif williamr@2: williamr@2: typedef _Stl_prime<bool> _Stl_prime_type; williamr@2: williamr@2: williamr@2: // Hashtables handle allocators a bit differently than other containers williamr@2: // do. If we're using standard-conforming allocators, then a hashtable williamr@2: // unconditionally has a member variable to hold its allocator, even if williamr@2: // it so happens that all instances of the allocator type are identical. williamr@2: // This is because, for hashtables, this extra storage is negligible. williamr@2: // Additionally, a base class wouldn't serve any other purposes; it williamr@2: // wouldn't, for example, simplify the exception-handling code. williamr@2: template <class _Val, class _Key, class _HF, williamr@2: class _ExK, class _EqK, class _All> williamr@2: class hashtable williamr@2: { williamr@2: typedef hashtable<_Val, _Key, _HF, _ExK, _EqK, _All> _Self; williamr@2: public: williamr@2: typedef _Key key_type; williamr@2: typedef _Val value_type; williamr@2: typedef _HF hasher; williamr@2: typedef _EqK key_equal; williamr@2: williamr@2: typedef size_t size_type; williamr@2: typedef ptrdiff_t difference_type; williamr@2: typedef value_type* pointer; williamr@2: typedef const value_type* const_pointer; williamr@2: typedef value_type& reference; williamr@2: typedef const value_type& const_reference; williamr@2: typedef forward_iterator_tag _Iterator_category; williamr@2: williamr@2: hasher hash_funct() const { return _M_hash; } williamr@2: key_equal key_eq() const { return _M_equals; } williamr@2: williamr@2: private: williamr@2: typedef _Hashtable_node<_Val> _Node; williamr@2: williamr@2: private: williamr@2: _STLP_FORCE_ALLOCATORS(_Val, _All) williamr@2: typedef typename _Alloc_traits<_Node, _All>::allocator_type _M_node_allocator_type; williamr@2: typedef typename _Alloc_traits<void*, _All>::allocator_type _M_node_ptr_allocator_type; williamr@2: typedef __vector__<void*, _M_node_ptr_allocator_type> _BucketVector; williamr@2: public: williamr@2: typedef typename _Alloc_traits<_Val,_All>::allocator_type allocator_type; williamr@2: allocator_type get_allocator() const { williamr@2: return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_num_elements, _Val); williamr@2: } williamr@2: private: williamr@2: hasher _M_hash; williamr@2: key_equal _M_equals; williamr@2: _ExK _M_get_key; williamr@2: _BucketVector _M_buckets; williamr@2: _STLP_alloc_proxy<size_type, _Node, _M_node_allocator_type> _M_num_elements; williamr@2: const _Node* _M_get_bucket(size_t __n) const { return (_Node*)_M_buckets[__n]; } williamr@2: williamr@2: public: williamr@2: typedef _Const_traits<_Val> __const_val_traits; williamr@2: typedef _Nonconst_traits<_Val> __nonconst_val_traits; williamr@2: typedef _Ht_iterator<_Val, __const_val_traits,_Key,_HF,_ExK,_EqK, _All> const_iterator; williamr@2: typedef _Ht_iterator<_Val, __nonconst_val_traits,_Key,_HF,_ExK,_EqK,_All> iterator; williamr@2: friend struct _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>; williamr@2: friend struct _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>; williamr@2: friend struct _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK, _All>; williamr@2: williamr@2: public: williamr@2: hashtable(size_type __n, williamr@2: const _HF& __hf, williamr@2: const _EqK& __eql, williamr@2: const _ExK& __ext, williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : williamr@2: _M_hash(__hf), williamr@2: _M_equals(__eql), williamr@2: _M_get_key(__ext), williamr@2: _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)), williamr@2: _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0) williamr@2: { williamr@2: _M_initialize_buckets(__n); williamr@2: } williamr@2: williamr@2: hashtable(size_type __n, williamr@2: const _HF& __hf = hasher(), williamr@2: const _EqK& __eql = key_equal(), williamr@2: const allocator_type& __a = allocator_type()) williamr@2: : williamr@2: _M_hash(__hf), williamr@2: _M_equals(__eql), williamr@2: _M_get_key(_ExK()), williamr@2: _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)), williamr@2: _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0) williamr@2: { williamr@2: _M_initialize_buckets(__n); williamr@2: } williamr@2: williamr@2: hashtable(const _Self& __ht) williamr@2: : williamr@2: _M_hash(__ht._M_hash), williamr@2: _M_equals(__ht._M_equals), williamr@2: _M_get_key(__ht._M_get_key), williamr@2: _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(),void*)), williamr@2: _M_num_elements((const _M_node_allocator_type&)__ht._M_num_elements, (size_type)0) williamr@2: { williamr@2: _M_copy_from(__ht); williamr@2: } williamr@2: williamr@2: _Self& operator= (const _Self& __ht) williamr@2: { williamr@2: if (&__ht != this) { williamr@2: clear(); williamr@2: _M_hash = __ht._M_hash; williamr@2: _M_equals = __ht._M_equals; williamr@2: _M_get_key = __ht._M_get_key; williamr@2: _M_copy_from(__ht); williamr@2: } williamr@2: return *this; williamr@2: } williamr@2: williamr@2: ~hashtable() { clear(); } williamr@2: williamr@2: size_type size() const { return _M_num_elements._M_data; } williamr@2: size_type max_size() const { return size_type(-1); } williamr@2: bool empty() const { return size() == 0; } williamr@2: williamr@2: void swap(_Self& __ht) williamr@2: { williamr@2: _STLP_STD::swap(_M_hash, __ht._M_hash); williamr@2: _STLP_STD::swap(_M_equals, __ht._M_equals); williamr@2: _STLP_STD::swap(_M_get_key, __ht._M_get_key); williamr@2: _M_buckets.swap(__ht._M_buckets); williamr@2: _STLP_STD::swap(_M_num_elements, __ht._M_num_elements); williamr@2: } williamr@2: williamr@2: iterator begin() williamr@2: { williamr@2: for (size_type __n = 0; __n < _M_buckets.size(); ++__n) williamr@2: if (_M_buckets[__n]) williamr@2: return iterator((_Node*)_M_buckets[__n], this); williamr@2: return end(); williamr@2: } williamr@2: williamr@2: iterator end() { return iterator((_Node*)0, this); } williamr@2: williamr@2: const_iterator begin() const williamr@2: { williamr@2: for (size_type __n = 0; __n < _M_buckets.size(); ++__n) williamr@2: if (_M_buckets[__n]) williamr@2: return const_iterator((_Node*)_M_buckets[__n], this); williamr@2: return end(); williamr@2: } williamr@2: williamr@2: const_iterator end() const { return const_iterator((_Node*)0, this); } williamr@2: williamr@2: static bool _STLP_CALL _M_equal (const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&, williamr@2: const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&); williamr@2: williamr@2: public: williamr@2: williamr@2: size_type bucket_count() const { return _M_buckets.size(); } williamr@2: williamr@2: size_type max_bucket_count() const williamr@2: { return _Stl_prime_type::_M_list[(int)__stl_num_primes - 1]; } williamr@2: williamr@2: size_type elems_in_bucket(size_type __bucket) const williamr@2: { williamr@2: size_type __result = 0; williamr@2: for (_Node* __cur = (_Node*)_M_buckets[__bucket]; __cur; __cur = __cur->_M_next) williamr@2: __result += 1; williamr@2: return __result; williamr@2: } williamr@2: williamr@2: pair<iterator, bool> insert_unique(const value_type& __obj) williamr@2: { williamr@2: resize(_M_num_elements._M_data + 1); williamr@2: return insert_unique_noresize(__obj); williamr@2: } williamr@2: williamr@2: iterator insert_equal(const value_type& __obj) williamr@2: { williamr@2: resize(_M_num_elements._M_data + 1); williamr@2: return insert_equal_noresize(__obj); williamr@2: } williamr@2: williamr@2: pair<iterator, bool> insert_unique_noresize(const value_type& __obj); williamr@2: iterator insert_equal_noresize(const value_type& __obj); williamr@2: williamr@2: #ifdef _STLP_MEMBER_TEMPLATES williamr@2: template <class _InputIterator> williamr@2: void insert_unique(_InputIterator __f, _InputIterator __l) williamr@2: { williamr@2: insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); williamr@2: } williamr@2: williamr@2: template <class _InputIterator> williamr@2: void insert_equal(_InputIterator __f, _InputIterator __l) williamr@2: { williamr@2: insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); williamr@2: } williamr@2: williamr@2: template <class _InputIterator> williamr@2: void insert_unique(_InputIterator __f, _InputIterator __l, williamr@2: const input_iterator_tag &) williamr@2: { williamr@2: for ( ; __f != __l; ++__f) williamr@2: insert_unique(*__f); williamr@2: } williamr@2: williamr@2: template <class _InputIterator> williamr@2: void insert_equal(_InputIterator __f, _InputIterator __l, williamr@2: const input_iterator_tag &) williamr@2: { williamr@2: for ( ; __f != __l; ++__f) williamr@2: insert_equal(*__f); williamr@2: } williamr@2: williamr@2: template <class _ForwardIterator> williamr@2: void insert_unique(_ForwardIterator __f, _ForwardIterator __l, williamr@2: const forward_iterator_tag &) williamr@2: { williamr@2: size_type __n = distance(__f, __l); williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_unique_noresize(*__f); williamr@2: } williamr@2: williamr@2: template <class _ForwardIterator> williamr@2: void insert_equal(_ForwardIterator __f, _ForwardIterator __l, williamr@2: const forward_iterator_tag &) williamr@2: { williamr@2: size_type __n = distance(__f, __l); williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_equal_noresize(*__f); williamr@2: } williamr@2: williamr@2: #else /* _STLP_MEMBER_TEMPLATES */ williamr@2: void insert_unique(const value_type* __f, const value_type* __l) williamr@2: { williamr@2: size_type __n = __l - __f; williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_unique_noresize(*__f); williamr@2: } williamr@2: williamr@2: void insert_equal(const value_type* __f, const value_type* __l) williamr@2: { williamr@2: size_type __n = __l - __f; williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_equal_noresize(*__f); williamr@2: } williamr@2: williamr@2: void insert_unique(const_iterator __f, const_iterator __l) williamr@2: { williamr@2: size_type __n = distance(__f, __l); williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_unique_noresize(*__f); williamr@2: } williamr@2: williamr@2: void insert_equal(const_iterator __f, const_iterator __l) williamr@2: { williamr@2: size_type __n = distance(__f, __l); williamr@2: resize(_M_num_elements._M_data + __n); williamr@2: for ( ; __n > 0; --__n, ++__f) williamr@2: insert_equal_noresize(*__f); williamr@2: } williamr@2: #endif /*_STLP_MEMBER_TEMPLATES */ williamr@2: williamr@2: reference find_or_insert(const value_type& __obj); williamr@2: williamr@2: private: williamr@2: # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC_))) williamr@2: template <class _KT> williamr@2: _Node* _M_find(const _KT& __key) const williamr@2: # else williamr@2: _Node* _M_find(const key_type& __key) const williamr@2: # endif williamr@2: { williamr@2: size_type __n = _M_hash(__key)% _M_buckets.size(); williamr@2: _Node* __first; williamr@2: for ( __first = (_Node*)_M_buckets[__n]; williamr@2: __first && !_M_equals(_M_get_key(__first->_M_val), __key); williamr@2: __first = __first->_M_next) williamr@2: {} williamr@2: return __first; williamr@2: } williamr@2: williamr@2: public: williamr@2: # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__))) williamr@2: template <class _KT> williamr@2: iterator find(const _KT& __key) williamr@2: # else williamr@2: iterator find(const key_type& __key) williamr@2: # endif williamr@2: { williamr@2: return iterator(_M_find(__key), this); williamr@2: } williamr@2: williamr@2: # if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__))) williamr@2: template <class _KT> williamr@2: const_iterator find(const _KT& __key) const williamr@2: # else williamr@2: const_iterator find(const key_type& __key) const williamr@2: # endif williamr@2: { williamr@2: return const_iterator(_M_find(__key), this); williamr@2: } williamr@2: williamr@2: size_type count(const key_type& __key) const williamr@2: { williamr@2: const size_type __n = _M_bkt_num_key(__key); williamr@2: size_type __result = 0; williamr@2: williamr@2: for (const _Node* __cur = (_Node*)_M_buckets[__n]; __cur; __cur = __cur->_M_next) williamr@2: if (_M_equals(_M_get_key(__cur->_M_val), __key)) williamr@2: ++__result; williamr@2: return __result; williamr@2: } williamr@2: williamr@2: pair<iterator, iterator> williamr@2: equal_range(const key_type& __key); williamr@2: williamr@2: pair<const_iterator, const_iterator> williamr@2: equal_range(const key_type& __key) const; williamr@2: williamr@2: size_type erase(const key_type& __key); williamr@2: // void erase(const iterator& __it); ` williamr@2: void erase(const const_iterator& __it) ; williamr@2: williamr@2: // void erase(const const_iterator& __first, const const_iterator __last) { williamr@2: // erase((const iterator&)__first, (const iterator&)__last); williamr@2: // } williamr@2: void erase(const_iterator __first, const_iterator __last); williamr@2: void resize(size_type __num_elements_hint); williamr@2: void clear(); williamr@2: williamr@2: public: williamr@2: // this is for hash_map::operator[] williamr@2: reference _M_insert(const value_type& __obj); williamr@2: williamr@2: private: williamr@2: williamr@2: size_type _M_next_size(size_type __n) const; williamr@2: williamr@2: void _M_initialize_buckets(size_type __n) williamr@2: { williamr@2: const size_type __n_buckets = _M_next_size(__n); williamr@2: _M_buckets.reserve(__n_buckets); williamr@2: _M_buckets.insert(_M_buckets.end(), __n_buckets, (void*) 0); williamr@2: _M_num_elements._M_data = 0; williamr@2: } williamr@2: williamr@2: size_type _M_bkt_num_key(const key_type& __key) const williamr@2: { williamr@2: return _M_bkt_num_key(__key, _M_buckets.size()); williamr@2: } williamr@2: williamr@2: size_type _M_bkt_num(const value_type& __obj) const williamr@2: { williamr@2: return _M_bkt_num_key(_M_get_key(__obj)); williamr@2: } williamr@2: williamr@2: size_type _M_bkt_num_key(const key_type& __key, size_t __n) const williamr@2: { williamr@2: return _M_hash(__key) % __n; williamr@2: } williamr@2: williamr@2: size_type _M_bkt_num(const value_type& __obj, size_t __n) const williamr@2: { williamr@2: return _M_bkt_num_key(_M_get_key(__obj), __n); williamr@2: } williamr@2: williamr@2: _Node* _M_new_node(const value_type& __obj) williamr@2: { williamr@2: _Node* __n = _M_num_elements.allocate(1); williamr@2: __n->_M_next = 0; williamr@2: _STLP_TRY { williamr@2: _Construct(&__n->_M_val, __obj); williamr@2: // return __n; williamr@2: } williamr@2: _STLP_UNWIND(_M_num_elements.deallocate(__n, 1)); williamr@2: return __n; williamr@2: } williamr@2: williamr@2: void _M_delete_node(_Node* __n) williamr@2: { williamr@2: _STLP_STD::_Destroy(&__n->_M_val); williamr@2: _M_num_elements.deallocate(__n, 1); williamr@2: } williamr@2: williamr@2: void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); williamr@2: void _M_erase_bucket(const size_type __n, _Node* __last); williamr@2: williamr@2: void _M_copy_from(const _Self& __ht); williamr@2: }; williamr@2: williamr@2: #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All> williamr@2: #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> williamr@2: #include <stl/_relops_hash_cont.h> williamr@2: #undef _STLP_TEMPLATE_CONTAINER williamr@2: #undef _STLP_TEMPLATE_HEADER williamr@2: williamr@2: _STLP_END_NAMESPACE williamr@2: williamr@2: # undef hashtable williamr@2: williamr@2: # if !defined (_STLP_LINK_TIME_INSTANTIATION) williamr@2: # include <stl/_hashtable.c> williamr@2: # endif williamr@2: williamr@2: # if defined (_STLP_DEBUG) williamr@2: # include <stl/debug/_hashtable.h> williamr@2: # endif williamr@2: williamr@2: #endif /* _STLP_INTERNAL_HASHTABLE_H */ williamr@2: williamr@2: // Local Variables: williamr@2: // mode:C++ williamr@2: // End: williamr@2: williamr@2: