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 #ifndef GNU_LIBSTDCXX_TR1_HASHTABLE_
00055 #define GNU_LIBSTDCXX_TR1_HASHTABLE_
00056
00057 #include <utility>
00058 #include <iterator>
00059 #include <cstddef>
00060 #include <cstdlib>
00061 #include <cmath>
00062 #include <bits/functexcept.h>
00063 #include <tr1/type_traits>
00064
00065
00066
00067
00068 namespace Internal {
00069 template <bool Flag, typename IfTrue, typename IfFalse> struct IF;
00070
00071 template <typename IfTrue, typename IfFalse>
00072 struct IF <true, IfTrue, IfFalse> { typedef IfTrue type; };
00073
00074 template <typename IfTrue, typename IfFalse>
00075 struct IF <false, IfTrue, IfFalse> { typedef IfFalse type; };
00076
00077
00078
00079
00080 template <class Iterator>
00081 inline typename std::iterator_traits<Iterator>::difference_type
00082 distance_fw (Iterator first, Iterator last, std::input_iterator_tag)
00083 {
00084 return 0;
00085 }
00086
00087 template <class Iterator>
00088 inline typename std::iterator_traits<Iterator>::difference_type
00089 distance_fw (Iterator first, Iterator last, std::forward_iterator_tag)
00090 {
00091 return std::distance(first, last);
00092 }
00093
00094 template <class Iterator>
00095 inline typename std::iterator_traits<Iterator>::difference_type
00096 distance_fw (Iterator first, Iterator last)
00097 {
00098 typedef typename std::iterator_traits<Iterator>::iterator_category tag;
00099 return distance_fw(first, last, tag());
00100 }
00101
00102 }
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113 namespace Internal {
00114
00115 template <typename Value, bool cache_hash_code> struct hash_node;
00116
00117 template <typename Value>
00118 struct hash_node<Value, true> {
00119 Value m_v;
00120 std::size_t hash_code;
00121 hash_node* m_next;
00122 };
00123
00124 template <typename Value>
00125 struct hash_node<Value, false> {
00126 Value m_v;
00127 hash_node* m_next;
00128 };
00129
00130
00131
00132
00133 template <typename Value, bool cache>
00134 struct node_iterator_base {
00135 node_iterator_base(hash_node<Value, cache>* p) : m_cur(p) { }
00136 void incr() { m_cur = m_cur->m_next; }
00137
00138 hash_node<Value, cache>* m_cur;
00139 };
00140
00141 template <typename Value, bool cache>
00142 inline bool operator== (const node_iterator_base<Value, cache>& x,
00143 const node_iterator_base<Value, cache>& y)
00144 {
00145 return x.m_cur == y.m_cur;
00146 }
00147
00148 template <typename Value, bool cache>
00149 inline bool operator!= (const node_iterator_base<Value, cache>& x,
00150 const node_iterator_base<Value, cache>& y)
00151 {
00152 return x.m_cur != y.m_cur;
00153 }
00154
00155 template <typename Value, bool is_const, bool cache>
00156 struct node_iterator : public node_iterator_base<Value, cache> {
00157 typedef Value value_type;
00158 typedef typename IF<is_const, const Value*, Value*>::type pointer;
00159 typedef typename IF<is_const, const Value&, Value&>::type reference;
00160 typedef std::ptrdiff_t difference_type;
00161 typedef std::forward_iterator_tag iterator_category;
00162
00163 explicit node_iterator (hash_node<Value, cache>* p = 0)
00164 : node_iterator_base<Value, cache>(p) { }
00165 node_iterator (const node_iterator<Value, false, cache>& x)
00166 : node_iterator_base<Value, cache>(x.m_cur) { }
00167
00168 reference operator*() const { return this->m_cur->m_v; }
00169 pointer operator->() const { return &this->m_cur->m_v; }
00170
00171 node_iterator& operator++() { this->incr(); return *this; }
00172 node_iterator operator++(int)
00173 { node_iterator tmp(*this); this->incr(); return tmp; }
00174 };
00175
00176 template <typename Value, bool cache>
00177 struct hashtable_iterator_base {
00178 hashtable_iterator_base(hash_node<Value, cache>* node,
00179 hash_node<Value, cache>** bucket)
00180 : m_cur_node (node), m_cur_bucket (bucket)
00181 { }
00182
00183 void incr() {
00184 m_cur_node = m_cur_node->m_next;
00185 if (!m_cur_node)
00186 m_incr_bucket();
00187 }
00188
00189 void m_incr_bucket();
00190
00191 hash_node<Value, cache>* m_cur_node;
00192 hash_node<Value, cache>** m_cur_bucket;
00193 };
00194
00195
00196
00197
00198
00199 template <typename Value, bool cache>
00200 void hashtable_iterator_base<Value, cache>::m_incr_bucket()
00201 {
00202 ++m_cur_bucket;
00203
00204
00205 while (!*m_cur_bucket)
00206 ++m_cur_bucket;
00207 m_cur_node = *m_cur_bucket;
00208 }
00209
00210 template <typename Value, bool cache>
00211 inline bool operator== (const hashtable_iterator_base<Value, cache>& x,
00212 const hashtable_iterator_base<Value, cache>& y)
00213 {
00214 return x.m_cur_node == y.m_cur_node;
00215 }
00216
00217 template <typename Value, bool cache>
00218 inline bool operator!= (const hashtable_iterator_base<Value, cache>& x,
00219 const hashtable_iterator_base<Value, cache>& y)
00220 {
00221 return x.m_cur_node != y.m_cur_node;
00222 }
00223
00224 template <typename Value, bool is_const, bool cache>
00225 struct hashtable_iterator : public hashtable_iterator_base<Value, cache>
00226 {
00227 typedef Value value_type;
00228 typedef typename IF<is_const, const Value*, Value*>::type pointer;
00229 typedef typename IF<is_const, const Value&, Value&>::type reference;
00230 typedef std::ptrdiff_t difference_type;
00231 typedef std::forward_iterator_tag iterator_category;
00232
00233 hashtable_iterator (hash_node<Value, cache>* p, hash_node<Value, cache>** b)
00234 : hashtable_iterator_base<Value, cache>(p, b) { }
00235 hashtable_iterator (hash_node<Value, cache>** b)
00236 : hashtable_iterator_base<Value, cache>(*b, b) { }
00237 hashtable_iterator (const hashtable_iterator<Value, false, cache>& x)
00238 : hashtable_iterator_base<Value, cache>(x.m_cur_node, x.m_cur_bucket) { }
00239
00240 reference operator*() const { return this->m_cur_node->m_v; }
00241 pointer operator->() const { return &this->m_cur_node->m_v; }
00242
00243 hashtable_iterator& operator++() { this->incr(); return *this; }
00244 hashtable_iterator operator++(int)
00245 { hashtable_iterator tmp(*this); this->incr(); return tmp; }
00246 };
00247
00248 }
00249
00250
00251
00252
00253
00254 namespace Internal {
00255
00256
00257 template <typename T>
00258 struct identity {
00259 T operator()(const T& t) const { return t; }
00260 };
00261
00262 template <typename Pair>
00263 struct extract1st {
00264 typename Pair::first_type operator()(const Pair& p) const { return p.first; }
00265 };
00266
00267
00268
00269 struct mod_range_hashing
00270 {
00271 typedef std::size_t first_argument_type;
00272 typedef std::size_t second_argument_type;
00273 typedef std::size_t result_type;
00274
00275 result_type operator() (first_argument_type r, second_argument_type N) const
00276 { return r % N; }
00277 };
00278
00279
00280
00281
00282
00283
00284 struct default_ranged_hash { };
00285
00286
00287
00288
00289 struct prime_rehash_policy
00290 {
00291 prime_rehash_policy (float z = 1.0);
00292
00293 float max_load_factor() const;
00294
00295
00296 std::size_t next_bkt (std::size_t n) const;
00297
00298
00299 std::size_t bkt_for_elements (std::size_t n) const;
00300
00301
00302
00303
00304
00305 std::pair<bool, std::size_t>
00306 need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const;
00307
00308 float m_max_load_factor;
00309 float m_growth_factor;
00310 mutable std::size_t m_next_resize;
00311 };
00312
00313
00314
00315
00316
00317
00318
00319
00320 struct lt {
00321 template <typename X, typename Y> bool operator()(X x, Y y) { return x < y; }
00322 };
00323
00324 template <int dummy>
00325 struct X {
00326 static const int n_primes = 256;
00327 static const unsigned long primes[n_primes + 1];
00328 };
00329
00330 template <int dummy>
00331 const int X<dummy>::n_primes;
00332
00333 template <int dummy>
00334 const unsigned long X<dummy>::primes[n_primes + 1] =
00335 {
00336 2ul, 3ul, 5ul, 7ul, 11ul, 13ul, 17ul, 19ul, 23ul, 29ul, 31ul,
00337 37ul, 41ul, 43ul, 47ul, 53ul, 59ul, 61ul, 67ul, 71ul, 73ul, 79ul,
00338 83ul, 89ul, 97ul, 103ul, 109ul, 113ul, 127ul, 137ul, 139ul, 149ul,
00339 157ul, 167ul, 179ul, 193ul, 199ul, 211ul, 227ul, 241ul, 257ul,
00340 277ul, 293ul, 313ul, 337ul, 359ul, 383ul, 409ul, 439ul, 467ul,
00341 503ul, 541ul, 577ul, 619ul, 661ul, 709ul, 761ul, 823ul, 887ul,
00342 953ul, 1031ul, 1109ul, 1193ul, 1289ul, 1381ul, 1493ul, 1613ul,
00343 1741ul, 1879ul, 2029ul, 2179ul, 2357ul, 2549ul, 2753ul, 2971ul,
00344 3209ul, 3469ul, 3739ul, 4027ul, 4349ul, 4703ul, 5087ul, 5503ul,
00345 5953ul, 6427ul, 6949ul, 7517ul, 8123ul, 8783ul, 9497ul, 10273ul,
00346 11113ul, 12011ul, 12983ul, 14033ul, 15173ul, 16411ul, 17749ul,
00347 19183ul, 20753ul, 22447ul, 24281ul, 26267ul, 28411ul, 30727ul,
00348 33223ul, 35933ul, 38873ul, 42043ul, 45481ul, 49201ul, 53201ul,
00349 57557ul, 62233ul, 67307ul, 72817ul, 78779ul, 85229ul, 92203ul,
00350 99733ul, 107897ul, 116731ul, 126271ul, 136607ul, 147793ul,
00351 159871ul, 172933ul, 187091ul, 202409ul, 218971ul, 236897ul,
00352 256279ul, 277261ul, 299951ul, 324503ul, 351061ul, 379787ul,
00353 410857ul, 444487ul, 480881ul, 520241ul, 562841ul, 608903ul,
00354 658753ul, 712697ul, 771049ul, 834181ul, 902483ul, 976369ul,
00355 1056323ul, 1142821ul, 1236397ul, 1337629ul, 1447153ul, 1565659ul,
00356 1693859ul, 1832561ul, 1982627ul, 2144977ul, 2320627ul, 2510653ul,
00357 2716249ul, 2938679ul, 3179303ul, 3439651ul, 3721303ul, 4026031ul,
00358 4355707ul, 4712381ul, 5098259ul, 5515729ul, 5967347ul, 6456007ul,
00359 6984629ul, 7556579ul, 8175383ul, 8844859ul, 9569143ul, 10352717ul,
00360 11200489ul, 12117689ul, 13109983ul, 14183539ul, 15345007ul,
00361 16601593ul, 17961079ul, 19431899ul, 21023161ul, 22744717ul,
00362 24607243ul, 26622317ul, 28802401ul, 31160981ul, 33712729ul,
00363 36473443ul, 39460231ul, 42691603ul, 46187573ul, 49969847ul,
00364 54061849ul, 58488943ul, 63278561ul, 68460391ul, 74066549ul,
00365 80131819ul, 86693767ul, 93793069ul, 101473717ul, 109783337ul,
00366 118773397ul, 128499677ul, 139022417ul, 150406843ul, 162723577ul,
00367 176048909ul, 190465427ul, 206062531ul, 222936881ul, 241193053ul,
00368 260944219ul, 282312799ul, 305431229ul, 330442829ul, 357502601ul,
00369 386778277ul, 418451333ul, 452718089ul, 489790921ul, 529899637ul,
00370 573292817ul, 620239453ul, 671030513ul, 725980837ul, 785430967ul,
00371 849749479ul, 919334987ul, 994618837ul, 1076067617ul, 1164186217ul,
00372 1259520799ul, 1362662261ul, 1474249943ul, 1594975441ul,
00373 1725587117ul, 1866894511ul, 2019773507ul, 2185171673ul,
00374 2364114217ul, 2557710269ul, 2767159799ul, 2993761039ul,
00375 3238918481ul, 3504151727ul, 3791104843ul, 4101556399ul,
00376 4294967291ul,
00377 4294967291ul
00378 };
00379
00380 inline prime_rehash_policy::prime_rehash_policy (float z)
00381 : m_max_load_factor(z),
00382 m_growth_factor (2.f),
00383 m_next_resize (0)
00384 { }
00385
00386 inline float prime_rehash_policy::max_load_factor() const
00387 {
00388 return m_max_load_factor;
00389 }
00390
00391
00392 inline std::size_t prime_rehash_policy::next_bkt (std::size_t n) const
00393 {
00394 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00395 const unsigned long* p = std::lower_bound (X<0>::primes, last, n);
00396 m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00397 return *p;
00398 }
00399
00400
00401
00402 inline std::size_t prime_rehash_policy::bkt_for_elements (std::size_t n) const
00403 {
00404 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00405 const float min_bkts = n / m_max_load_factor;
00406 const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
00407 m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00408 return *p;
00409 }
00410
00411
00412
00413
00414
00415
00416
00417
00418
00419
00420 inline std::pair<bool, std::size_t>
00421 prime_rehash_policy
00422 ::need_rehash (std::size_t n_bkt, std::size_t n_elt, std::size_t n_ins) const
00423 {
00424 if (n_elt + n_ins > m_next_resize) {
00425 float min_bkts = (float(n_ins) + float(n_elt)) / m_max_load_factor;
00426 if (min_bkts > n_bkt) {
00427 min_bkts = std::max (min_bkts, m_growth_factor * n_bkt);
00428 const unsigned long* const last = X<0>::primes + X<0>::n_primes;
00429 const unsigned long* p = std::lower_bound (X<0>::primes, last, min_bkts, lt());
00430 m_next_resize = static_cast<std::size_t>(std::ceil(*p * m_max_load_factor));
00431 return std::make_pair(true, *p);
00432 }
00433 else {
00434 m_next_resize = static_cast<std::size_t>(std::ceil(n_bkt * m_max_load_factor));
00435 return std::make_pair(false, 0);
00436 }
00437 }
00438 else
00439 return std::make_pair(false, 0);
00440 }
00441
00442 }
00443
00444
00445
00446
00447
00448
00449
00450
00451
00452
00453 namespace Internal {
00454
00455
00456
00457
00458
00459
00460
00461 template <typename K, typename V, typename Ex, bool unique, typename Hashtable>
00462 struct map_base { };
00463
00464 template <typename K, typename Pair, typename Hashtable>
00465 struct map_base<K, Pair, extract1st<Pair>, false, Hashtable>
00466 {
00467 typedef typename Pair::second_type mapped_type;
00468 };
00469
00470 template <typename K, typename Pair, typename Hashtable>
00471 struct map_base<K, Pair, extract1st<Pair>, true, Hashtable>
00472 {
00473 typedef typename Pair::second_type mapped_type;
00474 mapped_type& operator[](const K& k) {
00475 Hashtable* h = static_cast<Hashtable*>(this);
00476 typename Hashtable::iterator it = h->insert(std::make_pair(k, mapped_type())).first;
00477 return it->second;
00478 }
00479 };
00480
00481
00482
00483 template <typename RehashPolicy, typename Hashtable>
00484 struct rehash_base { };
00485
00486 template <typename Hashtable>
00487 struct rehash_base<prime_rehash_policy, Hashtable>
00488 {
00489 float max_load_factor() const {
00490 const Hashtable* This = static_cast<const Hashtable*>(this);
00491 return This->rehash_policy()->max_load_factor();
00492 }
00493
00494 void max_load_factor(float z) {
00495 Hashtable* This = static_cast<Hashtable*>(this);
00496 This->rehash_policy(prime_rehash_policy(z));
00497 }
00498 };
00499
00500
00501
00502
00503
00504
00505
00506
00507
00508
00509
00510
00511
00512
00513 template <typename Key, typename Value,
00514 typename ExtractKey, typename Equal,
00515 typename H1, typename H2, typename H,
00516 bool cache_hash_code>
00517 struct hash_code_base;
00518
00519
00520
00521 template <typename Key, typename Value,
00522 typename ExtractKey, typename Equal,
00523 typename H1, typename H2, typename H>
00524 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, false>
00525 {
00526 protected:
00527 hash_code_base (const ExtractKey& ex, const Equal& eq,
00528 const H1&, const H2&, const H& h)
00529 : m_extract(ex), m_eq(eq), m_ranged_hash(h) { }
00530
00531 typedef void* hash_code_t;
00532 hash_code_t m_hash_code (const Key& k) const { return 0; }
00533 std::size_t bucket_index (const Key& k, hash_code_t, std::size_t N) const
00534 { return m_ranged_hash (k, N); }
00535 std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
00536 return m_ranged_hash (m_extract (p->m_v), N);
00537 }
00538
00539 bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const
00540 { return m_eq (k, m_extract(n->m_v)); }
00541
00542 void store_code (hash_node<Value, false>*, hash_code_t) const { }
00543
00544 void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }
00545
00546 void m_swap(hash_code_base& x) {
00547 std::swap(m_extract, x.m_extract);
00548 std::swap(m_eq, x.m_eq);
00549 std::swap(m_ranged_hash, x.m_ranged_hash);
00550 }
00551
00552 protected:
00553 ExtractKey m_extract;
00554 Equal m_eq;
00555 H m_ranged_hash;
00556 };
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567 template <typename Key, typename Value,
00568 typename ExtractKey, typename Equal,
00569 typename H1, typename H2, typename H>
00570 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, H, true>;
00571
00572
00573
00574
00575
00576
00577 template <typename Key, typename Value,
00578 typename ExtractKey, typename Equal,
00579 typename H1, typename H2>
00580 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, false>
00581 {
00582 typedef H1 hasher;
00583 hasher hash_function() const { return m_h1; }
00584
00585 protected:
00586 hash_code_base (const ExtractKey& ex, const Equal& eq,
00587 const H1& h1, const H2& h2, const default_ranged_hash&)
00588 : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
00589
00590 typedef std::size_t hash_code_t;
00591 hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
00592 std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
00593 { return m_h2 (c, N); }
00594 std::size_t bucket_index (const hash_node<Value, false>* p, std::size_t N) const {
00595 return m_h2 (m_h1 (m_extract (p->m_v)), N);
00596 }
00597
00598 bool compare (const Key& k, hash_code_t, hash_node<Value, false>* n) const
00599 { return m_eq (k, m_extract(n->m_v)); }
00600
00601 void store_code (hash_node<Value, false>*, hash_code_t) const { }
00602
00603 void copy_code (hash_node<Value, false>*, const hash_node<Value, false>*) const { }
00604
00605 void m_swap(hash_code_base& x) {
00606 std::swap(m_extract, x.m_extract);
00607 std::swap(m_eq, x.m_eq);
00608 std::swap(m_h1, x.m_h1);
00609 std::swap(m_h2, x.m_h2);
00610 }
00611
00612 protected:
00613 ExtractKey m_extract;
00614 Equal m_eq;
00615 H1 m_h1;
00616 H2 m_h2;
00617 };
00618
00619
00620
00621
00622 template <typename Key, typename Value,
00623 typename ExtractKey, typename Equal,
00624 typename H1, typename H2>
00625 struct hash_code_base <Key, Value, ExtractKey, Equal, H1, H2, default_ranged_hash, true>
00626 {
00627 typedef H1 hasher;
00628 hasher hash_function() const { return m_h1; }
00629
00630 protected:
00631 hash_code_base (const ExtractKey& ex, const Equal& eq,
00632 const H1& h1, const H2& h2, const default_ranged_hash&)
00633 : m_extract(ex), m_eq(eq), m_h1(h1), m_h2(h2) { }
00634
00635 typedef std::size_t hash_code_t;
00636 hash_code_t m_hash_code (const Key& k) const { return m_h1(k); }
00637 std::size_t bucket_index (const Key&, hash_code_t c, std::size_t N) const
00638 { return m_h2 (c, N); }
00639
00640 std::size_t bucket_index (const hash_node<Value, true>* p, std::size_t N) const {
00641 return m_h2 (p->hash_code, N);
00642 }
00643
00644 bool compare (const Key& k, hash_code_t c, hash_node<Value, true>* n) const
00645 { return c == n->hash_code && m_eq (k, m_extract(n->m_v)); }
00646
00647 void store_code (hash_node<Value, true>* n, hash_code_t c) const
00648 { n->hash_code = c; }
00649
00650 void copy_code (hash_node<Value, true>* to, const hash_node<Value, true>* from) const
00651 { to->hash_code = from->hash_code; }
00652
00653 void m_swap(hash_code_base& x) {
00654 std::swap(m_extract, x.m_extract);
00655 std::swap(m_eq, x.m_eq);
00656 std::swap(m_h1, x.m_h1);
00657 std::swap(m_h2, x.m_h2);
00658 }
00659
00660 protected:
00661 ExtractKey m_extract;
00662 Equal m_eq;
00663 H1 m_h1;
00664 H2 m_h2;
00665 };
00666
00667 }
00668
00669 namespace std { namespace tr1 {
00670
00671
00672
00673
00674
00675
00676
00677
00678
00679
00680
00681
00682
00683
00684
00685
00686
00687
00688
00689
00690
00691
00692
00693
00694
00695
00696
00697
00698
00699
00700
00701
00702
00703
00704
00705
00706
00707
00708
00709
00710
00711
00712
00713
00714
00715
00716
00717
00718
00719
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729 template <typename Key, typename Value,
00730 typename Allocator,
00731 typename ExtractKey, typename Equal,
00732 typename H1, typename H2,
00733 typename H, typename RehashPolicy,
00734 bool cache_hash_code,
00735 bool mutable_iterators,
00736 bool unique_keys>
00737 class hashtable
00738 : public Internal::rehash_base<RehashPolicy, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >,
00739 public Internal::hash_code_base<Key, Value, ExtractKey, Equal, H1, H2, H, cache_hash_code>,
00740 public Internal::map_base<Key, Value, ExtractKey, unique_keys, hashtable<Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, cache_hash_code, mutable_iterators, unique_keys> >
00741 {
00742 public:
00743 typedef Allocator allocator_type;
00744 typedef Value value_type;
00745 typedef Key key_type;
00746 typedef Equal key_equal;
00747
00748
00749 typedef typename Allocator::difference_type difference_type;
00750 typedef typename Allocator::size_type size_type;
00751 typedef typename Allocator::reference reference;
00752 typedef typename Allocator::const_reference const_reference;
00753
00754 typedef Internal::node_iterator<value_type, !mutable_iterators, cache_hash_code>
00755 local_iterator;
00756 typedef Internal::node_iterator<value_type, true, cache_hash_code>
00757 const_local_iterator;
00758
00759 typedef Internal::hashtable_iterator<value_type, !mutable_iterators, cache_hash_code>
00760 iterator;
00761 typedef Internal::hashtable_iterator<value_type, true, cache_hash_code>
00762 const_iterator;
00763
00764 private:
00765 typedef Internal::hash_node<Value, cache_hash_code> node;
00766 typedef typename Allocator::template rebind<node>::other node_allocator_t;
00767 typedef typename Allocator::template rebind<node*>::other bucket_allocator_t;
00768
00769 private:
00770 node_allocator_t m_node_allocator;
00771 node** m_buckets;
00772 size_type m_bucket_count;
00773 size_type m_element_count;
00774 RehashPolicy m_rehash_policy;
00775
00776 node* m_allocate_node (const value_type& v);
00777 void m_deallocate_node (node* n);
00778 void m_deallocate_nodes (node**, size_type);
00779
00780 node** m_allocate_buckets (size_type n);
00781 void m_deallocate_buckets (node**, size_type n);
00782
00783 public:
00784 hashtable(size_type bucket_hint,
00785 const H1&, const H2&, const H&,
00786 const Equal&, const ExtractKey&,
00787 const allocator_type&);
00788
00789 template <typename InIter>
00790 hashtable(InIter first, InIter last,
00791 size_type bucket_hint,
00792 const H1&, const H2&, const H&,
00793 const Equal&, const ExtractKey&,
00794 const allocator_type&);
00795
00796 hashtable(const hashtable&);
00797 hashtable& operator=(const hashtable&);
00798 ~hashtable();
00799
00800 void swap(hashtable&);
00801
00802 public:
00803 iterator begin() {
00804 iterator i(m_buckets);
00805 if (!i.m_cur_node)
00806 i.m_incr_bucket();
00807 return i;
00808 }
00809
00810 const_iterator begin() const {
00811 const_iterator i(m_buckets);
00812 if (!i.m_cur_node)
00813 i.m_incr_bucket();
00814 return i;
00815 }
00816
00817 iterator end()
00818 { return iterator(m_buckets + m_bucket_count); }
00819 const_iterator end() const
00820 { return const_iterator(m_buckets + m_bucket_count); }
00821
00822 size_type size() const { return m_element_count; }
00823 bool empty() const { return size() == 0; }
00824
00825 allocator_type get_allocator() const { return m_node_allocator; }
00826 size_type max_size() const { return m_node_allocator.max_size(); }
00827
00828 public:
00829 size_type bucket_count() const
00830 { return m_bucket_count; }
00831 size_type max_bucket_count() const
00832 { return max_size(); }
00833 size_type bucket_size (size_type n) const
00834 { return std::distance(begin(n), end(n)); }
00835 size_type bucket (const key_type& k) const
00836 { return this->bucket_index (k, this->m_hash_code, this->m_bucket_count); }
00837
00838 local_iterator begin(size_type n)
00839 { return local_iterator(m_buckets[n]); }
00840 local_iterator end(size_type n)
00841 { return local_iterator(0); }
00842 const_local_iterator begin(size_type n) const
00843 { return const_local_iterator(m_buckets[n]); }
00844 const_local_iterator end(size_type n) const
00845 { return const_local_iterator(0); }
00846
00847 float load_factor() const
00848 { return static_cast<float>(size()) / static_cast<float>(bucket_count()); }
00849
00850
00851
00852
00853 const RehashPolicy& rehash_policy() const { return m_rehash_policy; }
00854 void rehash_policy (const RehashPolicy&);
00855
00856 public:
00857 iterator find(const key_type&);
00858 const_iterator find(const key_type& k) const;
00859 size_type count(const key_type& k) const;
00860 std::pair<iterator, iterator> equal_range(const key_type& k);
00861 std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
00862
00863 private:
00864
00865
00866
00867
00868 typedef typename Internal::IF<unique_keys, std::pair<iterator, bool>, iterator>::type
00869 Insert_Return_Type;
00870
00871 node* find_node (node* p, const key_type& k,
00872 typename hashtable::hash_code_t c) const;
00873
00874 std::pair<iterator, bool> insert (const value_type&, std::tr1::true_type);
00875 iterator insert (const value_type&, std::tr1::false_type);
00876
00877 public:
00878 Insert_Return_Type insert (const value_type& v)
00879 { return this->insert (v, std::tr1::integral_constant<bool, unique_keys>()); }
00880 Insert_Return_Type insert (const_iterator, const value_type& v)
00881 { return this->insert(v); }
00882
00883 template <typename InIter> void insert(InIter first, InIter last);
00884
00885 void erase(const_iterator);
00886 size_type erase(const key_type&);
00887 void erase(const_iterator, const_iterator);
00888 void clear();
00889
00890 public:
00891
00892 void rehash (size_type n);
00893
00894 private:
00895
00896 void m_rehash (size_type n);
00897 };
00898
00899
00900
00901
00902 template <typename K, typename V,
00903 typename A, typename Ex, typename Eq,
00904 typename H1, typename H2, typename H, typename RP,
00905 bool c, bool m, bool u>
00906 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node*
00907 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_node (const value_type& v)
00908 {
00909 node* n = m_node_allocator.allocate(1);
00910 try {
00911 get_allocator().construct(&n->m_v, v);
00912 n->m_next = 0;
00913 return n;
00914 }
00915 catch(...) {
00916 m_node_allocator.deallocate(n, 1);
00917 __throw_exception_again;
00918 }
00919 }
00920
00921 template <typename K, typename V,
00922 typename A, typename Ex, typename Eq,
00923 typename H1, typename H2, typename H, typename RP,
00924 bool c, bool m, bool u>
00925 void
00926 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_deallocate_node (node* n)
00927 {
00928 get_allocator().destroy(&n->m_v);
00929 m_node_allocator.deallocate(n, 1);
00930 }
00931
00932 template <typename K, typename V,
00933 typename A, typename Ex, typename Eq,
00934 typename H1, typename H2, typename H, typename RP,
00935 bool c, bool m, bool u>
00936 void
00937 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00938 ::m_deallocate_nodes (node** array, size_type n)
00939 {
00940 for (size_type i = 0; i < n; ++i) {
00941 node* p = array[i];
00942 while (p) {
00943 node* tmp = p;
00944 p = p->m_next;
00945 m_deallocate_node (tmp);
00946 }
00947 array[i] = 0;
00948 }
00949 }
00950
00951 template <typename K, typename V,
00952 typename A, typename Ex, typename Eq,
00953 typename H1, typename H2, typename H, typename RP,
00954 bool c, bool m, bool u>
00955 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node**
00956 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_allocate_buckets (size_type n)
00957 {
00958 bucket_allocator_t alloc(m_node_allocator);
00959
00960
00961
00962 node** p = alloc.allocate(n+1);
00963 std::fill(p, p+n, (node*) 0);
00964 p[n] = reinterpret_cast<node*>(0x1000);
00965 return p;
00966 }
00967
00968 template <typename K, typename V,
00969 typename A, typename Ex, typename Eq,
00970 typename H1, typename H2, typename H, typename RP,
00971 bool c, bool m, bool u>
00972 void
00973 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00974 ::m_deallocate_buckets (node** p, size_type n)
00975 {
00976 bucket_allocator_t alloc(m_node_allocator);
00977 alloc.deallocate(p, n+1);
00978 }
00979
00980 template <typename K, typename V,
00981 typename A, typename Ex, typename Eq,
00982 typename H1, typename H2, typename H, typename RP,
00983 bool c, bool m, bool u>
00984 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
00985 ::hashtable(size_type bucket_hint,
00986 const H1& h1, const H2& h2, const H& h,
00987 const Eq& eq, const Ex& exk,
00988 const allocator_type& a)
00989 : Internal::rehash_base<RP,hashtable> (),
00990 Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
00991 Internal::map_base<K,V,Ex,u,hashtable> (),
00992 m_node_allocator(a),
00993 m_bucket_count (0),
00994 m_element_count (0),
00995 m_rehash_policy ()
00996 {
00997 m_bucket_count = m_rehash_policy.next_bkt(bucket_hint);
00998 m_buckets = m_allocate_buckets (m_bucket_count);
00999 }
01000
01001 template <typename K, typename V,
01002 typename A, typename Ex, typename Eq,
01003 typename H1, typename H2, typename H, typename RP,
01004 bool c, bool m, bool u>
01005 template <typename InIter>
01006 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01007 ::hashtable(InIter f, InIter l,
01008 size_type bucket_hint,
01009 const H1& h1, const H2& h2, const H& h,
01010 const Eq& eq, const Ex& exk,
01011 const allocator_type& a)
01012 : Internal::rehash_base<RP,hashtable> (),
01013 Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (exk, eq, h1, h2, h),
01014 Internal::map_base<K,V,Ex,u,hashtable> (),
01015 m_node_allocator(a),
01016 m_bucket_count (0),
01017 m_element_count (0),
01018 m_rehash_policy ()
01019 {
01020 m_bucket_count = std::max(m_rehash_policy.next_bkt(bucket_hint),
01021 m_rehash_policy.bkt_for_elements(Internal::distance_fw(f, l)));
01022 m_buckets = m_allocate_buckets (m_bucket_count);
01023 try {
01024 for (; f != l; ++f)
01025 this->insert (*f);
01026 }
01027 catch(...) {
01028 clear();
01029 m_deallocate_buckets (m_buckets, m_bucket_count);
01030 __throw_exception_again;
01031 }
01032 }
01033
01034 template <typename K, typename V,
01035 typename A, typename Ex, typename Eq,
01036 typename H1, typename H2, typename H, typename RP,
01037 bool c, bool m, bool u>
01038 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01039 ::hashtable(const hashtable& ht)
01040 : Internal::rehash_base<RP,hashtable> (ht),
01041 Internal::hash_code_base<K,V,Ex,Eq,H1,H2,H,c> (ht),
01042 Internal::map_base<K,V,Ex,u,hashtable> (ht),
01043 m_node_allocator(ht.get_allocator()),
01044 m_bucket_count (ht.m_bucket_count),
01045 m_element_count (ht.m_element_count),
01046 m_rehash_policy (ht.m_rehash_policy)
01047 {
01048 m_buckets = m_allocate_buckets (m_bucket_count);
01049 try {
01050 for (size_t i = 0; i < ht.m_bucket_count; ++i) {
01051 node* n = ht.m_buckets[i];
01052 node** tail = m_buckets + i;
01053 while (n) {
01054 *tail = m_allocate_node(n->m_v);
01055 this->copy_code(*tail, n);
01056 tail = &((*tail)->m_next);
01057 n = n->m_next;
01058 }
01059 }
01060 }
01061 catch (...) {
01062 clear();
01063 m_deallocate_buckets (m_buckets, m_bucket_count);
01064 __throw_exception_again;
01065 }
01066 }
01067
01068 template <typename K, typename V,
01069 typename A, typename Ex, typename Eq,
01070 typename H1, typename H2, typename H, typename RP,
01071 bool c, bool m, bool u>
01072 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>&
01073 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::operator= (const hashtable& ht)
01074 {
01075 hashtable tmp(ht);
01076 this->swap(tmp);
01077 return *this;
01078 }
01079
01080 template <typename K, typename V,
01081 typename A, typename Ex, typename Eq,
01082 typename H1, typename H2, typename H, typename RP,
01083 bool c, bool m, bool u>
01084 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::~hashtable()
01085 {
01086 clear();
01087 m_deallocate_buckets(m_buckets, m_bucket_count);
01088 }
01089
01090 template <typename K, typename V,
01091 typename A, typename Ex, typename Eq,
01092 typename H1, typename H2, typename H, typename RP,
01093 bool c, bool m, bool u>
01094 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::swap (hashtable& x)
01095 {
01096
01097
01098
01099 Internal::hash_code_base<K, V, Ex, Eq, H1, H2, H, c>::m_swap(x);
01100
01101
01102
01103 std::swap (m_rehash_policy, x.m_rehash_policy);
01104 std::swap (m_buckets, x.m_buckets);
01105 std::swap (m_bucket_count, x.m_bucket_count);
01106 std::swap (m_element_count, x.m_element_count);
01107 }
01108
01109 template <typename K, typename V,
01110 typename A, typename Ex, typename Eq,
01111 typename H1, typename H2, typename H, typename RP,
01112 bool c, bool m, bool u>
01113 void
01114 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::rehash_policy (const RP& pol)
01115 {
01116 m_rehash_policy = pol;
01117 size_type n_bkt = pol.bkt_for_elements(m_element_count);
01118 if (n_bkt > m_bucket_count)
01119 m_rehash (n_bkt);
01120 }
01121
01122 template <typename K, typename V,
01123 typename A, typename Ex, typename Eq,
01124 typename H1, typename H2, typename H, typename RP,
01125 bool c, bool m, bool u>
01126 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator
01127 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k)
01128 {
01129 typename hashtable::hash_code_t code = this->m_hash_code (k);
01130 std::size_t n = this->bucket_index (k, code, this->bucket_count());
01131 node* p = find_node (m_buckets[n], k, code);
01132 return p ? iterator(p, m_buckets + n) : this->end();
01133 }
01134
01135 template <typename K, typename V,
01136 typename A, typename Ex, typename Eq,
01137 typename H1, typename H2, typename H, typename RP,
01138 bool c, bool m, bool u>
01139 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator
01140 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::find (const key_type& k) const
01141 {
01142 typename hashtable::hash_code_t code = this->m_hash_code (k);
01143 std::size_t n = this->bucket_index (k, code, this->bucket_count());
01144 node* p = find_node (m_buckets[n], k, code);
01145 return p ? const_iterator(p, m_buckets + n) : this->end();
01146 }
01147
01148 template <typename K, typename V,
01149 typename A, typename Ex, typename Eq,
01150 typename H1, typename H2, typename H, typename RP,
01151 bool c, bool m, bool u>
01152 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type
01153 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::count (const key_type& k) const
01154 {
01155 typename hashtable::hash_code_t code = this->m_hash_code (k);
01156 std::size_t n = this->bucket_index (k, code, this->bucket_count());
01157 size_t result = 0;
01158 for (node* p = m_buckets[n]; p ; p = p->m_next)
01159 if (this->compare (k, code, p))
01160 ++result;
01161 return result;
01162 }
01163
01164 template <typename K, typename V,
01165 typename A, typename Ex, typename Eq,
01166 typename H1, typename H2, typename H, typename RP,
01167 bool c, bool m, bool u>
01168 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator,
01169 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator>
01170 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k)
01171 {
01172 typename hashtable::hash_code_t code = this->m_hash_code (k);
01173 std::size_t n = this->bucket_index (k, code, this->bucket_count());
01174 node** head = m_buckets + n;
01175 node* p = find_node (*head, k, code);
01176
01177 if (p) {
01178 node* p1 = p->m_next;
01179 for (; p1 ; p1 = p1->m_next)
01180 if (!this->compare (k, code, p1))
01181 break;
01182 iterator first(p, head);
01183 iterator last(p1, head);
01184 if (!p1)
01185 last.m_incr_bucket();
01186 return std::make_pair(first, last);
01187 }
01188 else
01189 return std::make_pair (this->end(), this->end());
01190 }
01191
01192 template <typename K, typename V,
01193 typename A, typename Ex, typename Eq,
01194 typename H1, typename H2, typename H, typename RP,
01195 bool c, bool m, bool u>
01196 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator,
01197 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::const_iterator>
01198 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::equal_range (const key_type& k) const
01199 {
01200 typename hashtable::hash_code_t code = this->m_hash_code (k);
01201 std::size_t n = this->bucket_index (k, code, this->bucket_count());
01202 node** head = m_buckets + n;
01203 node* p = find_node (*head, k, code);
01204
01205 if (p) {
01206 node* p1 = p->m_next;
01207 for (; p1 ; p1 = p1->m_next)
01208 if (!this->compare (k, code, p1))
01209 break;
01210 const_iterator first(p, head);
01211 const_iterator last(p1, head);
01212 if (!p1)
01213 last.m_incr_bucket();
01214 return std::make_pair(first, last);
01215 }
01216 else
01217 return std::make_pair (this->end(), this->end());
01218 }
01219
01220
01221
01222 template <typename K, typename V,
01223 typename A, typename Ex, typename Eq,
01224 typename H1, typename H2, typename H, typename RP,
01225 bool c, bool m, bool u>
01226 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::node*
01227 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01228 ::find_node (node* p, const key_type& k,
01229 typename hashtable::hash_code_t code) const
01230 {
01231 for ( ; p ; p = p->m_next)
01232 if (this->compare (k, code, p))
01233 return p;
01234 return false;
01235 }
01236
01237
01238 template <typename K, typename V,
01239 typename A, typename Ex, typename Eq,
01240 typename H1, typename H2, typename H, typename RP,
01241 bool c, bool m, bool u>
01242 std::pair<typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator, bool>
01243 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01244 ::insert (const value_type& v, std::tr1::true_type)
01245 {
01246 const key_type& k = this->m_extract(v);
01247 typename hashtable::hash_code_t code = this->m_hash_code (k);
01248 size_type n = this->bucket_index (k, code, m_bucket_count);
01249
01250 if (node* p = find_node (m_buckets[n], k, code))
01251 return std::make_pair(iterator(p, m_buckets + n), false);
01252
01253 std::pair<bool, size_t> do_rehash
01254 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
01255
01256
01257
01258 node* new_node = m_allocate_node (v);
01259
01260 try {
01261 if (do_rehash.first) {
01262 n = this->bucket_index (k, code, do_rehash.second);
01263 m_rehash(do_rehash.second);
01264 }
01265
01266 new_node->m_next = m_buckets[n];
01267 this->store_code(new_node, code);
01268 m_buckets[n] = new_node;
01269 ++m_element_count;
01270 return std::make_pair(iterator (new_node, m_buckets + n), true);
01271 }
01272 catch (...) {
01273 m_deallocate_node (new_node);
01274 __throw_exception_again;
01275 }
01276 }
01277
01278
01279 template <typename K, typename V,
01280 typename A, typename Ex, typename Eq,
01281 typename H1, typename H2, typename H, typename RP,
01282 bool c, bool m, bool u>
01283 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::iterator
01284 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01285 ::insert (const value_type& v, std::tr1::false_type)
01286 {
01287 std::pair<bool, std::size_t> do_rehash
01288 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, 1);
01289 if (do_rehash.first)
01290 m_rehash(do_rehash.second);
01291
01292 const key_type& k = this->m_extract(v);
01293 typename hashtable::hash_code_t code = this->m_hash_code (k);
01294 size_type n = this->bucket_index (k, code, m_bucket_count);
01295
01296 node* new_node = m_allocate_node (v);
01297 node* prev = find_node (m_buckets[n], k, code);
01298 if (prev) {
01299 new_node->m_next = prev->m_next;
01300 prev->m_next = new_node;
01301 }
01302 else {
01303 new_node->m_next = m_buckets[n];
01304 m_buckets[n] = new_node;
01305 }
01306 this->store_code(new_node, code);
01307
01308 ++m_element_count;
01309 return iterator (new_node, m_buckets + n);
01310 }
01311
01312 template <typename K, typename V,
01313 typename A, typename Ex, typename Eq,
01314 typename H1, typename H2, typename H, typename RP,
01315 bool c, bool m, bool u>
01316 template <typename InIter>
01317 void
01318 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::insert(InIter first, InIter last)
01319 {
01320 size_type n_elt = Internal::distance_fw (first, last);
01321 std::pair<bool, std::size_t> do_rehash
01322 = m_rehash_policy.need_rehash(m_bucket_count, m_element_count, n_elt);
01323 if (do_rehash.first)
01324 m_rehash(do_rehash.second);
01325
01326 for (; first != last; ++first)
01327 this->insert (*first);
01328 }
01329
01330
01331
01332
01333
01334 template <typename K, typename V,
01335 typename A, typename Ex, typename Eq,
01336 typename H1, typename H2, typename H, typename RP,
01337 bool c, bool m, bool u>
01338 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase (const_iterator i)
01339 {
01340 node* p = i.m_cur_node;
01341 node* cur = *i.m_cur_bucket;
01342 if (cur == p)
01343 *i.m_cur_bucket = cur->m_next;
01344 else {
01345 node* next = cur->m_next;
01346 while (next != p) {
01347 cur = next;
01348 next = cur->m_next;
01349 }
01350 cur->m_next = next->m_next;
01351 }
01352
01353 m_deallocate_node (p);
01354 --m_element_count;
01355 }
01356
01357 template <typename K, typename V,
01358 typename A, typename Ex, typename Eq,
01359 typename H1, typename H2, typename H, typename RP,
01360 bool c, bool m, bool u>
01361 typename hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::size_type
01362 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::erase(const key_type& k)
01363 {
01364 typename hashtable::hash_code_t code = this->m_hash_code (k);
01365 size_type n = this->bucket_index (k, code, m_bucket_count);
01366 size_type result = 0;
01367
01368 node** slot = m_buckets + n;
01369 while (*slot && ! this->compare (k, code, *slot))
01370 slot = &((*slot)->m_next);
01371
01372 while (*slot && this->compare (k, code, *slot)) {
01373 node* n = *slot;
01374 *slot = n->m_next;
01375 m_deallocate_node (n);
01376 --m_element_count;
01377 ++result;
01378 }
01379
01380 return result;
01381 }
01382
01383
01384
01385
01386 template <typename K, typename V,
01387 typename A, typename Ex, typename Eq,
01388 typename H1, typename H2, typename H, typename RP,
01389 bool c, bool m, bool u>
01390 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>
01391 ::erase(const_iterator first, const_iterator last)
01392 {
01393 while (first != last) {
01394 const_iterator next = first;
01395 ++next;
01396 this->erase(first);
01397 first = next;
01398 }
01399 }
01400
01401 template <typename K, typename V,
01402 typename A, typename Ex, typename Eq,
01403 typename H1, typename H2, typename H, typename RP,
01404 bool c, bool m, bool u>
01405 void hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::clear()
01406 {
01407 m_deallocate_nodes (m_buckets, m_bucket_count);
01408 m_element_count = 0;
01409 }
01410
01411 template <typename K, typename V,
01412 typename A, typename Ex, typename Eq,
01413 typename H1, typename H2, typename H, typename RP,
01414 bool c, bool m, bool u>
01415 void
01416 hashtable<K,V,A,Ex,Eq,H1,H2,H,RP,c,m,u>::m_rehash (size_type N)
01417 {
01418 node** new_array = m_allocate_buckets (N);
01419 try {
01420 for (size_type i = 0; i < m_bucket_count; ++i)
01421 while (node* p = m_buckets[i]) {
01422 size_type new_index = this->bucket_index (p, N);
01423 m_buckets[i] = p->m_next;
01424 p->m_next = new_array[new_index];
01425 new_array[new_index] = p;
01426 }
01427 m_deallocate_buckets (m_buckets, m_bucket_count);
01428 m_bucket_count = N;
01429 m_buckets = new_array;
01430 }
01431 catch (...) {
01432
01433
01434
01435
01436 m_deallocate_nodes (new_array, N);
01437 m_deallocate_buckets (new_array, N);
01438 m_deallocate_nodes (m_buckets, m_bucket_count);
01439 m_element_count = 0;
01440 __throw_exception_again;
01441 }
01442 }
01443
01444 } }
01445
01446 #endif
01447