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