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