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