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