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