]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Hashing map implementation -*- C++ -*- |
2 | ||
ffe94f83 | 3 | // Copyright (C) 2001, 2002 Free Software Foundation, Inc. |
42526146 PE |
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 | ||
725dc051 BK |
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 | ||
ffe94f83 PE |
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. | |
725dc051 BK |
60 | */ |
61 | ||
b2acb86f BK |
62 | #ifndef _HASH_MAP |
63 | #define _HASH_MAP 1 | |
725dc051 | 64 | |
b2acb86f | 65 | #include <ext/hashtable.h> |
30a20a1e | 66 | #include <bits/concept_check.h> |
725dc051 | 67 | |
e538847e | 68 | namespace __gnu_cxx |
d53d7f6e | 69 | { |
b2acb86f BK |
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>&); | |
fc7f0a80 PE |
84 | /** |
85 | * This is an SGI extension. | |
86 | * @ingroup SGIextensions | |
87 | * @doctodo | |
88 | */ | |
725dc051 BK |
89 | template <class _Key, class _Tp, class _HashFcn, class _EqualKey, |
90 | class _Alloc> | |
91 | class hash_map | |
92 | { | |
93 | private: | |
94 | typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn, | |
95 | _Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht; | |
96 | _Ht _M_ht; | |
97 | ||
98 | public: | |
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 | ||
122 | public: | |
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 | ||
725dc051 BK |
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 | ||
725dc051 BK |
152 | public: |
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 | ||
725dc051 BK |
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>&); | |
725dc051 | 161 | |
725dc051 BK |
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 | ||
167 | public: | |
168 | pair<iterator,bool> insert(const value_type& __obj) | |
169 | { return _M_ht.insert_unique(__obj); } | |
725dc051 BK |
170 | template <class _InputIterator> |
171 | void insert(_InputIterator __f, _InputIterator __l) | |
172 | { _M_ht.insert_unique(__f,__l); } | |
725dc051 BK |
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 | ||
204 | template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> | |
205 | inline bool | |
206 | operator==(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 | ||
725dc051 BK |
212 | template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> |
213 | inline bool | |
214 | operator!=(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 | ||
219 | template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> | |
220 | inline void | |
221 | swap(hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, | |
222 | hash_map<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) | |
223 | { | |
224 | __hm1.swap(__hm2); | |
225 | } | |
226 | ||
725dc051 BK |
227 | // Forward declaration of equality operator; needed for friend declaration. |
228 | ||
229 | template <class _Key, class _Tp, | |
230 | class _HashFcn = hash<_Key>, | |
231 | class _EqualKey = equal_to<_Key>, | |
232 | class _Alloc = allocator<_Tp> > | |
233 | class hash_multimap; | |
234 | ||
235 | template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> | |
236 | inline bool | |
237 | operator==(const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm1, | |
238 | const hash_multimap<_Key,_Tp,_HF,_EqKey,_Alloc>& __hm2); | |
239 | ||
fc7f0a80 PE |
240 | /** |
241 | * This is an SGI extension. | |
242 | * @ingroup SGIextensions | |
243 | * @doctodo | |
244 | */ | |
725dc051 BK |
245 | template <class _Key, class _Tp, class _HashFcn, class _EqualKey, class _Alloc> |
246 | class hash_multimap | |
247 | { | |
30a20a1e | 248 | // concept requirements |
4d16bdbb PE |
249 | __glibcpp_class_requires(_Key, _SGIAssignableConcept) |
250 | __glibcpp_class_requires(_Tp, _SGIAssignableConcept) | |
62bb0c97 PE |
251 | __glibcpp_class_requires3(_HashFcn, size_t, _Key, _UnaryFunctionConcept); |
252 | __glibcpp_class_requires3(_EqualKey, _Key, _Key, _BinaryPredicateConcept); | |
725dc051 BK |
253 | |
254 | private: | |
255 | typedef hashtable<pair<const _Key, _Tp>, _Key, _HashFcn, | |
256 | _Select1st<pair<const _Key, _Tp> >, _EqualKey, _Alloc> | |
257 | _Ht; | |
258 | _Ht _M_ht; | |
259 | ||
260 | public: | |
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 | ||
284 | public: | |
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 | ||
725dc051 BK |
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 | ||
725dc051 BK |
314 | public: |
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 | ||
725dc051 BK |
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>&); | |
725dc051 BK |
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 | ||
329 | public: | |
330 | iterator insert(const value_type& __obj) | |
331 | { return _M_ht.insert_equal(__obj); } | |
725dc051 BK |
332 | template <class _InputIterator> |
333 | void insert(_InputIterator __f, _InputIterator __l) | |
334 | { _M_ht.insert_equal(__f,__l); } | |
725dc051 BK |
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 | ||
355 | public: | |
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 | ||
363 | template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> | |
364 | inline bool | |
365 | operator==(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 | ||
725dc051 BK |
371 | template <class _Key, class _Tp, class _HF, class _EqKey, class _Alloc> |
372 | inline bool | |
373 | operator!=(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 | ||
378 | template <class _Key, class _Tp, class _HashFcn, class _EqlKey, class _Alloc> | |
379 | inline void | |
380 | swap(hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm1, | |
381 | hash_multimap<_Key,_Tp,_HashFcn,_EqlKey,_Alloc>& __hm2) | |
382 | { | |
383 | __hm1.swap(__hm2); | |
384 | } | |
385 | ||
e538847e | 386 | } // namespace __gnu_cxx |
725dc051 | 387 | |
e538847e PC |
388 | namespace std |
389 | { | |
725dc051 BK |
390 | // Specialization of insert_iterator so that it will work for hash_map |
391 | // and hash_multimap. | |
392 | ||
725dc051 | 393 | template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> |
e538847e | 394 | class insert_iterator<__gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { |
725dc051 | 395 | protected: |
e538847e | 396 | typedef __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
725dc051 BK |
397 | _Container* container; |
398 | public: | |
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 | ||
419 | template <class _Key, class _Tp, class _HashFn, class _EqKey, class _Alloc> | |
e538847e | 420 | class insert_iterator<__gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> > { |
725dc051 | 421 | protected: |
e538847e | 422 | typedef __gnu_cxx::hash_multimap<_Key, _Tp, _HashFn, _EqKey, _Alloc> _Container; |
725dc051 BK |
423 | _Container* container; |
424 | typename _Container::iterator iter; | |
425 | public: | |
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 | }; | |
d53d7f6e | 445 | } // namespace std |
725dc051 | 446 | |
b2acb86f | 447 | #endif |