Main Page   Groups   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Concepts

itk_hashtable.h

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Program:   Insight Segmentation & Registration Toolkit
00004   Module:    $RCSfile: itk_hashtable.h,v $
00005   Language:  C++
00006   Date:      $Date: 2010-04-26 14:31:25 $
00007   Version:   $Revision: 1.35 $
00008 
00009   Copyright (c) Insight Software Consortium. All rights reserved.
00010   See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
00011 
00012      This software is distributed WITHOUT ANY WARRANTY; without even
00013      the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
00014      PURPOSE.  See the above copyright notices for more information.
00015 
00016 =========================================================================*/
00068 #ifndef __itk_hashtable_h
00069 #define __itk_hashtable_h
00070 
00071 #if defined(_MSC_VER)
00072 // unreachable code
00073 #pragma warning ( disable : 4702 )
00074 // assignment operator could not be generated
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 // Use this hashtable that is already define for GNU_C versions >= 3.1, IBMCPP >=600, or Intel compilers with GCCv4
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 // Note: assumes long is at least 32 bits.
00266 // fbp: try to avoid intances in every module
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   // give up
00282   static const unsigned long prime_list[num_primes] =
00283 #  endif /* __STL_WEAK_ATTRIBUTE */
00284 #endif /* __STL_STATIC_TEMPLATE_DATA */
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: // These are public to get around restriction on protected access
00312   typedef std::vector<VCL_SUNPRO_ALLOCATOR_HACK(node*) > buckets_type;
00313   buckets_type buckets; // awf killed optional allocator
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: // These are public to get around restriction on protected access
00345     hashtable_base() : num_elements(0) { }
00346 //    hashtable_base(size_type n) : num_elements(0) {}
00347     ~hashtable_base() { clear(); }
00348 };
00349 
00350 
00351 // forward declarations
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 // fbp: these defines are for outline methods definitions.
00639 // needed to definitions to be portable. Should not be used in method bodies.
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 }// end namespace itk
01134 
01135 
01136 # undef __difference_type__
01137 # undef __size_type__
01138 # undef __value_type__
01139 # undef __key_type__
01140 # undef __node__
01141 
01142 // the following is added for itk compatability:
01143 
01144 // --
01145 
01146 // A few compatability fixes.  Placed here for automatic include in
01147 // both the hash_set and the hash_map sources.
01148 # if (defined (_MSC_VER)&&(_MSC_VER < 1600 )) || defined(__BORLANDC__) || ((defined(__ICC)||defined(__ECC)) && defined(linux))
01149 // This should be replaced with a try_compile that tests the availability of std::identity. FIXME
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 // This should be replaced with a try_compile that tests the availability of std::select*. FIXME
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 // Add select* to std.
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 

Generated at Mon Jul 12 2010 17:41:17 for ITK by doxygen 1.7.1 written by Dimitri van Heesch, © 1997-2000