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