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