1 | // Hashtable implementation used by containers -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2017 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, 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 | // 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. |
19 | |
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/>. |
24 | |
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 | |
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). |
54 | */ |
55 | |
56 | #ifndef _BACKWARD_HASHTABLE_H |
57 | #define _BACKWARD_HASHTABLE_H 1 |
58 | |
59 | // Hashtable class, used to implement the hashed associative containers |
60 | // hash_set, hash_map, hash_multiset, and hash_multimap. |
61 | |
62 | #include <vector> |
63 | #include <iterator> |
64 | #include <algorithm> |
65 | #include <bits/stl_function.h> |
66 | #include <backward/hash_fun.h> |
67 | |
68 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
69 | { |
70 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
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 | (_Node* __n, _Hashtable* __tab) |
126 | : _M_cur(__n), _M_ht(__tab) { } |
127 | |
128 | () { } |
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 | (const _Node* __n, const _Hashtable* __tab) |
178 | : _M_cur(__n), _M_ht(__tab) { } |
179 | |
180 | () { } |
181 | |
182 | (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. |
209 | enum { _S_num_primes = 29 }; |
210 | |
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] = |
222 | { |
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 |
229 | }; |
230 | |
231 | template<class _PrimeType> inline const _PrimeType* |
232 | _Hashtable_prime_list<_PrimeType>::_S_get_prime_list() |
233 | { |
234 | return __stl_prime_list; |
235 | } |
236 | |
237 | inline unsigned long |
238 | __stl_next_prime(unsigned long __n) |
239 | { |
240 | const unsigned long* __first = _Hashtable_prime_list<unsigned long>::_S_get_prime_list(); |
241 | const unsigned long* __last = __first + (int)_S_num_primes; |
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 | (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 | (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 | (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 | () |
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 |
435 | { return _Hashtable_prime_list<unsigned long>:: |
436 | _S_get_prime_list()[(int)_S_num_primes - 1]; |
437 | } |
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; |
620 | __try |
621 | { |
622 | this->get_allocator().construct(&__n->_M_val, __obj); |
623 | return __n; |
624 | } |
625 | __catch(...) |
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]; |
886 | _Node* __saved_slot = 0; |
887 | size_type __erased = 0; |
888 | |
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 | { |
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 | } |
911 | } |
912 | else |
913 | { |
914 | __cur = __next; |
915 | __next = __cur->_M_next; |
916 | } |
917 | } |
918 | bool __delete_first = _M_equals(_M_get_key(__first->_M_val), __key); |
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; |
926 | } |
927 | if (__delete_first) |
928 | { |
929 | _M_buckets[__n] = __first->_M_next; |
930 | _M_delete_node(__first); |
931 | ++__erased; |
932 | --_M_num_elements; |
933 | } |
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()); |
1031 | __try |
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 | } |
1048 | __catch(...) |
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 | { |
1112 | if (_M_num_elements == 0) |
1113 | return; |
1114 | |
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); |
1137 | __try |
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 | } |
1157 | __catch(...) |
1158 | { |
1159 | clear(); |
1160 | __throw_exception_again; |
1161 | } |
1162 | } |
1163 | |
1164 | _GLIBCXX_END_NAMESPACE_VERSION |
1165 | } // namespace |
1166 | |
1167 | #endif |
1168 | |