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