1// Hashing set implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 2, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// You should have received a copy of the GNU General Public License along 17// with this library; see the file COPYING. If not, write to the Free 18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19// USA. 20 21// As a special exception, you may use this file as part of a free software 22// library without restriction. Specifically, if other files instantiate 23// templates or use macros or inline functions from this file, or you compile 24// this file and link it with other files to produce an executable, this 25// file does not by itself cause the resulting executable to be covered by 26// the GNU General Public License. This exception does not however 27// invalidate any other reasons why the executable file might be covered by 28// the GNU General Public License. 29 30/* 31 * Copyright (c) 1996 32 * Silicon Graphics Computer Systems, Inc. 33 * 34 * Permission to use, copy, modify, distribute and sell this software 35 * and its documentation for any purpose is hereby granted without fee, 36 * provided that the above copyright notice appear in all copies and 37 * that both that copyright notice and this permission notice appear 38 * in supporting documentation. Silicon Graphics makes no 39 * representations about the suitability of this software for any 40 * purpose. It is provided "as is" without express or implied warranty. 41 * 42 * 43 * Copyright (c) 1994 44 * Hewlett-Packard Company 45 * 46 * Permission to use, copy, modify, distribute and sell this software 47 * and its documentation for any purpose is hereby granted without fee, 48 * provided that the above copyright notice appear in all copies and 49 * that both that copyright notice and this permission notice appear 50 * in supporting documentation. Hewlett-Packard Company makes no 51 * representations about the suitability of this software for any 52 * purpose. It is provided "as is" without express or implied warranty. 53 * 54 */ 55 56/** @file ext/hash_set 57 * This file is a GNU extension to the Standard C++ Library (possibly 58 * containing extensions from the HP/SGI STL subset). 59 */ 60 61#ifndef _HASH_SET 62#define _HASH_SET 1 63 64#include <ext/hashtable.h> 65#include <bits/concept_check.h> 66 67namespace __gnu_cxx 68{ 69 using std::equal_to; 70 using std::allocator; 71 using std::pair; 72 using std::_Identity; 73 74 // Forward declaration of equality operator; needed for friend 75 // declaration. 76 template <class _Value, class _HashFcn = hash<_Value>, 77 class _EqualKey = equal_to<_Value>, 78 class _Alloc = allocator<_Value> > 79 class hash_set; 80 81 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 82 inline bool 83 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 84 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2); 85 86 /** 87 * This is an SGI extension. 88 * @ingroup SGIextensions 89 * @doctodo 90 */ 91 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 92 class hash_set 93 { 94 // concept requirements 95 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 96 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 97 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 98 99 private: 100 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 101 _EqualKey, _Alloc> _Ht; 102 _Ht _M_ht; 103 104 public: 105 typedef typename _Ht::key_type key_type; 106 typedef typename _Ht::value_type value_type; 107 typedef typename _Ht::hasher hasher; 108 typedef typename _Ht::key_equal key_equal; 109 110 typedef typename _Ht::size_type size_type; 111 typedef typename _Ht::difference_type difference_type; 112 typedef typename _Alloc::pointer pointer; 113 typedef typename _Alloc::const_pointer const_pointer; 114 typedef typename _Alloc::reference reference; 115 typedef typename _Alloc::const_reference const_reference; 116 117 typedef typename _Ht::const_iterator iterator; 118 typedef typename _Ht::const_iterator const_iterator; 119 120 typedef typename _Ht::allocator_type allocator_type; 121 122 hasher 123 hash_funct() const 124 { return _M_ht.hash_funct(); } 125 126 key_equal 127 key_eq() const 128 { return _M_ht.key_eq(); } 129 130 allocator_type 131 get_allocator() const 132 { return _M_ht.get_allocator(); } 133 134 public: 135 hash_set() 136 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 137 138 explicit 139 hash_set(size_type __n) 140 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 141 142 hash_set(size_type __n, const hasher& __hf) 143 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 144 145 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 146 const allocator_type& __a = allocator_type()) 147 : _M_ht(__n, __hf, __eql, __a) {} 148 149 template <class _InputIterator> 150 hash_set(_InputIterator __f, _InputIterator __l) 151 : _M_ht(100, hasher(), key_equal(), allocator_type()) 152 { _M_ht.insert_unique(__f, __l); } 153 154 template <class _InputIterator> 155 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 156 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 157 { _M_ht.insert_unique(__f, __l); } 158 159 template <class _InputIterator> 160 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 161 const hasher& __hf) 162 : _M_ht(__n, __hf, key_equal(), allocator_type()) 163 { _M_ht.insert_unique(__f, __l); } 164 165 template <class _InputIterator> 166 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 167 const hasher& __hf, const key_equal& __eql, 168 const allocator_type& __a = allocator_type()) 169 : _M_ht(__n, __hf, __eql, __a) 170 { _M_ht.insert_unique(__f, __l); } 171 172 public: 173 size_type 174 size() const 175 { return _M_ht.size(); } 176 177 size_type 178 max_size() const 179 { return _M_ht.max_size(); } 180 181 bool 182 empty() const 183 { return _M_ht.empty(); } 184 185 void 186 swap(hash_set& __hs) 187 { _M_ht.swap(__hs._M_ht); } 188 189 template <class _Val, class _HF, class _EqK, class _Al> 190 friend bool 191 operator==(const hash_set<_Val, _HF, _EqK, _Al>&, 192 const hash_set<_Val, _HF, _EqK, _Al>&); 193 194 iterator 195 begin() const 196 { return _M_ht.begin(); } 197 198 iterator 199 end() const 200 { return _M_ht.end(); } 201 202 public: 203 pair<iterator, bool> 204 insert(const value_type& __obj) 205 { 206 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 207 return pair<iterator,bool>(__p.first, __p.second); 208 } 209 210 template <class _InputIterator> 211 void 212 insert(_InputIterator __f, _InputIterator __l) 213 { _M_ht.insert_unique(__f, __l); } 214 215 pair<iterator, bool> 216 insert_noresize(const value_type& __obj) 217 { 218 pair<typename _Ht::iterator, bool> __p 219 = _M_ht.insert_unique_noresize(__obj); 220 return pair<iterator, bool>(__p.first, __p.second); 221 } 222 223 iterator 224 find(const key_type& __key) const 225 { return _M_ht.find(__key); } 226 227 size_type 228 count(const key_type& __key) const 229 { return _M_ht.count(__key); } 230 231 pair<iterator, iterator> 232 equal_range(const key_type& __key) const 233 { return _M_ht.equal_range(__key); } 234 235 size_type 236 erase(const key_type& __key) 237 {return _M_ht.erase(__key); } 238 239 void 240 erase(iterator __it) 241 { _M_ht.erase(__it); } 242 243 void 244 erase(iterator __f, iterator __l) 245 { _M_ht.erase(__f, __l); } 246 247 void 248 clear() 249 { _M_ht.clear(); } 250 251public: 252 void 253 resize(size_type __hint) 254 { _M_ht.resize(__hint); } 255 256 size_type 257 bucket_count() const 258 { return _M_ht.bucket_count(); } 259 260 size_type 261 max_bucket_count() const 262 { return _M_ht.max_bucket_count(); } 263 264 size_type 265 elems_in_bucket(size_type __n) const 266 { return _M_ht.elems_in_bucket(__n); } 267 }; 268 269 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 270 inline bool 271 operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 272 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 273 { return __hs1._M_ht == __hs2._M_ht; } 274 275 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 276 inline bool 277 operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, 278 const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) 279 { return !(__hs1 == __hs2); } 280 281 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 282 inline void 283 swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 284 hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 285 { __hs1.swap(__hs2); } 286 287 template <class _Value, 288 class _HashFcn = hash<_Value>, 289 class _EqualKey = equal_to<_Value>, 290 class _Alloc = allocator<_Value> > 291 class hash_multiset; 292 293 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 294 inline bool 295 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 296 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2); 297 298 299 /** 300 * This is an SGI extension. 301 * @ingroup SGIextensions 302 * @doctodo 303 */ 304 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 305 class hash_multiset 306 { 307 // concept requirements 308 __glibcxx_class_requires(_Value, _SGIAssignableConcept) 309 __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) 310 __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) 311 312 private: 313 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 314 _EqualKey, _Alloc> _Ht; 315 _Ht _M_ht; 316 317 public: 318 typedef typename _Ht::key_type key_type; 319 typedef typename _Ht::value_type value_type; 320 typedef typename _Ht::hasher hasher; 321 typedef typename _Ht::key_equal key_equal; 322 323 typedef typename _Ht::size_type size_type; 324 typedef typename _Ht::difference_type difference_type; 325 typedef typename _Alloc::pointer pointer; 326 typedef typename _Alloc::const_pointer const_pointer; 327 typedef typename _Alloc::reference reference; 328 typedef typename _Alloc::const_reference const_reference; 329 330 typedef typename _Ht::const_iterator iterator; 331 typedef typename _Ht::const_iterator const_iterator; 332 333 typedef typename _Ht::allocator_type allocator_type; 334 335 hasher 336 hash_funct() const 337 { return _M_ht.hash_funct(); } 338 339 key_equal 340 key_eq() const 341 { return _M_ht.key_eq(); } 342 343 allocator_type 344 get_allocator() const 345 { return _M_ht.get_allocator(); } 346 347 public: 348 hash_multiset() 349 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 350 351 explicit 352 hash_multiset(size_type __n) 353 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 354 355 hash_multiset(size_type __n, const hasher& __hf) 356 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 357 358 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 359 const allocator_type& __a = allocator_type()) 360 : _M_ht(__n, __hf, __eql, __a) {} 361 362 template <class _InputIterator> 363 hash_multiset(_InputIterator __f, _InputIterator __l) 364 : _M_ht(100, hasher(), key_equal(), allocator_type()) 365 { _M_ht.insert_equal(__f, __l); } 366 367 template <class _InputIterator> 368 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) 369 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 370 { _M_ht.insert_equal(__f, __l); } 371 372 template <class _InputIterator> 373 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 374 const hasher& __hf) 375 : _M_ht(__n, __hf, key_equal(), allocator_type()) 376 { _M_ht.insert_equal(__f, __l); } 377 378 template <class _InputIterator> 379 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 380 const hasher& __hf, const key_equal& __eql, 381 const allocator_type& __a = allocator_type()) 382 : _M_ht(__n, __hf, __eql, __a) 383 { _M_ht.insert_equal(__f, __l); } 384 385 public: 386 size_type 387 size() const 388 { return _M_ht.size(); } 389 390 size_type 391 max_size() const 392 { return _M_ht.max_size(); } 393 394 bool 395 empty() const 396 { return _M_ht.empty(); } 397 398 void 399 swap(hash_multiset& hs) 400 { _M_ht.swap(hs._M_ht); } 401 402 template <class _Val, class _HF, class _EqK, class _Al> 403 friend bool 404 operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, 405 const hash_multiset<_Val, _HF, _EqK, _Al>&); 406 407 iterator 408 begin() const 409 { return _M_ht.begin(); } 410 411 iterator 412 end() const 413 { return _M_ht.end(); } 414 415public: 416 iterator 417 insert(const value_type& __obj) 418 { return _M_ht.insert_equal(__obj); } 419 420 template <class _InputIterator> 421 void 422 insert(_InputIterator __f, _InputIterator __l) 423 { _M_ht.insert_equal(__f,__l); } 424 425 iterator 426 insert_noresize(const value_type& __obj) 427 { return _M_ht.insert_equal_noresize(__obj); } 428 429 iterator 430 find(const key_type& __key) const 431 { return _M_ht.find(__key); } 432 433 size_type 434 count(const key_type& __key) const 435 { return _M_ht.count(__key); } 436 437 pair<iterator, iterator> 438 equal_range(const key_type& __key) const 439 { return _M_ht.equal_range(__key); } 440 441 size_type 442 erase(const key_type& __key) 443 { return _M_ht.erase(__key); } 444 445 void 446 erase(iterator __it) 447 { _M_ht.erase(__it); } 448 449 void 450 erase(iterator __f, iterator __l) 451 { _M_ht.erase(__f, __l); } 452 453 void 454 clear() 455 { _M_ht.clear(); } 456 457 public: 458 void 459 resize(size_type __hint) 460 { _M_ht.resize(__hint); } 461 462 size_type 463 bucket_count() const 464 { return _M_ht.bucket_count(); } 465 466 size_type 467 max_bucket_count() const 468 { return _M_ht.max_bucket_count(); } 469 470 size_type 471 elems_in_bucket(size_type __n) const 472 { return _M_ht.elems_in_bucket(__n); } 473 }; 474 475 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 476 inline bool 477 operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 478 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 479 { return __hs1._M_ht == __hs2._M_ht; } 480 481 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 482 inline bool 483 operator!=(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 484 const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 485 { return !(__hs1 == __hs2); } 486 487 template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 488 inline void 489 swap(hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, 490 hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) 491 { __hs1.swap(__hs2); } 492 493} // namespace __gnu_cxx 494 495namespace std 496{ 497 // Specialization of insert_iterator so that it will work for hash_set 498 // and hash_multiset. 499 500 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 501 class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, 502 _EqualKey, _Alloc> > 503 { 504 protected: 505 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> 506 _Container; 507 _Container* container; 508 509 public: 510 typedef _Container container_type; 511 typedef output_iterator_tag iterator_category; 512 typedef void value_type; 513 typedef void difference_type; 514 typedef void pointer; 515 typedef void reference; 516 517 insert_iterator(_Container& __x) 518 : container(&__x) {} 519 520 insert_iterator(_Container& __x, typename _Container::iterator) 521 : container(&__x) {} 522 523 insert_iterator<_Container>& 524 operator=(const typename _Container::value_type& __value) 525 { 526 container->insert(__value); 527 return *this; 528 } 529 530 insert_iterator<_Container>& 531 operator*() 532 { return *this; } 533 534 insert_iterator<_Container>& 535 operator++() 536 { return *this; } 537 538 insert_iterator<_Container>& 539 operator++(int) 540 { return *this; } 541 }; 542 543 template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 544 class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, 545 _EqualKey, _Alloc> > 546 { 547 protected: 548 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> 549 _Container; 550 _Container* container; 551 typename _Container::iterator iter; 552 553 public: 554 typedef _Container container_type; 555 typedef output_iterator_tag iterator_category; 556 typedef void value_type; 557 typedef void difference_type; 558 typedef void pointer; 559 typedef void reference; 560 561 insert_iterator(_Container& __x) 562 : container(&__x) {} 563 564 insert_iterator(_Container& __x, typename _Container::iterator) 565 : container(&__x) {} 566 567 insert_iterator<_Container>& 568 operator=(const typename _Container::value_type& __value) 569 { 570 container->insert(__value); 571 return *this; 572 } 573 574 insert_iterator<_Container>& 575 operator*() 576 { return *this; } 577 578 insert_iterator<_Container>& 579 operator++() 580 { return *this; } 581 582 insert_iterator<_Container>& 583 operator++(int) { return *this; } 584 }; 585} // namespace std 586 587#ifdef _GLIBCXX_DEBUG 588# include <debug/hash_set> 589#endif 590 591#endif 592