OSDN Git Service

183bff556f4ae65a630726db29d5dddc31c00a42
[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     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