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