1// Hashing set implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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). You should only 59 * include this header if you are using GCC 3 or later. 60 */ 61 62#ifndef __SGI_STL_INTERNAL_HASH_SET_H 63#define __SGI_STL_INTERNAL_HASH_SET_H 64 65#include <ext/stl_hashtable.h> 66#include <bits/concept_check.h> 67 68namespace __gnu_cxx 69{ 70using std::equal_to; 71using std::allocator; 72using std::pair; 73using std::_Identity; 74 75// Forward declaration of equality operator; needed for friend declaration. 76 77template <class _Value, 78 class _HashFcn = hash<_Value>, 79 class _EqualKey = equal_to<_Value>, 80 class _Alloc = allocator<_Value> > 81class hash_set; 82 83template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 84inline bool 85operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 86 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2); 87 88/** 89 * This is an SGI extension. 90 * @ingroup SGIextensions 91 * @doctodo 92*/ 93template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 94class hash_set 95{ 96 // concept requirements 97 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 98 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 99 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 100 101private: 102 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 103 _EqualKey, _Alloc> _Ht; 104 _Ht _M_ht; 105 106public: 107 typedef typename _Ht::key_type key_type; 108 typedef typename _Ht::value_type value_type; 109 typedef typename _Ht::hasher hasher; 110 typedef typename _Ht::key_equal key_equal; 111 112 typedef typename _Ht::size_type size_type; 113 typedef typename _Ht::difference_type difference_type; 114 typedef typename _Ht::const_pointer pointer; 115 typedef typename _Ht::const_pointer const_pointer; 116 typedef typename _Ht::const_reference reference; 117 typedef typename _Ht::const_reference const_reference; 118 119 typedef typename _Ht::const_iterator iterator; 120 typedef typename _Ht::const_iterator const_iterator; 121 122 typedef typename _Ht::allocator_type allocator_type; 123 124 hasher hash_funct() const { return _M_ht.hash_funct(); } 125 key_equal key_eq() const { return _M_ht.key_eq(); } 126 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 127 128public: 129 hash_set() 130 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 131 explicit hash_set(size_type __n) 132 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 133 hash_set(size_type __n, const hasher& __hf) 134 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 135 hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, 136 const allocator_type& __a = allocator_type()) 137 : _M_ht(__n, __hf, __eql, __a) {} 138 139 template <class _InputIterator> 140 hash_set(_InputIterator __f, _InputIterator __l) 141 : _M_ht(100, hasher(), key_equal(), allocator_type()) 142 { _M_ht.insert_unique(__f, __l); } 143 template <class _InputIterator> 144 hash_set(_InputIterator __f, _InputIterator __l, size_type __n) 145 : _M_ht(__n, hasher(), key_equal(), allocator_type()) 146 { _M_ht.insert_unique(__f, __l); } 147 template <class _InputIterator> 148 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 149 const hasher& __hf) 150 : _M_ht(__n, __hf, key_equal(), allocator_type()) 151 { _M_ht.insert_unique(__f, __l); } 152 template <class _InputIterator> 153 hash_set(_InputIterator __f, _InputIterator __l, size_type __n, 154 const hasher& __hf, const key_equal& __eql, 155 const allocator_type& __a = allocator_type()) 156 : _M_ht(__n, __hf, __eql, __a) 157 { _M_ht.insert_unique(__f, __l); } 158 159public: 160 size_type size() const { return _M_ht.size(); } 161 size_type max_size() const { return _M_ht.max_size(); } 162 bool empty() const { return _M_ht.empty(); } 163 void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } 164 165 template <class _Val, class _HF, class _EqK, class _Al> 166 friend bool operator== (const hash_set<_Val, _HF, _EqK, _Al>&, 167 const hash_set<_Val, _HF, _EqK, _Al>&); 168 169 iterator begin() const { return _M_ht.begin(); } 170 iterator end() const { return _M_ht.end(); } 171 172public: 173 pair<iterator, bool> insert(const value_type& __obj) 174 { 175 pair<typename _Ht::iterator, bool> __p = _M_ht.insert_unique(__obj); 176 return pair<iterator,bool>(__p.first, __p.second); 177 } 178 template <class _InputIterator> 179 void insert(_InputIterator __f, _InputIterator __l) 180 { _M_ht.insert_unique(__f,__l); } 181 pair<iterator, bool> insert_noresize(const value_type& __obj) 182 { 183 pair<typename _Ht::iterator, bool> __p = 184 _M_ht.insert_unique_noresize(__obj); 185 return pair<iterator, bool>(__p.first, __p.second); 186 } 187 188 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 189 190 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 191 192 pair<iterator, iterator> equal_range(const key_type& __key) const 193 { return _M_ht.equal_range(__key); } 194 195 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 196 void erase(iterator __it) { _M_ht.erase(__it); } 197 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 198 void clear() { _M_ht.clear(); } 199 200public: 201 void resize(size_type __hint) { _M_ht.resize(__hint); } 202 size_type bucket_count() const { return _M_ht.bucket_count(); } 203 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 204 size_type elems_in_bucket(size_type __n) const 205 { return _M_ht.elems_in_bucket(__n); } 206}; 207 208template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 209inline bool 210operator==(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 211 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) 212{ 213 return __hs1._M_ht == __hs2._M_ht; 214} 215 216template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 217inline bool 218operator!=(const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs1, 219 const hash_set<_Value,_HashFcn,_EqualKey,_Alloc>& __hs2) { 220 return !(__hs1 == __hs2); 221} 222 223template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 224inline void 225swap(hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 226 hash_set<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 227{ 228 __hs1.swap(__hs2); 229} 230 231 232template <class _Value, 233 class _HashFcn = hash<_Value>, 234 class _EqualKey = equal_to<_Value>, 235 class _Alloc = allocator<_Value> > 236class hash_multiset; 237 238template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 239inline bool 240operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 241 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2); 242 243 244/** 245 * This is an SGI extension. 246 * @ingroup SGIextensions 247 * @doctodo 248*/ 249template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 250class hash_multiset 251{ 252 // concept requirements 253 __glibcpp_class_requires(_Value, _SGIAssignableConcept) 254 __glibcpp_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept); 255 __glibcpp_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept); 256 257private: 258 typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, 259 _EqualKey, _Alloc> _Ht; 260 _Ht _M_ht; 261 262public: 263 typedef typename _Ht::key_type key_type; 264 typedef typename _Ht::value_type value_type; 265 typedef typename _Ht::hasher hasher; 266 typedef typename _Ht::key_equal key_equal; 267 268 typedef typename _Ht::size_type size_type; 269 typedef typename _Ht::difference_type difference_type; 270 typedef typename _Ht::const_pointer pointer; 271 typedef typename _Ht::const_pointer const_pointer; 272 typedef typename _Ht::const_reference reference; 273 typedef typename _Ht::const_reference const_reference; 274 275 typedef typename _Ht::const_iterator iterator; 276 typedef typename _Ht::const_iterator const_iterator; 277 278 typedef typename _Ht::allocator_type allocator_type; 279 280 hasher hash_funct() const { return _M_ht.hash_funct(); } 281 key_equal key_eq() const { return _M_ht.key_eq(); } 282 allocator_type get_allocator() const { return _M_ht.get_allocator(); } 283 284public: 285 hash_multiset() 286 : _M_ht(100, hasher(), key_equal(), allocator_type()) {} 287 explicit hash_multiset(size_type __n) 288 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} 289 hash_multiset(size_type __n, const hasher& __hf) 290 : _M_ht(__n, __hf, key_equal(), allocator_type()) {} 291 hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, 292 const allocator_type& __a = allocator_type()) 293 : _M_ht(__n, __hf, __eql, __a) {} 294 295 template <class _InputIterator> 296 hash_multiset(_InputIterator __f, _InputIterator __l) 297 : _M_ht(100, hasher(), key_equal(), allocator_type()) 298 { _M_ht.insert_equal(__f, __l); } 299 template <class _InputIterator> 300 hash_multiset(_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_multiset(_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 template <class _InputIterator> 309 hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, 310 const hasher& __hf, const key_equal& __eql, 311 const allocator_type& __a = allocator_type()) 312 : _M_ht(__n, __hf, __eql, __a) 313 { _M_ht.insert_equal(__f, __l); } 314 315public: 316 size_type size() const { return _M_ht.size(); } 317 size_type max_size() const { return _M_ht.max_size(); } 318 bool empty() const { return _M_ht.empty(); } 319 void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } 320 321 template <class _Val, class _HF, class _EqK, class _Al> 322 friend bool operator== (const hash_multiset<_Val, _HF, _EqK, _Al>&, 323 const hash_multiset<_Val, _HF, _EqK, _Al>&); 324 325 iterator begin() const { return _M_ht.begin(); } 326 iterator end() const { return _M_ht.end(); } 327 328public: 329 iterator insert(const value_type& __obj) 330 { return _M_ht.insert_equal(__obj); } 331 template <class _InputIterator> 332 void insert(_InputIterator __f, _InputIterator __l) 333 { _M_ht.insert_equal(__f,__l); } 334 iterator insert_noresize(const value_type& __obj) 335 { return _M_ht.insert_equal_noresize(__obj); } 336 337 iterator find(const key_type& __key) const { return _M_ht.find(__key); } 338 339 size_type count(const key_type& __key) const { return _M_ht.count(__key); } 340 341 pair<iterator, iterator> equal_range(const key_type& __key) const 342 { return _M_ht.equal_range(__key); } 343 344 size_type erase(const key_type& __key) {return _M_ht.erase(__key); } 345 void erase(iterator __it) { _M_ht.erase(__it); } 346 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } 347 void clear() { _M_ht.clear(); } 348 349public: 350 void resize(size_type __hint) { _M_ht.resize(__hint); } 351 size_type bucket_count() const { return _M_ht.bucket_count(); } 352 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } 353 size_type elems_in_bucket(size_type __n) const 354 { return _M_ht.elems_in_bucket(__n); } 355}; 356 357template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 358inline bool 359operator==(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 360 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) 361{ 362 return __hs1._M_ht == __hs2._M_ht; 363} 364 365template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 366inline bool 367operator!=(const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 368 const hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 369 return !(__hs1 == __hs2); 370} 371 372template <class _Val, class _HashFcn, class _EqualKey, class _Alloc> 373inline void 374swap(hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs1, 375 hash_multiset<_Val,_HashFcn,_EqualKey,_Alloc>& __hs2) { 376 __hs1.swap(__hs2); 377} 378 379} // namespace __gnu_cxx 380 381namespace std 382{ 383// Specialization of insert_iterator so that it will work for hash_set 384// and hash_multiset. 385 386template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 387class insert_iterator<__gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> > { 388protected: 389 typedef __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 390 _Container* container; 391public: 392 typedef _Container container_type; 393 typedef output_iterator_tag iterator_category; 394 typedef void value_type; 395 typedef void difference_type; 396 typedef void pointer; 397 typedef void reference; 398 399 insert_iterator(_Container& __x) : container(&__x) {} 400 insert_iterator(_Container& __x, typename _Container::iterator) 401 : container(&__x) {} 402 insert_iterator<_Container>& 403 operator=(const typename _Container::value_type& __value) { 404 container->insert(__value); 405 return *this; 406 } 407 insert_iterator<_Container>& operator*() { return *this; } 408 insert_iterator<_Container>& operator++() { return *this; } 409 insert_iterator<_Container>& operator++(int) { return *this; } 410}; 411 412template <class _Value, class _HashFcn, class _EqualKey, class _Alloc> 413class insert_iterator<__gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> > { 414protected: 415 typedef __gnu_cxx::hash_multiset<_Value, _HashFcn, _EqualKey, _Alloc> _Container; 416 _Container* container; 417 typename _Container::iterator iter; 418public: 419 typedef _Container container_type; 420 typedef output_iterator_tag iterator_category; 421 typedef void value_type; 422 typedef void difference_type; 423 typedef void pointer; 424 typedef void reference; 425 426 insert_iterator(_Container& __x) : container(&__x) {} 427 insert_iterator(_Container& __x, typename _Container::iterator) 428 : container(&__x) {} 429 insert_iterator<_Container>& 430 operator=(const typename _Container::value_type& __value) { 431 container->insert(__value); 432 return *this; 433 } 434 insert_iterator<_Container>& operator*() { return *this; } 435 insert_iterator<_Container>& operator++() { return *this; } 436 insert_iterator<_Container>& operator++(int) { return *this; } 437}; 438 439} // namespace std 440 441#endif /* __SGI_STL_INTERNAL_HASH_SET_H */ 442 443// Local Variables: 444// mode:C++ 445// End: 446