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

Generated at Thu May 28 09:16:16 2009 for ITK by doxygen 1.5.5 written by Dimitri van Heesch, © 1997-2000