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