1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_hashtable.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,683 @@
1.4 +/*
1.5 + * Portions Copyright (c) 2008 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
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_SLIST_H
1.42 +# include <stl/_slist.h>
1.43 +#endif
1.44 +
1.45 +#ifndef _STLP_INTERNAL_ITERATOR_H
1.46 +# include <stl/_iterator.h>
1.47 +#endif
1.48 +
1.49 +#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
1.50 +# include <stl/_function_base.h>
1.51 +#endif
1.52 +
1.53 +#ifndef _STLP_INTERNAL_ALGOBASE_H
1.54 +# include <stl/_algobase.h>
1.55 +#endif
1.56 +
1.57 +#ifndef _STLP_HASH_FUN_H
1.58 +# include <stl/_hash_fun.h>
1.59 +#endif
1.60 +
1.61 +/*
1.62 + * Hashtable class, used to implement the hashed associative containers
1.63 + * hash_set, hash_map, hash_multiset, hash_multimap,
1.64 + * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
1.65 + */
1.66 +
1.67 +_STLP_BEGIN_NAMESPACE
1.68 +
1.69 +#if defined (_STLP_USE_TEMPLATE_EXPORT)
1.70 +//Export of the classes used to represent buckets in the hashtable implementation.
1.71 +# if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.72 +//If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
1.73 +//storage type for which internal classes have already been exported.
1.74 +_STLP_EXPORT_TEMPLATE_CLASS allocator<_STLP_PRIV _Slist_node_base*>;
1.75 +
1.76 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.77 +_STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Slist_node_base**, _Slist_node_base*,
1.78 + allocator<_Slist_node_base*> >;
1.79 +_STLP_EXPORT_TEMPLATE_CLASS _Vector_base<_Slist_node_base*,
1.80 + allocator<_Slist_node_base*> >;
1.81 +_STLP_MOVE_TO_STD_NAMESPACE
1.82 +# endif
1.83 +
1.84 +# if defined (_STLP_DEBUG)
1.85 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.86 +# define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
1.87 +_STLP_EXPORT_TEMPLATE_CLASS __construct_checker<_STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> > >;
1.88 +_STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
1.89 +# undef _STLP_NON_DBG_VECTOR
1.90 +_STLP_MOVE_TO_STD_NAMESPACE
1.91 +# endif
1.92 +
1.93 +_STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*,
1.94 + allocator<_STLP_PRIV _Slist_node_base*> >;
1.95 +#endif
1.96 +
1.97 +#if defined (_STLP_DEBUG)
1.98 +# define hashtable _STLP_NON_DBG_NAME(hashtable)
1.99 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.100 +#endif
1.101 +
1.102 +// some compilers require the names of template parameters to be the same
1.103 +template <class _Val, class _Key, class _HF,
1.104 + class _Traits, class _ExK, class _EqK, class _All>
1.105 +class hashtable;
1.106 +
1.107 +#if !defined (_STLP_DEBUG)
1.108 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.109 +#endif
1.110 +
1.111 +template <class _BaseIte, class _Traits>
1.112 +struct _Ht_iterator {
1.113 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.114 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.115 +
1.116 + typedef _Ht_iterator<_BaseIte,_Traits> _Self;
1.117 +
1.118 + typedef typename _Traits::value_type value_type;
1.119 + typedef typename _Traits::pointer pointer;
1.120 + typedef typename _Traits::reference reference;
1.121 + typedef forward_iterator_tag iterator_category;
1.122 + typedef ptrdiff_t difference_type;
1.123 + typedef size_t size_type;
1.124 +
1.125 + typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator;
1.126 + typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator;
1.127 +
1.128 + _Ht_iterator() {}
1.129 + //copy constructor for iterator and constructor from iterator for const_iterator
1.130 + _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {}
1.131 + _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
1.132 +
1.133 + reference operator*() const {
1.134 + return *_M_ite;
1.135 + }
1.136 + _STLP_DEFINE_ARROW_OPERATOR
1.137 +
1.138 + _Self& operator++() {
1.139 + ++_M_ite;
1.140 + return *this;
1.141 + }
1.142 + _Self operator++(int) {
1.143 + _Self __tmp = *this;
1.144 + ++*this;
1.145 + return __tmp;
1.146 + }
1.147 +
1.148 + bool operator == (const_iterator __rhs) const {
1.149 + return _M_ite == __rhs._M_ite;
1.150 + }
1.151 + bool operator != (const_iterator __rhs) const {
1.152 + return _M_ite != __rhs._M_ite;
1.153 + }
1.154 +
1.155 + _BaseIte _M_ite;
1.156 +};
1.157 +
1.158 +_STLP_MOVE_TO_STD_NAMESPACE
1.159 +
1.160 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.161 +template <class _BaseIte, class _Traits>
1.162 +struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
1.163 + typedef __false_type has_trivial_default_constructor;
1.164 + typedef __true_type has_trivial_copy_constructor;
1.165 + typedef __true_type has_trivial_assignment_operator;
1.166 + typedef __true_type has_trivial_destructor;
1.167 + typedef __false_type is_POD_type;
1.168 +};
1.169 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.170 +
1.171 +#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1.172 +template <class _BaseIte, class _Traits>
1.173 +inline
1.174 +# if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.175 +_STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
1.176 +# else
1.177 +_STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type *
1.178 +# endif
1.179 +value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
1.180 + typedef typename _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val;
1.181 + return (_Val*) 0;
1.182 +}
1.183 +template <class _BaseIte, class _Traits>
1.184 +inline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
1.185 +{ return forward_iterator_tag(); }
1.186 +template <class _BaseIte, class _Traits>
1.187 +inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
1.188 +{ return (ptrdiff_t*) 0; }
1.189 +#endif
1.190 +
1.191 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.192 +
1.193 +template <class _Dummy>
1.194 +class _Stl_prime {
1.195 +public:
1.196 + //Returns the maximum number of buckets handled by the hashtable implementation
1.197 + static size_t _STLP_CALL _S_max_nb_buckets();
1.198 +
1.199 + //Returns the bucket size next to a required size
1.200 + static size_t _STLP_CALL _S_next_size(size_t);
1.201 +};
1.202 +
1.203 +#if defined (_STLP_USE_TEMPLATE_EXPORT)
1.204 +_STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
1.205 +#endif
1.206 +
1.207 +typedef _Stl_prime<bool> _Stl_prime_type;
1.208 +
1.209 +#if !defined (_STLP_DEBUG)
1.210 +_STLP_MOVE_TO_STD_NAMESPACE
1.211 +#endif
1.212 +
1.213 +/*
1.214 + * Hashtables handle allocators a bit differently than other containers
1.215 + * do. If we're using standard-conforming allocators, then a hashtable
1.216 + * unconditionally has a member variable to hold its allocator, even if
1.217 + * it so happens that all instances of the allocator type are identical.
1.218 + * This is because, for hashtables, this extra storage is negligible.
1.219 + * Additionally, a base class wouldn't serve any other purposes; it
1.220 + * wouldn't, for example, simplify the exception-handling code.
1.221 + */
1.222 +template <class _Val, class _Key, class _HF,
1.223 + class _Traits, class _ExK, class _EqK, class _All>
1.224 +class hashtable {
1.225 + typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
1.226 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.227 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.228 + typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
1.229 + typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
1.230 +
1.231 +public:
1.232 + typedef _Key key_type;
1.233 + typedef _Val value_type;
1.234 + typedef _HF hasher;
1.235 + typedef _EqK key_equal;
1.236 +
1.237 + typedef size_t size_type;
1.238 + typedef ptrdiff_t difference_type;
1.239 + typedef typename _NonConstTraits::pointer pointer;
1.240 + typedef const value_type* const_pointer;
1.241 + typedef typename _NonConstTraits::reference reference;
1.242 + typedef const value_type& const_reference;
1.243 + typedef forward_iterator_tag _Iterator_category;
1.244 +
1.245 + hasher hash_funct() const { return _M_hash; }
1.246 + key_equal key_eq() const { return _M_equals; }
1.247 +
1.248 +private:
1.249 + _STLP_FORCE_ALLOCATORS(_Val, _All)
1.250 +#if defined (_STLP_DEBUG)
1.251 + typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
1.252 +#else
1.253 + typedef slist<value_type, _All> _ElemsCont;
1.254 +#endif
1.255 + typedef typename _ElemsCont::iterator _ElemsIte;
1.256 + typedef typename _ElemsCont::const_iterator _ElemsConstIte;
1.257 + typedef _STLP_PRIV _Slist_node_base _BucketType;
1.258 + typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _M_bucket_allocator_type;
1.259 + /*
1.260 + * We are going to use vector of _Slist_node_base pointers for 2 reasons:
1.261 + * - limit code bloat, all hashtable instanciation use the same buckets representation.
1.262 + * - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
1.263 + * method would be too slow because the slist::splice_after method become linear on
1.264 + * the number of iterators in the buckets rather than constant in time as the iterator
1.265 + * has to be move from a slist to the other.
1.266 + */
1.267 +#if defined (_STLP_DEBUG)
1.268 + typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _M_bucket_allocator_type> _BucketVector;
1.269 +#else
1.270 + typedef vector<_BucketType*, _M_bucket_allocator_type> _BucketVector;
1.271 +#endif
1.272 +
1.273 + hasher _M_hash;
1.274 + key_equal _M_equals;
1.275 + _ExK _M_get_key;
1.276 + _ElemsCont _M_elems;
1.277 + _BucketVector _M_buckets;
1.278 + size_type _M_num_elements;
1.279 + float _M_max_load_factor;
1.280 + _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
1.281 +
1.282 +public:
1.283 + typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator;
1.284 + typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator;
1.285 + //TODO: Avoids this debug check and make the local_iterator different from
1.286 + //iterator in debug mode too.
1.287 +#if !defined (_STLP_DEBUG)
1.288 + typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator;
1.289 + typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator;
1.290 +#else
1.291 + typedef iterator local_iterator;
1.292 + typedef const_iterator const_local_iterator;
1.293 +#endif
1.294 +
1.295 + typedef typename _Alloc_traits<_Val, _All>::allocator_type allocator_type;
1.296 + allocator_type get_allocator() const { return _M_elems.get_allocator(); }
1.297 +
1.298 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.299 + hashtable(size_type __n,
1.300 + const _HF& __hf,
1.301 + const _EqK& __eql,
1.302 + const _ExK& __ext,
1.303 + const allocator_type& __a = allocator_type())
1.304 +#else
1.305 + hashtable(size_type __n,
1.306 + const _HF& __hf,
1.307 + const _EqK& __eql,
1.308 + const _ExK& __ext)
1.309 + : _M_hash(__hf),
1.310 + _M_equals(__eql),
1.311 + _M_get_key(__ext),
1.312 + _M_elems(allocator_type()),
1.313 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
1.314 + _M_num_elements(0),
1.315 + _M_max_load_factor(1.0f)
1.316 + { _M_initialize_buckets(__n); }
1.317 +
1.318 + hashtable(size_type __n,
1.319 + const _HF& __hf,
1.320 + const _EqK& __eql,
1.321 + const _ExK& __ext,
1.322 + const allocator_type& __a)
1.323 +#endif
1.324 + : _M_hash(__hf),
1.325 + _M_equals(__eql),
1.326 + _M_get_key(__ext),
1.327 + _M_elems(__a),
1.328 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
1.329 + _M_num_elements(0),
1.330 + _M_max_load_factor(1.0f)
1.331 + { _M_initialize_buckets(__n); }
1.332 +
1.333 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.334 + hashtable(size_type __n,
1.335 + const _HF& __hf,
1.336 + const _EqK& __eql,
1.337 + const allocator_type& __a = allocator_type())
1.338 +#else
1.339 + hashtable(size_type __n,
1.340 + const _HF& __hf,
1.341 + const _EqK& __eql)
1.342 + : _M_hash(__hf),
1.343 + _M_equals(__eql),
1.344 + _M_get_key(_ExK()),
1.345 + _M_elems(allocator_type()),
1.346 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
1.347 + _M_num_elements(0),
1.348 + _M_max_load_factor(1.0f)
1.349 + { _M_initialize_buckets(__n); }
1.350 +
1.351 + hashtable(size_type __n,
1.352 + const _HF& __hf,
1.353 + const _EqK& __eql,
1.354 + const allocator_type& __a)
1.355 +#endif
1.356 + : _M_hash(__hf),
1.357 + _M_equals(__eql),
1.358 + _M_get_key(_ExK()),
1.359 + _M_elems(__a),
1.360 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
1.361 + _M_num_elements(0),
1.362 + _M_max_load_factor(1.0f)
1.363 + { _M_initialize_buckets(__n); }
1.364 +
1.365 + hashtable(const _Self& __ht)
1.366 + : _M_hash(__ht._M_hash),
1.367 + _M_equals(__ht._M_equals),
1.368 + _M_get_key(__ht._M_get_key),
1.369 + _M_elems(__ht.get_allocator()),
1.370 + _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
1.371 + _M_num_elements(0),
1.372 + _M_max_load_factor(1.0f)
1.373 + { _M_copy_from(__ht); }
1.374 +
1.375 + hashtable(__move_source<_Self> src)
1.376 + : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
1.377 + _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
1.378 + _M_get_key(_STLP_PRIV _AsMoveSource(src.get()._M_get_key)),
1.379 + _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
1.380 + _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
1.381 + _M_num_elements(src.get()._M_num_elements),
1.382 + _M_max_load_factor(src.get()._M_max_load_factor) {}
1.383 +
1.384 + _Self& operator= (const _Self& __ht) {
1.385 + if (&__ht != this) {
1.386 + clear();
1.387 + _M_hash = __ht._M_hash;
1.388 + _M_equals = __ht._M_equals;
1.389 + _M_get_key = __ht._M_get_key;
1.390 + _M_copy_from(__ht);
1.391 + }
1.392 + return *this;
1.393 + }
1.394 +
1.395 + ~hashtable() { clear(); }
1.396 +
1.397 + size_type size() const { return _M_num_elements; }
1.398 + size_type max_size() const { return size_type(-1); }
1.399 + bool empty() const { return size() == 0; }
1.400 +
1.401 + void swap(_Self& __ht) {
1.402 + _STLP_STD::swap(_M_hash, __ht._M_hash);
1.403 + _STLP_STD::swap(_M_equals, __ht._M_equals);
1.404 + _STLP_STD::swap(_M_get_key, __ht._M_get_key);
1.405 + _M_elems.swap(__ht._M_elems);
1.406 + _M_buckets.swap(__ht._M_buckets);
1.407 + _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
1.408 + _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
1.409 + }
1.410 +
1.411 + iterator begin() { return _M_elems.begin(); }
1.412 + iterator end() { return _M_elems.end(); }
1.413 + local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
1.414 + local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }
1.415 +
1.416 + const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
1.417 + const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
1.418 + const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
1.419 + const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }
1.420 +
1.421 + //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
1.422 +
1.423 +public:
1.424 + //The number of buckets is size() - 1 because the last bucket always contains
1.425 + //_M_elems.end() to make algo easier to implement.
1.426 + size_type bucket_count() const { return _M_buckets.size() - 1; }
1.427 + size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
1.428 + size_type elems_in_bucket(size_type __bucket) const
1.429 + { return distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
1.430 +
1.431 + _STLP_TEMPLATE_FOR_CONT_EXT
1.432 + size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
1.433 +
1.434 + // hash policy
1.435 + float load_factor() const { return (float)size() / (float)bucket_count(); }
1.436 + float max_load_factor() const { return _M_max_load_factor; }
1.437 + void max_load_factor(float __z) { _M_max_load_factor = __z;}
1.438 +
1.439 + pair<iterator, bool> insert_unique(const value_type& __obj) {
1.440 + resize(_M_num_elements + 1);
1.441 + return insert_unique_noresize(__obj);
1.442 + }
1.443 +
1.444 + iterator insert_equal(const value_type& __obj) {
1.445 + resize(_M_num_elements + 1);
1.446 + return insert_equal_noresize(__obj);
1.447 + }
1.448 +
1.449 +protected:
1.450 + iterator _M_insert_noresize(size_type __n, const value_type& __obj);
1.451 +public:
1.452 + pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
1.453 + iterator insert_equal_noresize(const value_type& __obj);
1.454 +
1.455 +#if defined (_STLP_MEMBER_TEMPLATES)
1.456 + template <class _InputIterator>
1.457 + void insert_unique(_InputIterator __f, _InputIterator __l)
1.458 + { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
1.459 +
1.460 + template <class _InputIterator>
1.461 + void insert_equal(_InputIterator __f, _InputIterator __l)
1.462 + { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
1.463 +
1.464 + template <class _InputIterator>
1.465 + void insert_unique(_InputIterator __f, _InputIterator __l,
1.466 + const input_iterator_tag &) {
1.467 + for ( ; __f != __l; ++__f)
1.468 + insert_unique(*__f);
1.469 + }
1.470 +
1.471 + template <class _InputIterator>
1.472 + void insert_equal(_InputIterator __f, _InputIterator __l,
1.473 + const input_iterator_tag &) {
1.474 + for ( ; __f != __l; ++__f)
1.475 + insert_equal(*__f);
1.476 + }
1.477 +
1.478 + template <class _ForwardIterator>
1.479 + void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
1.480 + const forward_iterator_tag &) {
1.481 + size_type __n = distance(__f, __l);
1.482 + resize(_M_num_elements + __n);
1.483 + for ( ; __n > 0; --__n, ++__f)
1.484 + insert_unique_noresize(*__f);
1.485 + }
1.486 +
1.487 + template <class _ForwardIterator>
1.488 + void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
1.489 + const forward_iterator_tag &) {
1.490 + size_type __n = distance(__f, __l);
1.491 + resize(_M_num_elements + __n);
1.492 + for ( ; __n > 0; --__n, ++__f)
1.493 + insert_equal_noresize(*__f);
1.494 + }
1.495 +
1.496 +#else /* _STLP_MEMBER_TEMPLATES */
1.497 + void insert_unique(const value_type* __f, const value_type* __l) {
1.498 + size_type __n = __l - __f;
1.499 + resize(_M_num_elements + __n);
1.500 + for ( ; __n > 0; --__n, ++__f)
1.501 + insert_unique_noresize(*__f);
1.502 + }
1.503 +
1.504 + void insert_equal(const value_type* __f, const value_type* __l) {
1.505 + size_type __n = __l - __f;
1.506 + resize(_M_num_elements + __n);
1.507 + for ( ; __n > 0; --__n, ++__f)
1.508 + insert_equal_noresize(*__f);
1.509 + }
1.510 +
1.511 + void insert_unique(const_iterator __f, const_iterator __l) {
1.512 + size_type __n = distance(__f, __l);
1.513 + resize(_M_num_elements + __n);
1.514 + for ( ; __n > 0; --__n, ++__f)
1.515 + insert_unique_noresize(*__f);
1.516 + }
1.517 +
1.518 + void insert_equal(const_iterator __f, const_iterator __l) {
1.519 + size_type __n = distance(__f, __l);
1.520 + resize(_M_num_elements + __n);
1.521 + for ( ; __n > 0; --__n, ++__f)
1.522 + insert_equal_noresize(*__f);
1.523 + }
1.524 +#endif /*_STLP_MEMBER_TEMPLATES */
1.525 +
1.526 + //reference find_or_insert(const value_type& __obj);
1.527 +
1.528 +private:
1.529 + _STLP_TEMPLATE_FOR_CONT_EXT
1.530 + _ElemsIte _M_find(const _KT& __key) const {
1.531 + size_type __n = _M_bkt_num_key(__key);
1.532 + _ElemsIte __first(_M_buckets[__n]);
1.533 + _ElemsIte __last(_M_buckets[__n + 1]);
1.534 + for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first) {}
1.535 + if (__first != __last)
1.536 + return __first;
1.537 + else
1.538 + return __CONST_CAST(_ElemsCont&, _M_elems).end();
1.539 + }
1.540 +
1.541 +public:
1.542 + _STLP_TEMPLATE_FOR_CONT_EXT
1.543 + iterator find(const _KT& __key) { return _M_find(__key); }
1.544 + _STLP_TEMPLATE_FOR_CONT_EXT
1.545 + const_iterator find(const _KT& __key) const { return _M_find(__key); }
1.546 +
1.547 + _STLP_TEMPLATE_FOR_CONT_EXT
1.548 + size_type count(const _KT& __key) const {
1.549 + const size_type __n = _M_bkt_num_key(__key);
1.550 +
1.551 + _ElemsIte __cur(_M_buckets[__n]);
1.552 + _ElemsIte __last(_M_buckets[__n + 1]);
1.553 + for (; __cur != __last; ++__cur) {
1.554 + if (_M_equals(_M_get_key(*__cur), __key)) {
1.555 + size_type __result = 1;
1.556 + for (++__cur;
1.557 + __cur != __last && _M_equals(_M_get_key(*__cur), __key);
1.558 + ++__result, ++__cur);
1.559 + return __result;
1.560 + }
1.561 + }
1.562 + return 0;
1.563 + }
1.564 +
1.565 + _STLP_TEMPLATE_FOR_CONT_EXT
1.566 + pair<iterator, iterator> equal_range(const _KT& __key) {
1.567 + typedef pair<iterator, iterator> _Pii;
1.568 + const size_type __n = _M_bkt_num_key(__key);
1.569 +
1.570 + for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
1.571 + __first != __last; ++__first) {
1.572 + if (_M_equals(_M_get_key(*__first), __key)) {
1.573 + _ElemsIte __cur(__first);
1.574 + for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
1.575 + return _Pii(__first, __cur);
1.576 + }
1.577 + }
1.578 + return _Pii(end(), end());
1.579 + }
1.580 +
1.581 + _STLP_TEMPLATE_FOR_CONT_EXT
1.582 + pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
1.583 + typedef pair<const_iterator, const_iterator> _Pii;
1.584 + const size_type __n = _M_bkt_num_key(__key);
1.585 +
1.586 + for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
1.587 + __first != __last; ++__first) {
1.588 + if (_M_equals(_M_get_key(*__first), __key)) {
1.589 + _ElemsIte __cur(__first);
1.590 + for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
1.591 + return _Pii(__first, __cur);
1.592 + }
1.593 + }
1.594 + return _Pii(end(), end());
1.595 + }
1.596 +
1.597 + size_type erase(const key_type& __key);
1.598 + void erase(const_iterator __it);
1.599 + void erase(const_iterator __first, const_iterator __last);
1.600 +
1.601 +private:
1.602 + void _M_rehash(size_type __num_buckets);
1.603 +#if defined (_STLP_DEBUG)
1.604 + void _M_check() const;
1.605 +#endif
1.606 +
1.607 +public:
1.608 + void rehash(size_type __num_buckets_hint);
1.609 + void resize(size_type __num_elements_hint);
1.610 + void clear();
1.611 +
1.612 + // this is for hash_map::operator[]
1.613 + reference _M_insert(const value_type& __obj);
1.614 +
1.615 +private:
1.616 + //__n is set to the first bucket that has to be modified if any
1.617 + //erase/insert operation is done after the returned iterator.
1.618 + iterator _M_before_begin(size_type &__n) const;
1.619 +
1.620 + static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
1.621 + size_type &__n);
1.622 +
1.623 + void _M_initialize_buckets(size_type __n) {
1.624 + const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
1.625 + _M_buckets.reserve(__n_buckets);
1.626 + _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
1.627 + }
1.628 +
1.629 + _STLP_TEMPLATE_FOR_CONT_EXT
1.630 + size_type _M_bkt_num_key(const _KT& __key) const
1.631 + { return _M_bkt_num_key(__key, bucket_count()); }
1.632 +
1.633 + size_type _M_bkt_num(const value_type& __obj) const
1.634 + { return _M_bkt_num_key(_M_get_key(__obj)); }
1.635 +
1.636 + _STLP_TEMPLATE_FOR_CONT_EXT
1.637 + size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
1.638 + { return _M_hash(__key) % __n; }
1.639 +
1.640 + size_type _M_bkt_num(const value_type& __obj, size_t __n) const
1.641 + { return _M_bkt_num_key(_M_get_key(__obj), __n); }
1.642 +
1.643 + void _M_copy_from(const _Self& __ht);
1.644 +};
1.645 +
1.646 +#if defined (_STLP_DEBUG)
1.647 +# undef hashtable
1.648 +_STLP_MOVE_TO_STD_NAMESPACE
1.649 +#endif
1.650 +
1.651 +_STLP_END_NAMESPACE
1.652 +
1.653 +#if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.654 +# include <stl/_hashtable.c>
1.655 +#endif
1.656 +
1.657 +#if defined (_STLP_DEBUG)
1.658 +# include <stl/debug/_hashtable.h>
1.659 +#endif
1.660 +
1.661 +_STLP_BEGIN_NAMESPACE
1.662 +
1.663 +#define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
1.664 +#define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
1.665 +#include <stl/_relops_hash_cont.h>
1.666 +#undef _STLP_TEMPLATE_CONTAINER
1.667 +#undef _STLP_TEMPLATE_HEADER
1.668 +
1.669 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.670 +template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
1.671 +struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
1.672 + //Hashtables are movable:
1.673 + typedef __stlp_movable implemented;
1.674 +
1.675 + //Completeness depends on many template parameters, for the moment we consider it not complete:
1.676 + typedef __false_type complete;
1.677 +};
1.678 +#endif
1.679 +
1.680 +_STLP_END_NAMESPACE
1.681 +
1.682 +#endif /* _STLP_INTERNAL_HASHTABLE_H */
1.683 +
1.684 +// Local Variables:
1.685 +// mode:C++
1.686 +// End: