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_HASHTABLE_H
31 #define _STLP_INTERNAL_HASHTABLE_H
33 #ifndef _STLP_INTERNAL_VECTOR_H
34 # include <stl/_vector.h>
37 #ifndef _STLP_INTERNAL_SLIST_H
38 # include <stl/_slist.h>
41 #ifndef _STLP_INTERNAL_ITERATOR_H
42 # include <stl/_iterator.h>
45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H
46 # include <stl/_function_base.h>
49 #ifndef _STLP_INTERNAL_ALGOBASE_H
50 # include <stl/_algobase.h>
53 #ifndef _STLP_HASH_FUN_H
54 # include <stl/_hash_fun.h>
58 * Hashtable class, used to implement the hashed associative containers
59 * hash_set, hash_map, hash_multiset, hash_multimap,
60 * unordered_set, unordered_map, unordered_multiset, unordered_multimap.
65 #if defined (_STLP_USE_TEMPLATE_EXPORT)
66 //Export of the classes used to represent buckets in the hashtable implementation.
67 # if !defined (_STLP_USE_PTR_SPECIALIZATIONS)
68 //If pointer specialization is enabled vector<_Slist_node_base*> will use the void*
69 //storage type for which internal classes have already been exported.
70 _STLP_EXPORT_TEMPLATE_CLASS allocator<_STLP_PRIV _Slist_node_base*>;
72 _STLP_MOVE_TO_PRIV_NAMESPACE
73 _STLP_EXPORT_TEMPLATE_CLASS _STLP_alloc_proxy<_Slist_node_base**, _Slist_node_base*,
74 allocator<_Slist_node_base*> >;
75 _STLP_EXPORT_TEMPLATE_CLASS _Vector_base<_Slist_node_base*,
76 allocator<_Slist_node_base*> >;
77 _STLP_MOVE_TO_STD_NAMESPACE
80 # if defined (_STLP_DEBUG)
81 _STLP_MOVE_TO_PRIV_NAMESPACE
82 # define _STLP_NON_DBG_VECTOR _STLP_NON_DBG_NAME(vector)
83 _STLP_EXPORT_TEMPLATE_CLASS __construct_checker<_STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> > >;
84 _STLP_EXPORT_TEMPLATE_CLASS _STLP_NON_DBG_VECTOR<_Slist_node_base*, allocator<_Slist_node_base*> >;
85 # undef _STLP_NON_DBG_VECTOR
86 _STLP_MOVE_TO_STD_NAMESPACE
89 _STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*,
90 allocator<_STLP_PRIV _Slist_node_base*> >;
93 #if defined (_STLP_DEBUG)
94 # define hashtable _STLP_NON_DBG_NAME(hashtable)
95 _STLP_MOVE_TO_PRIV_NAMESPACE
98 // some compilers require the names of template parameters to be the same
99 template <class _Val, class _Key, class _HF,
100 class _Traits, class _ExK, class _EqK, class _All>
103 #if !defined (_STLP_DEBUG)
104 _STLP_MOVE_TO_PRIV_NAMESPACE
107 template <class _BaseIte, class _Traits>
108 struct _Ht_iterator {
109 typedef typename _Traits::_ConstTraits _ConstTraits;
110 typedef typename _Traits::_NonConstTraits _NonConstTraits;
112 typedef _Ht_iterator<_BaseIte,_Traits> _Self;
114 typedef typename _Traits::value_type value_type;
115 typedef typename _Traits::pointer pointer;
116 typedef typename _Traits::reference reference;
117 typedef forward_iterator_tag iterator_category;
118 typedef ptrdiff_t difference_type;
119 typedef size_t size_type;
121 typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator;
122 typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator;
125 //copy constructor for iterator and constructor from iterator for const_iterator
126 _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {}
127 _Ht_iterator(_BaseIte __it) : _M_ite(__it) {}
129 reference operator*() const {
132 _STLP_DEFINE_ARROW_OPERATOR
134 _Self& operator++() {
138 _Self operator++(int) {
144 bool operator == (const_iterator __rhs) const {
145 return _M_ite == __rhs._M_ite;
147 bool operator != (const_iterator __rhs) const {
148 return _M_ite != __rhs._M_ite;
154 _STLP_MOVE_TO_STD_NAMESPACE
156 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
157 template <class _BaseIte, class _Traits>
158 struct __type_traits<_STLP_PRIV _Ht_iterator<_BaseIte, _Traits> > {
159 typedef __false_type has_trivial_default_constructor;
160 typedef __true_type has_trivial_copy_constructor;
161 typedef __true_type has_trivial_assignment_operator;
162 typedef __true_type has_trivial_destructor;
163 typedef __false_type is_POD_type;
165 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
167 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
168 template <class _BaseIte, class _Traits>
170 # if defined (_STLP_NESTED_TYPE_PARAM_BUG)
171 _STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type *
173 _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type *
175 value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) {
176 typedef typename _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val;
179 template <class _BaseIte, class _Traits>
180 inline forward_iterator_tag iterator_category(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
181 { return forward_iterator_tag(); }
182 template <class _BaseIte, class _Traits>
183 inline ptrdiff_t* distance_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&)
184 { return (ptrdiff_t*) 0; }
187 _STLP_MOVE_TO_PRIV_NAMESPACE
189 template <class _Dummy>
192 //Returns the maximum number of buckets handled by the hashtable implementation
193 static size_t _STLP_CALL _S_max_nb_buckets();
195 //Returns the bucket size next to a required size
196 static size_t _STLP_CALL _S_next_size(size_t);
199 #if defined (_STLP_USE_TEMPLATE_EXPORT)
200 _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>;
203 typedef _Stl_prime<bool> _Stl_prime_type;
205 #if !defined (_STLP_DEBUG)
206 _STLP_MOVE_TO_STD_NAMESPACE
210 * Hashtables handle allocators a bit differently than other containers
211 * do. If we're using standard-conforming allocators, then a hashtable
212 * unconditionally has a member variable to hold its allocator, even if
213 * it so happens that all instances of the allocator type are identical.
214 * This is because, for hashtables, this extra storage is negligible.
215 * Additionally, a base class wouldn't serve any other purposes; it
216 * wouldn't, for example, simplify the exception-handling code.
218 template <class _Val, class _Key, class _HF,
219 class _Traits, class _ExK, class _EqK, class _All>
221 typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self;
222 typedef typename _Traits::_NonConstTraits _NonConstTraits;
223 typedef typename _Traits::_ConstTraits _ConstTraits;
224 typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits;
225 typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits;
228 typedef _Key key_type;
229 typedef _Val value_type;
231 typedef _EqK key_equal;
233 typedef size_t size_type;
234 typedef ptrdiff_t difference_type;
235 typedef typename _NonConstTraits::pointer pointer;
236 typedef const value_type* const_pointer;
237 typedef typename _NonConstTraits::reference reference;
238 typedef const value_type& const_reference;
239 typedef forward_iterator_tag _Iterator_category;
241 hasher hash_funct() const { return _M_hash; }
242 key_equal key_eq() const { return _M_equals; }
245 _STLP_FORCE_ALLOCATORS(_Val, _All)
246 #if defined (_STLP_DEBUG)
247 typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont;
249 typedef slist<value_type, _All> _ElemsCont;
251 typedef typename _ElemsCont::iterator _ElemsIte;
252 typedef typename _ElemsCont::const_iterator _ElemsConstIte;
253 typedef _STLP_PRIV _Slist_node_base _BucketType;
254 typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _M_bucket_allocator_type;
256 * We are going to use vector of _Slist_node_base pointers for 2 reasons:
257 * - limit code bloat, all hashtable instanciation use the same buckets representation.
258 * - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize
259 * method would be too slow because the slist::splice_after method become linear on
260 * the number of iterators in the buckets rather than constant in time as the iterator
261 * has to be move from a slist to the other.
263 #if defined (_STLP_DEBUG)
264 typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _M_bucket_allocator_type> _BucketVector;
266 typedef vector<_BucketType*, _M_bucket_allocator_type> _BucketVector;
273 _BucketVector _M_buckets;
274 size_type _M_num_elements;
275 float _M_max_load_factor;
276 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type)
279 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator;
280 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator;
281 //TODO: Avoids this debug check and make the local_iterator different from
282 //iterator in debug mode too.
283 #if !defined (_STLP_DEBUG)
284 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator;
285 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator;
287 typedef iterator local_iterator;
288 typedef const_iterator const_local_iterator;
291 typedef typename _Alloc_traits<_Val, _All>::allocator_type allocator_type;
292 allocator_type get_allocator() const { return _M_elems.get_allocator(); }
294 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
295 hashtable(size_type __n,
299 const allocator_type& __a = allocator_type())
301 hashtable(size_type __n,
308 _M_elems(allocator_type()),
309 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
311 _M_max_load_factor(1.0f)
312 { _M_initialize_buckets(__n); }
314 hashtable(size_type __n,
318 const allocator_type& __a)
324 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
326 _M_max_load_factor(1.0f)
327 { _M_initialize_buckets(__n); }
329 #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
330 hashtable(size_type __n,
333 const allocator_type& __a = allocator_type())
335 hashtable(size_type __n,
341 _M_elems(allocator_type()),
342 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
344 _M_max_load_factor(1.0f)
345 { _M_initialize_buckets(__n); }
347 hashtable(size_type __n,
350 const allocator_type& __a)
356 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)),
358 _M_max_load_factor(1.0f)
359 { _M_initialize_buckets(__n); }
361 hashtable(const _Self& __ht)
362 : _M_hash(__ht._M_hash),
363 _M_equals(__ht._M_equals),
364 _M_get_key(__ht._M_get_key),
365 _M_elems(__ht.get_allocator()),
366 _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)),
368 _M_max_load_factor(1.0f)
369 { _M_copy_from(__ht); }
371 hashtable(__move_source<_Self> src)
372 : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)),
373 _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)),
374 _M_get_key(_STLP_PRIV _AsMoveSource(src.get()._M_get_key)),
375 _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)),
376 _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)),
377 _M_num_elements(src.get()._M_num_elements),
378 _M_max_load_factor(src.get()._M_max_load_factor) {}
380 _Self& operator= (const _Self& __ht) {
383 _M_hash = __ht._M_hash;
384 _M_equals = __ht._M_equals;
385 _M_get_key = __ht._M_get_key;
391 ~hashtable() { clear(); }
393 size_type size() const { return _M_num_elements; }
394 size_type max_size() const { return size_type(-1); }
395 bool empty() const { return size() == 0; }
397 void swap(_Self& __ht) {
398 _STLP_STD::swap(_M_hash, __ht._M_hash);
399 _STLP_STD::swap(_M_equals, __ht._M_equals);
400 _STLP_STD::swap(_M_get_key, __ht._M_get_key);
401 _M_elems.swap(__ht._M_elems);
402 _M_buckets.swap(__ht._M_buckets);
403 _STLP_STD::swap(_M_num_elements, __ht._M_num_elements);
404 _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor);
407 iterator begin() { return _M_elems.begin(); }
408 iterator end() { return _M_elems.end(); }
409 local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); }
410 local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); }
412 const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); }
413 const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); }
414 const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); }
415 const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); }
417 //static bool _STLP_CALL _M_equal (const _Self&, const _Self&);
420 //The number of buckets is size() - 1 because the last bucket always contains
421 //_M_elems.end() to make algo easier to implement.
422 size_type bucket_count() const { return _M_buckets.size() - 1; }
423 size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); }
424 size_type elems_in_bucket(size_type __bucket) const
425 { return distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); }
427 _STLP_TEMPLATE_FOR_CONT_EXT
428 size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); }
431 float load_factor() const { return (float)size() / (float)bucket_count(); }
432 float max_load_factor() const { return _M_max_load_factor; }
433 void max_load_factor(float __z) { _M_max_load_factor = __z;}
435 pair<iterator, bool> insert_unique(const value_type& __obj) {
436 resize(_M_num_elements + 1);
437 return insert_unique_noresize(__obj);
440 iterator insert_equal(const value_type& __obj) {
441 resize(_M_num_elements + 1);
442 return insert_equal_noresize(__obj);
446 iterator _M_insert_noresize(size_type __n, const value_type& __obj);
448 pair<iterator, bool> insert_unique_noresize(const value_type& __obj);
449 iterator insert_equal_noresize(const value_type& __obj);
451 #if defined (_STLP_MEMBER_TEMPLATES)
452 template <class _InputIterator>
453 void insert_unique(_InputIterator __f, _InputIterator __l)
454 { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
456 template <class _InputIterator>
457 void insert_equal(_InputIterator __f, _InputIterator __l)
458 { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); }
460 template <class _InputIterator>
461 void insert_unique(_InputIterator __f, _InputIterator __l,
462 const input_iterator_tag &) {
463 for ( ; __f != __l; ++__f)
467 template <class _InputIterator>
468 void insert_equal(_InputIterator __f, _InputIterator __l,
469 const input_iterator_tag &) {
470 for ( ; __f != __l; ++__f)
474 template <class _ForwardIterator>
475 void insert_unique(_ForwardIterator __f, _ForwardIterator __l,
476 const forward_iterator_tag &) {
477 size_type __n = distance(__f, __l);
478 resize(_M_num_elements + __n);
479 for ( ; __n > 0; --__n, ++__f)
480 insert_unique_noresize(*__f);
483 template <class _ForwardIterator>
484 void insert_equal(_ForwardIterator __f, _ForwardIterator __l,
485 const forward_iterator_tag &) {
486 size_type __n = distance(__f, __l);
487 resize(_M_num_elements + __n);
488 for ( ; __n > 0; --__n, ++__f)
489 insert_equal_noresize(*__f);
492 #else /* _STLP_MEMBER_TEMPLATES */
493 void insert_unique(const value_type* __f, const value_type* __l) {
494 size_type __n = __l - __f;
495 resize(_M_num_elements + __n);
496 for ( ; __n > 0; --__n, ++__f)
497 insert_unique_noresize(*__f);
500 void insert_equal(const value_type* __f, const value_type* __l) {
501 size_type __n = __l - __f;
502 resize(_M_num_elements + __n);
503 for ( ; __n > 0; --__n, ++__f)
504 insert_equal_noresize(*__f);
507 void insert_unique(const_iterator __f, const_iterator __l) {
508 size_type __n = distance(__f, __l);
509 resize(_M_num_elements + __n);
510 for ( ; __n > 0; --__n, ++__f)
511 insert_unique_noresize(*__f);
514 void insert_equal(const_iterator __f, const_iterator __l) {
515 size_type __n = distance(__f, __l);
516 resize(_M_num_elements + __n);
517 for ( ; __n > 0; --__n, ++__f)
518 insert_equal_noresize(*__f);
520 #endif /*_STLP_MEMBER_TEMPLATES */
522 //reference find_or_insert(const value_type& __obj);
525 _STLP_TEMPLATE_FOR_CONT_EXT
526 _ElemsIte _M_find(const _KT& __key) const {
527 size_type __n = _M_bkt_num_key(__key);
528 _ElemsIte __first(_M_buckets[__n]);
529 _ElemsIte __last(_M_buckets[__n + 1]);
530 for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first);
531 if (__first != __last)
534 return __CONST_CAST(_ElemsCont&, _M_elems).end();
538 _STLP_TEMPLATE_FOR_CONT_EXT
539 iterator find(const _KT& __key) { return _M_find(__key); }
540 _STLP_TEMPLATE_FOR_CONT_EXT
541 const_iterator find(const _KT& __key) const { return _M_find(__key); }
543 _STLP_TEMPLATE_FOR_CONT_EXT
544 size_type count(const _KT& __key) const {
545 const size_type __n = _M_bkt_num_key(__key);
547 _ElemsIte __cur(_M_buckets[__n]);
548 _ElemsIte __last(_M_buckets[__n + 1]);
549 for (; __cur != __last; ++__cur) {
550 if (_M_equals(_M_get_key(*__cur), __key)) {
551 size_type __result = 1;
553 __cur != __last && _M_equals(_M_get_key(*__cur), __key);
554 ++__result, ++__cur);
561 _STLP_TEMPLATE_FOR_CONT_EXT
562 pair<iterator, iterator> equal_range(const _KT& __key) {
563 typedef pair<iterator, iterator> _Pii;
564 const size_type __n = _M_bkt_num_key(__key);
566 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
567 __first != __last; ++__first) {
568 if (_M_equals(_M_get_key(*__first), __key)) {
569 _ElemsIte __cur(__first);
570 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
571 return _Pii(__first, __cur);
574 return _Pii(end(), end());
577 _STLP_TEMPLATE_FOR_CONT_EXT
578 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const {
579 typedef pair<const_iterator, const_iterator> _Pii;
580 const size_type __n = _M_bkt_num_key(__key);
582 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]);
583 __first != __last; ++__first) {
584 if (_M_equals(_M_get_key(*__first), __key)) {
585 _ElemsIte __cur(__first);
586 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur);
587 return _Pii(__first, __cur);
590 return _Pii(end(), end());
593 size_type erase(const key_type& __key);
594 void erase(const_iterator __it);
595 void erase(const_iterator __first, const_iterator __last);
598 void _M_rehash(size_type __num_buckets);
599 #if defined (_STLP_DEBUG)
600 void _M_check() const;
604 void rehash(size_type __num_buckets_hint);
605 void resize(size_type __num_elements_hint);
608 // this is for hash_map::operator[]
609 reference _M_insert(const value_type& __obj);
612 //__n is set to the first bucket that has to be modified if any
613 //erase/insert operation is done after the returned iterator.
614 iterator _M_before_begin(size_type &__n) const;
616 static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets,
619 void _M_initialize_buckets(size_type __n) {
620 const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1;
621 _M_buckets.reserve(__n_buckets);
622 _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0));
625 _STLP_TEMPLATE_FOR_CONT_EXT
626 size_type _M_bkt_num_key(const _KT& __key) const
627 { return _M_bkt_num_key(__key, bucket_count()); }
629 size_type _M_bkt_num(const value_type& __obj) const
630 { return _M_bkt_num_key(_M_get_key(__obj)); }
632 _STLP_TEMPLATE_FOR_CONT_EXT
633 size_type _M_bkt_num_key(const _KT& __key, size_type __n) const
634 { return _M_hash(__key) % __n; }
636 size_type _M_bkt_num(const value_type& __obj, size_t __n) const
637 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
639 void _M_copy_from(const _Self& __ht);
642 #if defined (_STLP_DEBUG)
644 _STLP_MOVE_TO_STD_NAMESPACE
649 #if !defined (_STLP_LINK_TIME_INSTANTIATION)
650 # include <stl/_hashtable.c>
653 #if defined (_STLP_DEBUG)
654 # include <stl/debug/_hashtable.h>
657 _STLP_BEGIN_NAMESPACE
659 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
660 #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All>
661 #include <stl/_relops_hash_cont.h>
662 #undef _STLP_TEMPLATE_CONTAINER
663 #undef _STLP_TEMPLATE_HEADER
665 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
666 template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All>
667 struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > {
668 //Hashtables are movable:
669 typedef __stlp_movable implemented;
671 //Completeness depends on many template parameters, for the moment we consider it not complete:
672 typedef __false_type complete;
678 #endif /* _STLP_INTERNAL_HASHTABLE_H */