4 * Hewlett-Packard Company
6 * Copyright (c) 1996,1997
7 * Silicon Graphics Computer Systems, Inc.
10 * Moscow Center for SPARC Technology
15 * This material is provided "as is", with absolutely no warranty expressed
16 * or implied. Any use is at your own risk.
18 * Permission to use or copy this software for any purpose is hereby granted
19 * without fee, provided the above notices are retained on all copies.
20 * Permission to modify the code and to distribute modified code is granted,
21 * provided the above notices are retained, and a notice that the code was
22 * modified is included with the above copyright notice.
26 /* NOTE: This is an internal header file, included by other STL headers.
27 * You should not attempt to use it directly.
30 #ifndef _STLP_INTERNAL_DBG_HASHTABLE_H
31 #define _STLP_INTERNAL_DBG_HASHTABLE_H
33 // Hashtable class, used to implement the hashed associative containers
34 // hash_set, hash_map, hash_multiset, and hash_multimap,
35 // unordered_set, unordered_map, unordered_multiset, unordered_multimap
37 #ifndef _STLP_DBG_ITERATOR_H
38 # include <stl/debug/_iterator.h>
43 _STLP_MOVE_TO_PRIV_NAMESPACE
45 template <class _Key
, class _Equal
>
49 _DbgEqual(const _Equal
& __eq
) : _M_non_dbg_eq(__eq
) {}
50 _DbgEqual(const _DbgEqual
& __eq
) : _M_non_dbg_eq(__eq
._M_non_dbg_eq
) {}
52 #if !defined (_STLP_USE_CONTAINERS_EXTENSION)
53 bool operator () (const _Key
& __lhs
, const _Key
& __rhs
) const
55 template <class _Kp1
, class _Kp2
>
56 bool operator () (const _Kp1
& __lhs
, const _Kp2
& __rhs
) const
59 #if !defined (_STLP_USE_CONTAINERS_EXTENSION)
60 _STLP_VERBOSE_ASSERT(_M_non_dbg_eq(__rhs
, __lhs
) == _M_non_dbg_eq(__lhs
, __rhs
), _StlMsg_INVALID_EQUIVALENT_PREDICATE
)
62 return _M_non_dbg_eq(__lhs
, __rhs
) ? true : false;
65 _Equal
non_dbg_key_eq() const { return _M_non_dbg_eq
; }
70 _STLP_MOVE_TO_STD_NAMESPACE
72 #define _STLP_NON_DBG_HT \
73 _STLP_PRIV _STLP_NON_DBG_NAME(hashtable) <_Val, _Key, _HF, _Traits, _ExK, _STLP_PRIV _DbgEqual<_Key, _EqK>, _All>
75 #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
76 template <class _Val
, class _Key
, class _HF
,
77 class _ExK
, class _EqK
, class _All
>
79 value_type(const _STLP_PRIV _DBG_iter_base
< _STLP_NON_DBG_HT
>&)
82 template <class _Val
, class _Key
, class _HF
,
83 class _ExK
, class _EqK
, class _All
>
84 inline forward_iterator_tag
85 iterator_category(const _STLP_PRIV _DBG_iter_base
< _STLP_NON_DBG_HT
>&)
86 { return forward_iterator_tag(); }
89 template <class _Val
, class _Key
, class _HF
,
90 class _Traits
, class _ExK
, class _EqK
, class _All
>
92 typedef hashtable
<_Val
, _Key
, _HF
, _Traits
, _ExK
, _EqK
, _All
> _Self
;
93 typedef _STLP_NON_DBG_HT _Base
;
95 typedef typename
_Traits::_NonConstTraits _NonConstTraits
;
96 typedef typename
_Traits::_ConstTraits _ConstTraits
;
97 typedef typename
_Traits::_NonConstLocalTraits _NonConstLocalTraits
;
98 typedef typename
_Traits::_ConstLocalTraits _ConstLocalTraits
;
100 _Base _M_non_dbg_impl
;
101 _STLP_PRIV __owned_list _M_iter_list
;
104 typedef _Key key_type
;
106 typedef _EqK key_equal
;
108 __IMPORT_CONTAINER_TYPEDEFS(_Base
)
110 typedef _STLP_PRIV _DBG_iter
<_Base
, _STLP_PRIV _DbgTraits
<_NonConstTraits
> > iterator
;
111 typedef _STLP_PRIV _DBG_iter
<_Base
, _STLP_PRIV _DbgTraits
<_ConstTraits
> > const_iterator
;
112 //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_NonConstLocalTraits> > local_iterator;
113 typedef iterator local_iterator
;
114 //typedef _STLP_PRIV _DBG_iter<_Base, _DbgTraits<_ConstLocalTraits> > const_local_iterator;
115 typedef const_iterator const_local_iterator
;
117 typedef typename
_Base::iterator _Base_iterator
;
118 typedef typename
_Base::const_iterator _Base_const_iterator
;
120 hasher
hash_funct() const { return _M_non_dbg_impl
.hash_funct(); }
121 key_equal
key_eq() const { return _M_non_dbg_impl
.key_eq().non_dbg_key_eq(); }
124 void _Invalidate_iterator(const const_iterator
& __it
)
125 { _STLP_PRIV
__invalidate_iterator(&_M_iter_list
, __it
); }
126 void _Invalidate_iterators(const const_iterator
& __first
, const const_iterator
& __last
)
127 { _STLP_PRIV
__invalidate_range(&_M_iter_list
, __first
, __last
); }
129 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type
)
132 allocator_type
get_allocator() const { return _M_non_dbg_impl
.get_allocator(); }
134 hashtable(size_type __n
,
138 const allocator_type
& __a
= allocator_type())
139 : _M_non_dbg_impl(__n
, __hf
, __eql
, __ext
, __a
),
140 _M_iter_list(&_M_non_dbg_impl
) {}
142 hashtable(size_type __n
,
145 const allocator_type
& __a
= allocator_type())
146 : _M_non_dbg_impl(__n
, __hf
, __eql
, __a
),
147 _M_iter_list(&_M_non_dbg_impl
) {}
149 hashtable(const _Self
& __ht
)
150 : _M_non_dbg_impl(__ht
._M_non_dbg_impl
),
151 _M_iter_list(&_M_non_dbg_impl
) {}
153 #if !defined (_STLP_NO_MOVE_SEMANTIC)
154 hashtable(__move_source
<_Self
> src
)
155 : _M_non_dbg_impl(__move_source
<_Base
>(src
.get()._M_non_dbg_impl
)),
156 _M_iter_list(&_M_non_dbg_impl
) {
157 # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
158 src
.get()._M_iter_list
._Invalidate_all();
160 src
.get()._M_iter_list
._Set_owner(_M_iter_list
);
165 size_type
size() const { return _M_non_dbg_impl
.size(); }
166 size_type
max_size() const { return _M_non_dbg_impl
.max_size(); }
167 bool empty() const { return _M_non_dbg_impl
.empty(); }
169 _Self
& operator=(const _Self
& __ht
) {
171 //Should not invalidate end iterator
172 _Invalidate_iterators(begin(), end());
173 _M_non_dbg_impl
= __ht
._M_non_dbg_impl
;
178 void swap(_Self
& __ht
) {
179 _M_iter_list
._Swap_owners(__ht
._M_iter_list
);
180 _M_non_dbg_impl
.swap(__ht
._M_non_dbg_impl
);
183 iterator
begin() { return iterator(&_M_iter_list
, _M_non_dbg_impl
.begin()); }
184 iterator
end() { return iterator(&_M_iter_list
, _M_non_dbg_impl
.end()); }
185 local_iterator
begin(size_type __n
) {
186 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
187 _STLP_VERBOSE_ASSERT((__n
< bucket_count()), _StlMsg_INVALID_ARGUMENT
)
188 return local_iterator(&_M_iter_list
, _M_non_dbg_impl
.begin(__n
));
190 local_iterator
end(size_type __n
) {
191 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
192 _STLP_VERBOSE_ASSERT((__n
< bucket_count()), _StlMsg_INVALID_ARGUMENT
)
193 return local_iterator(&_M_iter_list
, _M_non_dbg_impl
.end(__n
));
196 const_iterator
begin() const { return const_iterator(&_M_iter_list
, _M_non_dbg_impl
.begin()); }
197 const_iterator
end() const { return const_iterator(&_M_iter_list
, _M_non_dbg_impl
.end()); }
198 const_local_iterator
begin(size_type __n
) const {
199 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
200 _STLP_VERBOSE_ASSERT((__n
< bucket_count()), _StlMsg_INVALID_ARGUMENT
)
201 return const_local_iterator(&_M_iter_list
, _M_non_dbg_impl
.begin(__n
));
203 const_local_iterator
end(size_type __n
) const {
204 //TODO: Add checks for iterator locality -> avoids comparison between different bucket iterators
205 _STLP_VERBOSE_ASSERT((__n
< bucket_count()), _StlMsg_INVALID_ARGUMENT
)
206 return const_local_iterator(&_M_iter_list
, _M_non_dbg_impl
.end(__n
));
209 pair
<iterator
, bool> insert_unique(const value_type
& __obj
) {
210 pair
<_Base_iterator
, bool> __res
= _M_non_dbg_impl
.insert_unique(__obj
);
211 return pair
<iterator
, bool>(iterator(&_M_iter_list
, __res
.first
), __res
.second
);
214 iterator
insert_equal(const value_type
& __obj
)
215 { return iterator(&_M_iter_list
, _M_non_dbg_impl
.insert_equal(__obj
)); }
217 pair
<iterator
, bool> insert_unique_noresize(const value_type
& __obj
) {
218 pair
<_Base_iterator
, bool> __res
= _M_non_dbg_impl
.insert_unique_noresize(__obj
);
219 return pair
<iterator
, bool>(iterator(&_M_iter_list
, __res
.first
), __res
.second
);
222 iterator
insert_equal_noresize(const value_type
& __obj
)
223 { return iterator(&_M_iter_list
, _M_non_dbg_impl
.insert_equal_noresize(__obj
)); }
225 #if defined (_STLP_MEMBER_TEMPLATES)
226 template <class _InputIterator
>
227 void insert_unique(_InputIterator __f
, _InputIterator __l
) {
228 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__f
, __l
))
229 _M_non_dbg_impl
.insert_unique(_STLP_PRIV
_Non_Dbg_iter(__f
), _STLP_PRIV
_Non_Dbg_iter(__l
));
232 template <class _InputIterator
>
233 void insert_equal(_InputIterator __f
, _InputIterator __l
){
234 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__f
, __l
))
235 _M_non_dbg_impl
.insert_equal(_STLP_PRIV
_Non_Dbg_iter(__f
), _STLP_PRIV
_Non_Dbg_iter(__l
));
239 void insert_unique(const value_type
* __f
, const value_type
* __l
) {
240 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_ptr_range(__f
, __l
))
241 _M_non_dbg_impl
.insert_unique(__f
, __l
);
244 void insert_equal(const value_type
* __f
, const value_type
* __l
) {
245 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_ptr_range(__f
, __l
))
246 _M_non_dbg_impl
.insert_equal(__f
, __l
);
249 void insert_unique(const_iterator __f
, const_iterator __l
) {
250 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__f
, __l
))
251 _M_non_dbg_impl
.insert_unique(__f
._M_iterator
, __l
._M_iterator
);
254 void insert_equal(const_iterator __f
, const_iterator __l
) {
255 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__f
, __l
))
256 _M_non_dbg_impl
.insert_equal(__f
._M_iterator
, __l
._M_iterator
);
260 _STLP_TEMPLATE_FOR_CONT_EXT
261 iterator
find(const _KT
& __key
)
262 { return iterator(&_M_iter_list
, _M_non_dbg_impl
.find(__key
)); }
263 _STLP_TEMPLATE_FOR_CONT_EXT
264 const_iterator
find(const _KT
& __key
) const
265 { return const_iterator(&_M_iter_list
, _M_non_dbg_impl
.find(__key
)); }
267 _STLP_TEMPLATE_FOR_CONT_EXT
268 size_type
count(const _KT
& __key
) const { return _M_non_dbg_impl
.count(__key
); }
270 _STLP_TEMPLATE_FOR_CONT_EXT
271 pair
<iterator
, iterator
> equal_range(const _KT
& __key
) {
272 pair
<_Base_iterator
, _Base_iterator
> __res
= _M_non_dbg_impl
.equal_range(__key
);
273 return pair
<iterator
,iterator
> (iterator(&_M_iter_list
,__res
.first
),
274 iterator(&_M_iter_list
,__res
.second
));
277 _STLP_TEMPLATE_FOR_CONT_EXT
278 pair
<const_iterator
, const_iterator
> equal_range(const _KT
& __key
) const {
279 pair
<_Base_const_iterator
, _Base_const_iterator
> __res
= _M_non_dbg_impl
.equal_range(__key
);
280 return pair
<const_iterator
,const_iterator
> (const_iterator(&_M_iter_list
,__res
.first
),
281 const_iterator(&_M_iter_list
,__res
.second
));
284 size_type
erase(const key_type
& __key
) {
285 pair
<iterator
, iterator
> __p
= equal_range(__key
);
286 size_type __n
= _STLP_STD::distance(__p
.first
, __p
.second
);
287 _Invalidate_iterators(__p
.first
, __p
.second
);
288 _M_non_dbg_impl
.erase(__p
.first
._M_iterator
, __p
.second
._M_iterator
);
292 void erase(const const_iterator
& __it
) {
293 _STLP_DEBUG_CHECK(_STLP_PRIV
_Dereferenceable(__it
))
294 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_if_owner(&_M_iter_list
, __it
))
295 _Invalidate_iterator(__it
);
296 _M_non_dbg_impl
.erase(__it
._M_iterator
);
298 void erase(const_iterator __first
, const_iterator __last
) {
299 _STLP_DEBUG_CHECK(_STLP_PRIV
__check_range(__first
, __last
,
300 const_iterator(begin()), const_iterator(end())))
301 _Invalidate_iterators(__first
, __last
);
302 _M_non_dbg_impl
.erase(__first
._M_iterator
, __last
._M_iterator
);
305 void rehash(size_type __num_buckets_hint
) { _M_non_dbg_impl
.rehash(__num_buckets_hint
); }
306 void resize(size_type __num_elements_hint
) { _M_non_dbg_impl
.resize(__num_elements_hint
); }
309 _Invalidate_iterators(begin(), end());
310 _M_non_dbg_impl
.clear();
313 reference
_M_insert(const value_type
& __obj
) { return _M_non_dbg_impl
._M_insert(__obj
); }
315 size_type
bucket_count() const { return _M_non_dbg_impl
.bucket_count(); }
316 size_type
max_bucket_count() const { return _M_non_dbg_impl
.max_bucket_count(); }
317 size_type
elems_in_bucket(size_type __n
) const {
318 _STLP_VERBOSE_ASSERT((__n
< bucket_count()), _StlMsg_INVALID_ARGUMENT
)
319 return _M_non_dbg_impl
.elems_in_bucket(__n
);
321 _STLP_TEMPLATE_FOR_CONT_EXT
322 size_type
bucket(const _KT
& __k
) const { return _M_non_dbg_impl
.bucket(__k
); }
324 float load_factor() const { return _M_non_dbg_impl
.load_factor(); }
325 float max_load_factor() const { return _M_non_dbg_impl
.max_load_factor(); }
326 void max_load_factor(float __z
) {
327 _STLP_VERBOSE_ASSERT((__z
> 0.0f
), _StlMsg_INVALID_ARGUMENT
)
328 _M_non_dbg_impl
.max_load_factor(__z
);
334 #undef _STLP_NON_DBG_HT
336 #endif /* _STLP_INTERNAL_HASHTABLE_H */