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