]>
Commit | Line | Data |
---|---|---|
e63637ea | 1 | // Hashtable implementation used by containers -*- C++ -*- |
42526146 | 2 | |
a5544970 | 3 | // Copyright (C) 2001-2019 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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
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 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
42526146 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
42526146 | 24 | |
725dc051 BK |
25 | /* |
26 | * Copyright (c) 1996,1997 | |
27 | * Silicon Graphics Computer Systems, Inc. | |
28 | * | |
29 | * Permission to use, copy, modify, distribute and sell this software | |
30 | * and its documentation for any purpose is hereby granted without fee, | |
31 | * provided that the above copyright notice appear in all copies and | |
32 | * that both that copyright notice and this permission notice appear | |
33 | * in supporting documentation. Silicon Graphics makes no | |
34 | * representations about the suitability of this software for any | |
35 | * purpose. It is provided "as is" without express or implied warranty. | |
36 | * | |
37 | * | |
38 | * Copyright (c) 1994 | |
39 | * Hewlett-Packard Company | |
40 | * | |
41 | * Permission to use, copy, modify, distribute and sell this software | |
42 | * and its documentation for any purpose is hereby granted without fee, | |
43 | * provided that the above copyright notice appear in all copies and | |
44 | * that both that copyright notice and this permission notice appear | |
45 | * in supporting documentation. Hewlett-Packard Company makes no | |
46 | * representations about the suitability of this software for any | |
47 | * purpose. It is provided "as is" without express or implied warranty. | |
48 | * | |
49 | */ | |
50 | ||
e63637ea BK |
51 | /** @file backward/hashtable.h |
52 | * This file is a GNU extension to the Standard C++ Library (possibly | |
53 | * containing extensions from the HP/SGI STL subset). | |
725dc051 BK |
54 | */ |
55 | ||
5ecfce5c PC |
56 | #ifndef _BACKWARD_HASHTABLE_H |
57 | #define _BACKWARD_HASHTABLE_H 1 | |
725dc051 | 58 | |
e63637ea BK |
59 | // Hashtable class, used to implement the hashed associative containers |
60 | // hash_set, hash_map, hash_multiset, and hash_multimap. | |
725dc051 | 61 | |
e63637ea BK |
62 | #include <vector> |
63 | #include <iterator> | |
64 | #include <algorithm> | |
65 | #include <bits/stl_function.h> | |
66 | #include <backward/hash_fun.h> | |
725dc051 | 67 | |
12ffa228 BK |
68 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
69 | { | |
70 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
e63637ea BK |
71 | |
72 | using std::size_t; | |
73 | using std::ptrdiff_t; | |
74 | using std::forward_iterator_tag; | |
75 | using std::input_iterator_tag; | |
76 | using std::_Construct; | |
77 | using std::_Destroy; | |
78 | using std::distance; | |
79 | using std::vector; | |
80 | using std::pair; | |
81 | using std::__iterator_category; | |
82 | ||
83 | template<class _Val> | |
84 | struct _Hashtable_node | |
85 | { | |
86 | _Hashtable_node* _M_next; | |
87 | _Val _M_val; | |
88 | }; | |
89 | ||
90 | template<class _Val, class _Key, class _HashFcn, class _ExtractKey, | |
91 | class _EqualKey, class _Alloc = std::allocator<_Val> > | |
92 | class hashtable; | |
93 | ||
94 | template<class _Val, class _Key, class _HashFcn, | |
95 | class _ExtractKey, class _EqualKey, class _Alloc> | |
96 | struct _Hashtable_iterator; | |
97 | ||
98 | template<class _Val, class _Key, class _HashFcn, | |
99 | class _ExtractKey, class _EqualKey, class _Alloc> | |
100 | struct _Hashtable_const_iterator; | |
101 | ||
102 | template<class _Val, class _Key, class _HashFcn, | |
103 | class _ExtractKey, class _EqualKey, class _Alloc> | |
104 | struct _Hashtable_iterator | |
105 | { | |
106 | typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> | |
107 | _Hashtable; | |
108 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, | |
109 | _ExtractKey, _EqualKey, _Alloc> | |
110 | iterator; | |
111 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, | |
112 | _ExtractKey, _EqualKey, _Alloc> | |
113 | const_iterator; | |
114 | typedef _Hashtable_node<_Val> _Node; | |
115 | typedef forward_iterator_tag iterator_category; | |
116 | typedef _Val value_type; | |
117 | typedef ptrdiff_t difference_type; | |
118 | typedef size_t size_type; | |
119 | typedef _Val& reference; | |
120 | typedef _Val* pointer; | |
121 | ||
122 | _Node* _M_cur; | |
123 | _Hashtable* _M_ht; | |
124 | ||
125 | _Hashtable_iterator(_Node* __n, _Hashtable* __tab) | |
126 | : _M_cur(__n), _M_ht(__tab) { } | |
127 | ||
128 | _Hashtable_iterator() { } | |
129 | ||
130 | reference | |
131 | operator*() const | |
132 | { return _M_cur->_M_val; } | |
133 | ||
134 | pointer | |
135 | operator->() const | |
136 | { return &(operator*()); } | |
137 | ||
138 | iterator& | |
139 | operator++(); | |
140 | ||
141 | iterator | |
142 | operator++(int); | |
143 | ||
144 | bool | |
145 | operator==(const iterator& __it) const | |
146 | { return _M_cur == __it._M_cur; } | |
147 | ||
148 | bool | |
149 | operator!=(const iterator& __it) const | |
150 | { return _M_cur != __it._M_cur; } | |
151 | }; | |
152 | ||
153 | template<class _Val, class _Key, class _HashFcn, | |
154 | class _ExtractKey, class _EqualKey, class _Alloc> | |
155 | struct _Hashtable_const_iterator | |
156 | { | |
157 | typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc> | |
158 | _Hashtable; | |
159 | typedef _Hashtable_iterator<_Val,_Key,_HashFcn, | |
160 | _ExtractKey,_EqualKey,_Alloc> | |
161 | iterator; | |
162 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, | |
163 | _ExtractKey, _EqualKey, _Alloc> | |
164 | const_iterator; | |
165 | typedef _Hashtable_node<_Val> _Node; | |
166 | ||
167 | typedef forward_iterator_tag iterator_category; | |
168 | typedef _Val value_type; | |
169 | typedef ptrdiff_t difference_type; | |
170 | typedef size_t size_type; | |
171 | typedef const _Val& reference; | |
172 | typedef const _Val* pointer; | |
173 | ||
174 | const _Node* _M_cur; | |
175 | const _Hashtable* _M_ht; | |
176 | ||
177 | _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab) | |
178 | : _M_cur(__n), _M_ht(__tab) { } | |
179 | ||
180 | _Hashtable_const_iterator() { } | |
181 | ||
182 | _Hashtable_const_iterator(const iterator& __it) | |
183 | : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { } | |
184 | ||
185 | reference | |
186 | operator*() const | |
187 | { return _M_cur->_M_val; } | |
188 | ||
189 | pointer | |
190 | operator->() const | |
191 | { return &(operator*()); } | |
192 | ||
193 | const_iterator& | |
194 | operator++(); | |
195 | ||
196 | const_iterator | |
197 | operator++(int); | |
198 | ||
199 | bool | |
200 | operator==(const const_iterator& __it) const | |
201 | { return _M_cur == __it._M_cur; } | |
202 | ||
203 | bool | |
204 | operator!=(const const_iterator& __it) const | |
205 | { return _M_cur != __it._M_cur; } | |
206 | }; | |
207 | ||
208 | // Note: assumes long is at least 32 bits. | |
9027c95a | 209 | enum { _S_num_primes = 29 }; |
e63637ea | 210 | |
b9b8c6ae XDL |
211 | template<typename _PrimeType> |
212 | struct _Hashtable_prime_list | |
213 | { | |
214 | static const _PrimeType __stl_prime_list[_S_num_primes]; | |
215 | ||
216 | static const _PrimeType* | |
217 | _S_get_prime_list(); | |
218 | }; | |
219 | ||
220 | template<typename _PrimeType> const _PrimeType | |
221 | _Hashtable_prime_list<_PrimeType>::__stl_prime_list[_S_num_primes] = | |
e63637ea | 222 | { |
9027c95a ILT |
223 | 5ul, 53ul, 97ul, 193ul, 389ul, |
224 | 769ul, 1543ul, 3079ul, 6151ul, 12289ul, | |
225 | 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, | |
226 | 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, | |
227 | 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, | |
228 | 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul | |
e63637ea BK |
229 | }; |
230 | ||
b9b8c6ae XDL |
231 | template<class _PrimeType> inline const _PrimeType* |
232 | _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() | |
233 | { | |
234 | return __stl_prime_list; | |
235 | } | |
236 | ||
e63637ea BK |
237 | inline unsigned long |
238 | __stl_next_prime(unsigned long __n) | |
239 | { | |
b9b8c6ae XDL |
240 | const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); |
241 | const unsigned long* __last = __first + (int)_S_num_primes; | |
e63637ea BK |
242 | const unsigned long* pos = std::lower_bound(__first, __last, __n); |
243 | return pos == __last ? *(__last - 1) : *pos; | |
244 | } | |
245 | ||
246 | // Forward declaration of operator==. | |
247 | template<class _Val, class _Key, class _HF, class _Ex, | |
248 | class _Eq, class _All> | |
249 | class hashtable; | |
250 | ||
251 | template<class _Val, class _Key, class _HF, class _Ex, | |
252 | class _Eq, class _All> | |
253 | bool | |
254 | operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, | |
255 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2); | |
256 | ||
257 | // Hashtables handle allocators a bit differently than other | |
258 | // containers do. If we're using standard-conforming allocators, then | |
259 | // a hashtable unconditionally has a member variable to hold its | |
260 | // allocator, even if it so happens that all instances of the | |
261 | // allocator type are identical. This is because, for hashtables, | |
262 | // this extra storage is negligible. Additionally, a base class | |
263 | // wouldn't serve any other purposes; it wouldn't, for example, | |
264 | // simplify the exception-handling code. | |
265 | template<class _Val, class _Key, class _HashFcn, | |
266 | class _ExtractKey, class _EqualKey, class _Alloc> | |
267 | class hashtable | |
268 | { | |
269 | public: | |
270 | typedef _Key key_type; | |
271 | typedef _Val value_type; | |
272 | typedef _HashFcn hasher; | |
273 | typedef _EqualKey key_equal; | |
274 | ||
275 | typedef size_t size_type; | |
276 | typedef ptrdiff_t difference_type; | |
277 | typedef value_type* pointer; | |
278 | typedef const value_type* const_pointer; | |
279 | typedef value_type& reference; | |
280 | typedef const value_type& const_reference; | |
281 | ||
282 | hasher | |
283 | hash_funct() const | |
284 | { return _M_hash; } | |
285 | ||
286 | key_equal | |
287 | key_eq() const | |
288 | { return _M_equals; } | |
289 | ||
290 | private: | |
291 | typedef _Hashtable_node<_Val> _Node; | |
292 | ||
293 | public: | |
294 | typedef typename _Alloc::template rebind<value_type>::other allocator_type; | |
295 | allocator_type | |
296 | get_allocator() const | |
297 | { return _M_node_allocator; } | |
298 | ||
299 | private: | |
300 | typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc; | |
301 | typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc; | |
302 | typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type; | |
303 | ||
304 | _Node_Alloc _M_node_allocator; | |
305 | ||
306 | _Node* | |
307 | _M_get_node() | |
308 | { return _M_node_allocator.allocate(1); } | |
309 | ||
310 | void | |
311 | _M_put_node(_Node* __p) | |
312 | { _M_node_allocator.deallocate(__p, 1); } | |
313 | ||
314 | private: | |
315 | hasher _M_hash; | |
316 | key_equal _M_equals; | |
317 | _ExtractKey _M_get_key; | |
318 | _Vector_type _M_buckets; | |
319 | size_type _M_num_elements; | |
320 | ||
321 | public: | |
322 | typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, | |
323 | _EqualKey, _Alloc> | |
324 | iterator; | |
325 | typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, | |
326 | _EqualKey, _Alloc> | |
327 | const_iterator; | |
328 | ||
329 | friend struct | |
330 | _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>; | |
331 | ||
332 | friend struct | |
333 | _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey, | |
334 | _EqualKey, _Alloc>; | |
335 | ||
336 | public: | |
337 | hashtable(size_type __n, const _HashFcn& __hf, | |
338 | const _EqualKey& __eql, const _ExtractKey& __ext, | |
339 | const allocator_type& __a = allocator_type()) | |
340 | : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), | |
341 | _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0) | |
342 | { _M_initialize_buckets(__n); } | |
343 | ||
344 | hashtable(size_type __n, const _HashFcn& __hf, | |
345 | const _EqualKey& __eql, | |
346 | const allocator_type& __a = allocator_type()) | |
347 | : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql), | |
348 | _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0) | |
349 | { _M_initialize_buckets(__n); } | |
350 | ||
351 | hashtable(const hashtable& __ht) | |
352 | : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash), | |
353 | _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key), | |
354 | _M_buckets(__ht.get_allocator()), _M_num_elements(0) | |
355 | { _M_copy_from(__ht); } | |
356 | ||
357 | hashtable& | |
358 | operator= (const hashtable& __ht) | |
359 | { | |
360 | if (&__ht != this) | |
361 | { | |
362 | clear(); | |
363 | _M_hash = __ht._M_hash; | |
364 | _M_equals = __ht._M_equals; | |
365 | _M_get_key = __ht._M_get_key; | |
366 | _M_copy_from(__ht); | |
367 | } | |
368 | return *this; | |
369 | } | |
370 | ||
371 | ~hashtable() | |
372 | { clear(); } | |
373 | ||
374 | size_type | |
375 | size() const | |
376 | { return _M_num_elements; } | |
377 | ||
378 | size_type | |
379 | max_size() const | |
380 | { return size_type(-1); } | |
381 | ||
382 | bool | |
383 | empty() const | |
384 | { return size() == 0; } | |
385 | ||
386 | void | |
387 | swap(hashtable& __ht) | |
388 | { | |
389 | std::swap(_M_hash, __ht._M_hash); | |
390 | std::swap(_M_equals, __ht._M_equals); | |
391 | std::swap(_M_get_key, __ht._M_get_key); | |
392 | _M_buckets.swap(__ht._M_buckets); | |
393 | std::swap(_M_num_elements, __ht._M_num_elements); | |
394 | } | |
395 | ||
396 | iterator | |
397 | begin() | |
398 | { | |
399 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) | |
400 | if (_M_buckets[__n]) | |
401 | return iterator(_M_buckets[__n], this); | |
402 | return end(); | |
403 | } | |
404 | ||
405 | iterator | |
406 | end() | |
407 | { return iterator(0, this); } | |
408 | ||
409 | const_iterator | |
410 | begin() const | |
411 | { | |
412 | for (size_type __n = 0; __n < _M_buckets.size(); ++__n) | |
413 | if (_M_buckets[__n]) | |
414 | return const_iterator(_M_buckets[__n], this); | |
415 | return end(); | |
416 | } | |
417 | ||
418 | const_iterator | |
419 | end() const | |
420 | { return const_iterator(0, this); } | |
421 | ||
422 | template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq, | |
423 | class _Al> | |
424 | friend bool | |
425 | operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&, | |
426 | const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&); | |
427 | ||
428 | public: | |
429 | size_type | |
430 | bucket_count() const | |
431 | { return _M_buckets.size(); } | |
432 | ||
433 | size_type | |
434 | max_bucket_count() const | |
b9b8c6ae XDL |
435 | { return _Hashtable_prime_list<unsigned long>:: |
436 | _S_get_prime_list()[(int)_S_num_primes - 1]; | |
437 | } | |
e63637ea BK |
438 | |
439 | size_type | |
440 | elems_in_bucket(size_type __bucket) const | |
441 | { | |
442 | size_type __result = 0; | |
443 | for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next) | |
444 | __result += 1; | |
445 | return __result; | |
446 | } | |
447 | ||
448 | pair<iterator, bool> | |
449 | insert_unique(const value_type& __obj) | |
450 | { | |
451 | resize(_M_num_elements + 1); | |
452 | return insert_unique_noresize(__obj); | |
453 | } | |
454 | ||
455 | iterator | |
456 | insert_equal(const value_type& __obj) | |
457 | { | |
458 | resize(_M_num_elements + 1); | |
459 | return insert_equal_noresize(__obj); | |
460 | } | |
461 | ||
462 | pair<iterator, bool> | |
463 | insert_unique_noresize(const value_type& __obj); | |
464 | ||
465 | iterator | |
466 | insert_equal_noresize(const value_type& __obj); | |
467 | ||
468 | template<class _InputIterator> | |
469 | void | |
470 | insert_unique(_InputIterator __f, _InputIterator __l) | |
471 | { insert_unique(__f, __l, __iterator_category(__f)); } | |
472 | ||
473 | template<class _InputIterator> | |
474 | void | |
475 | insert_equal(_InputIterator __f, _InputIterator __l) | |
476 | { insert_equal(__f, __l, __iterator_category(__f)); } | |
477 | ||
478 | template<class _InputIterator> | |
479 | void | |
480 | insert_unique(_InputIterator __f, _InputIterator __l, | |
481 | input_iterator_tag) | |
482 | { | |
483 | for ( ; __f != __l; ++__f) | |
484 | insert_unique(*__f); | |
485 | } | |
486 | ||
487 | template<class _InputIterator> | |
488 | void | |
489 | insert_equal(_InputIterator __f, _InputIterator __l, | |
490 | input_iterator_tag) | |
491 | { | |
492 | for ( ; __f != __l; ++__f) | |
493 | insert_equal(*__f); | |
494 | } | |
495 | ||
496 | template<class _ForwardIterator> | |
497 | void | |
498 | insert_unique(_ForwardIterator __f, _ForwardIterator __l, | |
499 | forward_iterator_tag) | |
500 | { | |
501 | size_type __n = distance(__f, __l); | |
502 | resize(_M_num_elements + __n); | |
503 | for ( ; __n > 0; --__n, ++__f) | |
504 | insert_unique_noresize(*__f); | |
505 | } | |
506 | ||
507 | template<class _ForwardIterator> | |
508 | void | |
509 | insert_equal(_ForwardIterator __f, _ForwardIterator __l, | |
510 | forward_iterator_tag) | |
511 | { | |
512 | size_type __n = distance(__f, __l); | |
513 | resize(_M_num_elements + __n); | |
514 | for ( ; __n > 0; --__n, ++__f) | |
515 | insert_equal_noresize(*__f); | |
516 | } | |
517 | ||
518 | reference | |
519 | find_or_insert(const value_type& __obj); | |
520 | ||
521 | iterator | |
522 | find(const key_type& __key) | |
523 | { | |
524 | size_type __n = _M_bkt_num_key(__key); | |
525 | _Node* __first; | |
526 | for (__first = _M_buckets[__n]; | |
527 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); | |
528 | __first = __first->_M_next) | |
529 | { } | |
530 | return iterator(__first, this); | |
531 | } | |
532 | ||
533 | const_iterator | |
534 | find(const key_type& __key) const | |
535 | { | |
536 | size_type __n = _M_bkt_num_key(__key); | |
537 | const _Node* __first; | |
538 | for (__first = _M_buckets[__n]; | |
539 | __first && !_M_equals(_M_get_key(__first->_M_val), __key); | |
540 | __first = __first->_M_next) | |
541 | { } | |
542 | return const_iterator(__first, this); | |
543 | } | |
544 | ||
545 | size_type | |
546 | count(const key_type& __key) const | |
547 | { | |
548 | const size_type __n = _M_bkt_num_key(__key); | |
549 | size_type __result = 0; | |
550 | ||
551 | for (const _Node* __cur = _M_buckets[__n]; __cur; | |
552 | __cur = __cur->_M_next) | |
553 | if (_M_equals(_M_get_key(__cur->_M_val), __key)) | |
554 | ++__result; | |
555 | return __result; | |
556 | } | |
557 | ||
558 | pair<iterator, iterator> | |
559 | equal_range(const key_type& __key); | |
560 | ||
561 | pair<const_iterator, const_iterator> | |
562 | equal_range(const key_type& __key) const; | |
563 | ||
564 | size_type | |
565 | erase(const key_type& __key); | |
566 | ||
567 | void | |
568 | erase(const iterator& __it); | |
569 | ||
570 | void | |
571 | erase(iterator __first, iterator __last); | |
572 | ||
573 | void | |
574 | erase(const const_iterator& __it); | |
575 | ||
576 | void | |
577 | erase(const_iterator __first, const_iterator __last); | |
578 | ||
579 | void | |
580 | resize(size_type __num_elements_hint); | |
581 | ||
582 | void | |
583 | clear(); | |
584 | ||
585 | private: | |
586 | size_type | |
587 | _M_next_size(size_type __n) const | |
588 | { return __stl_next_prime(__n); } | |
589 | ||
590 | void | |
591 | _M_initialize_buckets(size_type __n) | |
592 | { | |
593 | const size_type __n_buckets = _M_next_size(__n); | |
594 | _M_buckets.reserve(__n_buckets); | |
595 | _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0); | |
596 | _M_num_elements = 0; | |
597 | } | |
598 | ||
599 | size_type | |
600 | _M_bkt_num_key(const key_type& __key) const | |
601 | { return _M_bkt_num_key(__key, _M_buckets.size()); } | |
602 | ||
603 | size_type | |
604 | _M_bkt_num(const value_type& __obj) const | |
605 | { return _M_bkt_num_key(_M_get_key(__obj)); } | |
606 | ||
607 | size_type | |
608 | _M_bkt_num_key(const key_type& __key, size_t __n) const | |
609 | { return _M_hash(__key) % __n; } | |
610 | ||
611 | size_type | |
612 | _M_bkt_num(const value_type& __obj, size_t __n) const | |
613 | { return _M_bkt_num_key(_M_get_key(__obj), __n); } | |
614 | ||
615 | _Node* | |
616 | _M_new_node(const value_type& __obj) | |
617 | { | |
618 | _Node* __n = _M_get_node(); | |
619 | __n->_M_next = 0; | |
bc2631e0 | 620 | __try |
e63637ea BK |
621 | { |
622 | this->get_allocator().construct(&__n->_M_val, __obj); | |
623 | return __n; | |
624 | } | |
bc2631e0 | 625 | __catch(...) |
e63637ea BK |
626 | { |
627 | _M_put_node(__n); | |
628 | __throw_exception_again; | |
629 | } | |
630 | } | |
631 | ||
632 | void | |
633 | _M_delete_node(_Node* __n) | |
634 | { | |
635 | this->get_allocator().destroy(&__n->_M_val); | |
636 | _M_put_node(__n); | |
637 | } | |
638 | ||
639 | void | |
640 | _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last); | |
641 | ||
642 | void | |
643 | _M_erase_bucket(const size_type __n, _Node* __last); | |
644 | ||
645 | void | |
646 | _M_copy_from(const hashtable& __ht); | |
647 | }; | |
648 | ||
649 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
650 | class _All> | |
651 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& | |
652 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: | |
653 | operator++() | |
654 | { | |
655 | const _Node* __old = _M_cur; | |
656 | _M_cur = _M_cur->_M_next; | |
657 | if (!_M_cur) | |
658 | { | |
659 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); | |
660 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) | |
661 | _M_cur = _M_ht->_M_buckets[__bucket]; | |
662 | } | |
663 | return *this; | |
664 | } | |
665 | ||
666 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
667 | class _All> | |
668 | inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> | |
669 | _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: | |
670 | operator++(int) | |
671 | { | |
672 | iterator __tmp = *this; | |
673 | ++*this; | |
674 | return __tmp; | |
675 | } | |
676 | ||
677 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
678 | class _All> | |
679 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>& | |
680 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: | |
681 | operator++() | |
682 | { | |
683 | const _Node* __old = _M_cur; | |
684 | _M_cur = _M_cur->_M_next; | |
685 | if (!_M_cur) | |
686 | { | |
687 | size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val); | |
688 | while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size()) | |
689 | _M_cur = _M_ht->_M_buckets[__bucket]; | |
690 | } | |
691 | return *this; | |
692 | } | |
693 | ||
694 | template<class _Val, class _Key, class _HF, class _ExK, class _EqK, | |
695 | class _All> | |
696 | inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All> | |
697 | _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>:: | |
698 | operator++(int) | |
699 | { | |
700 | const_iterator __tmp = *this; | |
701 | ++*this; | |
702 | return __tmp; | |
703 | } | |
704 | ||
705 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
706 | bool | |
707 | operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, | |
708 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) | |
709 | { | |
710 | typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node; | |
711 | ||
712 | if (__ht1._M_buckets.size() != __ht2._M_buckets.size()) | |
713 | return false; | |
714 | ||
715 | for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n) | |
716 | { | |
717 | _Node* __cur1 = __ht1._M_buckets[__n]; | |
718 | _Node* __cur2 = __ht2._M_buckets[__n]; | |
719 | // Check same length of lists | |
720 | for (; __cur1 && __cur2; | |
721 | __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next) | |
722 | { } | |
723 | if (__cur1 || __cur2) | |
724 | return false; | |
725 | // Now check one's elements are in the other | |
726 | for (__cur1 = __ht1._M_buckets[__n] ; __cur1; | |
727 | __cur1 = __cur1->_M_next) | |
728 | { | |
729 | bool _found__cur1 = false; | |
730 | for (__cur2 = __ht2._M_buckets[__n]; | |
731 | __cur2; __cur2 = __cur2->_M_next) | |
732 | { | |
733 | if (__cur1->_M_val == __cur2->_M_val) | |
734 | { | |
735 | _found__cur1 = true; | |
736 | break; | |
737 | } | |
738 | } | |
739 | if (!_found__cur1) | |
740 | return false; | |
741 | } | |
742 | } | |
743 | return true; | |
744 | } | |
745 | ||
746 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
747 | inline bool | |
748 | operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1, | |
749 | const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2) | |
750 | { return !(__ht1 == __ht2); } | |
751 | ||
752 | template<class _Val, class _Key, class _HF, class _Extract, class _EqKey, | |
753 | class _All> | |
754 | inline void | |
755 | swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1, | |
756 | hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2) | |
757 | { __ht1.swap(__ht2); } | |
758 | ||
759 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
760 | pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool> | |
761 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
762 | insert_unique_noresize(const value_type& __obj) | |
763 | { | |
764 | const size_type __n = _M_bkt_num(__obj); | |
765 | _Node* __first = _M_buckets[__n]; | |
766 | ||
767 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
768 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) | |
769 | return pair<iterator, bool>(iterator(__cur, this), false); | |
770 | ||
771 | _Node* __tmp = _M_new_node(__obj); | |
772 | __tmp->_M_next = __first; | |
773 | _M_buckets[__n] = __tmp; | |
774 | ++_M_num_elements; | |
775 | return pair<iterator, bool>(iterator(__tmp, this), true); | |
776 | } | |
777 | ||
778 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
779 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator | |
780 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
781 | insert_equal_noresize(const value_type& __obj) | |
782 | { | |
783 | const size_type __n = _M_bkt_num(__obj); | |
784 | _Node* __first = _M_buckets[__n]; | |
785 | ||
786 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
787 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) | |
788 | { | |
789 | _Node* __tmp = _M_new_node(__obj); | |
790 | __tmp->_M_next = __cur->_M_next; | |
791 | __cur->_M_next = __tmp; | |
792 | ++_M_num_elements; | |
793 | return iterator(__tmp, this); | |
794 | } | |
795 | ||
796 | _Node* __tmp = _M_new_node(__obj); | |
797 | __tmp->_M_next = __first; | |
798 | _M_buckets[__n] = __tmp; | |
799 | ++_M_num_elements; | |
800 | return iterator(__tmp, this); | |
801 | } | |
802 | ||
803 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
804 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference | |
805 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
806 | find_or_insert(const value_type& __obj) | |
807 | { | |
808 | resize(_M_num_elements + 1); | |
809 | ||
810 | size_type __n = _M_bkt_num(__obj); | |
811 | _Node* __first = _M_buckets[__n]; | |
812 | ||
813 | for (_Node* __cur = __first; __cur; __cur = __cur->_M_next) | |
814 | if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) | |
815 | return __cur->_M_val; | |
816 | ||
817 | _Node* __tmp = _M_new_node(__obj); | |
818 | __tmp->_M_next = __first; | |
819 | _M_buckets[__n] = __tmp; | |
820 | ++_M_num_elements; | |
821 | return __tmp->_M_val; | |
822 | } | |
823 | ||
824 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
825 | pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, | |
826 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator> | |
827 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
828 | equal_range(const key_type& __key) | |
829 | { | |
830 | typedef pair<iterator, iterator> _Pii; | |
831 | const size_type __n = _M_bkt_num_key(__key); | |
832 | ||
833 | for (_Node* __first = _M_buckets[__n]; __first; | |
834 | __first = __first->_M_next) | |
835 | if (_M_equals(_M_get_key(__first->_M_val), __key)) | |
836 | { | |
837 | for (_Node* __cur = __first->_M_next; __cur; | |
838 | __cur = __cur->_M_next) | |
839 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) | |
840 | return _Pii(iterator(__first, this), iterator(__cur, this)); | |
841 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) | |
842 | if (_M_buckets[__m]) | |
843 | return _Pii(iterator(__first, this), | |
844 | iterator(_M_buckets[__m], this)); | |
845 | return _Pii(iterator(__first, this), end()); | |
846 | } | |
847 | return _Pii(end(), end()); | |
848 | } | |
849 | ||
850 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
851 | pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator, | |
852 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator> | |
853 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
854 | equal_range(const key_type& __key) const | |
855 | { | |
856 | typedef pair<const_iterator, const_iterator> _Pii; | |
857 | const size_type __n = _M_bkt_num_key(__key); | |
858 | ||
859 | for (const _Node* __first = _M_buckets[__n]; __first; | |
860 | __first = __first->_M_next) | |
861 | { | |
862 | if (_M_equals(_M_get_key(__first->_M_val), __key)) | |
863 | { | |
864 | for (const _Node* __cur = __first->_M_next; __cur; | |
865 | __cur = __cur->_M_next) | |
866 | if (!_M_equals(_M_get_key(__cur->_M_val), __key)) | |
867 | return _Pii(const_iterator(__first, this), | |
868 | const_iterator(__cur, this)); | |
869 | for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m) | |
870 | if (_M_buckets[__m]) | |
871 | return _Pii(const_iterator(__first, this), | |
872 | const_iterator(_M_buckets[__m], this)); | |
873 | return _Pii(const_iterator(__first, this), end()); | |
874 | } | |
875 | } | |
876 | return _Pii(end(), end()); | |
877 | } | |
878 | ||
879 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
880 | typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type | |
881 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
882 | erase(const key_type& __key) | |
883 | { | |
884 | const size_type __n = _M_bkt_num_key(__key); | |
885 | _Node* __first = _M_buckets[__n]; | |
9767a048 | 886 | _Node* __saved_slot = 0; |
e63637ea | 887 | size_type __erased = 0; |
9767a048 | 888 | |
e63637ea BK |
889 | if (__first) |
890 | { | |
891 | _Node* __cur = __first; | |
892 | _Node* __next = __cur->_M_next; | |
893 | while (__next) | |
894 | { | |
895 | if (_M_equals(_M_get_key(__next->_M_val), __key)) | |
896 | { | |
9767a048 ILT |
897 | if (&_M_get_key(__next->_M_val) != &__key) |
898 | { | |
899 | __cur->_M_next = __next->_M_next; | |
900 | _M_delete_node(__next); | |
901 | __next = __cur->_M_next; | |
902 | ++__erased; | |
903 | --_M_num_elements; | |
904 | } | |
905 | else | |
906 | { | |
907 | __saved_slot = __cur; | |
908 | __cur = __next; | |
909 | __next = __cur->_M_next; | |
910 | } | |
e63637ea BK |
911 | } |
912 | else | |
913 | { | |
914 | __cur = __next; | |
915 | __next = __cur->_M_next; | |
916 | } | |
917 | } | |
2b4e07b8 | 918 | bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key); |
9767a048 ILT |
919 | if (__saved_slot) |
920 | { | |
921 | __next = __saved_slot->_M_next; | |
922 | __saved_slot->_M_next = __next->_M_next; | |
923 | _M_delete_node(__next); | |
924 | ++__erased; | |
925 | --_M_num_elements; | |
e63637ea | 926 | } |
2b4e07b8 ILT |
927 | if (__delete_first) |
928 | { | |
929 | _M_buckets[__n] = __first->_M_next; | |
930 | _M_delete_node(__first); | |
931 | ++__erased; | |
932 | --_M_num_elements; | |
933 | } | |
e63637ea BK |
934 | } |
935 | return __erased; | |
936 | } | |
937 | ||
938 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
939 | void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
940 | erase(const iterator& __it) | |
941 | { | |
942 | _Node* __p = __it._M_cur; | |
943 | if (__p) | |
944 | { | |
945 | const size_type __n = _M_bkt_num(__p->_M_val); | |
946 | _Node* __cur = _M_buckets[__n]; | |
947 | ||
948 | if (__cur == __p) | |
949 | { | |
950 | _M_buckets[__n] = __cur->_M_next; | |
951 | _M_delete_node(__cur); | |
952 | --_M_num_elements; | |
953 | } | |
954 | else | |
955 | { | |
956 | _Node* __next = __cur->_M_next; | |
957 | while (__next) | |
958 | { | |
959 | if (__next == __p) | |
960 | { | |
961 | __cur->_M_next = __next->_M_next; | |
962 | _M_delete_node(__next); | |
963 | --_M_num_elements; | |
964 | break; | |
965 | } | |
966 | else | |
967 | { | |
968 | __cur = __next; | |
969 | __next = __cur->_M_next; | |
970 | } | |
971 | } | |
972 | } | |
973 | } | |
974 | } | |
975 | ||
976 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
977 | void | |
978 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
979 | erase(iterator __first, iterator __last) | |
980 | { | |
981 | size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val) | |
982 | : _M_buckets.size(); | |
983 | ||
984 | size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val) | |
985 | : _M_buckets.size(); | |
986 | ||
987 | if (__first._M_cur == __last._M_cur) | |
988 | return; | |
989 | else if (__f_bucket == __l_bucket) | |
990 | _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur); | |
991 | else | |
992 | { | |
993 | _M_erase_bucket(__f_bucket, __first._M_cur, 0); | |
994 | for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n) | |
995 | _M_erase_bucket(__n, 0); | |
996 | if (__l_bucket != _M_buckets.size()) | |
997 | _M_erase_bucket(__l_bucket, __last._M_cur); | |
998 | } | |
999 | } | |
1000 | ||
1001 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1002 | inline void | |
1003 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1004 | erase(const_iterator __first, const_iterator __last) | |
1005 | { | |
1006 | erase(iterator(const_cast<_Node*>(__first._M_cur), | |
1007 | const_cast<hashtable*>(__first._M_ht)), | |
1008 | iterator(const_cast<_Node*>(__last._M_cur), | |
1009 | const_cast<hashtable*>(__last._M_ht))); | |
1010 | } | |
1011 | ||
1012 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1013 | inline void | |
1014 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1015 | erase(const const_iterator& __it) | |
1016 | { erase(iterator(const_cast<_Node*>(__it._M_cur), | |
1017 | const_cast<hashtable*>(__it._M_ht))); } | |
1018 | ||
1019 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1020 | void | |
1021 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1022 | resize(size_type __num_elements_hint) | |
1023 | { | |
1024 | const size_type __old_n = _M_buckets.size(); | |
1025 | if (__num_elements_hint > __old_n) | |
1026 | { | |
1027 | const size_type __n = _M_next_size(__num_elements_hint); | |
1028 | if (__n > __old_n) | |
1029 | { | |
1030 | _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator()); | |
bc2631e0 | 1031 | __try |
e63637ea BK |
1032 | { |
1033 | for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) | |
1034 | { | |
1035 | _Node* __first = _M_buckets[__bucket]; | |
1036 | while (__first) | |
1037 | { | |
1038 | size_type __new_bucket = _M_bkt_num(__first->_M_val, | |
1039 | __n); | |
1040 | _M_buckets[__bucket] = __first->_M_next; | |
1041 | __first->_M_next = __tmp[__new_bucket]; | |
1042 | __tmp[__new_bucket] = __first; | |
1043 | __first = _M_buckets[__bucket]; | |
1044 | } | |
1045 | } | |
1046 | _M_buckets.swap(__tmp); | |
1047 | } | |
bc2631e0 | 1048 | __catch(...) |
e63637ea BK |
1049 | { |
1050 | for (size_type __bucket = 0; __bucket < __tmp.size(); | |
1051 | ++__bucket) | |
1052 | { | |
1053 | while (__tmp[__bucket]) | |
1054 | { | |
1055 | _Node* __next = __tmp[__bucket]->_M_next; | |
1056 | _M_delete_node(__tmp[__bucket]); | |
1057 | __tmp[__bucket] = __next; | |
1058 | } | |
1059 | } | |
1060 | __throw_exception_again; | |
1061 | } | |
1062 | } | |
1063 | } | |
1064 | } | |
1065 | ||
1066 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1067 | void | |
1068 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1069 | _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last) | |
1070 | { | |
1071 | _Node* __cur = _M_buckets[__n]; | |
1072 | if (__cur == __first) | |
1073 | _M_erase_bucket(__n, __last); | |
1074 | else | |
1075 | { | |
1076 | _Node* __next; | |
1077 | for (__next = __cur->_M_next; | |
1078 | __next != __first; | |
1079 | __cur = __next, __next = __cur->_M_next) | |
1080 | ; | |
1081 | while (__next != __last) | |
1082 | { | |
1083 | __cur->_M_next = __next->_M_next; | |
1084 | _M_delete_node(__next); | |
1085 | __next = __cur->_M_next; | |
1086 | --_M_num_elements; | |
1087 | } | |
1088 | } | |
1089 | } | |
1090 | ||
1091 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1092 | void | |
1093 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1094 | _M_erase_bucket(const size_type __n, _Node* __last) | |
1095 | { | |
1096 | _Node* __cur = _M_buckets[__n]; | |
1097 | while (__cur != __last) | |
1098 | { | |
1099 | _Node* __next = __cur->_M_next; | |
1100 | _M_delete_node(__cur); | |
1101 | __cur = __next; | |
1102 | _M_buckets[__n] = __cur; | |
1103 | --_M_num_elements; | |
1104 | } | |
1105 | } | |
1106 | ||
1107 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1108 | void | |
1109 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1110 | clear() | |
1111 | { | |
7db6438d ILT |
1112 | if (_M_num_elements == 0) |
1113 | return; | |
1114 | ||
e63637ea BK |
1115 | for (size_type __i = 0; __i < _M_buckets.size(); ++__i) |
1116 | { | |
1117 | _Node* __cur = _M_buckets[__i]; | |
1118 | while (__cur != 0) | |
1119 | { | |
1120 | _Node* __next = __cur->_M_next; | |
1121 | _M_delete_node(__cur); | |
1122 | __cur = __next; | |
1123 | } | |
1124 | _M_buckets[__i] = 0; | |
1125 | } | |
1126 | _M_num_elements = 0; | |
1127 | } | |
1128 | ||
1129 | template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All> | |
1130 | void | |
1131 | hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>:: | |
1132 | _M_copy_from(const hashtable& __ht) | |
1133 | { | |
1134 | _M_buckets.clear(); | |
1135 | _M_buckets.reserve(__ht._M_buckets.size()); | |
1136 | _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0); | |
bc2631e0 | 1137 | __try |
e63637ea BK |
1138 | { |
1139 | for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) { | |
1140 | const _Node* __cur = __ht._M_buckets[__i]; | |
1141 | if (__cur) | |
1142 | { | |
1143 | _Node* __local_copy = _M_new_node(__cur->_M_val); | |
1144 | _M_buckets[__i] = __local_copy; | |
1145 | ||
1146 | for (_Node* __next = __cur->_M_next; | |
1147 | __next; | |
1148 | __cur = __next, __next = __cur->_M_next) | |
1149 | { | |
1150 | __local_copy->_M_next = _M_new_node(__next->_M_val); | |
1151 | __local_copy = __local_copy->_M_next; | |
1152 | } | |
1153 | } | |
1154 | } | |
1155 | _M_num_elements = __ht._M_num_elements; | |
1156 | } | |
bc2631e0 | 1157 | __catch(...) |
e63637ea BK |
1158 | { |
1159 | clear(); | |
1160 | __throw_exception_again; | |
1161 | } | |
1162 | } | |
1163 | ||
12ffa228 BK |
1164 | _GLIBCXX_END_NAMESPACE_VERSION |
1165 | } // namespace | |
e63637ea BK |
1166 | |
1167 | #endif |