KWStyle - itk_hashtable.h

Matrix View

Description

---

1		/*=========================================================================
2
3		Program:   Insight Segmentation & Registration Toolkit
4		Module:    $RCSfile: itk_hashtable.h.html,v $
5		Language:  C++
6		Date:      $Date: 2006/01/17 19:15:46 $
7		Version:   $Revision: 1.4 $
8
9		Copyright (c) Insight Software Consortium. All rights reserved.
10		See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details.
11
12		This software is distributed WITHOUT ANY WARRANTY; without even
13		the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14		PURPOSE.  See the above copyright notices for more information.
15
16		=========================================================================*/
17		/*
18	IND	** Copyright (c) 1996
19	IND	** Silicon Graphics Computer Systems, Inc.
20	IND	**
21	IND	** Permission to use, copy, modify, distribute and sell this software
22	IND	** and its documentation for any purpose is hereby granted without fee,
23	IND	** provided that the above copyright notice appear in all copies and
24	IND	** that both that copyright notice and this permission notice appear
25	IND	** in supporting documentation.  Silicon Graphics makes no
26	IND	** representations about the suitability of this software for any
27	IND	** purpose.  It is provided "as is" without express or implied warranty.
28	IND	**
29	IND	**
30	IND	** Copyright (c) 1994
31	IND	** Hewlett-Packard Company
32	IND	**
33	IND	** Permission to use, copy, modify, distribute and sell this software
34	IND	** and its documentation for any purpose is hereby granted without fee,
35	IND	** provided that the above copyright notice appear in all copies and
36	IND	** that both that copyright notice and this permission notice appear
37	IND	** in supporting documentation.  Hewlett-Packard Company makes no
38	IND	** representations about the suitability of this software for any
39	IND	** purpose.  It is provided "as is" without express or implied warranty.
40	IND	**
41	IND	** Exception Handling:
42	IND	** Copyright (c) 1997
43	IND	** Mark of the Unicorn, Inc.
44	IND	**
45	IND	** Permission to use, copy, modify, distribute and sell this software
46	IND	** and its documentation for any purpose is hereby granted without fee,
47	IND	** provided that the above copyright notice appear in all copies and
48	IND	** that both that copyright notice and this permission notice appear
49	IND	** in supporting documentation.  Mark of the Unicorn makes no
50	IND	** representations about the suitability of this software for any
51	IND	** purpose.  It is provided "as is" without express or implied warranty.
52	IND	**
53	IND	** Adaptation:
54	IND	** Copyright (c) 1997
55	IND	** Moscow Center for SPARC Technology
56	IND	**
57	IND	** Permission to use, copy, modify, distribute and sell this software
58	IND	** and its documentation for any purpose is hereby granted without fee,
59	IND	** provided that the above copyright notice appear in all copies and
60	IND	** that both that copyright notice and this permission notice appear
61	IND	** in supporting documentation.  Moscow Center for SPARC Technology makes no
62	IND	** representations about the suitability of this software for any
63	IND	** purpose.  It is provided "as is" without express or implied warranty.
64	IND	**
65	IND	**/
66
67
68	DEF	#ifndef itk_emulation_hashtable_h
69	DEF	#define itk_emulation_hashtable_h
70
71	LEN	#if !defined(__GNUC__) || !((__GNUC__==3) && (__GNUC_MINOR__>=1) || (__GNUC__>3)) || defined(__INTEL_COMPILER)
72
73		/** \brief Hashtable class, used to implement the hashed associative containers
74		* itk_hash_set, itk_hash_map, itk_hash_multiset, and itk_hash_multimap.
75		*/
76		#include "itkMacro.h"
77		#include <iostream>
78		#include "itk_alloc.h"
79		#include <vector>
80		#include <utility>
81		#include <memory>
82		#include "vcl_compiler.h"
83		#include <functional>
84		#include <algorithm>
85		#include <iterator>
86
87
88		namespace itk
89		{
90		template <class Key> struct hash { };
91
92		inline size_t hash_string(const char* s)
93		{
94		unsigned long h = 0;
95	SEM	for ( ; *s; ++s)
96	IND	****h = 5*h + *s;
97
98		return size_t(h);
99		}
100
101		template<>
102		struct hash<char*>
103		{
104		size_t operator()(const char* s) const { return hash_string(s); }
105		};
106
107		template<>
108		struct hash<const char*>
109		{
110		size_t operator()(const char* s) const { return hash_string(s); }
111		};
112
113		template<>
114		struct hash<char> {
115		size_t operator()(char x) const { return x; }
116		};
117
118		template<>
119		struct hash<unsigned char> {
120		size_t operator()(unsigned char x) const { return x; }
121		};
122
123		template<>
124		struct hash<signed char> {
125		size_t operator()(unsigned char x) const { return x; }
126		};
127
128		template<>
129		struct hash<short> {
130		size_t operator()(short x) const { return x; }
131		};
132
133		template<>
134		struct hash<unsigned short> {
135		size_t operator()(unsigned short x) const { return x; }
136		};
137
138		template<>
139		struct hash<int> {
140		size_t operator()(int x) const { return x; }
141		};
142
143		template<>
144		struct hash<unsigned int> {
145		size_t operator()(unsigned int x) const { return x; }
146		};
147
148		template<>
149		struct hash<long> {
150		size_t operator()(long x) const { return x; }
151		};
152
153		template<>
154		struct hash<unsigned long> {
155		size_t operator()(unsigned long x) const { return x; }
156		};
157
158		template <class Value>
159		struct hashtable_node
160		{
161	TDR	typedef hashtable_node<Value> self;
162		self* next;
163		Value val;
164		};
165
166	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey ,  VCL_DFL_TYPE_PARAM_STLDECL(Alloc,std::allocator<char>)>
167		class hashtable;
168
169	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
170		struct hashtable_iterator;
171
172	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
173		struct hashtable_const_iterator;
174
175	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
176		struct hashtable_iterator
177		{
178		typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
179	TDR,IND	**********hash_table;
180		typedef hashtable_iterator<Value, Key, HashFcn,
181		ExtractKey, EqualKey, Alloc>
182	TDR,IND	**********iterator;
183		typedef hashtable_const_iterator<Value, Key, HashFcn,
184		ExtractKey, EqualKey, Alloc>
185	TDR,IND	**********const_iterator;
186	TDA,TDR	typedef hashtable_node<Value> node;
187	TDA,TDR	typedef size_t size_type;
188	TDA,TDR	typedef Value& reference;
189	TDA,TDR	typedef const Value& const_reference;
190
191		node* cur;
192		hash_table* ht;
193
194		hashtable_iterator(node* n, hash_table* tab) : cur(n), ht(tab) {}
195		hashtable_iterator() {}
196		reference operator*() const {
197	IND	********return cur->val;
198	IND	**}
199		IUEi_STL_INLINE iterator& operator++();
200		IUEi_STL_INLINE iterator operator++(int);
201		bool operator==(const iterator& it) const {
202	IND	******return cur == it.cur;
203	IND	**}
204		bool operator!=(const iterator& it) const {
205	IND	******return cur != it.cur;
206	IND	**}
207		};
208
209
210	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
211		struct hashtable_const_iterator
212		{
213		typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
214	TDR,IND	**********hash_table;
215		typedef hashtable_iterator<Value, Key, HashFcn,
216	TDA,TDR	ExtractKey, EqualKey, Alloc> iterator;
217		typedef hashtable_const_iterator<Value, Key, HashFcn,
218	TDA,TDR	ExtractKey, EqualKey, Alloc> const_iterator;
219	TDA,TDR	typedef hashtable_node<Value> node;
220	TDA,TDR	typedef size_t size_type;
221	TDA,TDR	typedef Value& reference;
222	TDA,TDR	typedef const Value& const_reference;
223
224		const node* cur;
225		const hash_table* ht;
226
227	LEN	hashtable_const_iterator(const node* n, const hash_table* tab) : cur(n), ht(tab) {}
228		hashtable_const_iterator() {}
229		hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
230
231		const_reference operator*() const {
232	IND	******return cur->val;
233	IND	**}
234		IUEi_STL_INLINE const_iterator& operator++();
235		IUEi_STL_INLINE const_iterator operator++(int);
236		bool operator==(const const_iterator& it) const {
237	IND	******return cur == it.cur;
238	IND	**}
239		bool operator!=(const const_iterator& it) const {
240	IND	******return cur != it.cur;
241	IND	**}
242		};
243
244		// Note: assumes long is at least 32 bits.
245		// fbp: try to avoid intances in every module
246		enum { num_primes = 28 };
247
248		#if ( __STL_STATIC_TEMPLATE_DATA > 0 ) && ! defined (WIN32)
249		#  define prime_list prime<false>::list_
250	IND	***template <bool dummy>
251	IND,IND	***struct prime {
252	IND	***public:
253	IND	*******static const unsigned long list_[];
254	IND	***};
255	IND	******static const unsigned long prime_list_dummy[num_primes] =
256		#  else
257		#  if ( __STL_WEAK_ATTRIBUTE > 0 )
258	IND	******extern const unsigned long prime_list[num_primes] __attribute__((weak)) =
259		#  else
260	IND	******// give up
261	IND	******static const unsigned long prime_list[num_primes] =
262		#  endif /* __STL_WEAK_ATTRIBUTE */
263		#endif /* __STL_STATIC_TEMPLATE_DATA */
264		{
265		53,         97,         193,       389,       769,
266		1543,       3079,       6151,      12289,     24593,
267		49157,      98317,      196613,    393241,    786433,
268		1572869,    3145739,    6291469,   12582917,  25165843,
269		50331653,   100663319,  201326611, 402653189, 805306457,
270		1610612741, 3221225473U, 4294967291U
271		};
272
273		inline unsigned long next_prime(unsigned long n)
274		{
275		const unsigned long* first = prime_list;
276		const unsigned long* last = prime_list;
277		last += num_primes;
278		const unsigned long* pos = std::lower_bound(first, last, n);
279		return pos == last ? *(last - 1) : *pos;
280		}
281
282		template <class Value, class Alloc>
283		class hashtable_base
284		{
285		private:
286	TDR,IND	****typedef Value value_type;
287	TDA,TDR,IND	****typedef size_t size_type;
288	TDA,TDR,IND	****typedef hashtable_node<Value> node;
289	TDA,TDR,IND	****typedef itk_simple_alloc<node, Alloc> node_allocator;
290		public: // These are public to get around restriction on protected access
291	TDR,SEM,IND	****typedef std::vector<VCL_SUNPRO_ALLOCATOR_HACK(node*) > buckets_type ;
292	IND	****buckets_type buckets; // awf killed optional allocator
293	IND	****size_type num_elements;
294		protected:
295	IND	****IUEi_STL_INLINE void clear();
296
297	IND	****node* new_node(const value_type& obj)
298	IND	**{
299	IND	************node* n = node_allocator::allocate();
300	IND	************try {
301	IND	********new (&(n->val)) value_type(obj);
302	IND	************}
303	IND	************catch (...) {
304	IND	********node_allocator::deallocate(n);
305	IND	********throw "";
306	IND	************}
307	IND	************n->next = 0;
308	IND	************return n;
309	IND	**}
310
311	IND	****void delete_node(node* n)
312	IND	**{
313		#define vcli_destroy(T, p)    ((T*)p)->~T()
314	IND	************vcli_destroy(Value, &(n->val));
315	IND	#undef vcli_destroy
316	IND	************node_allocator::deallocate(n);
317	IND	**}
318
319	IND	****IUEi_STL_INLINE void copy_from(const hashtable_base<Value,Alloc>& ht);
320
321		public: // These are public to get around restriction on protected access
322	IND	****hashtable_base() : num_elements(0) { }
323	IND	//    hashtable_base(size_type n) : num_elements(0) {}
324	IND	****~hashtable_base() { clear(); }
325		};
326
327
328		// forward declarations
329	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class hashtable;
330	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
331	LEN,IND	**bool operator== (hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&,hashtable<Value,Key,HashFcn,ExtractKey,EqualKey,Alloc>const&);
332
333	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
334		class hashtable : protected hashtable_base<Value, Alloc>
335		{
336	TDR	typedef hashtable_base<Value, Alloc> super;
337	TDA,TDR	typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> self;
338		public:
339	TDR	typedef Key key_type;
340	TDA,TDR	typedef Value value_type;
341	TDA,TDR	typedef HashFcn hasher;
342	TDA,TDR	typedef EqualKey key_equal;
343
344	TDR	typedef size_t            size_type;
345	TDR	typedef ptrdiff_t         difference_type;
346	TDR	typedef value_type*       pointer;
347	TDR	typedef const value_type* const_pointer;
348	TDR	typedef value_type&       reference;
349	TDR	typedef const value_type& const_reference;
350
351		hasher hash_funct() const { return hashfun; }
352		key_equal key_eq() const { return equals; }
353
354		private:
355		hasher hashfun;
356		key_equal equals;
357		ExtractKey get_key;
358
359	TDR	typedef hashtable_node<Value> node;
360	TDA,TDR	typedef itk_simple_alloc<node, Alloc> node_allocator;
361
362		public:
363	LEN,TDR	typedef hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
364	LEN,TDA,TDR	typedef hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> const_iterator;
365		friend struct
366		hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
367		friend struct
368		hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
369
370		public:
371		hashtable(size_type n,
372		const HashFcn&    hf,
373		const EqualKey&   eql,
374		const ExtractKey& ext)
375	IND	******: hashfun(hf), equals(eql), get_key(ext) {
376	IND	********initialize_buckets(n);
377		}
378
379		hashtable(size_type n,
380		const HashFcn&    hf,
381		const EqualKey&   eql)
382	IND	******: hashfun(hf), equals(eql), get_key(ExtractKey()) {
383	IND	********initialize_buckets(n);
384		}
385
386		hashtable(const self& ht)
387	IND	****: hashfun(ht.hashfun), equals(ht.equals), get_key(ht.get_key) {
388	IND	********copy_from(ht);
389	IND	**}
390
391		self& operator= (const self& ht)
392	IND	**{
393		if (&ht != this) {
394		hashfun = ht.hashfun;
395		equals = ht.equals;
396		get_key = ht.get_key;
397		clear();
398		buckets.clear();
399		copy_from(ht);
400	IND	****}
401		return *this;
402	IND	**}
403
404		~hashtable() {}
405
406		size_type size() const { return num_elements; }
407		size_type max_size() const { return size_type(-1); }
408		bool empty() const { return size() == 0; }
409
410		void swap(self& ht)
411	IND	**{
412		std::swap(hashfun, ht.hashfun);
413		std::swap(equals, ht.equals);
414		std::swap(get_key, ht.get_key);
415		buckets.swap(ht.buckets);
416		std::swap(num_elements, ht.num_elements);
417	IND	**}
418
419		iterator begin()
420	IND	**{
421		for (size_type n = 0; n < buckets.size(); ++n)
422		if (buckets[n])
423		return iterator(buckets[n], this);
424		return end();
425		}
426
427		iterator end() { return iterator((node*)0, this); }
428
429		const_iterator begin() const
430		{
431		for (size_type n = 0; n < buckets.size(); ++n)
432		if (buckets[n])
433		return const_iterator(buckets[n], this);
434		return end();
435		}
436
437		const_iterator end() const { return const_iterator((node*)0, this); }
438
439		//  friend IUEi_STL_INLINE bool operator== VCL_NULL_TMPL_ARGS (const
440		//  self&,const self&);
441		friend bool operator== VCL_NULL_TMPL_ARGS (const self&,const self&);
442		public:
443
444		size_type bucket_count() const { return buckets.size(); }
445
446		size_type max_bucket_count() const
447		{ return prime_list[num_primes - 1]; }
448
449		size_type elems_in_bucket(size_type bucket) const
450		{
451		size_type result = 0;
452		for (node* cur = buckets[bucket]; cur; cur = cur->next)
453	IND	******result += 1;
454		return result;
455	IND	**}
456
457		std::pair<iterator, bool> insert_unique(const value_type& obj)
458	IND	**{
459		resize(num_elements + 1);
460		return insert_unique_noresize(obj);
461	IND	**}
462
463		iterator insert_equal(const value_type& obj)
464	IND	**{
465		resize(num_elements + 1);
466		return insert_equal_noresize(obj);
467	IND	**}
468
469	LEN	IUEi_STL_INLINE std::pair<iterator, bool> insert_unique_noresize(const value_type& obj);
470		IUEi_STL_INLINE iterator insert_equal_noresize(const value_type& obj);
471
472		void insert_unique(const value_type* f, const value_type* l)
473	IND	**{
474		size_type n = l - f;
475		resize(num_elements + n);
476	SEM	for ( ; n > 0; --n)
477	IND	******insert_unique_noresize(*f++);
478	IND	**}
479
480		void insert_equal(const value_type* f, const value_type* l)
481	IND	**{
482		size_type n = l - f;
483		resize(num_elements + n);
484	SEM	for ( ; n > 0; --n)
485	IND	******insert_equal_noresize(*f++);
486	IND	**}
487
488	IND	*void insert_unique(const_iterator f, const_iterator l)
489	IND	**{
490		size_type n = 0;
491		std::distance(f, l, n);
492		resize(num_elements + n);
493	SEM	for ( ; n > 0; --n)
494	IND	******insert_unique_noresize(*f++);
495	IND	**}
496
497		void insert_equal(const_iterator f, const_iterator l)
498	IND	**{
499		size_type n = 0;
500		std::distance(f, l, n);
501		resize(num_elements + n);
502	SEM	for ( ; n > 0; --n)
503	IND	******insert_equal_noresize(*f++);
504	IND	**}
505
506		IUEi_STL_INLINE reference find_or_insert(const value_type& obj);
507
508		iterator find(const key_type& key)
509	IND	**{
510		size_type n = bkt_num_key(key);
511		node* first;
512		for ( first = buckets[n];
513		first && !equals(get_key(first->val), key);
514	IND	**********first = first->next)
515		{}
516		return iterator(first, this);
517	IND	**}
518
519		const_iterator find(const key_type& key) const
520	IND	**{
521		size_type n = bkt_num_key(key);
522		const node* first;
523		for ( first = buckets[n];
524		first && !equals(get_key(first->val), key);
525	IND	**********first = first->next)
526		{}
527		return const_iterator(first, this);
528	IND	**}
529
530		size_type count(const key_type& key) const
531	IND	**{
532		const size_type n = bkt_num_key(key);
533		size_type result = 0;
534
535		for (const node* cur = buckets[n]; cur; cur = cur->next)
536	IND	******if (equals(get_key(cur->val), key))
537	IND	********++result;
538		return result;
539	IND	**}
540
541	LEN	IUEi_STL_INLINE std::pair<iterator, iterator> equal_range(const key_type& key);
542	LEN	IUEi_STL_INLINE std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
543
544		IUEi_STL_INLINE size_type erase(const key_type& key);
545		IUEi_STL_INLINE void erase(const iterator& it);
546		IUEi_STL_INLINE void erase(iterator first, iterator last);
547
548		IUEi_STL_INLINE void erase(const const_iterator& it);
549		IUEi_STL_INLINE void erase(const_iterator first, const_iterator last);
550
551		IUEi_STL_INLINE void resize(size_type num_elements_hint);
552		void clear() { super::clear(); }
553		private:
554	IND	****size_type next_size(size_type n) const {
555	IND	*******return static_cast<size_type>(
556		next_prime( static_cast<unsigned long>(n) ) ); }
557
558	IND	****void initialize_buckets(size_type n)
559		{
560	IND	********const size_type n_buckets = next_size(n);
561	IND	********buckets.reserve(n_buckets);
562	IND	********buckets.insert(buckets.end(), n_buckets, (node*) 0);
563	IND	********num_elements = 0;
564		}
565	IND	****size_type bkt_num_key(const key_type& key) const{
566	IND	********return bkt_num_key(key, buckets.size());
567		}
568
569	IND	****size_type bkt_num(const value_type& obj) const {
570	IND	********return bkt_num_key(get_key(obj));
571		}
572
573	IND	****size_type bkt_num_key(const key_type& key, size_t n) const {
574	IND	********return hashfun(key) % n;
575		}
576
577	IND	****size_type bkt_num(const value_type& obj, size_t n) const {
578	IND	********return bkt_num_key(get_key(obj), n);
579		}
580	LEN,IND	****IUEi_STL_INLINE void erase_bucket(const size_type n, node* first, node* last);
581	IND	****IUEi_STL_INLINE void erase_bucket(const size_type n, node* last);
582		};
583
584		// fbp: these defines are for outline methods definitions.
585		// needed to definitions to be portable. Should not be used in method bodies.
586
587		# if defined ( __STL_NESTED_TYPE_PARAM_BUG )
588		#  define __difference_type__ ptrdiff_t
589		#  define __size_type__       size_t
590		#  define __value_type__      Value
591		#  define __key_type__        Key
592		#  define __node__            hashtable_node<Value>
593		#  define __reference__       Value&
594		# else
595	LEN	#  define __difference_type__  typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::difference_type
596	LEN	#  define __size_type__        typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::size_type
597	LEN	#  define __value_type__       typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::value_type
598	LEN	#  define __key_type__         typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::key_type
599	LEN	#  define __node__             typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node
600	LEN	#  define __reference__        typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::reference
601		# endif
602
603	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
604		inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
605	LEN	hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
606		{
607		const node* old = cur;
608		cur = cur->next;
609		if (!cur) {
610		size_type bucket = ht->bkt_num(old->val);
611		while (!cur && ++bucket < ht->buckets.size())
612	IND	******cur = ht->buckets[bucket];
613	IND	**}
614		return *this;
615		}
616
617	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
618		inline hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
619	LEN	hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
620		{
621		iterator tmp = *this;
622		++*this;
623		return tmp;
624		}
625
626	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
627	LEN	inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
628	LEN	hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
629		{
630		const node* old = cur;
631		cur = cur->next;
632		if (!cur) {
633		size_type bucket = ht->bkt_num(old->val);
634		while (!cur && ++bucket < ht->buckets.size())
635	IND	******cur = ht->buckets[bucket];
636	IND	**}
637		return *this;
638		}
639
640	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
641	LEN	inline hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
642	LEN	hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
643		{
644		const_iterator tmp = *this;
645		++*this;
646		return tmp;
647		}
648
649	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
650		inline std::forward_iterator_tag
651	LEN	iterator_category (const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
652		{
653		return std::forward_iterator_tag();
654		}
655
656	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
657		inline Value*
658	LEN	value_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
659		{
660		return (Value*) 0;
661		}
662
663	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
664		inline ptrdiff_t*
665	LEN	distance_type(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
666		{
667		return (ptrdiff_t*) 0;
668		}
669
670	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
671		inline std::forward_iterator_tag
672	LEN	iterator_category (const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
673		{
674		return std::forward_iterator_tag();
675		}
676
677	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
678		inline Value*
679	LEN	value_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
680		{
681		return (Value*) 0;
682		}
683
684	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
685		inline ptrdiff_t*
686	LEN	distance_type(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
687		{
688		return (ptrdiff_t*) 0;
689		}
690
691
692	EML
693	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
694		IUEi_STL_INLINE
695	LEN	bool operator==(const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht1,
696	LEN	const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht2)
697		{
698	LEN,TDR	typedef typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node node;
699		if (ht1.buckets.size() != ht2.buckets.size())
700	IND	****return false;
701		for (int n = 0; n < ht1.buckets.size(); ++n) {
702		node* cur1 = ht1.buckets[n];
703		node* cur2 = ht2.buckets[n];
704	SEM	for ( ; cur1 && cur2 && cur1->val == cur2->val;
705		cur1 = cur1->next, cur2 = cur2->next)
706		{}
707		if (cur1 || cur2)
708	IND	******return false;
709	IND	**}
710		return true;
711		}
712
713	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
714	LEN	std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, bool>
715	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_unique_noresize(const __value_type__& obj)
716		{
717		const size_type n = bkt_num(obj);
718		node* first = buckets[n];
719
720		for (node* cur = first; cur; cur = cur->next)
721	IND	****if (equals(get_key(cur->val), get_key(obj)))
722	IND	******return std::pair<iterator, bool>(iterator(cur, this), false);
723
724		node* tmp = new_node(obj);
725		tmp->next = first;
726		buckets[n] = tmp;
727		++num_elements;
728		return std::pair<iterator, bool>(iterator(tmp, this), true);
729		}
730
731	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
732		hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
733	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_equal_noresize(const __value_type__& obj)
734		{
735		const size_type n = bkt_num(obj);
736		node* first = buckets[n];
737
738		for (node* cur = first; cur; cur = cur->next)
739	IND	****if (equals(get_key(cur->val), get_key(obj))) {
740	IND	******node* tmp = new_node(obj);
741	IND	******tmp->next = cur->next;
742	IND	******cur->next = tmp;
743	IND	******++num_elements;
744	IND	******return iterator(tmp, this);
745		}
746
747		node* tmp = new_node(obj);
748		tmp->next = first;
749		buckets[n] = tmp;
750		++num_elements;
751		return iterator(tmp, this);
752		}
753
754	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
755		__reference__
756	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::find_or_insert(const __value_type__& obj)
757		{
758		resize(num_elements + 1);
759
760		size_type n = bkt_num(obj);
761		node* first = buckets[n];
762
763		for (node* cur = first; cur; cur = cur->next)
764	IND	****if (equals(get_key(cur->val), get_key(obj)))
765	IND	******return cur->val;
766
767		node* tmp = new_node(obj);
768		tmp->next = first;
769		buckets[n] = tmp;
770		++num_elements;
771		return tmp->val;
772		}
773
774	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
775		std::pair<hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
776	IND	*****hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> >
777	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key)
778		{
779	TDR	typedef std::pair<iterator, iterator> pii;
780		const size_type n = bkt_num_key(key);
781
782		for (node* first = buckets[n]; first; first = first->next) {
783		if (equals(get_key(first->val), key)) {
784		for (node* cur = first->next; cur; cur = cur->next)
785	IND	********if (!equals(get_key(cur->val), key))
786	IND	**********return pii(iterator(first, this), iterator(cur, this));
787		for (size_type m = n + 1; m < buckets.size(); ++m)
788		if (buckets[m])
789		return pii(iterator(first, this),
790		iterator(buckets[m], this));
791		return pii(iterator(first, this), end());
792		}
793		}
794		return pii(end(), end());
795		}
796
797	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
798	LEN	std::pair<hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
799	LEN,IND	*****hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> >
800	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key) const
801		{
802	TDR	typedef std::pair<const_iterator, const_iterator> pii;
803		const size_type n = bkt_num_key(key);
804
805	SEM	for (const node* first = buckets[n] ; first; first = first->next) {
806		if (equals(get_key(first->val), key)) {
807		for (const node* cur = first->next; cur; cur = cur->next)
808	IND	********if (!equals(get_key(cur->val), key))
809	IND	**********return pii(const_iterator(first, this),
810	IND	*********************const_iterator(cur, this));
811		for (size_type m = n + 1; m < buckets.size(); ++m)
812		if (buckets[m])
813		return pii(const_iterator(first, this),
814		const_iterator(buckets[m], this));
815		return pii(const_iterator(first, this), end());
816		}
817		}
818		return pii(end(), end());
819		}
820
821	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
822		__size_type__
823	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __key_type__& key)
824		{
825		const size_type n = bkt_num_key(key);
826		node* first = buckets[n];
827		size_type erased = 0;
828
829		if (first) {
830		node* cur = first;
831		node* next = cur->next;
832		while (next) {
833		if (equals(get_key(next->val), key)) {
834		cur->next = next->next;
835		delete_node(next);
836		next = cur->next;
837		++erased;
838	IND	******}
839		else {
840		cur = next;
841		next = cur->next;
842	IND	******}
843	IND	****}
844		if (equals(get_key(first->val), key)) {
845		buckets[n] = first->next;
846		delete_node(first);
847		++erased;
848	IND	****}
849	IND	**}
850		num_elements -= erased;
851		return erased;
852		}
853
854	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
855		void
856	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
857		{
858		node* const p = it.cur;
859		if (p) {
860		const size_type n = bkt_num(p->val);
861		node* cur = buckets[n];
862
863		if (cur == p) {
864		buckets[n] = cur->next;
865		delete_node(cur);
866		--num_elements;
867	IND	****}
868		else {
869		node* next = cur->next;
870		while (next) {
871		if (next == p) {
872		cur->next = next->next;
873		delete_node(next);
874		--num_elements;
875		break;
876	IND	********}
877		else {
878		cur = next;
879		next = cur->next;
880	IND	********}
881	IND	******}
882	IND	****}
883	IND	**}
884		}
885
886	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
887		void
888	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first,
889	LEN	hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
890		{
891		size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
892		size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
893		if (first.cur == last.cur)
894	IND	****return;
895		else if (f_bucket == l_bucket)
896	IND	****erase_bucket(f_bucket, first.cur, last.cur);
897		else {
898		erase_bucket(f_bucket, first.cur, 0);
899		for (size_type n = f_bucket + 1; n < l_bucket; ++n)
900		erase_bucket(n, 0);
901		if (l_bucket != buckets.size())
902		erase_bucket(l_bucket, last.cur);
903		}
904		}
905
906	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
907		inline void
908	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first,
909	LEN	hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
910		{
911		erase(iterator(const_cast<node*>(first.cur),
912	IND	*****************const_cast<self*>(first.ht)),
913	IND	********iterator(const_cast<node*>(last.cur),
914	IND	*****************const_cast<self*>(last.ht)));
915		}
916
917	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
918		inline void
919	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
920		{
921		erase(iterator(const_cast<node*>(it.cur),
922	IND	*****************const_cast<self*>(it.ht)));
923		}
924
925	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
926		void
927	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::resize(__size_type__ num_elements_hint)
928		{
929	IND	****const size_type old_n = buckets.size();
930	IND	****if (num_elements_hint > old_n) {
931	IND	********const size_type n = next_size(num_elements_hint);
932	IND	********if (n > old_n) {
933	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::buckets_type tmp(n, (node*)0);
934	IND	************for (size_type bucket = 0; bucket < old_n; ++bucket) {
935		node* first = buckets[bucket];
936		while (first) {
937		size_type new_bucket = bkt_num(first->val, n);
938	IND	********************buckets[bucket] = first->next;
939	IND	********************first->next = tmp[new_bucket];
940	IND	********************tmp[new_bucket] = first;
941	IND	********************first = buckets[bucket];
942	IND	****************}
943	IND	************}
944	IND	************buckets.clear();
945	IND	************buckets.swap(tmp);
946	IND	********}
947		}
948		}
949
950
951	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
952		void
953	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
954		hashtable_node<Value>* first,
955		hashtable_node<Value>* last)
956		{
957		node* cur = buckets[n];
958		if (cur == first)
959	IND	****erase_bucket(n, last);
960		else {
961		node* next;
962		for (next = cur->next; next != first; cur = next, next = cur->next)
963	SEM,SEM,SEM,SEM,SEM,SEM,IND	******;
964		while (next) {
965		cur->next = next->next;
966		delete_node(next);
967		next = cur->next;
968		--num_elements;
969	IND	****}
970	IND	**}
971		}
972
973	LEN	template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
974		void
975	LEN	hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
976	LEN	hashtable_node<Value>* last)
977		{
978		node* cur = buckets[n];
979		while (cur != last) {
980		node* next = cur->next;
981		delete_node(cur);
982		cur = next;
983		buckets[n] = cur;
984		--num_elements;
985	IND	**}
986		}
987
988		template <class Value, class Alloc>
989		void hashtable_base<Value, Alloc>::clear()
990		{
991		for (size_type i = 0; i < buckets.size(); ++i) {
992		node* cur = buckets[i];
993		while (cur != 0) {
994		node* next = cur->next;
995		delete_node(cur);
996		cur = next;
997	IND	****}
998		buckets[i] = 0;
999	IND	**}
1000		num_elements = 0;
1001		}
1002
1003
1004		template <class Value, class Alloc>
1005	LEN	void hashtable_base<Value, Alloc>::copy_from(const hashtable_base<Value, Alloc>& ht)
1006		{
1007		buckets.reserve(ht.buckets.size());
1008		buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
1009		for (size_type i = 0; i < ht.buckets.size(); ++i) {
1010		const node* cur = ht.buckets[i];
1011		if (cur) {
1012		node* copy = new_node(cur->val);
1013		buckets[i] = copy;
1014		++num_elements;
1015
1016		for (node* next = cur->next; next; cur = next, next = cur->next) {
1017		copy->next = new_node(next->val);
1018		++num_elements;
1019		copy = copy->next;
1020	IND	******}
1021	IND	****}
1022	IND	**}
1023		}
1024
1025		}// end namespace itk
1026
1027
1028		# undef __difference_type__
1029		# undef __size_type__
1030		# undef __value_type__
1031		# undef __key_type__
1032		# undef __node__
1033
1034		// the following is added for itk compatability:
1035
1036		// --
1037
1038		// A few compatability fixes.  Placed here for automatic include in
1039		// both the hash_set and the hash_map sources.
1040	LEN	# if defined(VCL_SUNPRO_CC) || defined (_MSC_VER) || defined(__BORLANDC__) || ((defined(__ICC)||defined(__ECC)) && defined(linux))
1041		namespace std
1042		{
1043		template <class T>
1044		struct identity : public std::unary_function<T, T> {
1045		public:
1046		const T& operator()(const T& x) const { return x; }
1047		};
1048		}
1049
1050		template <class _Pair>
1051	LEN	struct itk_Select1st : public std::unary_function<_Pair, typename _Pair::first_type> {
1052		typename _Pair::first_type const & operator()(_Pair const & __x) const {
1053		return __x.first;
1054	IND	**}
1055	IND	};
1056
1057		template <class _Pair>
1058	LEN	struct itk_Select2nd : public std::unary_function<_Pair, typename _Pair::second_type> {
1059		typename _Pair::second_type const & operator()(_Pair const & __x) const {
1060		return __x.second;
1061	IND	**}
1062	IND	};
1063
1064		// Add select* to std.
1065		namespace std {
1066	IND	**template <class _Pair>
1067	IND,IND,IND	**struct select1st : public itk_Select1st<_Pair> { };
1068	IND,IND,IND	**template <class _Pair> struct select2nd : public itk_Select2nd<_Pair> { };
1069		};
1070
1071		#endif
1072
1073		#endif
1074
1075		#endif // itk_emulation_hashtable_h
1076

---

Generated by KWStyle 1.0b on Tuesday January,17 at 02:14:55PM

© Kitware Inc.