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

Generated at Tue Jul 29 19:03:32 2008 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000