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_HASH_MAP_H 31#define _STLP_INTERNAL_HASH_MAP_H 32 33#ifndef _STLP_INTERNAL_HASHTABLE_H 34# include <stl/_hashtable.h> 35#endif 36 37_STLP_BEGIN_NAMESPACE 38 39//Specific iterator traits creation 40_STLP_CREATE_HASH_ITERATOR_TRAITS(HashMapTraitsT, traits) 41 42template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 43 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>), 44 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 45class hash_map 46#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 47 : public __stlport_class<hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 48#endif 49{ 50private: 51 typedef hash_map<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 52public: 53 typedef _Key key_type; 54 typedef _Tp data_type; 55 typedef _Tp mapped_type; 56 typedef pair<_STLP_CONST key_type, data_type> value_type; 57private: 58 //Specific iterator traits creation 59 typedef _STLP_PRIV _HashMapTraitsT<value_type> _HashMapTraits; 60 61public: 62 typedef hashtable<value_type, key_type, _HashFcn, _HashMapTraits, 63 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 64 65 typedef typename _Ht::hasher hasher; 66 typedef typename _Ht::key_equal key_equal; 67 68 typedef typename _Ht::size_type size_type; 69 typedef typename _Ht::difference_type difference_type; 70 typedef typename _Ht::pointer pointer; 71 typedef typename _Ht::const_pointer const_pointer; 72 typedef typename _Ht::reference reference; 73 typedef typename _Ht::const_reference const_reference; 74 75 typedef typename _Ht::iterator iterator; 76 typedef typename _Ht::const_iterator const_iterator; 77 78 typedef typename _Ht::allocator_type allocator_type; 79 80 hasher hash_funct() const { return _M_ht.hash_funct(); } 81 key_equal key_eq() const { return _M_ht.key_eq(); } 82 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 83 84private: 85 _Ht _M_ht; 86 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 87public: 88 hash_map() : _M_ht(0, hasher(), key_equal(), allocator_type()) {} 89 explicit hash_map(size_type __n) 90 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 91 hash_map(size_type __n, const hasher& __hf) 92 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 93 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql, 94 const allocator_type& __a = allocator_type()) 95 : _M_ht(__n, __hf, __eql, __a) {} 96 97#if !defined (_STLP_NO_MOVE_SEMANTIC) 98 hash_map(__move_source<_Self> src) 99 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) { 100 } 101#endif 102 103#ifdef _STLP_MEMBER_TEMPLATES 104 template <class _InputIterator> 105 hash_map(_InputIterator __f, _InputIterator __l) 106 : _M_ht(0, hasher(), key_equal(), allocator_type()) 107 { _M_ht.insert_unique(__f, __l); } 108 template <class _InputIterator> 109 hash_map(_InputIterator __f, _InputIterator __l, size_type __n) 110 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 111 { _M_ht.insert_unique(__f, __l); } 112 template <class _InputIterator> 113 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 114 const hasher& __hf) 115 : _M_ht(__n, __hf, key_equal(), allocator_type()) 116 { _M_ht.insert_unique(__f, __l); } 117# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS 118 template <class _InputIterator> 119 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 120 const hasher& __hf, const key_equal& __eql) 121 : _M_ht(__n, __hf, __eql, allocator_type()) 122 { _M_ht.insert_unique(__f, __l); } 123# endif 124 template <class _InputIterator> 125 hash_map(_InputIterator __f, _InputIterator __l, size_type __n, 126 const hasher& __hf, const key_equal& __eql, 127 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 128 : _M_ht(__n, __hf, __eql, __a) 129 { _M_ht.insert_unique(__f, __l); } 130 131#else 132 hash_map(const value_type* __f, const value_type* __l) 133 : _M_ht(0, hasher(), key_equal(), allocator_type()) 134 { _M_ht.insert_unique(__f, __l); } 135 hash_map(const value_type* __f, const value_type* __l, size_type __n) 136 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 137 { _M_ht.insert_unique(__f, __l); } 138 hash_map(const value_type* __f, const value_type* __l, size_type __n, 139 const hasher& __hf) 140 : _M_ht(__n, __hf, key_equal(), allocator_type()) 141 { _M_ht.insert_unique(__f, __l); } 142 hash_map(const value_type* __f, const value_type* __l, size_type __n, 143 const hasher& __hf, const key_equal& __eql, 144 const allocator_type& __a = allocator_type()) 145 : _M_ht(__n, __hf, __eql, __a) 146 { _M_ht.insert_unique(__f, __l); } 147 148 hash_map(const_iterator __f, const_iterator __l) 149 : _M_ht(0, hasher(), key_equal(), allocator_type()) 150 { _M_ht.insert_unique(__f, __l); } 151 hash_map(const_iterator __f, const_iterator __l, size_type __n) 152 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 153 { _M_ht.insert_unique(__f, __l); } 154 hash_map(const_iterator __f, const_iterator __l, size_type __n, 155 const hasher& __hf) 156 : _M_ht(__n, __hf, key_equal(), allocator_type()) 157 { _M_ht.insert_unique(__f, __l); } 158 hash_map(const_iterator __f, const_iterator __l, size_type __n, 159 const hasher& __hf, const key_equal& __eql, 160 const allocator_type& __a = allocator_type()) 161 : _M_ht(__n, __hf, __eql, __a) 162 { _M_ht.insert_unique(__f, __l); } 163#endif /*_STLP_MEMBER_TEMPLATES */ 164 165public: 166 size_type size() const { return _M_ht.size(); } 167 size_type max_size() const { return _M_ht.max_size(); } 168 bool empty() const { return _M_ht.empty(); } 169 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 170#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 171 void _M_swap_workaround(_Self& __x) { swap(__x); } 172#endif 173 iterator begin() { return _M_ht.begin(); } 174 iterator end() { return _M_ht.end(); } 175 const_iterator begin() const { return _M_ht.begin(); } 176 const_iterator end() const { return _M_ht.end(); } 177 178public: 179 pair<iterator,bool> insert(const value_type& __obj) 180 { return _M_ht.insert_unique(__obj); } 181#ifdef _STLP_MEMBER_TEMPLATES 182 template <class _InputIterator> 183 void insert(_InputIterator __f, _InputIterator __l) 184 { _M_ht.insert_unique(__f,__l); } 185#else 186 void insert(const value_type* __f, const value_type* __l) 187 { _M_ht.insert_unique(__f,__l); } 188 void insert(const_iterator __f, const_iterator __l) 189 { _M_ht.insert_unique(__f, __l); } 190#endif /*_STLP_MEMBER_TEMPLATES */ 191 pair<iterator,bool> insert_noresize(const value_type& __obj) 192 { return _M_ht.insert_unique_noresize(__obj); } 193 194 _STLP_TEMPLATE_FOR_CONT_EXT 195 iterator find(const _KT& __key) { return _M_ht.find(__key); } 196 _STLP_TEMPLATE_FOR_CONT_EXT 197 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 198 199 _STLP_TEMPLATE_FOR_CONT_EXT 200 _Tp& operator[](const _KT& __key) { 201 iterator __it = _M_ht.find(__key); 202 return (__it == _M_ht.end() ? 203 _M_ht._M_insert(value_type(__key, _STLP_DEFAULT_CONSTRUCTED(_Tp))).second : 204 (*__it).second ); 205 } 206 207 _STLP_TEMPLATE_FOR_CONT_EXT 208 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 209 210 _STLP_TEMPLATE_FOR_CONT_EXT 211 pair<iterator, iterator> equal_range(const _KT& __key) 212 { return _M_ht.equal_range(__key); } 213 _STLP_TEMPLATE_FOR_CONT_EXT 214 pair<const_iterator, const_iterator> equal_range(const _KT& __key) const 215 { return _M_ht.equal_range(__key); } 216 217 _STLP_TEMPLATE_FOR_CONT_EXT 218 size_type erase(const _KT& __key) {return _M_ht.erase(__key); } 219 void erase(iterator __it) { _M_ht.erase(__it); } 220 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 221 void clear() { _M_ht.clear(); } 222 223 void resize(size_type __hint) { _M_ht.resize(__hint); } 224 size_type bucket_count() const { return _M_ht.bucket_count(); } 225 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 226 size_type elems_in_bucket(size_type __n) const 227 { return _M_ht.elems_in_bucket(__n); } 228}; 229 230//Specific iterator traits creation 231_STLP_CREATE_HASH_ITERATOR_TRAITS(HashMultimapTraitsT, traits) 232 233template <class _Key, class _Tp, _STLP_DFL_TMPL_PARAM(_HashFcn,hash<_Key>), 234 _STLP_DFL_TMPL_PARAM(_EqualKey,equal_to<_Key>), 235 _STLP_DEFAULT_PAIR_ALLOCATOR_SELECT(_STLP_CONST _Key, _Tp) > 236class hash_multimap 237#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 238 : public __stlport_class<hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> > 239#endif 240{ 241private: 242 typedef hash_multimap<_Key, _Tp, _HashFcn, _EqualKey, _Alloc> _Self; 243public: 244 typedef _Key key_type; 245 typedef _Tp data_type; 246 typedef _Tp mapped_type; 247 typedef pair<_STLP_CONST key_type, data_type> value_type; 248private: 249 //Specific iterator traits creation 250 typedef _STLP_PRIV _HashMultimapTraitsT<value_type> _HashMultimapTraits; 251 252public: 253 typedef hashtable<value_type, key_type, _HashFcn, _HashMultimapTraits, 254 _STLP_SELECT1ST(value_type, _Key), _EqualKey, _Alloc > _Ht; 255 256 typedef typename _Ht::hasher hasher; 257 typedef typename _Ht::key_equal key_equal; 258 259 typedef typename _Ht::size_type size_type; 260 typedef typename _Ht::difference_type difference_type; 261 typedef typename _Ht::pointer pointer; 262 typedef typename _Ht::const_pointer const_pointer; 263 typedef typename _Ht::reference reference; 264 typedef typename _Ht::const_reference const_reference; 265 266 typedef typename _Ht::iterator iterator; 267 typedef typename _Ht::const_iterator const_iterator; 268 269 typedef typename _Ht::allocator_type allocator_type; 270 271 hasher hash_funct() const { return _M_ht.hash_funct(); } 272 key_equal key_eq() const { return _M_ht.key_eq(); } 273 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 274 275private: 276 _Ht _M_ht; 277 _STLP_KEY_TYPE_FOR_CONT_EXT(key_type) 278public: 279 hash_multimap() : _M_ht(0, hasher(), key_equal(), allocator_type()) {} 280 explicit hash_multimap(size_type __n) 281 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 282 hash_multimap(size_type __n, const hasher& __hf) 283 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 284 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql, 285 const allocator_type& __a = allocator_type()) 286 : _M_ht(__n, __hf, __eql, __a) {} 287 288#if !defined (_STLP_NO_MOVE_SEMANTIC) 289 hash_multimap(__move_source<_Self> src) 290 : _M_ht(__move_source<_Ht>(src.get()._M_ht)) { 291 } 292#endif 293 294#ifdef _STLP_MEMBER_TEMPLATES 295 template <class _InputIterator> 296 hash_multimap(_InputIterator __f, _InputIterator __l) 297 : _M_ht(0, hasher(), key_equal(), allocator_type()) 298 { _M_ht.insert_equal(__f, __l); } 299 template <class _InputIterator> 300 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n) 301 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 302 { _M_ht.insert_equal(__f, __l); } 303 template <class _InputIterator> 304 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 305 const hasher& __hf) 306 : _M_ht(__n, __hf, key_equal(), allocator_type()) 307 { _M_ht.insert_equal(__f, __l); } 308# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS 309 template <class _InputIterator> 310 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 311 const hasher& __hf, const key_equal& __eql) 312 : _M_ht(__n, __hf, __eql, allocator_type()) 313 { _M_ht.insert_equal(__f, __l); } 314# endif 315 template <class _InputIterator> 316 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n, 317 const hasher& __hf, const key_equal& __eql, 318 const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) 319 : _M_ht(__n, __hf, __eql, __a) 320 { _M_ht.insert_equal(__f, __l); } 321 322#else 323 hash_multimap(const value_type* __f, const value_type* __l) 324 : _M_ht(0, hasher(), key_equal(), allocator_type()) 325 { _M_ht.insert_equal(__f, __l); } 326 hash_multimap(const value_type* __f, const value_type* __l, size_type __n) 327 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 328 { _M_ht.insert_equal(__f, __l); } 329 hash_multimap(const value_type* __f, const value_type* __l, size_type __n, 330 const hasher& __hf) 331 : _M_ht(__n, __hf, key_equal(), allocator_type()) 332 { _M_ht.insert_equal(__f, __l); } 333 hash_multimap(const value_type* __f, const value_type* __l, size_type __n, 334 const hasher& __hf, const key_equal& __eql, 335 const allocator_type& __a = allocator_type()) 336 : _M_ht(__n, __hf, __eql, __a) 337 { _M_ht.insert_equal(__f, __l); } 338 339 hash_multimap(const_iterator __f, const_iterator __l) 340 : _M_ht(0, hasher(), key_equal(), allocator_type()) 341 { _M_ht.insert_equal(__f, __l); } 342 hash_multimap(const_iterator __f, const_iterator __l, size_type __n) 343 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 344 { _M_ht.insert_equal(__f, __l); } 345 hash_multimap(const_iterator __f, const_iterator __l, size_type __n, 346 const hasher& __hf) 347 : _M_ht(__n, __hf, key_equal(), allocator_type()) 348 { _M_ht.insert_equal(__f, __l); } 349 hash_multimap(const_iterator __f, const_iterator __l, size_type __n, 350 const hasher& __hf, const key_equal& __eql, 351 const allocator_type& __a = allocator_type()) 352 : _M_ht(__n, __hf, __eql, __a) 353 { _M_ht.insert_equal(__f, __l); } 354#endif /*_STLP_MEMBER_TEMPLATES */ 355 356public: 357 size_type size() const { return _M_ht.size(); } 358 size_type max_size() const { return _M_ht.max_size(); } 359 bool empty() const { return _M_ht.empty(); } 360 void swap(_Self& __hs) { _M_ht.swap(__hs._M_ht); } 361#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 362 void _M_swap_workaround(_Self& __x) { swap(__x); } 363#endif 364 365 iterator begin() { return _M_ht.begin(); } 366 iterator end() { return _M_ht.end(); } 367 const_iterator begin() const { return _M_ht.begin(); } 368 const_iterator end() const { return _M_ht.end(); } 369 370public: 371 iterator insert(const value_type& __obj) 372 { return _M_ht.insert_equal(__obj); } 373#ifdef _STLP_MEMBER_TEMPLATES 374 template <class _InputIterator> 375 void insert(_InputIterator __f, _InputIterator __l) 376 { _M_ht.insert_equal(__f,__l); } 377#else 378 void insert(const value_type* __f, const value_type* __l) { 379 _M_ht.insert_equal(__f,__l); 380 } 381 void insert(const_iterator __f, const_iterator __l) 382 { _M_ht.insert_equal(__f, __l); } 383#endif /*_STLP_MEMBER_TEMPLATES */ 384 iterator insert_noresize(const value_type& __obj) 385 { return _M_ht.insert_equal_noresize(__obj); } 386 387 _STLP_TEMPLATE_FOR_CONT_EXT 388 iterator find(const _KT& __key) { return _M_ht.find(__key); } 389 _STLP_TEMPLATE_FOR_CONT_EXT 390 const_iterator find(const _KT& __key) const { return _M_ht.find(__key); } 391 392 _STLP_TEMPLATE_FOR_CONT_EXT 393 size_type count(const _KT& __key) const { return _M_ht.count(__key); } 394 395 _STLP_TEMPLATE_FOR_CONT_EXT 396 pair<iterator, iterator> 397 equal_range(const _KT& __key) { return _M_ht.equal_range(__key); } 398 _STLP_TEMPLATE_FOR_CONT_EXT 399 pair<const_iterator, const_iterator> 400 equal_range(const _KT& __key) const { return _M_ht.equal_range(__key); } 401 402 _STLP_TEMPLATE_FOR_CONT_EXT 403 size_type erase(const _KT& __key) {return _M_ht.erase(__key); } 404 void erase(iterator __it) { _M_ht.erase(__it); } 405 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 406 void clear() { _M_ht.clear(); } 407 408public: 409 void resize(size_type __hint) { _M_ht.resize(__hint); } 410 size_type bucket_count() const { return _M_ht.bucket_count(); } 411 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 412 size_type elems_in_bucket(size_type __n) const 413 { return _M_ht.elems_in_bucket(__n); } 414}; 415 416#define _STLP_TEMPLATE_HEADER template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> 417#define _STLP_TEMPLATE_CONTAINER hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 418#include <stl/_relops_hash_cont.h> 419#undef _STLP_TEMPLATE_CONTAINER 420#define _STLP_TEMPLATE_CONTAINER hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc> 421#include <stl/_relops_hash_cont.h> 422#undef _STLP_TEMPLATE_CONTAINER 423#undef _STLP_TEMPLATE_HEADER 424 425#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) 426# if !defined (_STLP_NO_MOVE_SEMANTIC) 427template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 428struct __move_traits<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 429 _STLP_PRIV __move_traits_help<typename hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 430{}; 431 432template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 433struct __move_traits<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > : 434 _STLP_PRIV __move_traits_help<typename hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>::_Ht> 435{}; 436# endif 437 438// Specialization of insert_iterator so that it will work for hash_map 439// and hash_multimap. 440template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 441class insert_iterator<hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 442protected: 443 typedef hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 444 _Container* container; 445public: 446 typedef _Container container_type; 447 typedef output_iterator_tag iterator_category; 448 typedef void value_type; 449 typedef void difference_type; 450 typedef void pointer; 451 typedef void reference; 452 453 insert_iterator(_Container& __x) : container(&__x) {} 454 insert_iterator(_Container& __x, typename _Container::iterator) 455 : container(&__x) {} 456 insert_iterator<_Container>& 457 operator=(const typename _Container::value_type& __val) { 458 container->insert(__val); 459 return *this; 460 } 461 insert_iterator<_Container>& operator*() { return *this; } 462 insert_iterator<_Container>& operator++() { return *this; } 463 insert_iterator<_Container>& operator++(int) { return *this; } 464}; 465 466template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> 467class insert_iterator<hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { 468protected: 469 typedef hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; 470 _Container* container; 471 typename _Container::iterator iter; 472public: 473 typedef _Container container_type; 474 typedef output_iterator_tag iterator_category; 475 typedef void value_type; 476 typedef void difference_type; 477 typedef void pointer; 478 typedef void reference; 479 480 insert_iterator(_Container& __x) : container(&__x) {} 481 insert_iterator(_Container& __x, typename _Container::iterator) 482 : container(&__x) {} 483 insert_iterator<_Container>& 484 operator=(const typename _Container::value_type& __val) { 485 container->insert(__val); 486 return *this; 487 } 488 insert_iterator<_Container>& operator*() { return *this; } 489 insert_iterator<_Container>& operator++() { return *this; } 490 insert_iterator<_Container>& operator++(int) { return *this; } 491}; 492#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */ 493 494_STLP_END_NAMESPACE 495 496#endif /* _STLP_INTERNAL_HASH_MAP_H */ 497 498// Local Variables: 499// mode:C++ 500// End: 501