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