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

Generated at Sun Mar 11 23:25:30 2007 for ITK by doxygen 1.5.1 written by Dimitri van Heesch, © 1997-2000