1// Hashing map implementation -*- C++ -*-
2
3// Copyright (C) 2001-2013 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