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