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

Generated at Sat Mar 31 02:13:55 2007 for ITK by doxygen 1.3.8 written by Dimitri van Heesch, © 1997-2000