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