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