Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / libstdc++-v3 / include / ext / hash_map
CommitLineData
003757ed
MD
1// Hashing map implementation -*- C++ -*-
2
3// Copyright (C) 2001, 2002 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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). You should only
59 * include this header if you are using GCC 3 or later.
60 */
61
62#ifndef _HASH_MAP
63#define _HASH_MAP 1
64
65#include <ext/hashtable.h>
66#include <bits/concept_check.h>
67
68namespace __gnu_cxx
69{
70 using std::equal_to;
71 using std::allocator;
72 using std::pair;
73 using std::_Select1st;
74
75 // Forward declaration of equality operator; needed for friend
76 // declaration.
77 template<class _Key, class _Tp, class _HashFcn = hash<_Key>,
78 class _EqualKey = equal_to<_Key>, class _Alloc = allocator<_Tp> >
79 class hash_map;
80
81 template<class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
82 inline bool operator==(const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&,
83 const hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc>&);
84/**
85 * This is an SGI extension.
86 * @ingroup SGIextensions
87 * @doctodo
88*/
89template <class _Key, class _Tp, class _HashFcn, class _EqualKey,
90 class _Alloc>
91class hash_map
92{
93private:
94 typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
95 _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
96 _Ht _M_ht;
97
98public:
99 typedef typename _Ht::key_type key_type;
100 typedef _Tp data_type;
101 typedef _Tp mapped_type;
102 typedef typename _Ht::value_type value_type;
103 typedef typename _Ht::hasher hasher;
104 typedef typename _Ht::key_equal key_equal;
105
106 typedef typename _Ht::size_type size_type;
107 typedef typename _Ht::difference_type difference_type;
108 typedef typename _Ht::pointer pointer;
109 typedef typename _Ht::const_pointer const_pointer;
110 typedef typename _Ht::reference reference;
111 typedef typename _Ht::const_reference const_reference;
112
113 typedef typename _Ht::iterator iterator;
114 typedef typename _Ht::const_iterator const_iterator;
115
116 typedef typename _Ht::allocator_type allocator_type;
117
118 hasher hash_funct() const { return _M_ht.hash_funct(); }
119 key_equal key_eq() const { return _M_ht.key_eq(); }
120 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
121
122public:
123 hash_map() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
124 explicit hash_map(size_type __n)
125 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
126 hash_map(size_type __n, const hasher& __hf)
127 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
128 hash_map(size_type __n, const hasher& __hf, const key_equal& __eql,
129 const allocator_type& __a = allocator_type())
130 : _M_ht(__n, __hf, __eql, __a) {}
131
132 template <class _InputIterator>
133 hash_map(_InputIterator __f, _InputIterator __l)
134 : _M_ht(100, hasher(), key_equal(), allocator_type())
135 { _M_ht.insert_unique(__f, __l); }
136 template <class _InputIterator>
137 hash_map(_InputIterator __f, _InputIterator __l, size_type __n)
138 : _M_ht(__n, hasher(), key_equal(), allocator_type())
139 { _M_ht.insert_unique(__f, __l); }
140 template <class _InputIterator>
141 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
142 const hasher& __hf)
143 : _M_ht(__n, __hf, key_equal(), allocator_type())
144 { _M_ht.insert_unique(__f, __l); }
145 template <class _InputIterator>
146 hash_map(_InputIterator __f, _InputIterator __l, size_type __n,
147 const hasher& __hf, const key_equal& __eql,
148 const allocator_type& __a = allocator_type())
149 : _M_ht(__n, __hf, __eql, __a)
150 { _M_ht.insert_unique(__f, __l); }
151
152public:
153 size_type size() const { return _M_ht.size(); }
154 size_type max_size() const { return _M_ht.max_size(); }
155 bool empty() const { return _M_ht.empty(); }
156 void swap(hash_map& __hs) { _M_ht.swap(__hs._M_ht); }
157
158 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
159 friend bool operator== (const hash_map<_K1, _T1, _HF, _EqK, _Al>&,
160 const hash_map<_K1, _T1, _HF, _EqK, _Al>&);
161
162 iterator begin() { return _M_ht.begin(); }
163 iterator end() { return _M_ht.end(); }
164 const_iterator begin() const { return _M_ht.begin(); }
165 const_iterator end() const { return _M_ht.end(); }
166
167public:
168 pair<iterator,bool> insert(const value_type& __obj)
169 { return _M_ht.insert_unique(__obj); }
170 template <class _InputIterator>
171 void insert(_InputIterator __f, _InputIterator __l)
172 { _M_ht.insert_unique(__f,__l); }
173 pair<iterator,bool> insert_noresize(const value_type& __obj)
174 { return _M_ht.insert_unique_noresize(__obj); }
175
176 iterator find(const key_type& __key) { return _M_ht.find(__key); }
177 const_iterator find(const key_type& __key) const
178 { return _M_ht.find(__key); }
179
180 _Tp& operator[](const key_type& __key) {
181 return _M_ht.find_or_insert(value_type(__key, _Tp())).second;
182 }
183
184 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
185
186 pair<iterator, iterator> equal_range(const key_type& __key)
187 { return _M_ht.equal_range(__key); }
188 pair<const_iterator, const_iterator>
189 equal_range(const key_type& __key) const
190 { return _M_ht.equal_range(__key); }
191
192 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
193 void erase(iterator __it) { _M_ht.erase(__it); }
194 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
195 void clear() { _M_ht.clear(); }
196
197 void resize(size_type __hint) { _M_ht.resize(__hint); }
198 size_type bucket_count() const { return _M_ht.bucket_count(); }
199 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
200 size_type elems_in_bucket(size_type __n) const
201 { return _M_ht.elems_in_bucket(__n); }
202};
203
204template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
205inline bool
206operator==(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
207 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
208{
209 return __hm1._M_ht == __hm2._M_ht;
210}
211
212template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
213inline bool
214operator!=(const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
215 const hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) {
216 return !(__hm1 == __hm2);
217}
218
219template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
220inline void
221swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
222 hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
223{
224 __hm1.swap(__hm2);
225}
226
227// Forward declaration of equality operator; needed for friend declaration.
228
229template <class _Key, class _Tp,
230 class _HashFcn = hash<_Key>,
231 class _EqualKey = equal_to<_Key>,
232 class _Alloc = allocator<_Tp> >
233class hash_multimap;
234
235template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
236inline bool
237operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
238 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2);
239
240/**
241 * This is an SGI extension.
242 * @ingroup SGIextensions
243 * @doctodo
244*/
245template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc>
246class hash_multimap
247{
248 // concept requirements
249 __glibcxx_class_requires(_Key, _SGIAssignableConcept)
250 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
251 __glibcxx_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept)
252 __glibcxx_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept)
253
254private:
255 typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn,
256 _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc>
257 _Ht;
258 _Ht _M_ht;
259
260public:
261 typedef typename _Ht::key_type key_type;
262 typedef _Tp data_type;
263 typedef _Tp mapped_type;
264 typedef typename _Ht::value_type value_type;
265 typedef typename _Ht::hasher hasher;
266 typedef typename _Ht::key_equal key_equal;
267
268 typedef typename _Ht::size_type size_type;
269 typedef typename _Ht::difference_type difference_type;
270 typedef typename _Ht::pointer pointer;
271 typedef typename _Ht::const_pointer const_pointer;
272 typedef typename _Ht::reference reference;
273 typedef typename _Ht::const_reference const_reference;
274
275 typedef typename _Ht::iterator iterator;
276 typedef typename _Ht::const_iterator const_iterator;
277
278 typedef typename _Ht::allocator_type allocator_type;
279
280 hasher hash_funct() const { return _M_ht.hash_funct(); }
281 key_equal key_eq() const { return _M_ht.key_eq(); }
282 allocator_type get_allocator() const { return _M_ht.get_allocator(); }
283
284public:
285 hash_multimap() : _M_ht(100, hasher(), key_equal(), allocator_type()) {}
286 explicit hash_multimap(size_type __n)
287 : _M_ht(__n, hasher(), key_equal(), allocator_type()) {}
288 hash_multimap(size_type __n, const hasher& __hf)
289 : _M_ht(__n, __hf, key_equal(), allocator_type()) {}
290 hash_multimap(size_type __n, const hasher& __hf, const key_equal& __eql,
291 const allocator_type& __a = allocator_type())
292 : _M_ht(__n, __hf, __eql, __a) {}
293
294 template <class _InputIterator>
295 hash_multimap(_InputIterator __f, _InputIterator __l)
296 : _M_ht(100, hasher(), key_equal(), allocator_type())
297 { _M_ht.insert_equal(__f, __l); }
298 template <class _InputIterator>
299 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n)
300 : _M_ht(__n, hasher(), key_equal(), allocator_type())
301 { _M_ht.insert_equal(__f, __l); }
302 template <class _InputIterator>
303 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
304 const hasher& __hf)
305 : _M_ht(__n, __hf, key_equal(), allocator_type())
306 { _M_ht.insert_equal(__f, __l); }
307 template <class _InputIterator>
308 hash_multimap(_InputIterator __f, _InputIterator __l, size_type __n,
309 const hasher& __hf, const key_equal& __eql,
310 const allocator_type& __a = allocator_type())
311 : _M_ht(__n, __hf, __eql, __a)
312 { _M_ht.insert_equal(__f, __l); }
313
314public:
315 size_type size() const { return _M_ht.size(); }
316 size_type max_size() const { return _M_ht.max_size(); }
317 bool empty() const { return _M_ht.empty(); }
318 void swap(hash_multimap& __hs) { _M_ht.swap(__hs._M_ht); }
319
320 template <class _K1, class _T1, class _HF, class _EqK, class _Al>
321 friend bool operator== (const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&,
322 const hash_multimap<_K1, _T1, _HF, _EqK, _Al>&);
323
324 iterator begin() { return _M_ht.begin(); }
325 iterator end() { return _M_ht.end(); }
326 const_iterator begin() const { return _M_ht.begin(); }
327 const_iterator end() const { return _M_ht.end(); }
328
329public:
330 iterator insert(const value_type& __obj)
331 { return _M_ht.insert_equal(__obj); }
332 template <class _InputIterator>
333 void insert(_InputIterator __f, _InputIterator __l)
334 { _M_ht.insert_equal(__f,__l); }
335 iterator insert_noresize(const value_type& __obj)
336 { return _M_ht.insert_equal_noresize(__obj); }
337
338 iterator find(const key_type& __key) { return _M_ht.find(__key); }
339 const_iterator find(const key_type& __key) const
340 { return _M_ht.find(__key); }
341
342 size_type count(const key_type& __key) const { return _M_ht.count(__key); }
343
344 pair<iterator, iterator> equal_range(const key_type& __key)
345 { return _M_ht.equal_range(__key); }
346 pair<const_iterator, const_iterator>
347 equal_range(const key_type& __key) const
348 { return _M_ht.equal_range(__key); }
349
350 size_type erase(const key_type& __key) {return _M_ht.erase(__key); }
351 void erase(iterator __it) { _M_ht.erase(__it); }
352 void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); }
353 void clear() { _M_ht.clear(); }
354
355public:
356 void resize(size_type __hint) { _M_ht.resize(__hint); }
357 size_type bucket_count() const { return _M_ht.bucket_count(); }
358 size_type max_bucket_count() const { return _M_ht.max_bucket_count(); }
359 size_type elems_in_bucket(size_type __n) const
360 { return _M_ht.elems_in_bucket(__n); }
361};
362
363template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
364inline bool
365operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
366 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2)
367{
368 return __hm1._M_ht == __hm2._M_ht;
369}
370
371template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc>
372inline bool
373operator!=(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1,
374 const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2) {
375 return !(__hm1 == __hm2);
376}
377
378template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc>
379inline void
380swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1,
381 hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2)
382{
383 __hm1.swap(__hm2);
384}
385
386} // namespace __gnu_cxx
387
388namespace std
389{
390// Specialization of insert_iterator so that it will work for hash_map
391// and hash_multimap.
392
393template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
394class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
395protected:
396 typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
397 _Container* container;
398public:
399 typedef _Container container_type;
400 typedef output_iterator_tag iterator_category;
401 typedef void value_type;
402 typedef void difference_type;
403 typedef void pointer;
404 typedef void reference;
405
406 insert_iterator(_Container& __x) : container(&__x) {}
407 insert_iterator(_Container& __x, typename _Container::iterator)
408 : container(&__x) {}
409 insert_iterator<_Container>&
410 operator=(const typename _Container::value_type& __value) {
411 container->insert(__value);
412 return *this;
413 }
414 insert_iterator<_Container>& operator*() { return *this; }
415 insert_iterator<_Container>& operator++() { return *this; }
416 insert_iterator<_Container>& operator++(int) { return *this; }
417};
418
419template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc>
420class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > {
421protected:
422 typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container;
423 _Container* container;
424 typename _Container::iterator iter;
425public:
426 typedef _Container container_type;
427 typedef output_iterator_tag iterator_category;
428 typedef void value_type;
429 typedef void difference_type;
430 typedef void pointer;
431 typedef void reference;
432
433 insert_iterator(_Container& __x) : container(&__x) {}
434 insert_iterator(_Container& __x, typename _Container::iterator)
435 : container(&__x) {}
436 insert_iterator<_Container>&
437 operator=(const typename _Container::value_type& __value) {
438 container->insert(__value);
439 return *this;
440 }
441 insert_iterator<_Container>& operator*() { return *this; }
442 insert_iterator<_Container>& operator++() { return *this; }
443 insert_iterator<_Container>& operator++(int) { return *this; }
444};
445} // namespace std
446
447#endif