]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Hashtable implementation used by containers -*- C++ -*- |
2 | ||
655d7821 | 3 | // Copyright (C) 2001, 2002, 2003 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,1997 | |
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 | ||
b2acb86f | 56 | /** @file ext/hashtable.h |
ffe94f83 PE |
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 _HASHTABLE_H |
63 | #define _HASHTABLE_H 1 | |
725dc051 BK |
64 | |
65 | // Hashtable class, used to implement the hashed associative containers | |
66 | // hash_set, hash_map, hash_multiset, and hash_multimap. | |
67 | ||
83144cfc PE |
68 | #include <vector> |
69 | #include <iterator> | |
725dc051 | 70 | #include <bits/stl_algo.h> |
725dc051 | 71 | #include <bits/stl_function.h> |
b2acb86f | 72 | #include <ext/hash_fun.h> |
725dc051 | 73 | |
e538847e | 74 | namespace __gnu_cxx |
d53d7f6e | 75 | { |
e538847e PC |
76 | using std::size_t; |
77 | using std::ptrdiff_t; | |
78 | using std::forward_iterator_tag; | |
79 | using std::input_iterator_tag; | |
80 | using std::_Alloc_traits; | |
81 | using std::_Construct; | |
82 | using std::_Destroy; | |
83 | using std::distance; | |
84 | using std::vector; | |
85 | using std::pair; | |
32c8d100 | 86 | using std::__iterator_category; |
725dc051 BK |
87 | |
88 | template <class _Val> | |
89 | struct _Hashtable_node | |
90 | { | |
91 | _Hashtable_node* _M_next; | |
92 | _Val _M_val; | |
93 | }; | |
94 | ||
95 | template <class _Val, class _Key, class _HashFcn, | |
e538847e | 96 | class _ExtractKey, class _EqualKey, class _Alloc = std::__alloc> |
725dc051 BK |
97 | class hashtable; |
98 | ||
99 | template <class _Val, class _Key, class _HashFcn, | |
100 | class _ExtractKey, class _EqualKey, class _Alloc> | |
101 | struct _Hashtable_iterator; | |
102 | ||
103 | template <class _Val, class _Key, class _HashFcn, | |
104 | class _ExtractKey, class _EqualKey, class _Alloc> | |
105 | struct _Hashtable_const_iterator; | |
106 | ||
107 | template <class _Val, class _Key, class _HashFcn, | |
108 | class _ExtractKey, class _EqualKey, class _Alloc> | |
109 | struct _Hashtable_iterator { | |
110 | typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> | |
111 | _Hashtable; | |
112 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, | |
113 | _ExtractKey, _EqualKey, _Alloc> | |
114 | iterator; | |
115 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, | |
116 | _ExtractKey, _EqualKey, _Alloc> | |
117 | const_iterator; | |
118 | typedef _Hashtable_node<_Val> _Node; | |
119 | ||
120 | typedef forward_iterator_tag iterator_category; | |
121 | typedef _Val value_type; | |
122 | typedef ptrdiff_t difference_type; | |
123 | typedef size_t size_type; | |
124 | typedef _Val& reference; | |
125 | typedef _Val* pointer; | |
126 | ||
127 | _Node* _M_cur; | |
128 | _Hashtable* _M_ht; | |
129 | ||
130 | _Hashtable_iterator(_Node* __n, _Hashtable* __tab) | |
131 | : _M_cur(__n), _M_ht(__tab) {} | |
132 | _Hashtable_iterator() {} | |
133 | reference operator*() const { return _M_cur->_M_val; } | |
725dc051 | 134 | pointer operator->() const { return &(operator*()); } |
725dc051 BK |
135 | iterator& operator++(); |
136 | iterator operator++(int); | |
137 | bool operator==(const iterator& __it) const | |
138 | { return _M_cur == __it._M_cur; } | |
139 | bool operator!=(const iterator& __it) const | |
140 | { return _M_cur != __it._M_cur; } | |
141 | }; | |
142 | ||
143 | ||
144 | template <class _Val, class _Key, class _HashFcn, | |
145 | class _ExtractKey, class _EqualKey, class _Alloc> | |
146 | struct _Hashtable_const_iterator { | |
147 | typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> | |
148 | _Hashtable; | |
149 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn, | |
150 | _ExtractKey,_EqualKey,_Alloc> | |
151 | iterator; | |
152 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, | |
153 | _ExtractKey, _EqualKey, _Alloc> | |
154 | const_iterator; | |
155 | typedef _Hashtable_node<_Val> _Node; | |
156 | ||
157 | typedef forward_iterator_tag iterator_category; | |
158 | typedef _Val value_type; | |
159 | typedef ptrdiff_t difference_type; | |
160 | typedef size_t size_type; | |
161 | typedef const _Val& reference; | |
162 | typedef const _Val* pointer; | |
163 | ||
164 | const _Node* _M_cur; | |
165 | const _Hashtable* _M_ht; | |
166 | ||
167 | _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) | |
168 | : _M_cur(__n), _M_ht(__tab) {} | |
169 | _Hashtable_const_iterator() {} | |
170 | _Hashtable_const_iterator(const iterator& __it) | |
171 | : _M_cur(__it._M_cur), _M_ht(__it._M_ht) {} | |
172 | reference operator*() const { return _M_cur->_M_val; } | |
725dc051 | 173 | pointer operator->() const { return &(operator*()); } |
725dc051 BK |
174 | const_iterator& operator++(); |
175 | const_iterator operator++(int); | |
176 | bool operator==(const const_iterator& __it) const | |
177 | { return _M_cur == __it._M_cur; } | |
178 | bool operator!=(const const_iterator& __it) const | |
179 | { return _M_cur != __it._M_cur; } | |
180 | }; | |
181 | ||
182 | // Note: assumes long is at least 32 bits. | |
655d7821 | 183 | enum { _S_num_primes = 28 }; |
725dc051 | 184 | |
655d7821 | 185 | static const unsigned long __stl_prime_list[_S_num_primes] = |
725dc051 BK |
186 | { |
187 | 53ul, 97ul, 193ul, 389ul, 769ul, | |
188 | 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, | |
189 | 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, | |
190 | 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, | |
191 | 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, | |
192 | 1610612741ul, 3221225473ul, 4294967291ul | |
193 | }; | |
194 | ||
195 | inline unsigned long __stl_next_prime(unsigned long __n) | |
196 | { | |
197 | const unsigned long* __first = __stl_prime_list; | |
655d7821 | 198 | const unsigned long* __last = __stl_prime_list + (int)_S_num_primes; |
e538847e | 199 | const unsigned long* pos = std::lower_bound(__first, __last, __n); |
725dc051 BK |
200 | return pos == __last ? *(__last - 1) : *pos; |
201 | } | |
202 | ||
203 | // Forward declaration of operator==. | |
204 | ||
205 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
206 | class hashtable; | |
207 | ||
208 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
209 | bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, | |
210 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2); | |
211 | ||
212 | ||
b2acb86f BK |
213 | // Hashtables handle allocators a bit differently than other |
214 | // containers do. If we're using standard-conforming allocators, then | |
215 | // a hashtable unconditionally has a member variable to hold its | |
216 | // allocator, even if it so happens that all instances of the | |
217 | // allocator type are identical. This is because, for hashtables, | |
218 | // this extra storage is negligible. Additionally, a base class | |
219 | // wouldn't serve any other purposes; it wouldn't, for example, | |
220 | // simplify the exception-handling code. | |
725dc051 BK |
221 | |
222 | template <class _Val, class _Key, class _HashFcn, | |
223 | class _ExtractKey, class _EqualKey, class _Alloc> | |
224 | class hashtable { | |
225 | public: | |
226 | typedef _Key key_type; | |
227 | typedef _Val value_type; | |
228 | typedef _HashFcn hasher; | |
229 | typedef _EqualKey key_equal; | |
230 | ||
231 | typedef size_t size_type; | |
232 | typedef ptrdiff_t difference_type; | |
233 | typedef value_type* pointer; | |
234 | typedef const value_type* const_pointer; | |
235 | typedef value_type& reference; | |
236 | typedef const value_type& const_reference; | |
237 | ||
238 | hasher hash_funct() const { return _M_hash; } | |
239 | key_equal key_eq() const { return _M_equals; } | |
240 | ||
241 | private: | |
242 | typedef _Hashtable_node<_Val> _Node; | |
243 | ||
725dc051 BK |
244 | public: |
245 | typedef typename _Alloc_traits<_Val,_Alloc>::allocator_type allocator_type; | |
246 | allocator_type get_allocator() const { return _M_node_allocator; } | |
247 | private: | |
248 | typename _Alloc_traits<_Node, _Alloc>::allocator_type _M_node_allocator; | |
249 | _Node* _M_get_node() { return _M_node_allocator.allocate(1); } | |
250 | void _M_put_node(_Node* __p) { _M_node_allocator.deallocate(__p, 1); } | |
725dc051 BK |
251 | |
252 | private: | |
253 | hasher _M_hash; | |
254 | key_equal _M_equals; | |
255 | _ExtractKey _M_get_key; | |
256 | vector<_Node*,_Alloc> _M_buckets; | |
257 | size_type _M_num_elements; | |
258 | ||
259 | public: | |
260 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc> | |
261 | iterator; | |
262 | typedef _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey, | |
263 | _Alloc> | |
264 | const_iterator; | |
265 | ||
266 | friend struct | |
267 | _Hashtable_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; | |
268 | friend struct | |
269 | _Hashtable_const_iterator<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>; | |
270 | ||
271 | public: | |
272 | hashtable(size_type __n, | |
273 | const _HashFcn& __hf, | |
274 | const _EqualKey& __eql, | |
275 | const _ExtractKey& __ext, | |
276 | const allocator_type& __a = allocator_type()) | |
d53d7f6e | 277 | : _M_node_allocator(__a), |
725dc051 BK |
278 | _M_hash(__hf), |
279 | _M_equals(__eql), | |
280 | _M_get_key(__ext), | |
281 | _M_buckets(__a), | |
282 | _M_num_elements(0) | |
283 | { | |
284 | _M_initialize_buckets(__n); | |
285 | } | |
286 | ||
287 | hashtable(size_type __n, | |
288 | const _HashFcn& __hf, | |
289 | const _EqualKey& __eql, | |
290 | const allocator_type& __a = allocator_type()) | |
d53d7f6e | 291 | : _M_node_allocator(__a), |
725dc051 BK |
292 | _M_hash(__hf), |
293 | _M_equals(__eql), | |
294 | _M_get_key(_ExtractKey()), | |
295 | _M_buckets(__a), | |
296 | _M_num_elements(0) | |
297 | { | |
298 | _M_initialize_buckets(__n); | |
299 | } | |
300 | ||
301 | hashtable(const hashtable& __ht) | |
d53d7f6e | 302 | : _M_node_allocator(__ht.get_allocator()), |
725dc051 BK |
303 | _M_hash(__ht._M_hash), |
304 | _M_equals(__ht._M_equals), | |
305 | _M_get_key(__ht._M_get_key), | |
306 | _M_buckets(__ht.get_allocator()), | |
307 | _M_num_elements(0) | |
308 | { | |
309 | _M_copy_from(__ht); | |
310 | } | |
311 | ||
725dc051 BK |
312 | hashtable& operator= (const hashtable& __ht) |
313 | { | |
314 | if (&__ht != this) { | |
315 | clear(); | |
316 | _M_hash = __ht._M_hash; | |
317 | _M_equals = __ht._M_equals; | |
318 | _M_get_key = __ht._M_get_key; | |
319 | _M_copy_from(__ht); | |
320 | } | |
321 | return *this; | |
322 | } | |
323 | ||
324 | ~hashtable() { clear(); } | |
325 | ||
326 | size_type size() const { return _M_num_elements; } | |
327 | size_type max_size() const { return size_type(-1); } | |
328 | bool empty() const { return size() == 0; } | |
329 | ||
330 | void swap(hashtable& __ht) | |
331 | { | |
d53d7f6e PE |
332 | std::swap(_M_hash, __ht._M_hash); |
333 | std::swap(_M_equals, __ht._M_equals); | |
334 | std::swap(_M_get_key, __ht._M_get_key); | |
725dc051 | 335 | _M_buckets.swap(__ht._M_buckets); |
d53d7f6e | 336 | std::swap(_M_num_elements, __ht._M_num_elements); |
725dc051 BK |
337 | } |
338 | ||
339 | iterator begin() | |
340 | { | |
341 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) | |
342 | if (_M_buckets[__n]) | |
343 | return iterator(_M_buckets[__n], this); | |
344 | return end(); | |
345 | } | |
346 | ||
347 | iterator end() { return iterator(0, this); } | |
348 | ||
349 | const_iterator begin() const | |
350 | { | |
351 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) | |
352 | if (_M_buckets[__n]) | |
353 | return const_iterator(_M_buckets[__n], this); | |
354 | return end(); | |
355 | } | |
356 | ||
357 | const_iterator end() const { return const_iterator(0, this); } | |
358 | ||
725dc051 BK |
359 | template <class _Vl, class _Ky, class _HF, class _Ex, class _Eq, class _Al> |
360 | friend bool operator== (const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, | |
361 | const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); | |
725dc051 BK |
362 | public: |
363 | ||
364 | size_type bucket_count() const { return _M_buckets.size(); } | |
365 | ||
366 | size_type max_bucket_count() const | |
655d7821 | 367 | { return __stl_prime_list[(int)_S_num_primes - 1]; } |
725dc051 BK |
368 | |
369 | size_type elems_in_bucket(size_type __bucket) const | |
370 | { | |
371 | size_type __result = 0; | |
372 | for (_Node* __cur = _M_buckets[__bucket]; __cur; __cur = __cur->_M_next) | |
373 | __result += 1; | |
374 | return __result; | |
375 | } | |
376 | ||
377 | pair<iterator, bool> insert_unique(const value_type& __obj) | |
378 | { | |
379 | resize(_M_num_elements + 1); | |
380 | return insert_unique_noresize(__obj); | |
381 | } | |
382 | ||
383 | iterator insert_equal(const value_type& __obj) | |
384 | { | |
385 | resize(_M_num_elements + 1); | |
386 | return insert_equal_noresize(__obj); | |
387 | } | |
388 | ||
389 | pair<iterator, bool> insert_unique_noresize(const value_type& __obj); | |
390 | iterator insert_equal_noresize(const value_type& __obj); | |
391 | ||
725dc051 BK |
392 | template <class _InputIterator> |
393 | void insert_unique(_InputIterator __f, _InputIterator __l) | |
394 | { | |
30a20a1e | 395 | insert_unique(__f, __l, __iterator_category(__f)); |
725dc051 BK |
396 | } |
397 | ||
398 | template <class _InputIterator> | |
399 | void insert_equal(_InputIterator __f, _InputIterator __l) | |
400 | { | |
30a20a1e | 401 | insert_equal(__f, __l, __iterator_category(__f)); |
725dc051 BK |
402 | } |
403 | ||
404 | template <class _InputIterator> | |
405 | void insert_unique(_InputIterator __f, _InputIterator __l, | |
406 | input_iterator_tag) | |
407 | { | |
408 | for ( ; __f != __l; ++__f) | |
409 | insert_unique(*__f); | |
410 | } | |
411 | ||
412 | template <class _InputIterator> | |
413 | void insert_equal(_InputIterator __f, _InputIterator __l, | |
414 | input_iterator_tag) | |
415 | { | |
416 | for ( ; __f != __l; ++__f) | |
417 | insert_equal(*__f); | |
418 | } | |
419 | ||
420 | template <class _ForwardIterator> | |
421 | void insert_unique(_ForwardIterator __f, _ForwardIterator __l, | |
422 | forward_iterator_tag) | |
423 | { | |
3d90ff93 | 424 | size_type __n = distance(__f, __l); |
725dc051 BK |
425 | resize(_M_num_elements + __n); |
426 | for ( ; __n > 0; --__n, ++__f) | |
427 | insert_unique_noresize(*__f); | |
428 | } | |
429 | ||
430 | template <class _ForwardIterator> | |
431 | void insert_equal(_ForwardIterator __f, _ForwardIterator __l, | |
432 | forward_iterator_tag) | |
433 | { | |
3d90ff93 | 434 | size_type __n = distance(__f, __l); |
725dc051 BK |
435 | resize(_M_num_elements + __n); |
436 | for ( ; __n > 0; --__n, ++__f) | |
437 | insert_equal_noresize(*__f); | |
438 | } | |
439 | ||
725dc051 BK |
440 | reference find_or_insert(const value_type& __obj); |
441 | ||
442 | iterator find(const key_type& __key) | |
443 | { | |
444 | size_type __n = _M_bkt_num_key(__key); | |
445 | _Node* __first; | |
446 | for ( __first = _M_buckets[__n]; | |
447 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); | |
448 | __first = __first->_M_next) | |
449 | {} | |
450 | return iterator(__first, this); | |
451 | } | |
452 | ||
453 | const_iterator find(const key_type& __key) const | |
454 | { | |
455 | size_type __n = _M_bkt_num_key(__key); | |
456 | const _Node* __first; | |
457 | for ( __first = _M_buckets[__n]; | |
458 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); | |
459 | __first = __first->_M_next) | |
460 | {} | |
461 | return const_iterator(__first, this); | |
462 | } | |
463 | ||
464 | size_type count(const key_type& __key) const | |
465 | { | |
466 | const size_type __n = _M_bkt_num_key(__key); | |
467 | size_type __result = 0; | |
468 | ||
469 | for (const _Node* __cur = _M_buckets[__n]; __cur; __cur = __cur->_M_next) | |
470 | if (_M_equals(_M_get_key(__cur->_M_val), __key)) | |
471 | ++__result; | |
472 | return __result; | |
473 | } | |
474 | ||
475 | pair<iterator, iterator> | |
476 | equal_range(const key_type& __key); | |
477 | ||
478 | pair<const_iterator, const_iterator> | |
479 | equal_range(const key_type& __key) const; | |
480 | ||
481 | size_type erase(const key_type& __key); | |
482 | void erase(const iterator& __it); | |
483 | void erase(iterator __first, iterator __last); | |
484 | ||
485 | void erase(const const_iterator& __it); | |
486 | void erase(const_iterator __first, const_iterator __last); | |
487 | ||
488 | void resize(size_type __num_elements_hint); | |
489 | void clear(); | |
490 | ||
491 | private: | |
492 | size_type _M_next_size(size_type __n) const | |
493 | { return __stl_next_prime(__n); } | |
494 | ||
495 | void _M_initialize_buckets(size_type __n) | |
496 | { | |
497 | const size_type __n_buckets = _M_next_size(__n); | |
498 | _M_buckets.reserve(__n_buckets); | |
499 | _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); | |
500 | _M_num_elements = 0; | |
501 | } | |
502 | ||
503 | size_type _M_bkt_num_key(const key_type& __key) const | |
504 | { | |
505 | return _M_bkt_num_key(__key, _M_buckets.size()); | |
506 | } | |
507 | ||
508 | size_type _M_bkt_num(const value_type& __obj) const | |
509 | { | |
510 | return _M_bkt_num_key(_M_get_key(__obj)); | |
511 | } | |
512 | ||
513 | size_type _M_bkt_num_key(const key_type& __key, size_t __n) const | |
514 | { | |
515 | return _M_hash(__key) % __n; | |
516 | } | |
517 | ||
518 | size_type _M_bkt_num(const value_type& __obj, size_t __n) const | |
519 | { | |
520 | return _M_bkt_num_key(_M_get_key(__obj), __n); | |
521 | } | |
522 | ||
523 | _Node* _M_new_node(const value_type& __obj) | |
524 | { | |
525 | _Node* __n = _M_get_node(); | |
526 | __n->_M_next = 0; | |
322821b9 | 527 | try { |
98aff0b5 | 528 | _Construct(&__n->_M_val, __obj); |
725dc051 BK |
529 | return __n; |
530 | } | |
322821b9 BK |
531 | catch(...) |
532 | { | |
533 | _M_put_node(__n); | |
534 | __throw_exception_again; | |
535 | } | |
725dc051 BK |
536 | } |
537 | ||
538 | void _M_delete_node(_Node* __n) | |
539 | { | |
98aff0b5 | 540 | _Destroy(&__n->_M_val); |
725dc051 BK |
541 | _M_put_node(__n); |
542 | } | |
543 | ||
544 | void _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); | |
545 | void _M_erase_bucket(const size_type __n, _Node* __last); | |
546 | ||
547 | void _M_copy_from(const hashtable& __ht); | |
548 | ||
549 | }; | |
550 | ||
551 | template <class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
552 | class _All> | |
553 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& | |
554 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() | |
555 | { | |
556 | const _Node* __old = _M_cur; | |
557 | _M_cur = _M_cur->_M_next; | |
558 | if (!_M_cur) { | |
559 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); | |
560 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) | |
561 | _M_cur = _M_ht->_M_buckets[__bucket]; | |
562 | } | |
563 | return *this; | |
564 | } | |
565 | ||
566 | template <class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
567 | class _All> | |
568 | inline _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> | |
569 | _Hashtable_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) | |
570 | { | |
571 | iterator __tmp = *this; | |
572 | ++*this; | |
573 | return __tmp; | |
574 | } | |
575 | ||
576 | template <class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
577 | class _All> | |
578 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>& | |
579 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++() | |
580 | { | |
581 | const _Node* __old = _M_cur; | |
582 | _M_cur = _M_cur->_M_next; | |
583 | if (!_M_cur) { | |
584 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); | |
585 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) | |
586 | _M_cur = _M_ht->_M_buckets[__bucket]; | |
587 | } | |
588 | return *this; | |
589 | } | |
590 | ||
591 | template <class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
592 | class _All> | |
593 | inline _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All> | |
594 | _Hashtable_const_iterator<_Val,_Key,_HF,_ExK,_EqK,_All>::operator++(int) | |
595 | { | |
596 | const_iterator __tmp = *this; | |
597 | ++*this; | |
598 | return __tmp; | |
599 | } | |
600 | ||
725dc051 BK |
601 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
602 | bool operator==(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, | |
603 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) | |
604 | { | |
605 | typedef typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::_Node _Node; | |
606 | if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) | |
607 | return false; | |
8f999578 | 608 | for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) { |
725dc051 BK |
609 | _Node* __cur1 = __ht1._M_buckets[__n]; |
610 | _Node* __cur2 = __ht2._M_buckets[__n]; | |
ec4d88f9 SW |
611 | // Check same length of lists |
612 | for ( ; __cur1 && __cur2; | |
725dc051 BK |
613 | __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) |
614 | {} | |
615 | if (__cur1 || __cur2) | |
616 | return false; | |
ec4d88f9 SW |
617 | // Now check one's elements are in the other |
618 | for (__cur1 = __ht1._M_buckets[__n] ; __cur1; __cur1 = __cur1->_M_next) | |
619 | { | |
620 | bool _found__cur1 = false; | |
621 | for (_Node* __cur2 = __ht2._M_buckets[__n]; | |
622 | __cur2; __cur2 = __cur2->_M_next) | |
623 | { | |
624 | if (__cur1->_M_val == __cur2->_M_val) | |
625 | { | |
626 | _found__cur1 = true; | |
627 | break; | |
628 | } | |
629 | } | |
630 | if (!_found__cur1) | |
631 | return false; | |
632 | } | |
725dc051 BK |
633 | } |
634 | return true; | |
635 | } | |
636 | ||
725dc051 BK |
637 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> |
638 | inline bool operator!=(const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht1, | |
639 | const hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>& __ht2) { | |
640 | return !(__ht1 == __ht2); | |
641 | } | |
642 | ||
643 | template <class _Val, class _Key, class _HF, class _Extract, class _EqKey, | |
644 | class _All> | |
645 | inline void swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, | |
646 | hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) { | |
647 | __ht1.swap(__ht2); | |
648 | } | |
649 | ||
725dc051 BK |
650 | |
651 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
652 | pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool> | |
653 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
654 | ::insert_unique_noresize(const value_type& __obj) | |
655 | { | |
656 | const size_type __n = _M_bkt_num(__obj); | |
657 | _Node* __first = _M_buckets[__n]; | |
658 | ||
659 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
660 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) | |
661 | return pair<iterator, bool>(iterator(__cur, this), false); | |
662 | ||
663 | _Node* __tmp = _M_new_node(__obj); | |
664 | __tmp->_M_next = __first; | |
665 | _M_buckets[__n] = __tmp; | |
666 | ++_M_num_elements; | |
667 | return pair<iterator, bool>(iterator(__tmp, this), true); | |
668 | } | |
669 | ||
670 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
671 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator | |
672 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
673 | ::insert_equal_noresize(const value_type& __obj) | |
674 | { | |
675 | const size_type __n = _M_bkt_num(__obj); | |
676 | _Node* __first = _M_buckets[__n]; | |
677 | ||
678 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
679 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) { | |
680 | _Node* __tmp = _M_new_node(__obj); | |
681 | __tmp->_M_next = __cur->_M_next; | |
682 | __cur->_M_next = __tmp; | |
683 | ++_M_num_elements; | |
684 | return iterator(__tmp, this); | |
685 | } | |
686 | ||
687 | _Node* __tmp = _M_new_node(__obj); | |
688 | __tmp->_M_next = __first; | |
689 | _M_buckets[__n] = __tmp; | |
690 | ++_M_num_elements; | |
691 | return iterator(__tmp, this); | |
692 | } | |
693 | ||
694 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
695 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::reference | |
696 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::find_or_insert(const value_type& __obj) | |
697 | { | |
698 | resize(_M_num_elements + 1); | |
699 | ||
700 | size_type __n = _M_bkt_num(__obj); | |
701 | _Node* __first = _M_buckets[__n]; | |
702 | ||
703 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
704 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) | |
705 | return __cur->_M_val; | |
706 | ||
707 | _Node* __tmp = _M_new_node(__obj); | |
708 | __tmp->_M_next = __first; | |
709 | _M_buckets[__n] = __tmp; | |
710 | ++_M_num_elements; | |
711 | return __tmp->_M_val; | |
712 | } | |
713 | ||
714 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
715 | pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, | |
716 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator> | |
717 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::equal_range(const key_type& __key) | |
718 | { | |
719 | typedef pair<iterator, iterator> _Pii; | |
720 | const size_type __n = _M_bkt_num_key(__key); | |
721 | ||
722 | for (_Node* __first = _M_buckets[__n]; __first; __first = __first->_M_next) | |
723 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { | |
724 | for (_Node* __cur = __first->_M_next; __cur; __cur = __cur->_M_next) | |
725 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) | |
726 | return _Pii(iterator(__first, this), iterator(__cur, this)); | |
727 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) | |
728 | if (_M_buckets[__m]) | |
729 | return _Pii(iterator(__first, this), | |
730 | iterator(_M_buckets[__m], this)); | |
731 | return _Pii(iterator(__first, this), end()); | |
732 | } | |
733 | return _Pii(end(), end()); | |
734 | } | |
735 | ||
736 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
737 | pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator, | |
738 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::const_iterator> | |
739 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
740 | ::equal_range(const key_type& __key) const | |
741 | { | |
742 | typedef pair<const_iterator, const_iterator> _Pii; | |
743 | const size_type __n = _M_bkt_num_key(__key); | |
744 | ||
745 | for (const _Node* __first = _M_buckets[__n] ; | |
746 | __first; | |
747 | __first = __first->_M_next) { | |
748 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { | |
749 | for (const _Node* __cur = __first->_M_next; | |
750 | __cur; | |
751 | __cur = __cur->_M_next) | |
752 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) | |
753 | return _Pii(const_iterator(__first, this), | |
754 | const_iterator(__cur, this)); | |
755 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) | |
756 | if (_M_buckets[__m]) | |
757 | return _Pii(const_iterator(__first, this), | |
758 | const_iterator(_M_buckets[__m], this)); | |
759 | return _Pii(const_iterator(__first, this), end()); | |
760 | } | |
761 | } | |
762 | return _Pii(end(), end()); | |
763 | } | |
764 | ||
765 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
766 | typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type | |
767 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key) | |
768 | { | |
769 | const size_type __n = _M_bkt_num_key(__key); | |
770 | _Node* __first = _M_buckets[__n]; | |
771 | size_type __erased = 0; | |
772 | ||
773 | if (__first) { | |
774 | _Node* __cur = __first; | |
775 | _Node* __next = __cur->_M_next; | |
776 | while (__next) { | |
777 | if (_M_equals(_M_get_key(__next->_M_val), __key)) { | |
778 | __cur->_M_next = __next->_M_next; | |
779 | _M_delete_node(__next); | |
780 | __next = __cur->_M_next; | |
781 | ++__erased; | |
782 | --_M_num_elements; | |
783 | } | |
784 | else { | |
785 | __cur = __next; | |
786 | __next = __cur->_M_next; | |
787 | } | |
788 | } | |
789 | if (_M_equals(_M_get_key(__first->_M_val), __key)) { | |
790 | _M_buckets[__n] = __first->_M_next; | |
791 | _M_delete_node(__first); | |
792 | ++__erased; | |
793 | --_M_num_elements; | |
794 | } | |
795 | } | |
796 | return __erased; | |
797 | } | |
798 | ||
799 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
800 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const iterator& __it) | |
801 | { | |
802 | _Node* __p = __it._M_cur; | |
803 | if (__p) { | |
804 | const size_type __n = _M_bkt_num(__p->_M_val); | |
805 | _Node* __cur = _M_buckets[__n]; | |
806 | ||
807 | if (__cur == __p) { | |
808 | _M_buckets[__n] = __cur->_M_next; | |
809 | _M_delete_node(__cur); | |
810 | --_M_num_elements; | |
811 | } | |
812 | else { | |
813 | _Node* __next = __cur->_M_next; | |
814 | while (__next) { | |
815 | if (__next == __p) { | |
816 | __cur->_M_next = __next->_M_next; | |
817 | _M_delete_node(__next); | |
818 | --_M_num_elements; | |
819 | break; | |
820 | } | |
821 | else { | |
822 | __cur = __next; | |
823 | __next = __cur->_M_next; | |
824 | } | |
825 | } | |
826 | } | |
827 | } | |
828 | } | |
829 | ||
830 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
831 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
832 | ::erase(iterator __first, iterator __last) | |
833 | { | |
834 | size_type __f_bucket = __first._M_cur ? | |
835 | _M_bkt_num(__first._M_cur->_M_val) : _M_buckets.size(); | |
836 | size_type __l_bucket = __last._M_cur ? | |
837 | _M_bkt_num(__last._M_cur->_M_val) : _M_buckets.size(); | |
838 | ||
839 | if (__first._M_cur == __last._M_cur) | |
840 | return; | |
841 | else if (__f_bucket == __l_bucket) | |
842 | _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); | |
843 | else { | |
844 | _M_erase_bucket(__f_bucket, __first._M_cur, 0); | |
845 | for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) | |
846 | _M_erase_bucket(__n, 0); | |
847 | if (__l_bucket != _M_buckets.size()) | |
848 | _M_erase_bucket(__l_bucket, __last._M_cur); | |
849 | } | |
850 | } | |
851 | ||
852 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
853 | inline void | |
854 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const_iterator __first, | |
855 | const_iterator __last) | |
856 | { | |
857 | erase(iterator(const_cast<_Node*>(__first._M_cur), | |
858 | const_cast<hashtable*>(__first._M_ht)), | |
859 | iterator(const_cast<_Node*>(__last._M_cur), | |
860 | const_cast<hashtable*>(__last._M_ht))); | |
861 | } | |
862 | ||
863 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
864 | inline void | |
865 | hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const const_iterator& __it) | |
866 | { | |
867 | erase(iterator(const_cast<_Node*>(__it._M_cur), | |
868 | const_cast<hashtable*>(__it._M_ht))); | |
869 | } | |
870 | ||
871 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
872 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
873 | ::resize(size_type __num_elements_hint) | |
874 | { | |
875 | const size_type __old_n = _M_buckets.size(); | |
876 | if (__num_elements_hint > __old_n) { | |
877 | const size_type __n = _M_next_size(__num_elements_hint); | |
878 | if (__n > __old_n) { | |
879 | vector<_Node*, _All> __tmp(__n, (_Node*)(0), | |
880 | _M_buckets.get_allocator()); | |
322821b9 | 881 | try { |
725dc051 BK |
882 | for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) { |
883 | _Node* __first = _M_buckets[__bucket]; | |
884 | while (__first) { | |
885 | size_type __new_bucket = _M_bkt_num(__first->_M_val, __n); | |
886 | _M_buckets[__bucket] = __first->_M_next; | |
887 | __first->_M_next = __tmp[__new_bucket]; | |
888 | __tmp[__new_bucket] = __first; | |
889 | __first = _M_buckets[__bucket]; | |
890 | } | |
891 | } | |
892 | _M_buckets.swap(__tmp); | |
893 | } | |
725dc051 BK |
894 | catch(...) { |
895 | for (size_type __bucket = 0; __bucket < __tmp.size(); ++__bucket) { | |
896 | while (__tmp[__bucket]) { | |
897 | _Node* __next = __tmp[__bucket]->_M_next; | |
898 | _M_delete_node(__tmp[__bucket]); | |
899 | __tmp[__bucket] = __next; | |
900 | } | |
901 | } | |
322821b9 | 902 | __throw_exception_again; |
725dc051 | 903 | } |
725dc051 BK |
904 | } |
905 | } | |
906 | } | |
907 | ||
908 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
909 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
910 | ::_M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) | |
911 | { | |
912 | _Node* __cur = _M_buckets[__n]; | |
913 | if (__cur == __first) | |
914 | _M_erase_bucket(__n, __last); | |
915 | else { | |
916 | _Node* __next; | |
917 | for (__next = __cur->_M_next; | |
918 | __next != __first; | |
919 | __cur = __next, __next = __cur->_M_next) | |
920 | ; | |
921 | while (__next != __last) { | |
922 | __cur->_M_next = __next->_M_next; | |
923 | _M_delete_node(__next); | |
924 | __next = __cur->_M_next; | |
925 | --_M_num_elements; | |
926 | } | |
927 | } | |
928 | } | |
929 | ||
930 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
931 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
932 | ::_M_erase_bucket(const size_type __n, _Node* __last) | |
933 | { | |
934 | _Node* __cur = _M_buckets[__n]; | |
935 | while (__cur != __last) { | |
936 | _Node* __next = __cur->_M_next; | |
937 | _M_delete_node(__cur); | |
938 | __cur = __next; | |
939 | _M_buckets[__n] = __cur; | |
940 | --_M_num_elements; | |
941 | } | |
942 | } | |
943 | ||
944 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
945 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::clear() | |
946 | { | |
947 | for (size_type __i = 0; __i < _M_buckets.size(); ++__i) { | |
948 | _Node* __cur = _M_buckets[__i]; | |
949 | while (__cur != 0) { | |
950 | _Node* __next = __cur->_M_next; | |
951 | _M_delete_node(__cur); | |
952 | __cur = __next; | |
953 | } | |
954 | _M_buckets[__i] = 0; | |
955 | } | |
956 | _M_num_elements = 0; | |
957 | } | |
958 | ||
959 | ||
960 | template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
961 | void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All> | |
962 | ::_M_copy_from(const hashtable& __ht) | |
963 | { | |
964 | _M_buckets.clear(); | |
965 | _M_buckets.reserve(__ht._M_buckets.size()); | |
966 | _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); | |
322821b9 | 967 | try { |
725dc051 BK |
968 | for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { |
969 | const _Node* __cur = __ht._M_buckets[__i]; | |
970 | if (__cur) { | |
971 | _Node* __local_copy = _M_new_node(__cur->_M_val); | |
972 | _M_buckets[__i] = __local_copy; | |
973 | ||
974 | for (_Node* __next = __cur->_M_next; | |
975 | __next; | |
976 | __cur = __next, __next = __cur->_M_next) { | |
977 | __local_copy->_M_next = _M_new_node(__next->_M_val); | |
978 | __local_copy = __local_copy->_M_next; | |
979 | } | |
980 | } | |
981 | } | |
982 | _M_num_elements = __ht._M_num_elements; | |
983 | } | |
322821b9 BK |
984 | catch(...) |
985 | { | |
986 | clear(); | |
987 | __throw_exception_again; | |
988 | } | |
725dc051 | 989 | } |
e538847e | 990 | } // namespace __gnu_cxx |
725dc051 | 991 | |
b2acb86f | 992 | #endif |