1 // Hashtable implementation used by containers -*- C++ -*-
2
3 // Copyright (C) 2001-2018 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
_GLIBCXX_VISIBILITY(default)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 _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.
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 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
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