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
00063
00064
00065
00066
00067
00068 #ifndef itk_emulation_hashtable_h
00069 #define itk_emulation_hashtable_h
00070
00071 #if !defined(__GNUC__) || !((__GNUC__==3) && (__GNUC_MINOR__>=1))
00072
00076 #include "itkMacro.h"
00077 #include <iostream>
00078 #include "itk_alloc.h"
00079 #include <vector>
00080 #include <utility>
00081 #include <memory>
00082 #include "vcl_compiler.h"
00083 #include <functional>
00084 #include <algorithm>
00085 #include <iterator>
00086
00087
00088 namespace itk
00089 {
00090 template <class Key> struct hash { };
00091
00092 inline size_t hash_string(const char* s)
00093 {
00094 unsigned long h = 0;
00095 for ( ; *s; ++s)
00096 h = 5*h + *s;
00097
00098 return size_t(h);
00099 }
00100
00101 template<>
00102 struct hash<char*>
00103 {
00104 size_t operator()(const char* s) const { return hash_string(s); }
00105 };
00106
00107 template<>
00108 struct hash<const char*>
00109 {
00110 size_t operator()(const char* s) const { return hash_string(s); }
00111 };
00112
00113 template<>
00114 struct hash<char> {
00115 size_t operator()(char x) const { return x; }
00116 };
00117
00118 template<>
00119 struct hash<unsigned char> {
00120 size_t operator()(unsigned char x) const { return x; }
00121 };
00122
00123 template<>
00124 struct hash<signed char> {
00125 size_t operator()(unsigned char x) const { return x; }
00126 };
00127
00128 template<>
00129 struct hash<short> {
00130 size_t operator()(short x) const { return x; }
00131 };
00132
00133 template<>
00134 struct hash<unsigned short> {
00135 size_t operator()(unsigned short x) const { return x; }
00136 };
00137
00138 template<>
00139 struct hash<int> {
00140 size_t operator()(int x) const { return x; }
00141 };
00142
00143 template<>
00144 struct hash<unsigned int> {
00145 size_t operator()(unsigned int x) const { return x; }
00146 };
00147
00148 template<>
00149 struct hash<long> {
00150 size_t operator()(long x) const { return x; }
00151 };
00152
00153 template<>
00154 struct hash<unsigned long> {
00155 size_t operator()(unsigned long x) const { return x; }
00156 };
00157
00158 template <class Value>
00159 struct hashtable_node
00160 {
00161 typedef hashtable_node<Value> self;
00162 self* next;
00163 Value val;
00164 };
00165
00166 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey , VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char>)>
00167 class hashtable;
00168
00169 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00170 struct hashtable_iterator;
00171
00172 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00173 struct hashtable_const_iterator;
00174
00175 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00176 struct hashtable_iterator
00177 {
00178 typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00179 hash_table;
00180 typedef hashtable_iterator<Value, Key, HashFcn,
00181 ExtractKey, EqualKey, Alloc>
00182 iterator;
00183 typedef hashtable_const_iterator<Value, Key, HashFcn,
00184 ExtractKey, EqualKey, Alloc>
00185 const_iterator;
00186 typedef hashtable_node<Value> node;
00187 typedef size_t size_type;
00188 typedef Value& reference;
00189 typedef const Value& const_reference;
00190
00191 node* cur;
00192 hash_table* ht;
00193
00194 hashtable_iterator(node* n, hash_table* tab) : cur(n), ht(tab) {}
00195 hashtable_iterator() {}
00196 reference operator*() const {
00197 return cur->val;
00198 }
00199 IUEi_STL_INLINE iterator& operator++();
00200 IUEi_STL_INLINE iterator operator++(int);
00201 bool operator==(const iterator& it) const {
00202 return cur == it.cur;
00203 }
00204 bool operator!=(const iterator& it) const {
00205 return cur != it.cur;
00206 }
00207 };
00208
00209
00210 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00211 struct hashtable_const_iterator
00212 {
00213 typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00214 hash_table;
00215 typedef hashtable_iterator<Value, Key, HashFcn,
00216 ExtractKey, EqualKey, Alloc> iterator;
00217 typedef hashtable_const_iterator<Value, Key, HashFcn,
00218 ExtractKey, EqualKey, Alloc> const_iterator;
00219 typedef hashtable_node<Value> node;
00220 typedef size_t size_type;
00221 typedef Value& reference;
00222 typedef const Value& const_reference;
00223
00224 const node* cur;
00225 const hash_table* ht;
00226
00227 hashtable_const_iterator(const node* n, const hash_table* tab) : cur(n), ht(tab) {}
00228 hashtable_const_iterator() {}
00229 hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
00230
00231 const_reference operator*() const {
00232 return cur->val;
00233 }
00234 IUEi_STL_INLINE const_iterator& operator++();
00235 IUEi_STL_INLINE const_iterator operator++(int);
00236 bool operator==(const const_iterator& it) const {
00237 return cur == it.cur;
00238 }
00239 bool operator!=(const const_iterator& it) const {
00240 return cur != it.cur;
00241 }
00242 };
00243
00244
00245
00246 enum { num_primes = 28 };
00247
00248 #if ( __STL_STATIC_TEMPLATE_DATA > 0 ) && ! defined (WIN32)
00249 # define prime_list prime<false>::list_
00250 template <bool dummy>
00251 struct prime {
00252 public:
00253 static const unsigned long list_[];
00254 };
00255 static const unsigned long prime_list_dummy[num_primes] =
00256 # else
00257 # if ( __STL_WEAK_ATTRIBUTE > 0 )
00258 extern const unsigned long prime_list[num_primes] __attribute__((weak)) =
00259 # else
00260
00261 static const unsigned long prime_list[num_primes] =
00262 # endif
00263 #endif
00264 {
00265 53, 97, 193, 389, 769,
00266 1543, 3079, 6151, 12289, 24593,
00267 49157, 98317, 196613, 393241, 786433,
00268 1572869, 3145739, 6291469, 12582917, 25165843,
00269 50331653, 100663319, 201326611, 402653189, 805306457,
00270 1610612741, 3221225473U, 4294967291U
00271 };
00272
00273 inline unsigned long next_prime(unsigned long n)
00274 {
00275 const unsigned long* first = prime_list;
00276 const unsigned long* last = prime_list;
00277 last += num_primes;
00278 const unsigned long* pos = std::lower_bound(first, last, n);
00279 return pos == last ? *(last - 1) : *pos;
00280 }
00281
00282 template <class Value, class Alloc>
00283 class hashtable_base
00284 {
00285 private:
00286 typedef Value value_type;
00287 typedef size_t size_type;
00288 typedef hashtable_node<Value> node;
00289 typedef itk_simple_alloc<node, Alloc> node_allocator;
00290 public:
00291 typedef std::vector<VCL_SUNPRO_ALLOCATOR_HACK(node*) > buckets_type ;
00292 buckets_type buckets;
00293 size_type num_elements;
00294 protected:
00295 IUEi_STL_INLINE void clear();
00296
00297 node* new_node(const value_type& obj)
00298 {
00299 node* n = node_allocator::allocate();
00300 try {
00301 new (&(n->val)) value_type(obj);
00302 }
00303 catch (...) {
00304 node_allocator::deallocate(n);
00305 throw "";
00306 }
00307 n->next = 0;
00308 return n;
00309 }
00310
00311 void delete_node(node* n)
00312 {
00313 #define vcli_destroy(T, p) ((T*)p)->~T()
00314 vcli_destroy(Value, &(n->val));
00315 #undef vcli_destroy
00316 node_allocator::deallocate(n);
00317 }
00318
00319 IUEi_STL_INLINE void copy_from(const hashtable_base<Value,Alloc>& ht);
00320
00321 public:
00322 hashtable_base() : num_elements(0) { }
00323
00324 ~hashtable_base() { clear(); }
00325 };
00326
00327
00328
00329 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class hashtable;
00330 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00331 bool operator== (hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&,hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&);
00332
00333 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00334 class hashtable : protected hashtable_base<Value, Alloc>
00335 {
00336 typedef hashtable_base<Value, Alloc> super;
00337 typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> self;
00338 public:
00339 typedef Key key_type;
00340 typedef Value value_type;
00341 typedef HashFcn hasher;
00342 typedef EqualKey key_equal;
00343
00344 typedef size_t size_type;
00345 typedef ptrdiff_t difference_type;
00346 typedef value_type* pointer;
00347 typedef const value_type* const_pointer;
00348 typedef value_type& reference;
00349 typedef const value_type& const_reference;
00350
00351 hasher hash_funct() const { return hashfun; }
00352 key_equal key_eq() const { return equals; }
00353
00354 private:
00355 hasher hashfun;
00356 key_equal equals;
00357 ExtractKey get_key;
00358
00359 typedef hashtable_node<Value> node;
00360 typedef itk_simple_alloc<node, Alloc> node_allocator;
00361
00362 public:
00363 typedef hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
00364 typedef hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> const_iterator;
00365 friend struct
00366 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
00367 friend struct
00368 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
00369
00370 public:
00371 hashtable(size_type n,
00372 const HashFcn& hf,
00373 const EqualKey& eql,
00374 const ExtractKey& ext)
00375 : hashfun(hf), equals(eql), get_key(ext) {
00376 initialize_buckets(n);
00377 }
00378
00379 hashtable(size_type n,
00380 const HashFcn& hf,
00381 const EqualKey& eql)
00382 : hashfun(hf), equals(eql), get_key(ExtractKey()) {
00383 initialize_buckets(n);
00384 }
00385
00386 hashtable(const self& ht)
00387 : hashfun(ht.hashfun), equals(ht.equals), get_key(ht.get_key) {
00388 copy_from(ht);
00389 }
00390
00391 self& operator= (const self& ht)
00392 {
00393 if (&ht != this) {
00394 hashfun = ht.hashfun;
00395 equals = ht.equals;
00396 get_key = ht.get_key;
00397 clear();
00398 buckets.clear();
00399 copy_from(ht);
00400 }
00401 return *this;
00402 }
00403
00404 ~hashtable() {}
00405
00406 size_type size() const { return num_elements; }
00407 size_type max_size() const { return size_type(-1); }
00408 bool empty() const { return size() == 0; }
00409
00410 void swap(self& ht)
00411 {
00412 std::swap(hashfun, ht.hashfun);
00413 std::swap(equals, ht.equals);
00414 std::swap(get_key, ht.get_key);
00415 buckets.swap(ht.buckets);
00416 std::swap(num_elements, ht.num_elements);
00417 }
00418
00419 iterator begin()
00420 {
00421 for (size_type n = 0; n < buckets.size(); ++n)
00422 if (buckets[n])
00423 return iterator(buckets[n], this);
00424 return end();
00425 }
00426
00427 iterator end() { return iterator((node*)0, this); }
00428
00429 const_iterator begin() const
00430 {
00431 for (size_type n = 0; n < buckets.size(); ++n)
00432 if (buckets[n])
00433 return const_iterator(buckets[n], this);
00434 return end();
00435 }
00436
00437 const_iterator end() const { return const_iterator((node*)0, this); }
00438
00439
00440
00441 friend bool operator== VCL_NULL_TMPL_ARGS (const self&,const self&);
00442 public:
00443
00444 size_type bucket_count() const { return buckets.size(); }
00445
00446 size_type max_bucket_count() const
00447 { return prime_list[num_primes - 1]; }
00448
00449 size_type elems_in_bucket(size_type bucket) const
00450 {
00451 size_type result = 0;
00452 for (node* cur = buckets[bucket]; cur; cur = cur->next)
00453 result += 1;
00454 return result;
00455 }
00456
00457 std::pair<iterator, bool> insert_unique(const value_type& obj)
00458 {
00459 resize(num_elements + 1);
00460 return insert_unique_noresize(obj);
00461 }
00462
00463 iterator insert_equal(const value_type& obj)
00464 {
00465 resize(num_elements + 1);
00466 return insert_equal_noresize(obj);
00467 }
00468
00469 IUEi_STL_INLINE std::pair<iterator, bool> insert_unique_noresize(const value_type& obj);
00470 IUEi_STL_INLINE iterator insert_equal_noresize(const value_type& obj);
00471
00472 void insert_unique(const value_type* f, const value_type* l)
00473 {
00474 size_type n = l - f;
00475 resize(num_elements + n);
00476 for ( ; n > 0; --n)
00477 insert_unique_noresize(*f++);
00478 }
00479
00480 void insert_equal(const value_type* f, const value_type* l)
00481 {
00482 size_type n = l - f;
00483 resize(num_elements + n);
00484 for ( ; n > 0; --n)
00485 insert_equal_noresize(*f++);
00486 }
00487
00488 void insert_unique(const_iterator f, const_iterator l)
00489 {
00490 size_type n = 0;
00491 std::distance(f, l, n);
00492 resize(num_elements + n);
00493 for ( ; n > 0; --n)
00494 insert_unique_noresize(*f++);
00495 }
00496
00497 void insert_equal(const_iterator f, const_iterator l)
00498 {
00499 size_type n = 0;
00500 std::distance(f, l, n);
00501 resize(num_elements + n);
00502 for ( ; n > 0; --n)
00503 insert_equal_noresize(*f++);
00504 }
00505
00506 IUEi_STL_INLINE reference find_or_insert(const value_type& obj);
00507
00508 iterator find(const key_type& key)
00509 {
00510 size_type n = bkt_num_key(key);
00511 node* first;
00512 for ( first = buckets[n];
00513 first && !equals(get_key(first->val), key);
00514 first = first->next)
00515 {}
00516 return iterator(first, this);
00517 }
00518
00519 const_iterator find(const key_type& key) const
00520 {
00521 size_type n = bkt_num_key(key);
00522 const node* first;
00523 for ( first = buckets[n];
00524 first && !equals(get_key(first->val), key);
00525 first = first->next)
00526 {}
00527 return const_iterator(first, this);
00528 }
00529
00530 size_type count(const key_type& key) const
00531 {
00532 const size_type n = bkt_num_key(key);
00533 size_type result = 0;
00534
00535 for (const node* cur = buckets[n]; cur; cur = cur->next)
00536 if (equals(get_key(cur->val), key))
00537 ++result;
00538 return result;
00539 }
00540
00541 IUEi_STL_INLINE std::pair<iterator, iterator> equal_range(const key_type& key);
00542 IUEi_STL_INLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
00543
00544 IUEi_STL_INLINE size_type erase(const key_type& key);
00545 IUEi_STL_INLINE void erase(const iterator& it);
00546 IUEi_STL_INLINE void erase(iterator first, iterator last);
00547
00548 IUEi_STL_INLINE void erase(const const_iterator& it);
00549 IUEi_STL_INLINE void erase(const_iterator first, const_iterator last);
00550
00551 IUEi_STL_INLINE void resize(size_type num_elements_hint);
00552 void clear() { super::clear(); }
00553 private:
00554 size_type next_size(size_type n) const { return next_prime(n); }
00555
00556 void initialize_buckets(size_type n)
00557 {
00558 const size_type n_buckets = next_size(n);
00559 buckets.reserve(n_buckets);
00560 buckets.insert(buckets.end(), n_buckets, (node*) 0);
00561 num_elements = 0;
00562 }
00563 size_type bkt_num_key(const key_type& key) const{
00564 return bkt_num_key(key, buckets.size());
00565 }
00566
00567 size_type bkt_num(const value_type& obj) const {
00568 return bkt_num_key(get_key(obj));
00569 }
00570
00571 size_type bkt_num_key(const key_type& key, size_t n) const {
00572 return hashfun(key) % n;
00573 }
00574
00575 size_type bkt_num(const value_type& obj, size_t n) const {
00576 return bkt_num_key(get_key(obj), n);
00577 }
00578 IUEi_STL_INLINE void erase_bucket(const size_type n, node* first, node* last);
00579 IUEi_STL_INLINE void erase_bucket(const size_type n, node* last);
00580 };
00581
00582
00583
00584
00585 # if defined ( __STL_NESTED_TYPE_PARAM_BUG )
00586 # define __difference_type__ ptrdiff_t
00587 # define __size_type__ size_t
00588 # define __value_type__ Value
00589 # define __key_type__ Key
00590 # define __node__ hashtable_node<Value>
00591 # define __reference__ Value&
00592 # else
00593 # define __difference_type__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::difference_type
00594 # define __size_type__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::size_type
00595 # define __value_type__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::value_type
00596 # define __key_type__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::key_type
00597 # define __node__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node
00598 # define __reference__ hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::reference
00599 # endif
00600
00601 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00602 inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
00603 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
00604 {
00605 const node* old = cur;
00606 cur = cur->next;
00607 if (!cur) {
00608 size_type bucket = ht->bkt_num(old->val);
00609 while (!cur && ++bucket < ht->buckets.size())
00610 cur = ht->buckets[bucket];
00611 }
00612 return *this;
00613 }
00614
00615 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00616 inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00617 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
00618 {
00619 iterator tmp = *this;
00620 ++*this;
00621 return tmp;
00622 }
00623
00624 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00625 inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
00626 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
00627 {
00628 const node* old = cur;
00629 cur = cur->next;
00630 if (!cur) {
00631 size_type bucket = ht->bkt_num(old->val);
00632 while (!cur && ++bucket < ht->buckets.size())
00633 cur = ht->buckets[bucket];
00634 }
00635 return *this;
00636 }
00637
00638 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00639 inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00640 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
00641 {
00642 const_iterator tmp = *this;
00643 ++*this;
00644 return tmp;
00645 }
00646
00647 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00648 inline std::forward_iterator_tag
00649 iterator_category (const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00650 {
00651 return std::forward_iterator_tag();
00652 }
00653
00654 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00655 inline Value*
00656 value_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00657 {
00658 return (Value*) 0;
00659 }
00660
00661 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00662 inline ptrdiff_t*
00663 distance_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00664 {
00665 return (ptrdiff_t*) 0;
00666 }
00667
00668 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00669 inline std::forward_iterator_tag
00670 iterator_category (const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00671 {
00672 return std::forward_iterator_tag();
00673 }
00674
00675 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00676 inline Value*
00677 value_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00678 {
00679 return (Value*) 0;
00680 }
00681
00682 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00683 inline ptrdiff_t*
00684 distance_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
00685 {
00686 return (ptrdiff_t*) 0;
00687 }
00688
00689
00690
00691 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00692 IUEi_STL_INLINE
00693 bool operator==(const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht1,
00694 const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht2)
00695 {
00696 typedef typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node node;
00697 if (ht1.buckets.size() != ht2.buckets.size())
00698 return false;
00699 for (int n = 0; n < ht1.buckets.size(); ++n) {
00700 node* cur1 = ht1.buckets[n];
00701 node* cur2 = ht2.buckets[n];
00702 for ( ; cur1 && cur2 && cur1->val == cur2->val;
00703 cur1 = cur1->next, cur2 = cur2->next)
00704 {}
00705 if (cur1 || cur2)
00706 return false;
00707 }
00708 return true;
00709 }
00710
00711 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00712 std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, bool>
00713 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_unique_noresize(const __value_type__& obj)
00714 {
00715 const size_type n = bkt_num(obj);
00716 node* first = buckets[n];
00717
00718 for (node* cur = first; cur; cur = cur->next)
00719 if (equals(get_key(cur->val), get_key(obj)))
00720 return std::pair<iterator, bool>(iterator(cur, this), false);
00721
00722 node* tmp = new_node(obj);
00723 tmp->next = first;
00724 buckets[n] = tmp;
00725 ++num_elements;
00726 return std::pair<iterator, bool>(iterator(tmp, this), true);
00727 }
00728
00729 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00730 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
00731 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_equal_noresize(const __value_type__& obj)
00732 {
00733 const size_type n = bkt_num(obj);
00734 node* first = buckets[n];
00735
00736 for (node* cur = first; cur; cur = cur->next)
00737 if (equals(get_key(cur->val), get_key(obj))) {
00738 node* tmp = new_node(obj);
00739 tmp->next = cur->next;
00740 cur->next = tmp;
00741 ++num_elements;
00742 return iterator(tmp, this);
00743 }
00744
00745 node* tmp = new_node(obj);
00746 tmp->next = first;
00747 buckets[n] = tmp;
00748 ++num_elements;
00749 return iterator(tmp, this);
00750 }
00751
00752 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00753 __reference__
00754 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::find_or_insert(const __value_type__& obj)
00755 {
00756 resize(num_elements + 1);
00757
00758 size_type n = bkt_num(obj);
00759 node* first = buckets[n];
00760
00761 for (node* cur = first; cur; cur = cur->next)
00762 if (equals(get_key(cur->val), get_key(obj)))
00763 return cur->val;
00764
00765 node* tmp = new_node(obj);
00766 tmp->next = first;
00767 buckets[n] = tmp;
00768 ++num_elements;
00769 return tmp->val;
00770 }
00771
00772 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00773 std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
00774 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> >
00775 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key)
00776 {
00777 typedef std::pair<iterator, iterator> pii;
00778 const size_type n = bkt_num_key(key);
00779
00780 for (node* first = buckets[n]; first; first = first->next) {
00781 if (equals(get_key(first->val), key)) {
00782 for (node* cur = first->next; cur; cur = cur->next)
00783 if (!equals(get_key(cur->val), key))
00784 return pii(iterator(first, this), iterator(cur, this));
00785 for (size_type m = n + 1; m < buckets.size(); ++m)
00786 if (buckets[m])
00787 return pii(iterator(first, this),
00788 iterator(buckets[m], this));
00789 return pii(iterator(first, this), end());
00790 }
00791 }
00792 return pii(end(), end());
00793 }
00794
00795 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00796 std::pair<hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
00797 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> >
00798 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key) const
00799 {
00800 typedef std::pair<const_iterator, const_iterator> pii;
00801 const size_type n = bkt_num_key(key);
00802
00803 for (const node* first = buckets[n] ; first; first = first->next) {
00804 if (equals(get_key(first->val), key)) {
00805 for (const node* cur = first->next; cur; cur = cur->next)
00806 if (!equals(get_key(cur->val), key))
00807 return pii(const_iterator(first, this),
00808 const_iterator(cur, this));
00809 for (size_type m = n + 1; m < buckets.size(); ++m)
00810 if (buckets[m])
00811 return pii(const_iterator(first, this),
00812 const_iterator(buckets[m], this));
00813 return pii(const_iterator(first, this), end());
00814 }
00815 }
00816 return pii(end(), end());
00817 }
00818
00819 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00820 __size_type__
00821 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __key_type__& key)
00822 {
00823 const size_type n = bkt_num_key(key);
00824 node* first = buckets[n];
00825 size_type erased = 0;
00826
00827 if (first) {
00828 node* cur = first;
00829 node* next = cur->next;
00830 while (next) {
00831 if (equals(get_key(next->val), key)) {
00832 cur->next = next->next;
00833 delete_node(next);
00834 next = cur->next;
00835 ++erased;
00836 }
00837 else {
00838 cur = next;
00839 next = cur->next;
00840 }
00841 }
00842 if (equals(get_key(first->val), key)) {
00843 buckets[n] = first->next;
00844 delete_node(first);
00845 ++erased;
00846 }
00847 }
00848 num_elements -= erased;
00849 return erased;
00850 }
00851
00852 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00853 void
00854 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
00855 {
00856 node* const p = it.cur;
00857 if (p) {
00858 const size_type n = bkt_num(p->val);
00859 node* cur = buckets[n];
00860
00861 if (cur == p) {
00862 buckets[n] = cur->next;
00863 delete_node(cur);
00864 --num_elements;
00865 }
00866 else {
00867 node* next = cur->next;
00868 while (next) {
00869 if (next == p) {
00870 cur->next = next->next;
00871 delete_node(next);
00872 --num_elements;
00873 break;
00874 }
00875 else {
00876 cur = next;
00877 next = cur->next;
00878 }
00879 }
00880 }
00881 }
00882 }
00883
00884 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00885 void
00886 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first,
00887 hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
00888 {
00889 size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
00890 size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
00891 if (first.cur == last.cur)
00892 return;
00893 else if (f_bucket == l_bucket)
00894 erase_bucket(f_bucket, first.cur, last.cur);
00895 else {
00896 erase_bucket(f_bucket, first.cur, 0);
00897 for (size_type n = f_bucket + 1; n < l_bucket; ++n)
00898 erase_bucket(n, 0);
00899 if (l_bucket != buckets.size())
00900 erase_bucket(l_bucket, last.cur);
00901 }
00902 }
00903
00904 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00905 inline void
00906 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first,
00907 hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
00908 {
00909 erase(iterator(const_cast<node*>(first.cur),
00910 const_cast<self*>(first.ht)),
00911 iterator(const_cast<node*>(last.cur),
00912 const_cast<self*>(last.ht)));
00913 }
00914
00915 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00916 inline void
00917 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
00918 {
00919 erase(iterator(const_cast<node*>(it.cur),
00920 const_cast<self*>(it.ht)));
00921 }
00922
00923 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00924 void
00925 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::resize(__size_type__ num_elements_hint)
00926 {
00927 const size_type old_n = buckets.size();
00928 if (num_elements_hint > old_n) {
00929 const size_type n = next_size(num_elements_hint);
00930 if (n > old_n) {
00931 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::buckets_type tmp(n, (node*)0);
00932 for (size_type bucket = 0; bucket < old_n; ++bucket) {
00933 node* first = buckets[bucket];
00934 while (first) {
00935 size_type new_bucket = bkt_num(first->val, n);
00936 buckets[bucket] = first->next;
00937 first->next = tmp[new_bucket];
00938 tmp[new_bucket] = first;
00939 first = buckets[bucket];
00940 }
00941 }
00942 buckets.clear();
00943 buckets.swap(tmp);
00944 }
00945 }
00946 }
00947
00948
00949 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00950 void
00951 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
00952 hashtable_node<Value>* first,
00953 hashtable_node<Value>* last)
00954 {
00955 node* cur = buckets[n];
00956 if (cur == first)
00957 erase_bucket(n, last);
00958 else {
00959 node* next;
00960 for (next = cur->next; next != first; cur = next, next = cur->next)
00961 ;
00962 while (next) {
00963 cur->next = next->next;
00964 delete_node(next);
00965 next = cur->next;
00966 --num_elements;
00967 }
00968 }
00969 }
00970
00971 template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
00972 void
00973 hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
00974 hashtable_node<Value>* last)
00975 {
00976 node* cur = buckets[n];
00977 while (cur != last) {
00978 node* next = cur->next;
00979 delete_node(cur);
00980 cur = next;
00981 buckets[n] = cur;
00982 --num_elements;
00983 }
00984 }
00985
00986 template <class Value, class Alloc>
00987 void hashtable_base<Value, Alloc>::clear()
00988 {
00989 for (size_type i = 0; i < buckets.size(); ++i) {
00990 node* cur = buckets[i];
00991 while (cur != 0) {
00992 node* next = cur->next;
00993 delete_node(cur);
00994 cur = next;
00995 }
00996 buckets[i] = 0;
00997 }
00998 num_elements = 0;
00999 }
01000
01001
01002 template <class Value, class Alloc>
01003 void hashtable_base<Value, Alloc>::copy_from(const hashtable_base<Value, Alloc>& ht)
01004 {
01005 buckets.reserve(ht.buckets.size());
01006 buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
01007 for (size_type i = 0; i < ht.buckets.size(); ++i) {
01008 const node* cur = ht.buckets[i];
01009 if (cur) {
01010 node* copy = new_node(cur->val);
01011 buckets[i] = copy;
01012 ++num_elements;
01013
01014 for (node* next = cur->next; next; cur = next, next = cur->next) {
01015 copy->next = new_node(next->val);
01016 ++num_elements;
01017 copy = copy->next;
01018 }
01019 }
01020 }
01021 }
01022
01023 }
01024
01025
01026 # undef __difference_type__
01027 # undef __size_type__
01028 # undef __value_type__
01029 # undef __key_type__
01030 # undef __node__
01031
01032
01033
01034
01035
01036
01037
01038 # if defined(VCL_SUNPRO_CC) || defined (_MSC_VER) || defined(__BORLANDC__)
01039 namespace std
01040 {
01041 template <class T>
01042 struct identity : public std::unary_function<T, T> {
01043 public:
01044 const T& operator()(const T& x) const { return x; }
01045 };
01046 }
01047
01048 template <class _Pair>
01049 struct itk_Select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
01050 typename _Pair::first_type const & operator()(_Pair const & __x) const {
01051 return __x.first;
01052 }
01053 };
01054
01055 template <class _Pair>
01056 struct itk_Select2nd : public std::unary_function<_Pair, typename _Pair::second_type> {
01057 typename _Pair::second_type const & operator()(_Pair const & __x) const {
01058 return __x.second;
01059 }
01060 };
01061
01062
01063 namespace std {
01064 template <class _Pair>
01065 struct select1st : public itk_Select1st<_Pair> { };
01066 template <class _Pair> struct select2nd : public itk_Select2nd<_Pair> { };
01067 };
01068
01069 #endif
01070
01071 #endif
01072
01073 #endif // itk_emulation_hashtable_h