1// Hashing map 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_map
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_MAP
57#define _BACKWARD_HASH_MAP 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::_Select1st;
75
76 /**
77 * This is an SGI extension.
78 * @ingroup SGIextensions
79 * @doctodo
80 */
81 template<class _Key, class _Tp, class _HashFn = hash<_Key>,
82 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
83 class hash_map
84 {
85 private:
86 typedef hashtable<pair<const _Key, _Tp>,_Key, _HashFn,
87 _Select1st<pair<const _Key, _Tp> >,
88 _EqualKey, _Alloc> _Ht;
89
90 _Ht _M_ht;
91
92 public:
93 typedef typename _Ht::key_type key_type;
94 typedef _Tp data_type;
95 typedef _Tp mapped_type;
96 typedef typename _Ht::value_type value_type;
97 typedef typename _Ht::hasher hasher;
98 typedef typename _Ht::key_equal key_equal;
99
100 typedef typename _Ht::size_type size_type;
101 typedef typename _Ht::difference_type difference_type;
102 typedef typename _Ht::pointer pointer;
103 typedef typename _Ht::const_pointer const_pointer;
104 typedef typename _Ht::reference reference;
105 typedef typename _Ht::const_reference const_reference;
106
107 typedef typename _Ht::iterator iterator;
108 typedef typename _Ht::const_iterator const_iterator;
109
110 typedef typename _Ht::allocator_type allocator_type;
111
112 hasher
113 hash_funct() const
114 { return _M_ht.hash_funct(); }
115
116 key_equal
117 key_eq() const
118 { return _M_ht.key_eq(); }
119
120 allocator_type
121 get_allocator() const
122 { return _M_ht.get_allocator(); }
123
124 hash_map()
125 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
126
127 explicit
128 hash_map(size_type __n)
129 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
130
131 hash_map(size_type __n, const hasher& __hf)
132 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
133
134 hash_map(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_map(_InputIterator __f, _InputIterator __l)
140 : _M_ht(100, hasher(), key_equal(), allocator_type())
141 { _M_ht.insert_unique(__f, __l); }
142
143 template<class _InputIterator>
144 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
145 : _M_ht(__n, hasher(), key_equal(), allocator_type())
146 { _M_ht.insert_unique(__f, __l); }
147
148 template<class _InputIterator>
149 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
150 const hasher& __hf)
151 : _M_ht(__n, __hf, key_equal(), allocator_type())
152 { _M_ht.insert_unique(__f, __l); }
153
154 template<class _InputIterator>
155 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
156 const hasher& __hf, const key_equal& __eql,
157 const allocator_type& __a = allocator_type())
158 : _M_ht(__n, __hf, __eql, __a)
159 { _M_ht.insert_unique(__f, __l); }
160
161 size_type
162 size() const
163 { return _M_ht.size(); }
164
165 size_type
166 max_size() const
167 { return _M_ht.max_size(); }
168
169 bool
170 empty() const
171 { return _M_ht.empty(); }
172
173 void
174 swap(hash_map& __hs)
175 { _M_ht.swap(__hs._M_ht); }
176
177 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
178 friend bool
179 operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
180 const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
181
182 iterator
183 begin()
184 { return _M_ht.begin(); }
185
186 iterator
187 end()
188 { return _M_ht.end(); }
189
190 const_iterator
191 begin() const
192 { return _M_ht.begin(); }
193
194 const_iterator
195 end() const
196 { return _M_ht.end(); }
197
198 pair<iterator, bool>
199 insert(const value_type& __obj)
200 { return _M_ht.insert_unique(__obj); }
201
202 template<class _InputIterator>
203 void
204 insert(_InputIterator __f, _InputIterator __l)
205 { _M_ht.insert_unique(__f, __l); }
206
207 pair<iterator, bool>
208 insert_noresize(const value_type& __obj)
209 { return _M_ht.insert_unique_noresize(__obj); }
210
211 iterator
212 find(const key_type& __key)
213 { return _M_ht.find(__key); }
214
215 const_iterator
216 find(const key_type& __key) const
217 { return _M_ht.find(__key); }
218
219 _Tp&
220 operator[](const key_type& __key)
221 { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
222
223 size_type
224 count(const key_type& __key) const
225 { return _M_ht.count(__key); }
226
227 pair<iterator, iterator>
228 equal_range(const key_type& __key)
229 { return _M_ht.equal_range(__key); }
230
231 pair<const_iterator, const_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
251 void
252 resize(size_type __hint)
253 { _M_ht.resize(__hint); }
254
255 size_type
256 bucket_count() const
257 { return _M_ht.bucket_count(); }
258
259 size_type
260 max_bucket_count() const
261 { return _M_ht.max_bucket_count(); }
262
263 size_type
264 elems_in_bucket(size_type __n) const
265 { return _M_ht.elems_in_bucket(__n); }
266 };
267
268 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
269 inline bool
270 operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
271 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
272 { return __hm1._M_ht == __hm2._M_ht; }
273
274 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
275 inline bool
276 operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
277 const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
278 { return !(__hm1 == __hm2); }
279
280 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
281 inline void
282 swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
283 hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
284 { __hm1.swap(__hm2); }
285
286
287 /**
288 * This is an SGI extension.
289 * @ingroup SGIextensions
290 * @doctodo
291 */
292 template<class _Key, class _Tp,
293 class _HashFn = hash<_Key>,
294 class _EqualKey = equal_to<_Key>,
295 class _Alloc = allocator<_Tp> >
296 class hash_multimap
297 {
298 // concept requirements
299 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
300 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
301 __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
302 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
303
304 private:
305 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
306 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
307 _Ht;
308
309 _Ht _M_ht;
310
311 public:
312 typedef typename _Ht::key_type key_type;
313 typedef _Tp data_type;
314 typedef _Tp mapped_type;
315 typedef typename _Ht::value_type value_type;
316 typedef typename _Ht::hasher hasher;
317 typedef typename _Ht::key_equal key_equal;
318
319 typedef typename _Ht::size_type size_type;
320 typedef typename _Ht::difference_type difference_type;
321 typedef typename _Ht::pointer pointer;
322 typedef typename _Ht::const_pointer const_pointer;
323 typedef typename _Ht::reference reference;
324 typedef typename _Ht::const_reference const_reference;
325
326 typedef typename _Ht::iterator iterator;
327 typedef typename _Ht::const_iterator const_iterator;
328
329 typedef typename _Ht::allocator_type allocator_type;
330
331 hasher
332 hash_funct() const
333 { return _M_ht.hash_funct(); }
334
335 key_equal
336 key_eq() const
337 { return _M_ht.key_eq(); }
338
339 allocator_type
340 get_allocator() const
341 { return _M_ht.get_allocator(); }
342
343 hash_multimap()
344 : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
345
346 explicit
347 hash_multimap(size_type __n)
348 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
349
350 hash_multimap(size_type __n, const hasher& __hf)
351 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
352
353 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
354 const allocator_type& __a = allocator_type())
355 : _M_ht(__n, __hf, __eql, __a) {}
356
357 template<class _InputIterator>
358 hash_multimap(_InputIterator __f, _InputIterator __l)
359 : _M_ht(100, hasher(), key_equal(), allocator_type())
360 { _M_ht.insert_equal(__f, __l); }
361
362 template<class _InputIterator>
363 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
364 : _M_ht(__n, hasher(), key_equal(), allocator_type())
365 { _M_ht.insert_equal(__f, __l); }
366
367 template<class _InputIterator>
368 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
369 const hasher& __hf)
370 : _M_ht(__n, __hf, key_equal(), allocator_type())
371 { _M_ht.insert_equal(__f, __l); }
372
373 template<class _InputIterator>
374 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
375 const hasher& __hf, const key_equal& __eql,
376 const allocator_type& __a = allocator_type())
377 : _M_ht(__n, __hf, __eql, __a)
378 { _M_ht.insert_equal(__f, __l); }
379
380 size_type
381 size() const
382 { return _M_ht.size(); }
383
384 size_type
385 max_size() const
386 { return _M_ht.max_size(); }
387
388 bool
389 empty() const
390 { return _M_ht.empty(); }
391
392 void
393 swap(hash_multimap& __hs)
394 { _M_ht.swap(__hs._M_ht); }
395
396 template<class _K1, class _T1, class _HF, class _EqK, class _Al>
397 friend bool
398 operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
399 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
400
401 iterator
402 begin()
403 { return _M_ht.begin(); }
404
405 iterator
406 end()
407 { return _M_ht.end(); }
408
409 const_iterator
410 begin() const
411 { return _M_ht.begin(); }
412
413 const_iterator
414 end() const
415 { return _M_ht.end(); }
416
417 iterator
418 insert(const value_type& __obj)
419 { return _M_ht.insert_equal(__obj); }
420
421 template<class _InputIterator>
422 void
423 insert(_InputIterator __f, _InputIterator __l)
424 { _M_ht.insert_equal(__f,__l); }
425
426 iterator
427 insert_noresize(const value_type& __obj)
428 { return _M_ht.insert_equal_noresize(__obj); }
429
430 iterator
431 find(const key_type& __key)
432 { return _M_ht.find(__key); }
433
434 const_iterator
435 find(const key_type& __key) const
436 { return _M_ht.find(__key); }
437
438 size_type
439 count(const key_type& __key) const
440 { return _M_ht.count(__key); }
441
442 pair<iterator, iterator>
443 equal_range(const key_type& __key)
444 { return _M_ht.equal_range(__key); }
445
446 pair<const_iterator, const_iterator>
447 equal_range(const key_type& __key) const
448 { return _M_ht.equal_range(__key); }
449
450 size_type
451 erase(const key_type& __key)
452 { return _M_ht.erase(__key); }
453
454 void
455 erase(iterator __it)
456 { _M_ht.erase(__it); }
457
458 void
459 erase(iterator __f, iterator __l)
460 { _M_ht.erase(__f, __l); }
461
462 void
463 clear()
464 { _M_ht.clear(); }
465
466 void
467 resize(size_type __hint)
468 { _M_ht.resize(__hint); }
469
470 size_type
471 bucket_count() const
472 { return _M_ht.bucket_count(); }
473
474 size_type
475 max_bucket_count() const
476 { return _M_ht.max_bucket_count(); }
477
478 size_type
479 elems_in_bucket(size_type __n) const
480 { return _M_ht.elems_in_bucket(__n); }
481 };
482
483 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
484 inline bool
485 operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
486 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
487 { return __hm1._M_ht == __hm2._M_ht; }
488
489 template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
490 inline bool
491 operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
492 const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
493 { return !(__hm1 == __hm2); }
494
495 template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
496 inline void
497 swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
498 hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
499 { __hm1.swap(__hm2); }
500
501_GLIBCXX_END_NAMESPACE_VERSION
502} // namespace
503
504namespace std _GLIBCXX_VISIBILITY(default)
505{
506_GLIBCXX_BEGIN_NAMESPACE_VERSION
507
508 // Specialization of insert_iterator so that it will work for hash_map
509 // and hash_multimap.
510 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
511 class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn,
512 _EqKey, _Alloc> >
513 {
514 protected:
515 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>
516 _Container;
517 _Container* container;
518
519 public:
520 typedef _Container container_type;
521 typedef output_iterator_tag iterator_category;
522 typedef void value_type;
523 typedef void difference_type;
524 typedef void pointer;
525 typedef void reference;
526
527 insert_iterator(_Container& __x)
528 : container(&__x) {}
529
530 insert_iterator(_Container& __x, typename _Container::iterator)
531 : container(&__x) {}
532
533 insert_iterator<_Container>&
534 operator=(const typename _Container::value_type& __value)
535 {
536 container->insert(__value);
537 return *this;
538 }
539
540 insert_iterator<_Container>&
541 operator*()
542 { return *this; }
543
544 insert_iterator<_Container>&
545 operator++() { return *this; }
546
547 insert_iterator<_Container>&
548 operator++(int)
549 { return *this; }
550 };
551
552 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
553 class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn,
554 _EqKey, _Alloc> >
555 {
556 protected:
557 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc>
558 _Container;
559 _Container* container;
560 typename _Container::iterator iter;
561
562 public:
563 typedef _Container container_type;
564 typedef output_iterator_tag iterator_category;
565 typedef void value_type;
566 typedef void difference_type;
567 typedef void pointer;
568 typedef void reference;
569
570 insert_iterator(_Container& __x)
571 : container(&__x) {}
572
573 insert_iterator(_Container& __x, typename _Container::iterator)
574 : container(&__x) {}
575
576 insert_iterator<_Container>&
577 operator=(const typename _Container::value_type& __value)
578 {
579 container->insert(__value);
580 return *this;
581 }
582
583 insert_iterator<_Container>&
584 operator*()
585 { return *this; }
586
587 insert_iterator<_Container>&
588 operator++()
589 { return *this; }
590
591 insert_iterator<_Container>&
592 operator++(int)
593 { return *this; }
594 };
595
596_GLIBCXX_END_NAMESPACE_VERSION
597} // namespace
598
599#endif
600