00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062 #ifndef _HASHTABLE_H
00063 #define _HASHTABLE_H 1
00064
00065
00066
00067
00068 #include <vector>
00069 #include <iterator>
00070 #include <bits/stl_algo.h>
00071 #include <bits/stl_function.h>
00072 #include <ext/hash_fun.h>
00073
00074 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00075
00076 using std::size_t;
00077 using std::ptrdiff_t;
00078 using std::forward_iterator_tag;
00079 using std::input_iterator_tag;
00080 using std::_Construct;
00081 using std::_Destroy;
00082 using std::distance;
00083 using std::vector;
00084 using std::pair;
00085 using std::__iterator_category;
00086
00087 template<class _Val>
00088 struct _Hashtable_node
00089 {
00090 _Hashtable_node* _M_next;
00091 _Val _M_val;
00092 };
00093
00094 template<class _Val, class _Key, class _HashFcn, class _ExtractKey,
00095 class _EqualKey, class _Alloc = std::allocator<_Val> >
00096 class hashtable;
00097
00098 template<class _Val, class _Key, class _HashFcn,
00099 class _ExtractKey, class _EqualKey, class _Alloc>
00100 struct _Hashtable_iterator;
00101
00102 template<class _Val, class _Key, class _HashFcn,
00103 class _ExtractKey, class _EqualKey, class _Alloc>
00104 struct _Hashtable_const_iterator;
00105
00106 template<class _Val, class _Key, class _HashFcn,
00107 class _ExtractKey, class _EqualKey, class _Alloc>
00108 struct _Hashtable_iterator
00109 {
00110 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
00111 _Hashtable;
00112 typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
00113 _ExtractKey, _EqualKey, _Alloc>
00114 iterator;
00115 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
00116 _ExtractKey, _EqualKey, _Alloc>
00117 const_iterator;
00118 typedef _Hashtable_node<_Val> _Node;
00119 typedef forward_iterator_tag iterator_category;
00120 typedef _Val value_type;
00121 typedef ptrdiff_t difference_type;
00122 typedef size_t size_type;
00123 typedef _Val& reference;
00124 typedef _Val* pointer;
00125
00126 _Node* _M_cur;
00127 _Hashtable* _M_ht;
00128
00129 _Hashtable_iterator(_Node* __n, _Hashtable* __tab)
00130 : _M_cur(__n), _M_ht(__tab) { }
00131
00132 _Hashtable_iterator() { }
00133
00134 reference
00135 operator*() const
00136 { return _M_cur->_M_val; }
00137
00138 pointer
00139 operator->() const
00140 { return &(operator*()); }
00141
00142 iterator&
00143 operator++();
00144
00145 iterator
00146 operator++(int);
00147
00148 bool
00149 operator==(const iterator& __it) const
00150 { return _M_cur == __it._M_cur; }
00151
00152 bool
00153 operator!=(const iterator& __it) const
00154 { return _M_cur != __it._M_cur; }
00155 };
00156
00157 template<class _Val, class _Key, class _HashFcn,
00158 class _ExtractKey, class _EqualKey, class _Alloc>
00159 struct _Hashtable_const_iterator
00160 {
00161 typedef hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>
00162 _Hashtable;
00163 typedef _Hashtable_iterator<_Val,_Key,_HashFcn,
00164 _ExtractKey,_EqualKey,_Alloc>
00165 iterator;
00166 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn,
00167 _ExtractKey, _EqualKey, _Alloc>
00168 const_iterator;
00169 typedef _Hashtable_node<_Val> _Node;
00170
00171 typedef forward_iterator_tag iterator_category;
00172 typedef _Val value_type;
00173 typedef ptrdiff_t difference_type;
00174 typedef size_t size_type;
00175 typedef const _Val& reference;
00176 typedef const _Val* pointer;
00177
00178 const _Node* _M_cur;
00179 const _Hashtable* _M_ht;
00180
00181 _Hashtable_const_iterator(const _Node* __n, const _Hashtable* __tab)
00182 : _M_cur(__n), _M_ht(__tab) { }
00183
00184 _Hashtable_const_iterator() { }
00185
00186 _Hashtable_const_iterator(const iterator& __it)
00187 : _M_cur(__it._M_cur), _M_ht(__it._M_ht) { }
00188
00189 reference
00190 operator*() const
00191 { return _M_cur->_M_val; }
00192
00193 pointer
00194 operator->() const
00195 { return &(operator*()); }
00196
00197 const_iterator&
00198 operator++();
00199
00200 const_iterator
00201 operator++(int);
00202
00203 bool
00204 operator==(const const_iterator& __it) const
00205 { return _M_cur == __it._M_cur; }
00206
00207 bool
00208 operator!=(const const_iterator& __it) const
00209 { return _M_cur != __it._M_cur; }
00210 };
00211
00212
00213 enum { _S_num_primes = 28 };
00214
00215 static const unsigned long __stl_prime_list[_S_num_primes] =
00216 {
00217 53ul, 97ul, 193ul, 389ul, 769ul,
00218 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
00219 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
00220 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
00221 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
00222 1610612741ul, 3221225473ul, 4294967291ul
00223 };
00224
00225 inline unsigned long
00226 __stl_next_prime(unsigned long __n)
00227 {
00228 const unsigned long* __first = __stl_prime_list;
00229 const unsigned long* __last = __stl_prime_list + (int)_S_num_primes;
00230 const unsigned long* pos = std::lower_bound(__first, __last, __n);
00231 return pos == __last ? *(__last - 1) : *pos;
00232 }
00233
00234
00235 template<class _Val, class _Key, class _HF, class _Ex,
00236 class _Eq, class _All>
00237 class hashtable;
00238
00239 template<class _Val, class _Key, class _HF, class _Ex,
00240 class _Eq, class _All>
00241 bool
00242 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00243 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2);
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253 template<class _Val, class _Key, class _HashFcn,
00254 class _ExtractKey, class _EqualKey, class _Alloc>
00255 class hashtable
00256 {
00257 public:
00258 typedef _Key key_type;
00259 typedef _Val value_type;
00260 typedef _HashFcn hasher;
00261 typedef _EqualKey key_equal;
00262
00263 typedef size_t size_type;
00264 typedef ptrdiff_t difference_type;
00265 typedef value_type* pointer;
00266 typedef const value_type* const_pointer;
00267 typedef value_type& reference;
00268 typedef const value_type& const_reference;
00269
00270 hasher
00271 hash_funct() const
00272 { return _M_hash; }
00273
00274 key_equal
00275 key_eq() const
00276 { return _M_equals; }
00277
00278 private:
00279 typedef _Hashtable_node<_Val> _Node;
00280
00281 public:
00282 typedef typename _Alloc::template rebind<value_type>::other allocator_type;
00283 allocator_type
00284 get_allocator() const
00285 { return _M_node_allocator; }
00286
00287 private:
00288 typedef typename _Alloc::template rebind<_Node>::other _Node_Alloc;
00289 typedef typename _Alloc::template rebind<_Node*>::other _Nodeptr_Alloc;
00290 typedef vector<_Node*, _Nodeptr_Alloc> _Vector_type;
00291
00292 _Node_Alloc _M_node_allocator;
00293
00294 _Node*
00295 _M_get_node()
00296 { return _M_node_allocator.allocate(1); }
00297
00298 void
00299 _M_put_node(_Node* __p)
00300 { _M_node_allocator.deallocate(__p, 1); }
00301
00302 private:
00303 hasher _M_hash;
00304 key_equal _M_equals;
00305 _ExtractKey _M_get_key;
00306 _Vector_type _M_buckets;
00307 size_type _M_num_elements;
00308
00309 public:
00310 typedef _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00311 _EqualKey, _Alloc>
00312 iterator;
00313 typedef _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00314 _EqualKey, _Alloc>
00315 const_iterator;
00316
00317 friend struct
00318 _Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>;
00319
00320 friend struct
00321 _Hashtable_const_iterator<_Val, _Key, _HashFcn, _ExtractKey,
00322 _EqualKey, _Alloc>;
00323
00324 public:
00325 hashtable(size_type __n, const _HashFcn& __hf,
00326 const _EqualKey& __eql, const _ExtractKey& __ext,
00327 const allocator_type& __a = allocator_type())
00328 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
00329 _M_get_key(__ext), _M_buckets(__a), _M_num_elements(0)
00330 { _M_initialize_buckets(__n); }
00331
00332 hashtable(size_type __n, const _HashFcn& __hf,
00333 const _EqualKey& __eql,
00334 const allocator_type& __a = allocator_type())
00335 : _M_node_allocator(__a), _M_hash(__hf), _M_equals(__eql),
00336 _M_get_key(_ExtractKey()), _M_buckets(__a), _M_num_elements(0)
00337 { _M_initialize_buckets(__n); }
00338
00339 hashtable(const hashtable& __ht)
00340 : _M_node_allocator(__ht.get_allocator()), _M_hash(__ht._M_hash),
00341 _M_equals(__ht._M_equals), _M_get_key(__ht._M_get_key),
00342 _M_buckets(__ht.get_allocator()), _M_num_elements(0)
00343 { _M_copy_from(__ht); }
00344
00345 hashtable&
00346 operator= (const hashtable& __ht)
00347 {
00348 if (&__ht != this)
00349 {
00350 clear();
00351 _M_hash = __ht._M_hash;
00352 _M_equals = __ht._M_equals;
00353 _M_get_key = __ht._M_get_key;
00354 _M_copy_from(__ht);
00355 }
00356 return *this;
00357 }
00358
00359 ~hashtable()
00360 { clear(); }
00361
00362 size_type
00363 size() const
00364 { return _M_num_elements; }
00365
00366 size_type
00367 max_size() const
00368 { return size_type(-1); }
00369
00370 bool
00371 empty() const
00372 { return size() == 0; }
00373
00374 void
00375 swap(hashtable& __ht)
00376 {
00377 std::swap(_M_hash, __ht._M_hash);
00378 std::swap(_M_equals, __ht._M_equals);
00379 std::swap(_M_get_key, __ht._M_get_key);
00380 _M_buckets.swap(__ht._M_buckets);
00381 std::swap(_M_num_elements, __ht._M_num_elements);
00382 }
00383
00384 iterator
00385 begin()
00386 {
00387 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
00388 if (_M_buckets[__n])
00389 return iterator(_M_buckets[__n], this);
00390 return end();
00391 }
00392
00393 iterator
00394 end()
00395 { return iterator(0, this); }
00396
00397 const_iterator
00398 begin() const
00399 {
00400 for (size_type __n = 0; __n < _M_buckets.size(); ++__n)
00401 if (_M_buckets[__n])
00402 return const_iterator(_M_buckets[__n], this);
00403 return end();
00404 }
00405
00406 const_iterator
00407 end() const
00408 { return const_iterator(0, this); }
00409
00410 template<class _Vl, class _Ky, class _HF, class _Ex, class _Eq,
00411 class _Al>
00412 friend bool
00413 operator==(const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&,
00414 const hashtable<_Vl, _Ky, _HF, _Ex, _Eq, _Al>&);
00415
00416 public:
00417 size_type
00418 bucket_count() const
00419 { return _M_buckets.size(); }
00420
00421 size_type
00422 max_bucket_count() const
00423 { return __stl_prime_list[(int)_S_num_primes - 1]; }
00424
00425 size_type
00426 elems_in_bucket(size_type __bucket) const
00427 {
00428 size_type __result = 0;
00429 for (_Node* __n = _M_buckets[__bucket]; __n; __n = __n->_M_next)
00430 __result += 1;
00431 return __result;
00432 }
00433
00434 pair<iterator, bool>
00435 insert_unique(const value_type& __obj)
00436 {
00437 resize(_M_num_elements + 1);
00438 return insert_unique_noresize(__obj);
00439 }
00440
00441 iterator
00442 insert_equal(const value_type& __obj)
00443 {
00444 resize(_M_num_elements + 1);
00445 return insert_equal_noresize(__obj);
00446 }
00447
00448 pair<iterator, bool>
00449 insert_unique_noresize(const value_type& __obj);
00450
00451 iterator
00452 insert_equal_noresize(const value_type& __obj);
00453
00454 template<class _InputIterator>
00455 void
00456 insert_unique(_InputIterator __f, _InputIterator __l)
00457 { insert_unique(__f, __l, __iterator_category(__f)); }
00458
00459 template<class _InputIterator>
00460 void
00461 insert_equal(_InputIterator __f, _InputIterator __l)
00462 { insert_equal(__f, __l, __iterator_category(__f)); }
00463
00464 template<class _InputIterator>
00465 void
00466 insert_unique(_InputIterator __f, _InputIterator __l,
00467 input_iterator_tag)
00468 {
00469 for ( ; __f != __l; ++__f)
00470 insert_unique(*__f);
00471 }
00472
00473 template<class _InputIterator>
00474 void
00475 insert_equal(_InputIterator __f, _InputIterator __l,
00476 input_iterator_tag)
00477 {
00478 for ( ; __f != __l; ++__f)
00479 insert_equal(*__f);
00480 }
00481
00482 template<class _ForwardIterator>
00483 void
00484 insert_unique(_ForwardIterator __f, _ForwardIterator __l,
00485 forward_iterator_tag)
00486 {
00487 size_type __n = distance(__f, __l);
00488 resize(_M_num_elements + __n);
00489 for ( ; __n > 0; --__n, ++__f)
00490 insert_unique_noresize(*__f);
00491 }
00492
00493 template<class _ForwardIterator>
00494 void
00495 insert_equal(_ForwardIterator __f, _ForwardIterator __l,
00496 forward_iterator_tag)
00497 {
00498 size_type __n = distance(__f, __l);
00499 resize(_M_num_elements + __n);
00500 for ( ; __n > 0; --__n, ++__f)
00501 insert_equal_noresize(*__f);
00502 }
00503
00504 reference
00505 find_or_insert(const value_type& __obj);
00506
00507 iterator
00508 find(const key_type& __key)
00509 {
00510 size_type __n = _M_bkt_num_key(__key);
00511 _Node* __first;
00512 for (__first = _M_buckets[__n];
00513 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
00514 __first = __first->_M_next)
00515 { }
00516 return iterator(__first, this);
00517 }
00518
00519 const_iterator
00520 find(const key_type& __key) const
00521 {
00522 size_type __n = _M_bkt_num_key(__key);
00523 const _Node* __first;
00524 for (__first = _M_buckets[__n];
00525 __first && !_M_equals(_M_get_key(__first->_M_val), __key);
00526 __first = __first->_M_next)
00527 { }
00528 return const_iterator(__first, this);
00529 }
00530
00531 size_type
00532 count(const key_type& __key) const
00533 {
00534 const size_type __n = _M_bkt_num_key(__key);
00535 size_type __result = 0;
00536
00537 for (const _Node* __cur = _M_buckets[__n]; __cur;
00538 __cur = __cur->_M_next)
00539 if (_M_equals(_M_get_key(__cur->_M_val), __key))
00540 ++__result;
00541 return __result;
00542 }
00543
00544 pair<iterator, iterator>
00545 equal_range(const key_type& __key);
00546
00547 pair<const_iterator, const_iterator>
00548 equal_range(const key_type& __key) const;
00549
00550 size_type
00551 erase(const key_type& __key);
00552
00553 void
00554 erase(const iterator& __it);
00555
00556 void
00557 erase(iterator __first, iterator __last);
00558
00559 void
00560 erase(const const_iterator& __it);
00561
00562 void
00563 erase(const_iterator __first, const_iterator __last);
00564
00565 void
00566 resize(size_type __num_elements_hint);
00567
00568 void
00569 clear();
00570
00571 private:
00572 size_type
00573 _M_next_size(size_type __n) const
00574 { return __stl_next_prime(__n); }
00575
00576 void
00577 _M_initialize_buckets(size_type __n)
00578 {
00579 const size_type __n_buckets = _M_next_size(__n);
00580 _M_buckets.reserve(__n_buckets);
00581 _M_buckets.insert(_M_buckets.end(), __n_buckets, (_Node*) 0);
00582 _M_num_elements = 0;
00583 }
00584
00585 size_type
00586 _M_bkt_num_key(const key_type& __key) const
00587 { return _M_bkt_num_key(__key, _M_buckets.size()); }
00588
00589 size_type
00590 _M_bkt_num(const value_type& __obj) const
00591 { return _M_bkt_num_key(_M_get_key(__obj)); }
00592
00593 size_type
00594 _M_bkt_num_key(const key_type& __key, size_t __n) const
00595 { return _M_hash(__key) % __n; }
00596
00597 size_type
00598 _M_bkt_num(const value_type& __obj, size_t __n) const
00599 { return _M_bkt_num_key(_M_get_key(__obj), __n); }
00600
00601 _Node*
00602 _M_new_node(const value_type& __obj)
00603 {
00604 _Node* __n = _M_get_node();
00605 __n->_M_next = 0;
00606 try
00607 {
00608 this->get_allocator().construct(&__n->_M_val, __obj);
00609 return __n;
00610 }
00611 catch(...)
00612 {
00613 _M_put_node(__n);
00614 __throw_exception_again;
00615 }
00616 }
00617
00618 void
00619 _M_delete_node(_Node* __n)
00620 {
00621 this->get_allocator().destroy(&__n->_M_val);
00622 _M_put_node(__n);
00623 }
00624
00625 void
00626 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last);
00627
00628 void
00629 _M_erase_bucket(const size_type __n, _Node* __last);
00630
00631 void
00632 _M_copy_from(const hashtable& __ht);
00633 };
00634
00635 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
00636 class _All>
00637 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
00638 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00639 operator++()
00640 {
00641 const _Node* __old = _M_cur;
00642 _M_cur = _M_cur->_M_next;
00643 if (!_M_cur)
00644 {
00645 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
00646 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
00647 _M_cur = _M_ht->_M_buckets[__bucket];
00648 }
00649 return *this;
00650 }
00651
00652 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
00653 class _All>
00654 inline _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
00655 _Hashtable_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00656 operator++(int)
00657 {
00658 iterator __tmp = *this;
00659 ++*this;
00660 return __tmp;
00661 }
00662
00663 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
00664 class _All>
00665 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>&
00666 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00667 operator++()
00668 {
00669 const _Node* __old = _M_cur;
00670 _M_cur = _M_cur->_M_next;
00671 if (!_M_cur)
00672 {
00673 size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
00674 while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
00675 _M_cur = _M_ht->_M_buckets[__bucket];
00676 }
00677 return *this;
00678 }
00679
00680 template<class _Val, class _Key, class _HF, class _ExK, class _EqK,
00681 class _All>
00682 inline _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>
00683 _Hashtable_const_iterator<_Val, _Key, _HF, _ExK, _EqK, _All>::
00684 operator++(int)
00685 {
00686 const_iterator __tmp = *this;
00687 ++*this;
00688 return __tmp;
00689 }
00690
00691 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00692 bool
00693 operator==(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00694 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
00695 {
00696 typedef typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::_Node _Node;
00697
00698 if (__ht1._M_buckets.size() != __ht2._M_buckets.size())
00699 return false;
00700
00701 for (size_t __n = 0; __n < __ht1._M_buckets.size(); ++__n)
00702 {
00703 _Node* __cur1 = __ht1._M_buckets[__n];
00704 _Node* __cur2 = __ht2._M_buckets[__n];
00705
00706 for (; __cur1 && __cur2;
00707 __cur1 = __cur1->_M_next, __cur2 = __cur2->_M_next)
00708 { }
00709 if (__cur1 || __cur2)
00710 return false;
00711
00712 for (__cur1 = __ht1._M_buckets[__n] ; __cur1;
00713 __cur1 = __cur1->_M_next)
00714 {
00715 bool _found__cur1 = false;
00716 for (__cur2 = __ht2._M_buckets[__n];
00717 __cur2; __cur2 = __cur2->_M_next)
00718 {
00719 if (__cur1->_M_val == __cur2->_M_val)
00720 {
00721 _found__cur1 = true;
00722 break;
00723 }
00724 }
00725 if (!_found__cur1)
00726 return false;
00727 }
00728 }
00729 return true;
00730 }
00731
00732 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00733 inline bool
00734 operator!=(const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht1,
00735 const hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>& __ht2)
00736 { return !(__ht1 == __ht2); }
00737
00738 template<class _Val, class _Key, class _HF, class _Extract, class _EqKey,
00739 class _All>
00740 inline void
00741 swap(hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht1,
00742 hashtable<_Val, _Key, _HF, _Extract, _EqKey, _All>& __ht2)
00743 { __ht1.swap(__ht2); }
00744
00745 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00746 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator, bool>
00747 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00748 insert_unique_noresize(const value_type& __obj)
00749 {
00750 const size_type __n = _M_bkt_num(__obj);
00751 _Node* __first = _M_buckets[__n];
00752
00753 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00754 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00755 return pair<iterator, bool>(iterator(__cur, this), false);
00756
00757 _Node* __tmp = _M_new_node(__obj);
00758 __tmp->_M_next = __first;
00759 _M_buckets[__n] = __tmp;
00760 ++_M_num_elements;
00761 return pair<iterator, bool>(iterator(__tmp, this), true);
00762 }
00763
00764 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00765 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator
00766 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00767 insert_equal_noresize(const value_type& __obj)
00768 {
00769 const size_type __n = _M_bkt_num(__obj);
00770 _Node* __first = _M_buckets[__n];
00771
00772 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00773 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00774 {
00775 _Node* __tmp = _M_new_node(__obj);
00776 __tmp->_M_next = __cur->_M_next;
00777 __cur->_M_next = __tmp;
00778 ++_M_num_elements;
00779 return iterator(__tmp, this);
00780 }
00781
00782 _Node* __tmp = _M_new_node(__obj);
00783 __tmp->_M_next = __first;
00784 _M_buckets[__n] = __tmp;
00785 ++_M_num_elements;
00786 return iterator(__tmp, this);
00787 }
00788
00789 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00790 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::reference
00791 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00792 find_or_insert(const value_type& __obj)
00793 {
00794 resize(_M_num_elements + 1);
00795
00796 size_type __n = _M_bkt_num(__obj);
00797 _Node* __first = _M_buckets[__n];
00798
00799 for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
00800 if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
00801 return __cur->_M_val;
00802
00803 _Node* __tmp = _M_new_node(__obj);
00804 __tmp->_M_next = __first;
00805 _M_buckets[__n] = __tmp;
00806 ++_M_num_elements;
00807 return __tmp->_M_val;
00808 }
00809
00810 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00811 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator,
00812 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::iterator>
00813 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00814 equal_range(const key_type& __key)
00815 {
00816 typedef pair<iterator, iterator> _Pii;
00817 const size_type __n = _M_bkt_num_key(__key);
00818
00819 for (_Node* __first = _M_buckets[__n]; __first;
00820 __first = __first->_M_next)
00821 if (_M_equals(_M_get_key(__first->_M_val), __key))
00822 {
00823 for (_Node* __cur = __first->_M_next; __cur;
00824 __cur = __cur->_M_next)
00825 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
00826 return _Pii(iterator(__first, this), iterator(__cur, this));
00827 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
00828 if (_M_buckets[__m])
00829 return _Pii(iterator(__first, this),
00830 iterator(_M_buckets[__m], this));
00831 return _Pii(iterator(__first, this), end());
00832 }
00833 return _Pii(end(), end());
00834 }
00835
00836 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00837 pair<typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator,
00838 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::const_iterator>
00839 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00840 equal_range(const key_type& __key) const
00841 {
00842 typedef pair<const_iterator, const_iterator> _Pii;
00843 const size_type __n = _M_bkt_num_key(__key);
00844
00845 for (const _Node* __first = _M_buckets[__n]; __first;
00846 __first = __first->_M_next)
00847 {
00848 if (_M_equals(_M_get_key(__first->_M_val), __key))
00849 {
00850 for (const _Node* __cur = __first->_M_next; __cur;
00851 __cur = __cur->_M_next)
00852 if (!_M_equals(_M_get_key(__cur->_M_val), __key))
00853 return _Pii(const_iterator(__first, this),
00854 const_iterator(__cur, this));
00855 for (size_type __m = __n + 1; __m < _M_buckets.size(); ++__m)
00856 if (_M_buckets[__m])
00857 return _Pii(const_iterator(__first, this),
00858 const_iterator(_M_buckets[__m], this));
00859 return _Pii(const_iterator(__first, this), end());
00860 }
00861 }
00862 return _Pii(end(), end());
00863 }
00864
00865 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00866 typename hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::size_type
00867 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00868 erase(const key_type& __key)
00869 {
00870 const size_type __n = _M_bkt_num_key(__key);
00871 _Node* __first = _M_buckets[__n];
00872 size_type __erased = 0;
00873
00874 if (__first)
00875 {
00876 _Node* __cur = __first;
00877 _Node* __next = __cur->_M_next;
00878 while (__next)
00879 {
00880 if (_M_equals(_M_get_key(__next->_M_val), __key))
00881 {
00882 __cur->_M_next = __next->_M_next;
00883 _M_delete_node(__next);
00884 __next = __cur->_M_next;
00885 ++__erased;
00886 --_M_num_elements;
00887 }
00888 else
00889 {
00890 __cur = __next;
00891 __next = __cur->_M_next;
00892 }
00893 }
00894 if (_M_equals(_M_get_key(__first->_M_val), __key))
00895 {
00896 _M_buckets[__n] = __first->_M_next;
00897 _M_delete_node(__first);
00898 ++__erased;
00899 --_M_num_elements;
00900 }
00901 }
00902 return __erased;
00903 }
00904
00905 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00906 void hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00907 erase(const iterator& __it)
00908 {
00909 _Node* __p = __it._M_cur;
00910 if (__p)
00911 {
00912 const size_type __n = _M_bkt_num(__p->_M_val);
00913 _Node* __cur = _M_buckets[__n];
00914
00915 if (__cur == __p)
00916 {
00917 _M_buckets[__n] = __cur->_M_next;
00918 _M_delete_node(__cur);
00919 --_M_num_elements;
00920 }
00921 else
00922 {
00923 _Node* __next = __cur->_M_next;
00924 while (__next)
00925 {
00926 if (__next == __p)
00927 {
00928 __cur->_M_next = __next->_M_next;
00929 _M_delete_node(__next);
00930 --_M_num_elements;
00931 break;
00932 }
00933 else
00934 {
00935 __cur = __next;
00936 __next = __cur->_M_next;
00937 }
00938 }
00939 }
00940 }
00941 }
00942
00943 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00944 void
00945 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00946 erase(iterator __first, iterator __last)
00947 {
00948 size_type __f_bucket = __first._M_cur ? _M_bkt_num(__first._M_cur->_M_val)
00949 : _M_buckets.size();
00950
00951 size_type __l_bucket = __last._M_cur ? _M_bkt_num(__last._M_cur->_M_val)
00952 : _M_buckets.size();
00953
00954 if (__first._M_cur == __last._M_cur)
00955 return;
00956 else if (__f_bucket == __l_bucket)
00957 _M_erase_bucket(__f_bucket, __first._M_cur, __last._M_cur);
00958 else
00959 {
00960 _M_erase_bucket(__f_bucket, __first._M_cur, 0);
00961 for (size_type __n = __f_bucket + 1; __n < __l_bucket; ++__n)
00962 _M_erase_bucket(__n, 0);
00963 if (__l_bucket != _M_buckets.size())
00964 _M_erase_bucket(__l_bucket, __last._M_cur);
00965 }
00966 }
00967
00968 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00969 inline void
00970 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00971 erase(const_iterator __first, const_iterator __last)
00972 {
00973 erase(iterator(const_cast<_Node*>(__first._M_cur),
00974 const_cast<hashtable*>(__first._M_ht)),
00975 iterator(const_cast<_Node*>(__last._M_cur),
00976 const_cast<hashtable*>(__last._M_ht)));
00977 }
00978
00979 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00980 inline void
00981 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00982 erase(const const_iterator& __it)
00983 { erase(iterator(const_cast<_Node*>(__it._M_cur),
00984 const_cast<hashtable*>(__it._M_ht))); }
00985
00986 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
00987 void
00988 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
00989 resize(size_type __num_elements_hint)
00990 {
00991 const size_type __old_n = _M_buckets.size();
00992 if (__num_elements_hint > __old_n)
00993 {
00994 const size_type __n = _M_next_size(__num_elements_hint);
00995 if (__n > __old_n)
00996 {
00997 _Vector_type __tmp(__n, (_Node*)(0), _M_buckets.get_allocator());
00998 try
00999 {
01000 for (size_type __bucket = 0; __bucket < __old_n; ++__bucket)
01001 {
01002 _Node* __first = _M_buckets[__bucket];
01003 while (__first)
01004 {
01005 size_type __new_bucket = _M_bkt_num(__first->_M_val,
01006 __n);
01007 _M_buckets[__bucket] = __first->_M_next;
01008 __first->_M_next = __tmp[__new_bucket];
01009 __tmp[__new_bucket] = __first;
01010 __first = _M_buckets[__bucket];
01011 }
01012 }
01013 _M_buckets.swap(__tmp);
01014 }
01015 catch(...)
01016 {
01017 for (size_type __bucket = 0; __bucket < __tmp.size();
01018 ++__bucket)
01019 {
01020 while (__tmp[__bucket])
01021 {
01022 _Node* __next = __tmp[__bucket]->_M_next;
01023 _M_delete_node(__tmp[__bucket]);
01024 __tmp[__bucket] = __next;
01025 }
01026 }
01027 __throw_exception_again;
01028 }
01029 }
01030 }
01031 }
01032
01033 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
01034 void
01035 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01036 _M_erase_bucket(const size_type __n, _Node* __first, _Node* __last)
01037 {
01038 _Node* __cur = _M_buckets[__n];
01039 if (__cur == __first)
01040 _M_erase_bucket(__n, __last);
01041 else
01042 {
01043 _Node* __next;
01044 for (__next = __cur->_M_next;
01045 __next != __first;
01046 __cur = __next, __next = __cur->_M_next)
01047 ;
01048 while (__next != __last)
01049 {
01050 __cur->_M_next = __next->_M_next;
01051 _M_delete_node(__next);
01052 __next = __cur->_M_next;
01053 --_M_num_elements;
01054 }
01055 }
01056 }
01057
01058 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
01059 void
01060 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01061 _M_erase_bucket(const size_type __n, _Node* __last)
01062 {
01063 _Node* __cur = _M_buckets[__n];
01064 while (__cur != __last)
01065 {
01066 _Node* __next = __cur->_M_next;
01067 _M_delete_node(__cur);
01068 __cur = __next;
01069 _M_buckets[__n] = __cur;
01070 --_M_num_elements;
01071 }
01072 }
01073
01074 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
01075 void
01076 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01077 clear()
01078 {
01079 for (size_type __i = 0; __i < _M_buckets.size(); ++__i)
01080 {
01081 _Node* __cur = _M_buckets[__i];
01082 while (__cur != 0)
01083 {
01084 _Node* __next = __cur->_M_next;
01085 _M_delete_node(__cur);
01086 __cur = __next;
01087 }
01088 _M_buckets[__i] = 0;
01089 }
01090 _M_num_elements = 0;
01091 }
01092
01093 template<class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
01094 void
01095 hashtable<_Val, _Key, _HF, _Ex, _Eq, _All>::
01096 _M_copy_from(const hashtable& __ht)
01097 {
01098 _M_buckets.clear();
01099 _M_buckets.reserve(__ht._M_buckets.size());
01100 _M_buckets.insert(_M_buckets.end(), __ht._M_buckets.size(), (_Node*) 0);
01101 try
01102 {
01103 for (size_type __i = 0; __i < __ht._M_buckets.size(); ++__i) {
01104 const _Node* __cur = __ht._M_buckets[__i];
01105 if (__cur)
01106 {
01107 _Node* __local_copy = _M_new_node(__cur->_M_val);
01108 _M_buckets[__i] = __local_copy;
01109
01110 for (_Node* __next = __cur->_M_next;
01111 __next;
01112 __cur = __next, __next = __cur->_M_next)
01113 {
01114 __local_copy->_M_next = _M_new_node(__next->_M_val);
01115 __local_copy = __local_copy->_M_next;
01116 }
01117 }
01118 }
01119 _M_num_elements = __ht._M_num_elements;
01120 }
01121 catch(...)
01122 {
01123 clear();
01124 __throw_exception_again;
01125 }
01126 }
01127
01128 _GLIBCXX_END_NAMESPACE
01129
01130 #endif