1.1 --- a/epoc32/include/stdapis/stlport/stl/_hashtable.h Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_hashtable.h Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,614 @@
1.4 -_hashtable.h
1.5 +/*
1.6 + *
1.7 + * Copyright (c) 1994
1.8 + * Hewlett-Packard Company
1.9 + *
1.10 + * Copyright (c) 1996,1997
1.11 + * Silicon Graphics Computer Systems, Inc.
1.12 + *
1.13 + * Copyright (c) 1997
1.14 + * Moscow Center for SPARC Technology
1.15 + *
1.16 + * Copyright (c) 1999
1.17 + * Boris Fomitchev
1.18 + *
1.19 + * This material is provided "as is", with absolutely no warranty expressed
1.20 + * or implied. Any use is at your own risk.
1.21 + *
1.22 + * Permission to use or copy this software for any purpose is hereby granted
1.23 + * without fee, provided the above notices are retained on all copies.
1.24 + * Permission to modify the code and to distribute modified code is granted,
1.25 + * provided the above notices are retained, and a notice that the code was
1.26 + * modified is included with the above copyright notice.
1.27 + *
1.28 + */
1.29 +
1.30 +/* NOTE: This is an internal header file, included by other STL headers.
1.31 + * You should not attempt to use it directly.
1.32 + */
1.33 +
1.34 +#ifndef _STLP_INTERNAL_HASHTABLE_H
1.35 +#define _STLP_INTERNAL_HASHTABLE_H
1.36 +
1.37 +# ifndef _STLP_INTERNAL_VECTOR_H
1.38 +# include <stl/_vector.h>
1.39 +# endif
1.40 +
1.41 +# ifndef _STLP_INTERNAL_ITERATOR_H
1.42 +# include <stl/_iterator.h>
1.43 +# endif
1.44 +
1.45 +# ifndef _STLP_INTERNAL_FUNCTION_H
1.46 +# include <stl/_function_base.h>
1.47 +# endif
1.48 +
1.49 +# ifndef _STLP_INTERNAL_ALGOBASE_H
1.50 +# include <stl/_algobase.h>
1.51 +# endif
1.52 +
1.53 +# ifndef _STLP_HASH_FUN_H
1.54 +# include <stl/_hash_fun.h>
1.55 +# endif
1.56 +
1.57 +// Hashtable class, used to implement the hashed associative containers
1.58 +// hash_set, hash_map, hash_multiset, and hash_multimap.
1.59 +
1.60 +#ifdef _STLP_DEBUG
1.61 +# define hashtable __WORKAROUND_DBG_RENAME(hashtable)
1.62 +#endif
1.63 +
1.64 +_STLP_BEGIN_NAMESPACE
1.65 +
1.66 +template <class _Val>
1.67 +struct _Hashtable_node
1.68 +{
1.69 + typedef _Hashtable_node<_Val> _Self;
1.70 + _Self* _M_next;
1.71 + _Val _M_val;
1.72 + __TRIVIAL_STUFF(_Hashtable_node)
1.73 +};
1.74 +
1.75 +// some compilers require the names of template parameters to be the same
1.76 +template <class _Val, class _Key, class _HF,
1.77 + class _ExK, class _EqK, class _All>
1.78 +class hashtable;
1.79 +
1.80 +template <class _Val, class _Key, class _HF,
1.81 + class _ExK, class _EqK, class _All>
1.82 +struct _Hashtable_iterator
1.83 +{
1.84 + typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.85 + _Hashtable;
1.86 + typedef _Hashtable_node<_Val> _Node;
1.87 +
1.88 + _Node* _M_cur;
1.89 + _Hashtable* _M_ht;
1.90 +
1.91 + _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
1.92 + : _M_cur(__n), _M_ht(__tab) {}
1.93 + _Hashtable_iterator() {}
1.94 +
1.95 + _Node* _M_skip_to_next();
1.96 +};
1.97 +
1.98 +
1.99 +template <class _Val, class _Traits, class _Key, class _HF,
1.100 + class _ExK, class _EqK, class _All>
1.101 +struct _Ht_iterator : public _Hashtable_iterator< _Val, _Key,_HF, _ExK,_EqK,_All>
1.102 +{
1.103 +
1.104 + typedef _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> _Base;
1.105 +
1.106 + // typedef _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> iterator;
1.107 + // typedef _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All> const_iterator;
1.108 + typedef _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All> _Self;
1.109 +
1.110 + typedef hashtable<_Val,_Key,_HF,_ExK,_EqK,_All> _Hashtable;
1.111 + typedef _Hashtable_node<_Val> _Node;
1.112 +
1.113 + typedef _Val value_type;
1.114 + typedef forward_iterator_tag iterator_category;
1.115 + typedef ptrdiff_t difference_type;
1.116 + typedef size_t size_type;
1.117 + typedef typename _Traits::reference reference;
1.118 + typedef typename _Traits::pointer pointer;
1.119 +
1.120 + _Ht_iterator(const _Node* __n, const _Hashtable* __tab) :
1.121 + _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>((_Node*)__n, (_Hashtable*)__tab) {}
1.122 + _Ht_iterator() {}
1.123 + _Ht_iterator(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __it) :
1.124 + _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>(__it) {}
1.125 +
1.126 + reference operator*() const {
1.127 + return this->_M_cur->_M_val;
1.128 + }
1.129 + _STLP_DEFINE_ARROW_OPERATOR
1.130 +
1.131 + _Self& operator++() {
1.132 + _Node* __n = this->_M_cur->_M_next;
1.133 + this->_M_cur = (__n !=0 ? __n : this->_M_skip_to_next());
1.134 + return *this;
1.135 + }
1.136 + inline _Self operator++(int) {
1.137 + _Self __tmp = *this;
1.138 + ++*this;
1.139 + return __tmp;
1.140 + }
1.141 +};
1.142 +
1.143 +template <class _Val, class _Traits, class _Traits1, class _Key, class _HF,
1.144 + class _ExK, class _EqK, class _All>
1.145 +inline bool
1.146 +operator==(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>& __x,
1.147 + const _Ht_iterator<_Val, _Traits1,_Key,_HF,_ExK,_EqK,_All>& __y) {
1.148 + return __x._M_cur == __y._M_cur;
1.149 +}
1.150 +
1.151 +#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
1.152 +template <class _Val, class _Key, class _HF,
1.153 + class _ExK, class _EqK, class _All>
1.154 +inline bool
1.155 +operator!=(const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __x,
1.156 + const _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& __y) {
1.157 + return __x._M_cur != __y._M_cur;
1.158 +}
1.159 +#else
1.160 +
1.161 +# if (defined (__GNUC__) && (__GNUC_MINOR__ < 8))
1.162 +template <class _Val, class _Key, class _HF,
1.163 + class _ExK, class _EqK, class _All>
1.164 +inline bool
1.165 +operator!=(const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x,
1.166 + const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) {
1.167 + return __x._M_cur != __y._M_cur;
1.168 +}
1.169 +# endif
1.170 +
1.171 +template <class _Val, class _Key, class _HF,
1.172 + class _ExK, class _EqK, class _All>
1.173 +inline bool
1.174 +operator!=(const _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __x,
1.175 + const _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>& __y) {
1.176 + return __x._M_cur != __y._M_cur;
1.177 +}
1.178 +#endif
1.179 +
1.180 +# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
1.181 +template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.182 +inline _Val* value_type(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (_Val*) 0; }
1.183 +template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.184 +inline forward_iterator_tag iterator_category(const _Ht_iterator<_Val, _Traits,_Key,_HF,_ExK,_EqK,_All>&) { return forward_iterator_tag(); }
1.185 +template <class _Val, class _Traits, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.186 +inline ptrdiff_t* distance_type(const _Ht_iterator<_Val,_Traits,_Key,_HF,_ExK,_EqK,_All>&) { return (ptrdiff_t*) 0; }
1.187 +#endif
1.188 +
1.189 +#define __stl_num_primes 28
1.190 +template <class _Tp>
1.191 +class _Stl_prime {
1.192 +public:
1.193 + static const size_t _M_list[__stl_num_primes];
1.194 +};
1.195 +
1.196 +# if defined (_STLP_USE_TEMPLATE_EXPORT)
1.197 +_STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
1.198 +# endif
1.199 +
1.200 +typedef _Stl_prime<bool> _Stl_prime_type;
1.201 +
1.202 +
1.203 +// Hashtables handle allocators a bit differently than other containers
1.204 +// do. If we're using standard-conforming allocators, then a hashtable
1.205 +// unconditionally has a member variable to hold its allocator, even if
1.206 +// it so happens that all instances of the allocator type are identical.
1.207 +// This is because, for hashtables, this extra storage is negligible.
1.208 +// Additionally, a base class wouldn't serve any other purposes; it
1.209 +// wouldn't, for example, simplify the exception-handling code.
1.210 +template <class _Val, class _Key, class _HF,
1.211 + class _ExK, class _EqK, class _All>
1.212 +class hashtable
1.213 +{
1.214 + typedef hashtable<_Val, _Key, _HF, _ExK, _EqK, _All> _Self;
1.215 +public:
1.216 + typedef _Key key_type;
1.217 + typedef _Val value_type;
1.218 + typedef _HF hasher;
1.219 + typedef _EqK key_equal;
1.220 +
1.221 + typedef size_t size_type;
1.222 + typedef ptrdiff_t difference_type;
1.223 + typedef value_type* pointer;
1.224 + typedef const value_type* const_pointer;
1.225 + typedef value_type& reference;
1.226 + typedef const value_type& const_reference;
1.227 + typedef forward_iterator_tag _Iterator_category;
1.228 +
1.229 + hasher hash_funct() const { return _M_hash; }
1.230 + key_equal key_eq() const { return _M_equals; }
1.231 +
1.232 +private:
1.233 + typedef _Hashtable_node<_Val> _Node;
1.234 +
1.235 +private:
1.236 + _STLP_FORCE_ALLOCATORS(_Val, _All)
1.237 + typedef typename _Alloc_traits<_Node, _All>::allocator_type _M_node_allocator_type;
1.238 + typedef typename _Alloc_traits<void*, _All>::allocator_type _M_node_ptr_allocator_type;
1.239 + typedef __vector__<void*, _M_node_ptr_allocator_type> _BucketVector;
1.240 +public:
1.241 + typedef typename _Alloc_traits<_Val,_All>::allocator_type allocator_type;
1.242 + allocator_type get_allocator() const {
1.243 + return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_num_elements, _Val);
1.244 + }
1.245 +private:
1.246 + hasher _M_hash;
1.247 + key_equal _M_equals;
1.248 + _ExK _M_get_key;
1.249 + _BucketVector _M_buckets;
1.250 + _STLP_alloc_proxy<size_type, _Node, _M_node_allocator_type> _M_num_elements;
1.251 + const _Node* _M_get_bucket(size_t __n) const { return (_Node*)_M_buckets[__n]; }
1.252 +
1.253 +public:
1.254 + typedef _Const_traits<_Val> __const_val_traits;
1.255 + typedef _Nonconst_traits<_Val> __nonconst_val_traits;
1.256 + typedef _Ht_iterator<_Val, __const_val_traits,_Key,_HF,_ExK,_EqK, _All> const_iterator;
1.257 + typedef _Ht_iterator<_Val, __nonconst_val_traits,_Key,_HF,_ExK,_EqK,_All> iterator;
1.258 + friend struct _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>;
1.259 + friend struct _Ht_iterator<_Val, _Nonconst_traits<_Val>,_Key,_HF,_ExK,_EqK,_All>;
1.260 + friend struct _Ht_iterator<_Val, _Const_traits<_Val>,_Key,_HF,_ExK,_EqK, _All>;
1.261 +
1.262 +public:
1.263 + hashtable(size_type __n,
1.264 + const _HF& __hf,
1.265 + const _EqK& __eql,
1.266 + const _ExK& __ext,
1.267 + const allocator_type& __a = allocator_type())
1.268 + :
1.269 + _M_hash(__hf),
1.270 + _M_equals(__eql),
1.271 + _M_get_key(__ext),
1.272 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)),
1.273 + _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0)
1.274 + {
1.275 + _M_initialize_buckets(__n);
1.276 + }
1.277 +
1.278 + hashtable(size_type __n,
1.279 + const _HF& __hf = hasher(),
1.280 + const _EqK& __eql = key_equal(),
1.281 + const allocator_type& __a = allocator_type())
1.282 + :
1.283 + _M_hash(__hf),
1.284 + _M_equals(__eql),
1.285 + _M_get_key(_ExK()),
1.286 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a,void*)),
1.287 + _M_num_elements(_STLP_CONVERT_ALLOCATOR(__a,_Node), (size_type)0)
1.288 + {
1.289 + _M_initialize_buckets(__n);
1.290 + }
1.291 +
1.292 + hashtable(const _Self& __ht)
1.293 + :
1.294 + _M_hash(__ht._M_hash),
1.295 + _M_equals(__ht._M_equals),
1.296 + _M_get_key(__ht._M_get_key),
1.297 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(),void*)),
1.298 + _M_num_elements((const _M_node_allocator_type&)__ht._M_num_elements, (size_type)0)
1.299 + {
1.300 + _M_copy_from(__ht);
1.301 + }
1.302 +
1.303 + _Self& operator= (const _Self& __ht)
1.304 + {
1.305 + if (&__ht != this) {
1.306 + clear();
1.307 + _M_hash = __ht._M_hash;
1.308 + _M_equals = __ht._M_equals;
1.309 + _M_get_key = __ht._M_get_key;
1.310 + _M_copy_from(__ht);
1.311 + }
1.312 + return *this;
1.313 + }
1.314 +
1.315 + ~hashtable() { clear(); }
1.316 +
1.317 + size_type size() const { return _M_num_elements._M_data; }
1.318 + size_type max_size() const { return size_type(-1); }
1.319 + bool empty() const { return size() == 0; }
1.320 +
1.321 + void swap(_Self& __ht)
1.322 + {
1.323 + _STLP_STD::swap(_M_hash, __ht._M_hash);
1.324 + _STLP_STD::swap(_M_equals, __ht._M_equals);
1.325 + _STLP_STD::swap(_M_get_key, __ht._M_get_key);
1.326 + _M_buckets.swap(__ht._M_buckets);
1.327 + _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
1.328 + }
1.329 +
1.330 + iterator begin()
1.331 + {
1.332 + for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
1.333 + if (_M_buckets[__n])
1.334 + return iterator((_Node*)_M_buckets[__n], this);
1.335 + return end();
1.336 + }
1.337 +
1.338 + iterator end() { return iterator((_Node*)0, this); }
1.339 +
1.340 + const_iterator begin() const
1.341 + {
1.342 + for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
1.343 + if (_M_buckets[__n])
1.344 + return const_iterator((_Node*)_M_buckets[__n], this);
1.345 + return end();
1.346 + }
1.347 +
1.348 + const_iterator end() const { return const_iterator((_Node*)0, this); }
1.349 +
1.350 + static bool _STLP_CALL _M_equal (const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&,
1.351 + const hashtable<_Val, _Key, _HF, _ExK, _EqK, _All>&);
1.352 +
1.353 +public:
1.354 +
1.355 + size_type bucket_count() const { return _M_buckets.size(); }
1.356 +
1.357 + size_type max_bucket_count() const
1.358 + { return _Stl_prime_type::_M_list[(int)__stl_num_primes - 1]; }
1.359 +
1.360 + size_type elems_in_bucket(size_type __bucket) const
1.361 + {
1.362 + size_type __result = 0;
1.363 + for (_Node* __cur = (_Node*)_M_buckets[__bucket]; __cur; __cur = __cur->_M_next)
1.364 + __result += 1;
1.365 + return __result;
1.366 + }
1.367 +
1.368 + pair<iterator, bool> insert_unique(const value_type& __obj)
1.369 + {
1.370 + resize(_M_num_elements._M_data + 1);
1.371 + return insert_unique_noresize(__obj);
1.372 + }
1.373 +
1.374 + iterator insert_equal(const value_type& __obj)
1.375 + {
1.376 + resize(_M_num_elements._M_data + 1);
1.377 + return insert_equal_noresize(__obj);
1.378 + }
1.379 +
1.380 + pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
1.381 + iterator insert_equal_noresize(const value_type& __obj);
1.382 +
1.383 +#ifdef _STLP_MEMBER_TEMPLATES
1.384 + template <class _InputIterator>
1.385 + void insert_unique(_InputIterator __f, _InputIterator __l)
1.386 + {
1.387 + insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
1.388 + }
1.389 +
1.390 + template <class _InputIterator>
1.391 + void insert_equal(_InputIterator __f, _InputIterator __l)
1.392 + {
1.393 + insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator));
1.394 + }
1.395 +
1.396 + template <class _InputIterator>
1.397 + void insert_unique(_InputIterator __f, _InputIterator __l,
1.398 + const input_iterator_tag &)
1.399 + {
1.400 + for ( ; __f != __l; ++__f)
1.401 + insert_unique(*__f);
1.402 + }
1.403 +
1.404 + template <class _InputIterator>
1.405 + void insert_equal(_InputIterator __f, _InputIterator __l,
1.406 + const input_iterator_tag &)
1.407 + {
1.408 + for ( ; __f != __l; ++__f)
1.409 + insert_equal(*__f);
1.410 + }
1.411 +
1.412 + template <class _ForwardIterator>
1.413 + void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
1.414 + const forward_iterator_tag &)
1.415 + {
1.416 + size_type __n = distance(__f, __l);
1.417 + resize(_M_num_elements._M_data + __n);
1.418 + for ( ; __n > 0; --__n, ++__f)
1.419 + insert_unique_noresize(*__f);
1.420 + }
1.421 +
1.422 + template <class _ForwardIterator>
1.423 + void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
1.424 + const forward_iterator_tag &)
1.425 + {
1.426 + size_type __n = distance(__f, __l);
1.427 + resize(_M_num_elements._M_data + __n);
1.428 + for ( ; __n > 0; --__n, ++__f)
1.429 + insert_equal_noresize(*__f);
1.430 + }
1.431 +
1.432 +#else /* _STLP_MEMBER_TEMPLATES */
1.433 + void insert_unique(const value_type* __f, const value_type* __l)
1.434 + {
1.435 + size_type __n = __l - __f;
1.436 + resize(_M_num_elements._M_data + __n);
1.437 + for ( ; __n > 0; --__n, ++__f)
1.438 + insert_unique_noresize(*__f);
1.439 + }
1.440 +
1.441 + void insert_equal(const value_type* __f, const value_type* __l)
1.442 + {
1.443 + size_type __n = __l - __f;
1.444 + resize(_M_num_elements._M_data + __n);
1.445 + for ( ; __n > 0; --__n, ++__f)
1.446 + insert_equal_noresize(*__f);
1.447 + }
1.448 +
1.449 + void insert_unique(const_iterator __f, const_iterator __l)
1.450 + {
1.451 + size_type __n = distance(__f, __l);
1.452 + resize(_M_num_elements._M_data + __n);
1.453 + for ( ; __n > 0; --__n, ++__f)
1.454 + insert_unique_noresize(*__f);
1.455 + }
1.456 +
1.457 + void insert_equal(const_iterator __f, const_iterator __l)
1.458 + {
1.459 + size_type __n = distance(__f, __l);
1.460 + resize(_M_num_elements._M_data + __n);
1.461 + for ( ; __n > 0; --__n, ++__f)
1.462 + insert_equal_noresize(*__f);
1.463 + }
1.464 +#endif /*_STLP_MEMBER_TEMPLATES */
1.465 +
1.466 + reference find_or_insert(const value_type& __obj);
1.467 +
1.468 +private:
1.469 +# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC_)))
1.470 + template <class _KT>
1.471 + _Node* _M_find(const _KT& __key) const
1.472 +# else
1.473 + _Node* _M_find(const key_type& __key) const
1.474 +# endif
1.475 + {
1.476 + size_type __n = _M_hash(__key)% _M_buckets.size();
1.477 + _Node* __first;
1.478 + for ( __first = (_Node*)_M_buckets[__n];
1.479 + __first && !_M_equals(_M_get_key(__first->_M_val), __key);
1.480 + __first = __first->_M_next)
1.481 + {}
1.482 + return __first;
1.483 + }
1.484 +
1.485 +public:
1.486 +# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)))
1.487 + template <class _KT>
1.488 + iterator find(const _KT& __key)
1.489 +# else
1.490 + iterator find(const key_type& __key)
1.491 +# endif
1.492 + {
1.493 + return iterator(_M_find(__key), this);
1.494 + }
1.495 +
1.496 +# if defined(_STLP_MEMBER_TEMPLATES) && ! defined ( _STLP_NO_EXTENSIONS ) && !(defined(__MRC__)||(defined(__SC__)&&!defined(__DMC__)))
1.497 + template <class _KT>
1.498 + const_iterator find(const _KT& __key) const
1.499 +# else
1.500 + const_iterator find(const key_type& __key) const
1.501 +# endif
1.502 + {
1.503 + return const_iterator(_M_find(__key), this);
1.504 + }
1.505 +
1.506 + size_type count(const key_type& __key) const
1.507 + {
1.508 + const size_type __n = _M_bkt_num_key(__key);
1.509 + size_type __result = 0;
1.510 +
1.511 + for (const _Node* __cur = (_Node*)_M_buckets[__n]; __cur; __cur = __cur->_M_next)
1.512 + if (_M_equals(_M_get_key(__cur->_M_val), __key))
1.513 + ++__result;
1.514 + return __result;
1.515 + }
1.516 +
1.517 + pair<iterator, iterator>
1.518 + equal_range(const key_type& __key);
1.519 +
1.520 + pair<const_iterator, const_iterator>
1.521 + equal_range(const key_type& __key) const;
1.522 +
1.523 + size_type erase(const key_type& __key);
1.524 + // void erase(const iterator& __it); `
1.525 + void erase(const const_iterator& __it) ;
1.526 +
1.527 + // void erase(const const_iterator& __first, const const_iterator __last) {
1.528 + // erase((const iterator&)__first, (const iterator&)__last);
1.529 + // }
1.530 + void erase(const_iterator __first, const_iterator __last);
1.531 + void resize(size_type __num_elements_hint);
1.532 + void clear();
1.533 +
1.534 +public:
1.535 + // this is for hash_map::operator[]
1.536 + reference _M_insert(const value_type& __obj);
1.537 +
1.538 +private:
1.539 +
1.540 + size_type _M_next_size(size_type __n) const;
1.541 +
1.542 + void _M_initialize_buckets(size_type __n)
1.543 + {
1.544 + const size_type __n_buckets = _M_next_size(__n);
1.545 + _M_buckets.reserve(__n_buckets);
1.546 + _M_buckets.insert(_M_buckets.end(), __n_buckets, (void*) 0);
1.547 + _M_num_elements._M_data = 0;
1.548 + }
1.549 +
1.550 + size_type _M_bkt_num_key(const key_type& __key) const
1.551 + {
1.552 + return _M_bkt_num_key(__key, _M_buckets.size());
1.553 + }
1.554 +
1.555 + size_type _M_bkt_num(const value_type& __obj) const
1.556 + {
1.557 + return _M_bkt_num_key(_M_get_key(__obj));
1.558 + }
1.559 +
1.560 + size_type _M_bkt_num_key(const key_type& __key, size_t __n) const
1.561 + {
1.562 + return _M_hash(__key) % __n;
1.563 + }
1.564 +
1.565 + size_type _M_bkt_num(const value_type& __obj, size_t __n) const
1.566 + {
1.567 + return _M_bkt_num_key(_M_get_key(__obj), __n);
1.568 + }
1.569 +
1.570 + _Node* _M_new_node(const value_type& __obj)
1.571 + {
1.572 + _Node* __n = _M_num_elements.allocate(1);
1.573 + __n->_M_next = 0;
1.574 + _STLP_TRY {
1.575 + _Construct(&__n->_M_val, __obj);
1.576 + // return __n;
1.577 + }
1.578 + _STLP_UNWIND(_M_num_elements.deallocate(__n, 1));
1.579 + return __n;
1.580 + }
1.581 +
1.582 + void _M_delete_node(_Node* __n)
1.583 + {
1.584 + _STLP_STD::_Destroy(&__n->_M_val);
1.585 + _M_num_elements.deallocate(__n, 1);
1.586 + }
1.587 +
1.588 + void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
1.589 + void _M_erase_bucket(const size_type __n, _Node* __last);
1.590 +
1.591 + void _M_copy_from(const _Self& __ht);
1.592 +};
1.593 +
1.594 +#define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _ExK, class _EqK, class _All>
1.595 +#define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_ExK,_EqK,_All>
1.596 +#include <stl/_relops_hash_cont.h>
1.597 +#undef _STLP_TEMPLATE_CONTAINER
1.598 +#undef _STLP_TEMPLATE_HEADER
1.599 +
1.600 +_STLP_END_NAMESPACE
1.601 +
1.602 +# undef hashtable
1.603 +
1.604 +# if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.605 +# include <stl/_hashtable.c>
1.606 +# endif
1.607 +
1.608 +# if defined (_STLP_DEBUG)
1.609 +# include <stl/debug/_hashtable.h>
1.610 +# endif
1.611 +
1.612 +#endif /* _STLP_INTERNAL_HASHTABLE_H */
1.613 +
1.614 +// Local Variables:
1.615 +// mode:C++
1.616 +// End:
1.617 +
1.618 +