OSDN Git Service

2007-10-12 Benjamin Kosnik <bkoz@redhat.com>
[pf3gnuchains/gcc-fork.git] / libstdc++-v3 / include / ext / hash_map
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_D)
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       hash_map()
124       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
125   
126       explicit
127       hash_map(size_type __n)
128       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
129
130       hash_map(size_type __n, const hasher& __hf)
131       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
132
133       hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
134                const allocator_type& __a = allocator_type())
135       : _M_ht(__n, __hf, __eql, __a) {}
136
137       template<class _InputIterator>
138         hash_map(_InputIterator __f, _InputIterator __l)
139         : _M_ht(100, hasher(), key_equal(), allocator_type())
140         { _M_ht.insert_unique(__f, __l); }
141
142       template<class _InputIterator>
143         hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
144         : _M_ht(__n, hasher(), key_equal(), allocator_type())
145         { _M_ht.insert_unique(__f, __l); }
146
147       template<class _InputIterator>
148         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
149                  const hasher& __hf)
150         : _M_ht(__n, __hf, key_equal(), allocator_type())
151         { _M_ht.insert_unique(__f, __l); }
152
153       template<class _InputIterator>
154         hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
155                  const hasher& __hf, const key_equal& __eql,
156                  const allocator_type& __a = allocator_type())
157         : _M_ht(__n, __hf, __eql, __a)
158         { _M_ht.insert_unique(__f, __l); }
159
160       size_type
161       size() const
162       { return _M_ht.size(); }
163       
164       size_type
165       max_size() const
166       { return _M_ht.max_size(); }
167       
168       bool
169       empty() const
170       { return _M_ht.empty(); }
171   
172       void
173       swap(hash_map& __hs)
174       { _M_ht.swap(__hs._M_ht); }
175
176       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
177         friend bool
178         operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
179                     const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
180
181       iterator
182       begin()
183       { return _M_ht.begin(); }
184
185       iterator
186       end()
187       { return _M_ht.end(); }
188
189       const_iterator
190       begin() const
191       { return _M_ht.begin(); }
192
193       const_iterator
194       end() const
195       { return _M_ht.end(); }
196
197       pair<iterator, bool>
198       insert(const value_type& __obj)
199       { return _M_ht.insert_unique(__obj); }
200
201       template<class _InputIterator>
202         void
203         insert(_InputIterator __f, _InputIterator __l)
204         { _M_ht.insert_unique(__f, __l); }
205
206       pair<iterator, bool>
207       insert_noresize(const value_type& __obj)
208       { return _M_ht.insert_unique_noresize(__obj); }
209
210       iterator
211       find(const key_type& __key)
212       { return _M_ht.find(__key); }
213
214       const_iterator
215       find(const key_type& __key) const
216       { return _M_ht.find(__key); }
217
218       _Tp&
219       operator[](const key_type& __key)
220       { return _M_ht.find_or_insert(value_type(__key, _Tp())).second; }
221
222       size_type
223       count(const key_type& __key) const
224       { return _M_ht.count(__key); }
225
226       pair<iterator, iterator>
227       equal_range(const key_type& __key)
228       { return _M_ht.equal_range(__key); }
229
230       pair<const_iterator, const_iterator>
231       equal_range(const key_type& __key) const
232       { return _M_ht.equal_range(__key); }
233
234       size_type
235       erase(const key_type& __key)
236       {return _M_ht.erase(__key); }
237
238       void
239       erase(iterator __it)
240       { _M_ht.erase(__it); }
241
242       void
243       erase(iterator __f, iterator __l)
244       { _M_ht.erase(__f, __l); }
245
246       void
247       clear()
248       { _M_ht.clear(); }
249
250       void
251       resize(size_type __hint)
252       { _M_ht.resize(__hint); }
253
254       size_type
255       bucket_count() const
256       { return _M_ht.bucket_count(); }
257
258       size_type
259       max_bucket_count() const
260       { return _M_ht.max_bucket_count(); }
261
262       size_type
263       elems_in_bucket(size_type __n) const
264       { return _M_ht.elems_in_bucket(__n); }
265     };
266
267   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
268     inline bool
269     operator==(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
270                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
271     { return __hm1._M_ht == __hm2._M_ht; }
272
273   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
274     inline bool
275     operator!=(const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
276                const hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
277     { return !(__hm1 == __hm2); }
278
279   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
280     inline void
281     swap(hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
282          hash_map<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
283     { __hm1.swap(__hm2); }
284
285
286   /**
287    *  This is an SGI extension.
288    *  @ingroup SGIextensions
289    *  @doctodo
290    */
291   template<class _Key, class _Tp,
292            class _HashFn = hash<_Key>,
293            class _EqualKey = equal_to<_Key>,
294            class _Alloc = allocator<_Tp> >
295     class hash_multimap
296     {
297       // concept requirements
298       __glibcxx_class_requires(_Key, _SGIAssignableConcept)
299       __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
300       __glibcxx_class_requires3(_HashFn, size_t, _Key, _UnaryFunctionConcept)
301       __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
302         
303     private:
304       typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFn,
305                         _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
306           _Ht;
307
308       _Ht _M_ht;
309
310     public:
311       typedef typename _Ht::key_type key_type;
312       typedef _Tp data_type;
313       typedef _Tp mapped_type;
314       typedef typename _Ht::value_type value_type;
315       typedef typename _Ht::hasher hasher;
316       typedef typename _Ht::key_equal key_equal;
317       
318       typedef typename _Ht::size_type size_type;
319       typedef typename _Ht::difference_type difference_type;
320       typedef typename _Ht::pointer pointer;
321       typedef typename _Ht::const_pointer const_pointer;
322       typedef typename _Ht::reference reference;
323       typedef typename _Ht::const_reference const_reference;
324       
325       typedef typename _Ht::iterator iterator;
326       typedef typename _Ht::const_iterator const_iterator;
327       
328       typedef typename _Ht::allocator_type allocator_type;
329       
330       hasher
331       hash_funct() const
332       { return _M_ht.hash_funct(); }
333
334       key_equal
335       key_eq() const
336       { return _M_ht.key_eq(); }
337
338       allocator_type
339       get_allocator() const
340       { return _M_ht.get_allocator(); }
341
342       hash_multimap()
343       : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
344
345       explicit
346       hash_multimap(size_type __n)
347       : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
348
349       hash_multimap(size_type __n, const hasher& __hf)
350       : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
351
352       hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
353                     const allocator_type& __a = allocator_type())
354       : _M_ht(__n, __hf, __eql, __a) {}
355
356       template<class _InputIterator>
357         hash_multimap(_InputIterator __f, _InputIterator __l)
358         : _M_ht(100, hasher(), key_equal(), allocator_type())
359         { _M_ht.insert_equal(__f, __l); }
360
361       template<class _InputIterator>
362         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
363         : _M_ht(__n, hasher(), key_equal(), allocator_type())
364         { _M_ht.insert_equal(__f, __l); }
365
366       template<class _InputIterator>
367         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
368                       const hasher& __hf)
369         : _M_ht(__n, __hf, key_equal(), allocator_type())
370         { _M_ht.insert_equal(__f, __l); }
371
372       template<class _InputIterator>
373         hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
374                       const hasher& __hf, const key_equal& __eql,
375                       const allocator_type& __a = allocator_type())
376         : _M_ht(__n, __hf, __eql, __a)
377         { _M_ht.insert_equal(__f, __l); }
378
379       size_type
380       size() const
381       { return _M_ht.size(); }
382
383       size_type
384       max_size() const
385       { return _M_ht.max_size(); }
386
387       bool
388       empty() const
389       { return _M_ht.empty(); }
390
391       void
392       swap(hash_multimap& __hs)
393       { _M_ht.swap(__hs._M_ht); }
394
395       template<class _K1, class _T1, class _HF, class _EqK, class _Al>
396         friend bool
397         operator==(const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
398                    const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
399
400       iterator
401       begin()
402       { return _M_ht.begin(); }
403
404       iterator
405       end()
406       { return _M_ht.end(); }
407
408       const_iterator
409       begin() const
410       { return _M_ht.begin(); }
411
412       const_iterator
413       end() const
414       { return _M_ht.end(); }
415
416       iterator
417       insert(const value_type& __obj)
418       { return _M_ht.insert_equal(__obj); }
419
420       template<class _InputIterator>
421         void
422         insert(_InputIterator __f, _InputIterator __l)
423         { _M_ht.insert_equal(__f,__l); }
424
425       iterator
426       insert_noresize(const value_type& __obj)
427       { return _M_ht.insert_equal_noresize(__obj); }
428
429       iterator
430       find(const key_type& __key)
431       { return _M_ht.find(__key); }
432
433       const_iterator
434       find(const key_type& __key) const
435       { return _M_ht.find(__key); }
436
437       size_type
438       count(const key_type& __key) const
439       { return _M_ht.count(__key); }
440
441       pair<iterator, iterator>
442       equal_range(const key_type& __key)
443       { return _M_ht.equal_range(__key); }
444
445       pair<const_iterator, const_iterator>
446       equal_range(const key_type& __key) const
447       { return _M_ht.equal_range(__key); }
448
449       size_type
450       erase(const key_type& __key)
451       { return _M_ht.erase(__key); }
452
453       void
454       erase(iterator __it)
455       { _M_ht.erase(__it); }
456
457       void
458       erase(iterator __f, iterator __l)
459       { _M_ht.erase(__f, __l); }
460
461       void
462       clear()
463       { _M_ht.clear(); }
464
465       void
466       resize(size_type __hint)
467       { _M_ht.resize(__hint); }
468
469       size_type
470       bucket_count() const
471       { return _M_ht.bucket_count(); }
472
473       size_type
474       max_bucket_count() const
475       { return _M_ht.max_bucket_count(); }
476       
477       size_type
478       elems_in_bucket(size_type __n) const
479       { return _M_ht.elems_in_bucket(__n); }
480     };
481
482   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
483     inline bool
484     operator==(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
485                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
486     { return __hm1._M_ht == __hm2._M_ht; }
487
488   template<class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
489     inline bool
490     operator!=(const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm1,
491                const hash_multimap<_Key, _Tp, _HF, _EqKey, _Alloc>& __hm2)
492     { return !(__hm1 == __hm2); }
493
494   template<class _Key, class _Tp, class _HashFn, class _EqlKey, class _Alloc>
495     inline void
496     swap(hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm1,
497          hash_multimap<_Key, _Tp, _HashFn, _EqlKey, _Alloc>& __hm2)
498     { __hm1.swap(__hm2); }
499
500 _GLIBCXX_END_NESTED_NAMESPACE
501
502 #ifdef _GLIBCXX_DEBUG
503 # include <debug/hash_map>
504 #endif
505
506 _GLIBCXX_BEGIN_NAMESPACE(std)
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
597
598 #endif