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