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