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