1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 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. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_HASHTABLE_H 31 #define _STLP_INTERNAL_HASHTABLE_H 32 33 #ifndef _STLP_INTERNAL_VECTOR_H 34 # include <stl/_vector.h> 35 #endif 36 37 #ifndef _STLP_INTERNAL_SLIST_H 38 # include <stl/_slist.h> 39 #endif 40 41 #ifndef _STLP_INTERNAL_ITERATOR_H 42 # include <stl/_iterator.h> 43 #endif 44 45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 46 # include <stl/_function_base.h> 47 #endif 48 49 #ifndef _STLP_INTERNAL_ALGOBASE_H 50 # include <stl/_algobase.h> 51 #endif 52 53 #ifndef _STLP_HASH_FUN_H 54 # include <stl/_hash_fun.h> 55 #endif 56 57 /* 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. 61 */ 62 63 _STLP_BEGIN_NAMESPACE 64 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*>; 71 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 78 # endif 79 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 87 # endif 88 89 _STLP_EXPORT_TEMPLATE_CLASS vector<_STLP_PRIV _Slist_node_base*, 90 allocator<_STLP_PRIV _Slist_node_base*> >; 91 #endif 92 93 #if defined (_STLP_DEBUG) 94 # define hashtable _STLP_NON_DBG_NAME(hashtable) 95 _STLP_MOVE_TO_PRIV_NAMESPACE 96 #endif 97 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> 101 class hashtable; 102 103 #if !defined (_STLP_DEBUG) 104 _STLP_MOVE_TO_PRIV_NAMESPACE 105 #endif 106 107 template <class _BaseIte, class _Traits> 108 struct _Ht_iterator { 109 typedef typename _Traits::_ConstTraits _ConstTraits; 110 typedef typename _Traits::_NonConstTraits _NonConstTraits; 111 112 typedef _Ht_iterator<_BaseIte,_Traits> _Self; 113 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; 120 121 typedef _Ht_iterator<_BaseIte, _NonConstTraits> iterator; 122 typedef _Ht_iterator<_BaseIte, _ConstTraits> const_iterator; 123 _Ht_iterator_Ht_iterator124 _Ht_iterator() {} 125 //copy constructor for iterator and constructor from iterator for const_iterator _Ht_iterator_Ht_iterator126 _Ht_iterator(const iterator& __it) : _M_ite(__it._M_ite) {} _Ht_iterator_Ht_iterator127 _Ht_iterator(_BaseIte __it) : _M_ite(__it) {} 128 129 reference operator*() const { 130 return *_M_ite; 131 } 132 _STLP_DEFINE_ARROW_OPERATOR 133 134 _Self& operator++() { 135 ++_M_ite; 136 return *this; 137 } 138 _Self operator++(int) { 139 _Self __tmp = *this; 140 ++*this; 141 return __tmp; 142 } 143 144 bool operator == (const_iterator __rhs) const { 145 return _M_ite == __rhs._M_ite; 146 } 147 bool operator != (const_iterator __rhs) const { 148 return _M_ite != __rhs._M_ite; 149 } 150 151 _BaseIte _M_ite; 152 }; 153 154 _STLP_MOVE_TO_STD_NAMESPACE 155 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; 164 }; 165 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 166 167 #if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES) 168 template <class _BaseIte, class _Traits> 169 inline 170 # if defined (_STLP_NESTED_TYPE_PARAM_BUG) 171 _STLP_TYPENAME_ON_RETURN_TYPE _Traits::value_type * 172 # else 173 _STLP_TYPENAME_ON_RETURN_TYPE _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type * 174 # endif 175 value_type(const _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>&) { 176 typedef _STLP_TYPENAME _STLP_PRIV _Ht_iterator<_BaseIte,_Traits>::value_type _Val; 177 return (_Val*) 0; 178 } 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; } 185 #endif 186 187 _STLP_MOVE_TO_PRIV_NAMESPACE 188 189 template <class _Dummy> 190 class _Stl_prime { 191 // Returns begining of primes list and size by reference. 192 static const size_t* _S_primes(size_t&); 193 public: 194 //Returns the maximum number of buckets handled by the hashtable implementation 195 static size_t _STLP_CALL _S_max_nb_buckets(); 196 197 //Returns the bucket size next to a required size 198 static size_t _STLP_CALL _S_next_size(size_t); 199 200 // Returns the bucket range containing sorted list of prime numbers <= __hint. 201 static void _STLP_CALL _S_prev_sizes(size_t __hint, const size_t *&__begin, const size_t *&__end); 202 }; 203 204 #if defined (_STLP_USE_TEMPLATE_EXPORT) 205 _STLP_EXPORT_TEMPLATE_CLASS _Stl_prime<bool>; 206 #endif 207 208 typedef _Stl_prime<bool> _Stl_prime_type; 209 210 #if !defined (_STLP_DEBUG) 211 _STLP_MOVE_TO_STD_NAMESPACE 212 #endif 213 214 /* 215 * Hashtables handle allocators a bit differently than other containers 216 * do. If we're using standard-conforming allocators, then a hashtable 217 * unconditionally has a member variable to hold its allocator, even if 218 * it so happens that all instances of the allocator type are identical. 219 * This is because, for hashtables, this extra storage is negligible. 220 * Additionally, a base class wouldn't serve any other purposes; it 221 * wouldn't, for example, simplify the exception-handling code. 222 */ 223 template <class _Val, class _Key, class _HF, 224 class _Traits, class _ExK, class _EqK, class _All> 225 class hashtable { 226 typedef hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> _Self; 227 typedef typename _Traits::_NonConstTraits _NonConstTraits; 228 typedef typename _Traits::_ConstTraits _ConstTraits; 229 typedef typename _Traits::_NonConstLocalTraits _NonConstLocalTraits; 230 typedef typename _Traits::_ConstLocalTraits _ConstLocalTraits; 231 232 public: 233 typedef _Key key_type; 234 typedef _Val value_type; 235 typedef _HF hasher; 236 typedef _EqK key_equal; 237 238 typedef size_t size_type; 239 typedef ptrdiff_t difference_type; 240 typedef typename _NonConstTraits::pointer pointer; 241 typedef const value_type* const_pointer; 242 typedef typename _NonConstTraits::reference reference; 243 typedef const value_type& const_reference; 244 typedef forward_iterator_tag _Iterator_category; 245 246 hasher hash_funct() const { return _M_hash; } 247 key_equal key_eq() const { return _M_equals; } 248 249 private: 250 _STLP_FORCE_ALLOCATORS(_Val, _All) 251 #if defined (_STLP_DEBUG) 252 typedef _STLP_PRIV _STLP_NON_DBG_NAME(slist)<value_type, _All> _ElemsCont; 253 #else 254 typedef slist<value_type, _All> _ElemsCont; 255 #endif 256 typedef typename _ElemsCont::iterator _ElemsIte; 257 typedef typename _ElemsCont::const_iterator _ElemsConstIte; 258 typedef _STLP_PRIV _Slist_node_base _BucketType; 259 typedef typename _Alloc_traits<_BucketType*, _All>::allocator_type _BucketAllocType; 260 /* 261 * We are going to use vector of _Slist_node_base pointers for 2 reasons: 262 * - limit code bloat, all hashtable instanciation use the same buckets representation. 263 * - avoid _STLP_DEBUG performance trouble: with a vector of iterator on slist the resize 264 * method would be too slow because the slist::splice_after method become linear on 265 * the number of iterators in the buckets rather than constant in time as the iterator 266 * has to be move from a slist to the other. 267 */ 268 #if defined (_STLP_DEBUG) 269 typedef _STLP_PRIV _STLP_NON_DBG_NAME(vector)<_BucketType*, _BucketAllocType> _BucketVector; 270 #else 271 typedef vector<_BucketType*, _BucketAllocType> _BucketVector; 272 #endif 273 274 hasher _M_hash; 275 key_equal _M_equals; 276 _ElemsCont _M_elems; 277 _BucketVector _M_buckets; 278 size_type _M_num_elements; 279 float _M_max_load_factor; 280 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 281 282 static const key_type& _M_get_key(const value_type& __val) { 283 _ExK k; 284 return k(__val); 285 } 286 public: 287 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstTraits> iterator; 288 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstTraits> const_iterator; 289 //TODO: Avoids this debug check and make the local_iterator different from 290 //iterator in debug mode too. 291 #if !defined (_STLP_DEBUG) 292 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _NonConstLocalTraits> local_iterator; 293 typedef _STLP_PRIV _Ht_iterator<_ElemsIte, _ConstLocalTraits> const_local_iterator; 294 #else 295 typedef iterator local_iterator; 296 typedef const_iterator const_local_iterator; 297 #endif 298 299 typedef _All allocator_type; 300 allocator_type get_allocator() const { return _M_elems.get_allocator(); } 301 302 #if !defined (_STLP_DONT_SUP_DFLT_PARAM) 303 hashtable(size_type __n, 304 const _HF& __hf, 305 const _EqK& __eql, 306 const allocator_type& __a = allocator_type()) 307 #else 308 hashtable(size_type __n, 309 const _HF& __hf, 310 const _EqK& __eql) 311 : _M_hash(__hf), 312 _M_equals(__eql), 313 _M_elems(allocator_type()), 314 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 315 _M_num_elements(0), 316 _M_max_load_factor(1.0f) 317 { _M_initialize_buckets(__n); } 318 319 hashtable(size_type __n, 320 const _HF& __hf, 321 const _EqK& __eql, 322 const allocator_type& __a) 323 #endif 324 : _M_hash(__hf), 325 _M_equals(__eql), 326 _M_elems(__a), 327 _M_buckets(_STLP_CONVERT_ALLOCATOR(__a, _BucketType*)), 328 _M_num_elements(0), 329 _M_max_load_factor(1.0f) 330 { _M_initialize_buckets(__n); } 331 332 hashtable(const _Self& __ht) 333 : _M_hash(__ht._M_hash), 334 _M_equals(__ht._M_equals), 335 _M_elems(__ht.get_allocator()), 336 _M_buckets(_STLP_CONVERT_ALLOCATOR(__ht.get_allocator(), _BucketType*)), 337 _M_num_elements(0), 338 _M_max_load_factor(1.0f) 339 { _M_copy_from(__ht); } 340 341 #if !defined (_STLP_NO_MOVE_SEMANTIC) 342 hashtable(__move_source<_Self> src) 343 : _M_hash(_STLP_PRIV _AsMoveSource(src.get()._M_hash)), 344 _M_equals(_STLP_PRIV _AsMoveSource(src.get()._M_equals)), 345 _M_elems(__move_source<_ElemsCont>(src.get()._M_elems)), 346 _M_buckets(__move_source<_BucketVector>(src.get()._M_buckets)), 347 _M_num_elements(src.get()._M_num_elements), 348 _M_max_load_factor(src.get()._M_max_load_factor) {} 349 #endif 350 351 _Self& operator= (const _Self& __ht) { 352 if (&__ht != this) { 353 clear(); 354 _M_hash = __ht._M_hash; 355 _M_equals = __ht._M_equals; 356 _M_copy_from(__ht); 357 } 358 return *this; 359 } 360 361 ~hashtable() { clear(); } 362 363 size_type size() const { return _M_num_elements; } 364 size_type max_size() const { return size_type(-1); } 365 bool empty() const { return size() == 0; } 366 367 void swap(_Self& __ht) { 368 _STLP_STD::swap(_M_hash, __ht._M_hash); 369 _STLP_STD::swap(_M_equals, __ht._M_equals); 370 _M_elems.swap(__ht._M_elems); 371 _M_buckets.swap(__ht._M_buckets); 372 _STLP_STD::swap(_M_num_elements, __ht._M_num_elements); 373 _STLP_STD::swap(_M_max_load_factor, __ht._M_max_load_factor); 374 } 375 376 iterator begin() { return _M_elems.begin(); } 377 iterator end() { return _M_elems.end(); } 378 local_iterator begin(size_type __n) { return _ElemsIte(_M_buckets[__n]); } 379 local_iterator end(size_type __n) { return _ElemsIte(_M_buckets[__n + 1]); } 380 381 const_iterator begin() const { return __CONST_CAST(_ElemsCont&, _M_elems).begin(); } 382 const_iterator end() const { return __CONST_CAST(_ElemsCont&, _M_elems).end(); } 383 const_local_iterator begin(size_type __n) const { return _ElemsIte(_M_buckets[__n]); } 384 const_local_iterator end(size_type __n) const { return _ElemsIte(_M_buckets[__n + 1]); } 385 386 //static bool _STLP_CALL _M_equal (const _Self&, const _Self&); 387 388 public: 389 //The number of buckets is size() - 1 because the last bucket always contains 390 //_M_elems.end() to make algo easier to implement. 391 size_type bucket_count() const { return _M_buckets.size() - 1; } 392 size_type max_bucket_count() const { return _STLP_PRIV _Stl_prime_type::_S_max_nb_buckets(); } 393 size_type elems_in_bucket(size_type __bucket) const 394 { return _STLP_STD::distance(_ElemsIte(_M_buckets[__bucket]), _ElemsIte(_M_buckets[__bucket + 1])); } 395 396 _STLP_TEMPLATE_FOR_CONT_EXT 397 size_type bucket(const _KT& __k) const { return _M_bkt_num_key(__k); } 398 399 // hash policy 400 float load_factor() const { return (float)size() / (float)bucket_count(); } 401 float max_load_factor() const { return _M_max_load_factor; } 402 void max_load_factor(float __z) { 403 _M_max_load_factor = __z; 404 _M_resize(); 405 } 406 407 pair<iterator, bool> insert_unique(const value_type& __obj) { 408 _M_enlarge(_M_num_elements + 1); 409 return insert_unique_noresize(__obj); 410 } 411 412 iterator insert_equal(const value_type& __obj) { 413 _M_enlarge(_M_num_elements + 1); 414 return insert_equal_noresize(__obj); 415 } 416 417 protected: 418 iterator _M_insert_noresize(size_type __n, const value_type& __obj); 419 public: 420 pair<iterator, bool> insert_unique_noresize(const value_type& __obj); 421 iterator insert_equal_noresize(const value_type& __obj); 422 423 #if defined (_STLP_MEMBER_TEMPLATES) 424 template <class _InputIterator> 425 void insert_unique(_InputIterator __f, _InputIterator __l) 426 { insert_unique(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); } 427 428 template <class _InputIterator> 429 void insert_equal(_InputIterator __f, _InputIterator __l) 430 { insert_equal(__f, __l, _STLP_ITERATOR_CATEGORY(__f, _InputIterator)); } 431 432 template <class _InputIterator> 433 void insert_unique(_InputIterator __f, _InputIterator __l, 434 const input_iterator_tag &) { 435 for ( ; __f != __l; ++__f) 436 insert_unique(*__f); 437 } 438 439 template <class _InputIterator> 440 void insert_equal(_InputIterator __f, _InputIterator __l, 441 const input_iterator_tag &) { 442 for ( ; __f != __l; ++__f) 443 insert_equal(*__f); 444 } 445 446 template <class _ForwardIterator> 447 void insert_unique(_ForwardIterator __f, _ForwardIterator __l, 448 const forward_iterator_tag &) { 449 size_type __n = _STLP_STD::distance(__f, __l); 450 _M_enlarge(_M_num_elements + __n); 451 for ( ; __n > 0; --__n, ++__f) 452 insert_unique_noresize(*__f); 453 } 454 455 template <class _ForwardIterator> 456 void insert_equal(_ForwardIterator __f, _ForwardIterator __l, 457 const forward_iterator_tag &) { 458 size_type __n = _STLP_STD::distance(__f, __l); 459 _M_enlarge(_M_num_elements + __n); 460 for ( ; __n > 0; --__n, ++__f) 461 insert_equal_noresize(*__f); 462 } 463 464 #else /* _STLP_MEMBER_TEMPLATES */ 465 void insert_unique(const value_type* __f, const value_type* __l) { 466 size_type __n = __l - __f; 467 _M_enlarge(_M_num_elements + __n); 468 for ( ; __n > 0; --__n, ++__f) 469 insert_unique_noresize(*__f); 470 } 471 472 void insert_equal(const value_type* __f, const value_type* __l) { 473 size_type __n = __l - __f; 474 _M_enlarge(_M_num_elements + __n); 475 for ( ; __n > 0; --__n, ++__f) 476 insert_equal_noresize(*__f); 477 } 478 479 void insert_unique(const_iterator __f, const_iterator __l) { 480 size_type __n = _STLP_STD::distance(__f, __l); 481 _M_enlarge(_M_num_elements + __n); 482 for ( ; __n > 0; --__n, ++__f) 483 insert_unique_noresize(*__f); 484 } 485 486 void insert_equal(const_iterator __f, const_iterator __l) { 487 size_type __n = _STLP_STD::distance(__f, __l); 488 _M_enlarge(_M_num_elements + __n); 489 for ( ; __n > 0; --__n, ++__f) 490 insert_equal_noresize(*__f); 491 } 492 #endif /*_STLP_MEMBER_TEMPLATES */ 493 494 //reference find_or_insert(const value_type& __obj); 495 496 private: 497 _STLP_TEMPLATE_FOR_CONT_EXT 498 _ElemsIte _M_find(const _KT& __key) const { 499 size_type __n = _M_bkt_num_key(__key); 500 _ElemsIte __first(_M_buckets[__n]); 501 _ElemsIte __last(_M_buckets[__n + 1]); 502 for ( ; (__first != __last) && !_M_equals(_M_get_key(*__first), __key); ++__first); 503 if (__first != __last) 504 return __first; 505 else 506 return __CONST_CAST(_ElemsCont&, _M_elems).end(); 507 } 508 509 public: 510 _STLP_TEMPLATE_FOR_CONT_EXT 511 iterator find(const _KT& __key) { return _M_find(__key); } 512 _STLP_TEMPLATE_FOR_CONT_EXT 513 const_iterator find(const _KT& __key) const { return _M_find(__key); } 514 515 _STLP_TEMPLATE_FOR_CONT_EXT 516 size_type count(const _KT& __key) const { 517 const size_type __n = _M_bkt_num_key(__key); 518 519 _ElemsIte __cur(_M_buckets[__n]); 520 _ElemsIte __last(_M_buckets[__n + 1]); 521 for (; __cur != __last; ++__cur) { 522 if (_M_equals(_M_get_key(*__cur), __key)) { 523 size_type __result = 1; 524 for (++__cur; 525 __cur != __last && _M_equals(_M_get_key(*__cur), __key); 526 ++__result, ++__cur); 527 return __result; 528 } 529 } 530 return 0; 531 } 532 533 _STLP_TEMPLATE_FOR_CONT_EXT 534 pair<iterator, iterator> equal_range(const _KT& __key) { 535 typedef pair<iterator, iterator> _Pii; 536 const size_type __n = _M_bkt_num_key(__key); 537 538 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]); 539 __first != __last; ++__first) { 540 if (_M_equals(_M_get_key(*__first), __key)) { 541 _ElemsIte __cur(__first); 542 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur); 543 return _Pii(__first, __cur); 544 } 545 } 546 return _Pii(end(), end()); 547 } 548 549 _STLP_TEMPLATE_FOR_CONT_EXT 550 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const { 551 typedef pair<const_iterator, const_iterator> _Pii; 552 const size_type __n = _M_bkt_num_key(__key); 553 554 for (_ElemsIte __first(_M_buckets[__n]), __last(_M_buckets[__n + 1]); 555 __first != __last; ++__first) { 556 if (_M_equals(_M_get_key(*__first), __key)) { 557 _ElemsIte __cur(__first); 558 for (++__cur; (__cur != __last) && _M_equals(_M_get_key(*__cur), __key); ++__cur); 559 return _Pii(__first, __cur); 560 } 561 } 562 return _Pii(end(), end()); 563 } 564 565 size_type erase(const key_type& __key); 566 void erase(const_iterator __it); 567 void erase(const_iterator __first, const_iterator __last); 568 569 private: 570 void _M_enlarge(size_type __n); 571 void _M_reduce(); 572 void _M_resize(); 573 void _M_rehash(size_type __num_buckets); 574 #if defined (_STLP_DEBUG) 575 void _M_check() const; 576 #endif 577 578 public: 579 void rehash(size_type __num_buckets_hint); 580 void resize(size_type __num_buckets_hint) 581 { rehash(__num_buckets_hint); } 582 void clear(); 583 584 // this is for hash_map::operator[] 585 reference _M_insert(const value_type& __obj); 586 587 private: 588 //__n is set to the first bucket that has to be modified if any 589 //erase/insert operation is done after the returned iterator. 590 iterator _M_before_begin(size_type &__n) const; 591 592 static iterator _S_before_begin(const _ElemsCont& __elems, const _BucketVector& __buckets, 593 size_type &__n); 594 595 void _M_initialize_buckets(size_type __n) { 596 const size_type __n_buckets = _STLP_PRIV _Stl_prime_type::_S_next_size(__n) + 1; 597 _M_buckets.reserve(__n_buckets); 598 _M_buckets.assign(__n_buckets, __STATIC_CAST(_BucketType*, 0)); 599 } 600 601 _STLP_TEMPLATE_FOR_CONT_EXT 602 size_type _M_bkt_num_key(const _KT& __key) const 603 { return _M_bkt_num_key(__key, bucket_count()); } 604 605 size_type _M_bkt_num(const value_type& __obj) const 606 { return _M_bkt_num_key(_M_get_key(__obj)); } 607 608 _STLP_TEMPLATE_FOR_CONT_EXT 609 size_type _M_bkt_num_key(const _KT& __key, size_type __n) const 610 { return _M_hash(__key) % __n; } 611 612 size_type _M_bkt_num(const value_type& __obj, size_t __n) const 613 { return _M_bkt_num_key(_M_get_key(__obj), __n); } 614 615 void _M_copy_from(const _Self& __ht); 616 }; 617 618 #if defined (_STLP_DEBUG) 619 # undef hashtable 620 _STLP_MOVE_TO_STD_NAMESPACE 621 #endif 622 623 _STLP_END_NAMESPACE 624 625 #if !defined (_STLP_LINK_TIME_INSTANTIATION) 626 # include <stl/_hashtable.c> 627 #endif 628 629 #if defined (_STLP_DEBUG) 630 # include <stl/debug/_hashtable.h> 631 #endif 632 633 _STLP_BEGIN_NAMESPACE 634 635 #define _STLP_TEMPLATE_HEADER template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All> 636 #define _STLP_TEMPLATE_CONTAINER hashtable<_Val,_Key,_HF,_Traits,_ExK,_EqK,_All> 637 #include <stl/_relops_hash_cont.h> 638 #undef _STLP_TEMPLATE_CONTAINER 639 #undef _STLP_TEMPLATE_HEADER 640 641 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 642 template <class _Val, class _Key, class _HF, class _Traits, class _ExK, class _EqK, class _All> 643 struct __move_traits<hashtable<_Val, _Key, _HF, _Traits, _ExK, _EqK, _All> > { 644 //Hashtables are movable: 645 typedef __true_type implemented; 646 647 //Completeness depends on many template parameters, for the moment we consider it not complete: 648 typedef __false_type complete; 649 }; 650 #endif 651 652 _STLP_END_NAMESPACE 653 654 #endif /* _STLP_INTERNAL_HASHTABLE_H */ 655 656 // Local Variables: 657 // mode:C++ 658 // End: 659