1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/debug/_hashtable.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,341 @@
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_DBG_HASHTABLE_H
1.34 +#define _STLP_INTERNAL_DBG_HASHTABLE_H
1.35 +
1.36 +// Hashtable class, used to implement the hashed associative containers
1.37 +// hash_set, hash_map, hash_multiset, and hash_multimap,
1.38 +// unordered_set, unordered_map, unordered_multiset, unordered_multimap
1.39 +
1.40 +#ifndef _STLP_DBG_ITERATOR_H
1.41 +# include <stl/debug/_iterator.h>
1.42 +#endif
1.43 +
1.44 +_STLP_BEGIN_NAMESPACE
1.45 +
1.46 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.47 +
1.48 +template <class _Key, class _Equal>
1.49 +class _DbgEqual {
1.50 +public:
1.51 + _DbgEqual() {}
1.52 + _DbgEqual(const _Equal& __eq) : _M_non_dbg_eq(__eq) {}
1.53 + _DbgEqual(const _DbgEqual& __eq) : _M_non_dbg_eq(__eq._M_non_dbg_eq) {}
1.54 +
1.55 +#if !defined (_STLP_USE_CONTAINERS_EXTENSION)
1.56 + bool operator () (const _Key& __lhs, const _Key& __rhs) const {
1.57 +#else
1.58 + template <class _Kp1, class _Kp2>
1.59 + bool operator () (const _Kp1& __lhs, const _Kp2& __rhs) const {
1.60 +#endif
1.61 + if (_M_non_dbg_eq(__lhs, __rhs)) {
1.62 + _STLP_VERBOSE_ASSERT(_M_non_dbg_eq(__rhs, __lhs), _StlMsg_INVALID_EQUIVALENT_PREDICATE)
1.63 + return true;
1.64 + }
1.65 + else {
1.66 + _STLP_VERBOSE_ASSERT(!_M_non_dbg_eq(__rhs, __lhs), _StlMsg_INVALID_EQUIVALENT_PREDICATE)
1.67 + return false;
1.68 + }
1.69 + }
1.70 +
1.71 + _Equal non_dbg_key_eq() const { return _M_non_dbg_eq; }
1.72 +private:
1.73 + _Equal _M_non_dbg_eq;
1.74 +};
1.75 +
1.76 +_STLP_MOVE_TO_STD_NAMESPACE
1.77 +
1.78 +#define _STLP_NON_DBG_HT \
1.79 +_STLP_PRIV _STLP_NON_DBG_NAME(hashtable) <_Val, _Key, _HF, _Traits, _ExK, _STLP_PRIV _DbgEqual<_Key, _EqK>, _All>
1.80 +
1.81 +#if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
1.82 +template <class _Val, class _Key, class _HF,
1.83 + class _ExK, class _EqK, class _All>
1.84 +inline _Val*
1.85 +value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_HT >&)
1.86 +{ return (_Val*)0; }
1.87 +
1.88 +template <class _Val, class _Key, class _HF,
1.89 + class _ExK, class _EqK, class _All>
1.90 +inline forward_iterator_tag
1.91 +iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_HT >&)
1.92 +{ return forward_iterator_tag(); }
1.93 +#endif
1.94 +
1.95 +template <class _Val, class _Key, class _HF,
1.96 + class _Traits, class _ExK, class _EqK, class _All>
1.97 +class hashtable {
1.98 + typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
1.99 + typedef _STLP_NON_DBG_HT _Base;
1.100 +
1.101 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.102 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.103 + typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
1.104 + typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
1.105 +
1.106 + _Base _M_non_dbg_impl;
1.107 + _STLP_PRIV __owned_list _M_iter_list;
1.108 +
1.109 +public:
1.110 + typedef _Key key_type;
1.111 + typedef _HF hasher;
1.112 + typedef _EqK key_equal;
1.113 +
1.114 + __IMPORT_CONTAINER_TYPEDEFS(_Base)
1.115 +
1.116 + typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_NonConstTraits> > iterator;
1.117 + typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_ConstTraits> > const_iterator;
1.118 + //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_NonConstLocalTraits> > local_iterator;
1.119 + typedef iterator local_iterator;
1.120 + //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_ConstLocalTraits> > const_local_iterator;
1.121 + typedef const_iterator const_local_iterator;
1.122 +
1.123 + typedef typename _Base::iterator _Base_iterator;
1.124 + typedef typename _Base::const_iterator _Base_const_iterator;
1.125 +
1.126 + hasher hash_funct() const { return _M_non_dbg_impl.hash_funct(); }
1.127 + key_equal key_eq() const { return _M_non_dbg_impl.key_eq().non_dbg_key_eq(); }
1.128 +
1.129 +private:
1.130 + void _Invalidate_iterator(const const_iterator& __it)
1.131 + { _STLP_PRIV __invalidate_iterator(&_M_iter_list, __it); }
1.132 + void _Invalidate_iterators(const const_iterator& __first, const const_iterator& __last)
1.133 + { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
1.134 +
1.135 + _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
1.136 +
1.137 +public:
1.138 + allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); }
1.139 +
1.140 + hashtable(size_type __n,
1.141 + const _HF& __hf,
1.142 + const _EqK& __eql,
1.143 + const _ExK& __ext,
1.144 + const allocator_type& __a = allocator_type())
1.145 + : _M_non_dbg_impl(__n, __hf, __eql, __ext, __a),
1.146 + _M_iter_list(&_M_non_dbg_impl) {}
1.147 +
1.148 + hashtable(size_type __n,
1.149 + const _HF& __hf,
1.150 + const _EqK& __eql,
1.151 + const allocator_type& __a = allocator_type())
1.152 + : _M_non_dbg_impl(__n, __hf, __eql, __a),
1.153 + _M_iter_list(&_M_non_dbg_impl) {}
1.154 +
1.155 + hashtable(const _Self& __ht)
1.156 + : _M_non_dbg_impl(__ht._M_non_dbg_impl),
1.157 + _M_iter_list(&_M_non_dbg_impl) {}
1.158 +
1.159 + hashtable(__move_source<_Self> src)
1.160 + : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
1.161 + _M_iter_list(&_M_non_dbg_impl) {
1.162 +#if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
1.163 + src.get()._M_iter_list._Invalidate_all();
1.164 +#else
1.165 + src.get()._M_iter_list._Set_owner(_M_iter_list);
1.166 +#endif
1.167 + }
1.168 +
1.169 + size_type size() const { return _M_non_dbg_impl.size(); }
1.170 + size_type max_size() const { return _M_non_dbg_impl.max_size(); }
1.171 + bool empty() const { return _M_non_dbg_impl.empty(); }
1.172 +
1.173 + _Self& operator=(const _Self& __ht) {
1.174 + if (this != &__ht) {
1.175 + //Should not invalidate end iterator
1.176 + _Invalidate_iterators(begin(), end());
1.177 + _M_non_dbg_impl = __ht._M_non_dbg_impl;
1.178 + }
1.179 + return *this;
1.180 + }
1.181 +
1.182 + void swap(_Self& __ht) {
1.183 + _M_iter_list._Swap_owners(__ht._M_iter_list);
1.184 + _M_non_dbg_impl.swap(__ht._M_non_dbg_impl);
1.185 + }
1.186 +
1.187 + iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
1.188 + iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
1.189 + local_iterator begin(size_type __n) {
1.190 + //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
1.191 + _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
1.192 + return local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n));
1.193 + }
1.194 + local_iterator end(size_type __n) {
1.195 + //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
1.196 + _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
1.197 + return local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n));
1.198 + }
1.199 +
1.200 + const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
1.201 + const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
1.202 + const_local_iterator begin(size_type __n) const {
1.203 + //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
1.204 + _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
1.205 + return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.begin(__n));
1.206 + }
1.207 + const_local_iterator end(size_type __n) const {
1.208 + //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
1.209 + _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
1.210 + return const_local_iterator(&_M_iter_list, _M_non_dbg_impl.end(__n));
1.211 + }
1.212 +
1.213 + pair<iterator, bool> insert_unique(const value_type& __obj) {
1.214 + pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique(__obj);
1.215 + return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
1.216 + }
1.217 +
1.218 + iterator insert_equal(const value_type& __obj)
1.219 + { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal(__obj)); }
1.220 +
1.221 + pair<iterator, bool> insert_unique_noresize(const value_type& __obj) {
1.222 + pair<_Base_iterator, bool> __res = _M_non_dbg_impl.insert_unique_noresize(__obj);
1.223 + return pair<iterator, bool>(iterator(&_M_iter_list, __res.first), __res.second);
1.224 + }
1.225 +
1.226 + iterator insert_equal_noresize(const value_type& __obj)
1.227 + { return iterator(&_M_iter_list, _M_non_dbg_impl.insert_equal_noresize(__obj)); }
1.228 +
1.229 +#if defined (_STLP_MEMBER_TEMPLATES)
1.230 + template <class _InputIterator>
1.231 + void insert_unique(_InputIterator __f, _InputIterator __l) {
1.232 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
1.233 + _M_non_dbg_impl.insert_unique(_STLP_PRIV _Non_Dbg_iter(__f), _STLP_PRIV _Non_Dbg_iter(__l));
1.234 + }
1.235 +
1.236 + template <class _InputIterator>
1.237 + void insert_equal(_InputIterator __f, _InputIterator __l){
1.238 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
1.239 + _M_non_dbg_impl.insert_equal(_STLP_PRIV _Non_Dbg_iter(__f), _STLP_PRIV _Non_Dbg_iter(__l));
1.240 + }
1.241 +
1.242 +#else
1.243 + void insert_unique(const value_type* __f, const value_type* __l) {
1.244 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
1.245 + _M_non_dbg_impl.insert_unique(__f, __l);
1.246 + }
1.247 +
1.248 + void insert_equal(const value_type* __f, const value_type* __l) {
1.249 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__f, __l))
1.250 + _M_non_dbg_impl.insert_equal(__f, __l);
1.251 + }
1.252 +
1.253 + void insert_unique(const_iterator __f, const_iterator __l) {
1.254 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
1.255 + _M_non_dbg_impl.insert_unique(__f._M_iterator, __l._M_iterator);
1.256 + }
1.257 +
1.258 + void insert_equal(const_iterator __f, const_iterator __l) {
1.259 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__f, __l))
1.260 + _M_non_dbg_impl.insert_equal(__f._M_iterator, __l._M_iterator);
1.261 + }
1.262 +#endif
1.263 +
1.264 + _STLP_TEMPLATE_FOR_CONT_EXT
1.265 + iterator find(const _KT& __key)
1.266 + { return iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }
1.267 + _STLP_TEMPLATE_FOR_CONT_EXT
1.268 + const_iterator find(const _KT& __key) const
1.269 + { return const_iterator(&_M_iter_list, _M_non_dbg_impl.find(__key)); }
1.270 +
1.271 + _STLP_TEMPLATE_FOR_CONT_EXT
1.272 + size_type count(const _KT& __key) const { return _M_non_dbg_impl.count(__key); }
1.273 +
1.274 + _STLP_TEMPLATE_FOR_CONT_EXT
1.275 + pair<iterator, iterator> equal_range(const _KT& __key) {
1.276 + pair<_Base_iterator, _Base_iterator> __res = _M_non_dbg_impl.equal_range(__key);
1.277 + return pair<iterator,iterator> (iterator(&_M_iter_list,__res.first),
1.278 + iterator(&_M_iter_list,__res.second));
1.279 + }
1.280 +
1.281 + _STLP_TEMPLATE_FOR_CONT_EXT
1.282 + pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
1.283 + pair <_Base_const_iterator, _Base_const_iterator> __res = _M_non_dbg_impl.equal_range(__key);
1.284 + return pair<const_iterator,const_iterator> (const_iterator(&_M_iter_list,__res.first),
1.285 + const_iterator(&_M_iter_list,__res.second));
1.286 + }
1.287 +
1.288 + size_type erase(const key_type& __key) {
1.289 + pair<_Base_iterator, _Base_iterator> __p = _M_non_dbg_impl.equal_range(__key);
1.290 + size_type __n = _STLP_STD::distance(__p.first, __p.second);
1.291 + _Invalidate_iterators(const_iterator(&_M_iter_list, __p.first), const_iterator(&_M_iter_list, __p.second));
1.292 + _M_non_dbg_impl.erase(__p.first, __p.second);
1.293 + return __n;
1.294 + }
1.295 +
1.296 + void erase(const const_iterator& __it) {
1.297 + _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__it))
1.298 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __it))
1.299 + _Invalidate_iterator(__it);
1.300 + _M_non_dbg_impl.erase(__it._M_iterator);
1.301 + }
1.302 + void erase(const_iterator __first, const_iterator __last) {
1.303 + _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last,
1.304 + const_iterator(begin()), const_iterator(end())))
1.305 + _Invalidate_iterators(__first, __last);
1.306 + _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator);
1.307 + }
1.308 +
1.309 + void rehash(size_type __num_buckets_hint) { _M_non_dbg_impl.rehash(__num_buckets_hint); }
1.310 + void resize(size_type __num_elements_hint) { _M_non_dbg_impl.resize(__num_elements_hint); }
1.311 +
1.312 + void clear() {
1.313 + _Invalidate_iterators(begin(), end());
1.314 + _M_non_dbg_impl.clear();
1.315 + }
1.316 +
1.317 + reference _M_insert(const value_type& __obj) { return _M_non_dbg_impl._M_insert(__obj); }
1.318 +
1.319 + size_type bucket_count() const { return _M_non_dbg_impl.bucket_count(); }
1.320 + size_type max_bucket_count() const { return _M_non_dbg_impl.max_bucket_count(); }
1.321 + size_type elems_in_bucket(size_type __n) const {
1.322 + _STLP_VERBOSE_ASSERT((__n < bucket_count()), _StlMsg_INVALID_ARGUMENT)
1.323 + return _M_non_dbg_impl.elems_in_bucket(__n);
1.324 + }
1.325 + _STLP_TEMPLATE_FOR_CONT_EXT
1.326 + size_type bucket(const _KT& __k) const { return _M_non_dbg_impl.bucket(__k); }
1.327 +
1.328 + float load_factor() const { return _M_non_dbg_impl.load_factor(); }
1.329 + float max_load_factor() const { return _M_non_dbg_impl.max_load_factor(); }
1.330 + void max_load_factor(float __z) {
1.331 + _STLP_VERBOSE_ASSERT((__z > 0.0f), _StlMsg_INVALID_ARGUMENT)
1.332 + _M_non_dbg_impl.max_load_factor(__z);
1.333 + }
1.334 +};
1.335 +
1.336 +_STLP_END_NAMESPACE
1.337 +
1.338 +#undef _STLP_NON_DBG_HT
1.339 +
1.340 +#endif /* _STLP_INTERNAL_HASHTABLE_H */
1.341 +
1.342 +// Local Variables:
1.343 +// mode:C++
1.344 +// End: