xhash

来自「C语言库函数的原型,有用的拿去」· 代码 · 共 1,029 行 · 第 1/2 页

		return (_Num);
		}

	iterator lower_bound(key_type _Keyval)
		{	// find leftmost node not less than _Keyval
		return (make_iterator(lower_bound_node(_Keyval)));
		}

	node_type^ lower_bound_node(key_type _Keyval)
		{	// find leftmost node not less than _Keyval
		size_type _Bucket = _Hashval(_Keyval);
		node_type^ _Where = hash_node(_Bucket);

		for (; _Where != hash_node(_Bucket + 1);
			_Where = _Where->next_node())
			if (this->comp(this->get_key(_Where->_Myval), _Keyval))
				return (!this->comp(_Keyval,
					this->get_key(_Where->_Myval)) ? head_node() : _Where);
		return (head_node());
		}

	iterator upper_bound(key_type _Keyval)
		{	// find leftmost node greater than _Keyval
		return (make_iterator(upper_bound_node(_Keyval)));
		}

	node_type^ upper_bound_node(key_type _Keyval)
		{	// find leftmost node greater than _Keyval
		size_type _Bucket = _Hashval(_Keyval);
		node_type^ _Where = hash_node(_Bucket + 1);

		for (; _Where != hash_node(_Bucket); )
			{	// scan down to first that matches key, then back up one
			_Where = _Where->prev_node();
			if (this->comp(_Keyval, this->get_key(_Where->_Myval)))
				return (!this->comp(this->get_key(_Where->_Myval),
					_Keyval) ? head_node() : _Where->next_node());
			}
		return (head_node());
		}

	pair_iter_iter equal_range(key_type _Keyval)
		{	// find range equivalent to _Keyval
		_Pairnn _Ans = equal_range_node(_Keyval);
		return (pair_iter_iter(iterator(_Ans.first),
			iterator(_Ans.second)));
		}

	_Pairnn equal_range_node(key_type _Keyval)
		{	// find range equivalent to _Keyval
		return (_Pairnn(lower_bound_node(_Keyval),
			upper_bound_node(_Keyval)));
		}

#if 0
void dumptab()
	{
	int i;
	int siz = _Myvector->Length;

	System::Console::WriteLine("\nmaxidx = {0}, mask = {1}", _Maxidx, _Mask);
	for (i = 0; i < siz; ++i)
		{
		node_type^ p;

		System::Console::Write("bucket {0}:", i);
		if (hash_node(i) != head_node())
		System::Console::Write("begins with {0}:",
			(char)hash_node(i)->_Myval->first);
		if (hash_node(i) == head_node())
			break;
		else if (i + 1 == siz)
			for (p = hash_node(i); p != head_node(); p = p->next_node())
				System::Console::Write(" {0}", (char)p->_Myval->first);
		else
			for (p = hash_node(i); p != hash_node(i + 1); p = p->next_node())
				System::Console::Write(" {0}", (char)p->_Myval->first);
		System::Console::WriteLine(" end");
		}
	System::Console::WriteLine("dump end");
	}
#endif

_STLCLR_FIELD_ACCESS:
	void _Resize(size_type _Newsize, node_type^ _Pad)
		{	// change table size
		size_type _Idx = 0;
		size_type _Oldsize = _Myvector == nullptr ? 0 : _Myvector->Length;
		_Myvector_t^ _Newvector = gcnew _Myvector_t(_Newsize);

		for (; _Idx < _Oldsize; ++_Idx)
			 _Newvector[_Idx] = _Myvector[_Idx];
		for (; _Idx < _Newvector->Length; ++_Idx)
			 _Newvector[_Idx] = _Pad;
		_Myvector = _Newvector;
		}

	void _Grow(int _Buckets)
		{	// incrementally grow table
		for (; bucket_count() < _Buckets; )
			{	// too dense, need to grow hash table
			node_type^ _Node;

			if (_Myvector->Length - 1 <= _Maxidx)
				{	// table full, double its size
				_Mask = ((_Myvector->Length - 1) << 1) - 1;
				_Resize(_Mask + 2, head_node());
				}
			else if (_Mask < _Maxidx)
				_Mask = (_Mask << 1) + 1;

			size_type _Bucket = _Maxidx - (_Mask >> 1) - 1;

			for (_Node = hash_node(_Bucket);
				_Node != hash_node(_Bucket + 1); )
				{	// split old bucket
				size_type _Newbucket =
					this->hash_fun(this->get_key(_Node->_Myval)) & _Mask;

				if (_Newbucket == _Bucket)
					_Node = _Node->next_node();	// leave element in old bucket
				else
					{	// move element to new bucket
					size_type _Idx;
					node_type^ _Next = _Node->next_node();

					if (_Next != head_node())
						{	// not at end, move it
						for (_Idx = _Bucket; _Node == hash_node(_Idx); )
							{	// update end iterators if moving first
							set_hash_node(_Idx, _Next);
							if (--_Idx < 0)
								break;
							}
						_Mylist->splice_node(_Mylist->head_node(), _Mylist,
							(list_node<value_type>^)_Node,
							(list_node<value_type>^)_Next);
						_Node = back_node();
						_Myvector[_Maxidx + 1] = head_node();
						}

					for (_Idx = _Maxidx; _Bucket < _Idx; --_Idx)
						{	// update end iterators if new bucket filled
						if (hash_node(_Idx) != head_node())
							break;
						set_hash_node(_Idx, _Node);
						}

					if (_Next == head_node())
						break;
					else
						_Node = _Next;
					}
				}
			++_Maxidx;	// open new bucket for hash lookup
			}
		}

	size_type _Hashval(key_type% _Keyval)
		{	// return hash value, masked and wrapped to current table size
		size_type _Num = this->hash_fun(_Keyval) & _Mask;

		if (_Maxidx <= _Num)
			_Num -= (_Mask >> 1) + 1;
		return (_Num);
		}

	void _Init(int _Buckets)
		{	// initialize for a minimum table size of _Buckets
		_Buckets = _True_buckets(_Buckets);
		_Mylist = gcnew _Mylist_t;
		_Myvector = nullptr;
		_Resize(_Buckets + 1, head_node());
		_Mygen = 0;

		_Mask = _Buckets - 1;
		_Maxidx = _Buckets;
		_Max_load_factor = _Default_load;
		}

	void _Reinsert()
		{	// insert elements at beginning of list into table
		for (; front_node() != hash_node(0); )
			{	// hash another node
			list_node<value_type>^ _Node = _Mylist->front_node();

			insert_node(_Node->_Myval, _Node);
			}
		}

	void _Rebuild_table(int _Buckets)
		{	// rebuild hash table
		_Myvector = nullptr;
		_Resize(_Buckets + 1, head_node());
		_Mask = _Buckets - 1;
		_Maxidx = _Buckets;	// blow away old hash table

		_Reinsert();	// insert old list into table
		}

	int _True_buckets(int _Buckets)
		{	// canonicalize bucket count
		if (_Buckets < 0)
			throw gcnew System::ArgumentException();

		int _Newsize = _Default_buckets;

		for (; _Newsize < _Buckets && _Newsize < _Maxsize / 2; )
			_Newsize *= 2;	// double until big enough
		return (_Newsize);
		}

	// data members
	_Mylist_t^ _Mylist;		// list of elements
	_Myvector_t^ _Myvector;	// the hash table
	unsigned long _Mygen;	// current change generation	///INCREMENT!!!

	int _Mask;		// the key mask
	int _Maxidx;	// current maximum key value
	float _Max_load_factor;	// maximum average elements per bucket

	// interfaces
public:
	virtual System::Object^ Clone()
		{	// clone the hash
		return (gcnew hash(*this));
		}

private:
	property size_type Count
		{	// element count
		virtual size_type get() sealed
			= System::Collections::ICollection::Count::get
			{	// get element count
			return (size());
			}
		};

	property bool IsSynchronized
		{	// synchronized status
		virtual bool get() sealed
			= System::Collections::ICollection::IsSynchronized::get
			{	// test if synchronized
			return (false);
			}
		};

	property System::Object^ SyncRoot
		{	// synchronizer
		virtual System::Object^ get() sealed
			= System::Collections::ICollection::SyncRoot::get
			{	// get synchronizer
			return (this);
			}
		};

	virtual void CopyTo(System::Array^ _Dest_arg, int _First) sealed
		= System::Collections::ICollection::CopyTo
		{	// copy to _Dest_arg, beginning at _First
		cli::array<System::Object^>^ _Dest =
			(cli::array<System::Object ^>^)_Dest_arg;
		node_type^ _Node = head_node();

		for (int _Idx = size(); 0 <= --_Idx; )
			{	// copy back to front
			_Node = _Node->prev_node();
			_Dest[_First + _Idx] = _Node->_Myval;
			}
		}

	virtual System::Collections::IEnumerator^ GetEnumerator() sealed
		= System::Collections::IEnumerable::GetEnumerator
		{	// get enumerator for the container
		return (gcnew _STLCLR HashEnumerator<_Key_t, _Value_t>(front_node()));
		}

	virtual unsigned long get_generation_virtual() sealed
		= _Mycont_it::get_generation
		{	// get underlying container generation
		return (get_generation());
		}

//	virtual bool valid_bias_virtual(size_type _Bias);
//	virtual reference at_virtual(size_type _Pos);
//	virtual reference at_bias_virtual(size_type _Bias);

//	virtual reference front_virtual();
//	virtual reference back_virtual();

	// converters
	virtual key_compare^ key_comp_virtual() sealed
		= _Mycont_it::key_comp
		{	// return object for comparing keys
		return (key_comp());
		}

	virtual value_compare^ value_comp_virtual() sealed
		= _Mycont_it::value_comp
		{	// return object for comparing keys
		return (value_comp());
		}

	// iterator generators
	virtual generic_iterator begin_virtual() sealed
		= _Mycont_it::begin
		{	// return iterator for beginning of mutable sequence
		return (begin());
		}
	virtual generic_iterator end_virtual() sealed
		= _Mycont_it::end
		{	// return iterator for end of mutable sequence
		return (end());
		}

	virtual generic_reverse_iterator rbegin_virtual() sealed
		= _Mycont_it::rbegin
		{	// return reverse iterator for beginning of mutable sequence
		return (generic_reverse_iterator(end()));
		}

	virtual generic_reverse_iterator rend_virtual() sealed
		= _Mycont_it::rend
		{	// return reverse iterator for end of mutable sequence
		return (generic_reverse_iterator(begin()));
		}

	// size controllers
//	virtual void reserve_virtual(size_type _Capacity);
//	virtual size_type capacity_virtual();
//	virtual void resize_virtual(size_type _Newsize);
//	virtual void resize_virtual(size_type _Newsize, value_type _Val);

	virtual size_type size_virtual() sealed
		= _Mycont_it::size
		{	// return length of sequence
		return (size());
		}

	virtual bool empty_virtual() sealed
		= _Mycont_it::empty
		{	// test if sequence is empty
		return (empty());
		}

	// hash controllers
	virtual hasher^ hash_delegate_virtual() sealed
		= _Mycont_it::hash_delegate
		{	// return object for hashing key
		return (hash_delegate());
		}

	virtual int bucket_count_virtual() sealed
		= _Mycont_it::bucket_count
		{	// return number of buckets in table
		return (bucket_count());
		}

	virtual float load_factor_virtual() sealed
		= _Mycont_it::load_factor
		{	// return average number of elements per bucket
		return (load_factor());
		}

	virtual float max_load_factor_virtual() sealed
		= _Mycont_it::max_load_factor
		{	// return maximum number of elements per bucket
		return (max_load_factor());
		}

	virtual void max_load_factor_virtual(float _Newmax) sealed
		= _Mycont_it::max_load_factor
		{	// set maximum load factor
		max_load_factor(_Newmax);
		}

	virtual void rehash_virtual(int _Buckets) sealed
		= _Mycont_it::rehash
		{	// try to grow table to at least _Buckets buckets
		rehash(_Buckets);
		}

	// mutators
//	virtual void push_front_virtual(value_type _Val);
//	virtual void pop_front_virtual();
//	virtual void push_back_virtual(value_type _Val);
//	virtual void pop_back_virtual();

//	virtual void assign_virtual(size_type _Count, value_type _Val);
//	virtual void assign_virtual(
//		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _Last);
//	virtual void assign_virtual(_Myenum_it^ _Right);

	virtual generic_pair_iter_bool insert_virtual(value_type _Val) sealed
		= _Mycont_it::insert
		{	// try to insert node with value _Val, return iterator, bool
		_Pairnb _Ans = insert_node(_Val, nullptr);
		return (generic_pair_iter_bool(gcnew generic_iterator(_Ans.first),
			_Ans.second));
		}

	virtual generic_iterator insert_virtual(generic_iterator _Where,
		value_type _Val) sealed
		= _Mycont_it::insert
		{	// insert _Val at _Where
		return (insert(iterator(_Where), _Val));
		}

//	virtual void insert_virtual(generic_iterator _Where,
//		size_type _Count, value_type _Val);
//	virtual void insert_virtual(generic_iterator _Where_iter,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
//		_STLCLR Generic::IInputIterator<_Value_t>^ _Last);
//	virtual void insert_virtual(generic_iterator _Where_iter,
//		_Myenum_it^ _Right);

	virtual void insert_virtual(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last) sealed
		= _Mycont_it::insert
		{	// insert [_First, _Last) one at a time
		insert(_First, _Last);
		}

	virtual void insert_virtual(
		System::Collections::IEnumerable^ _Right) sealed
		= _Mycont_it::insert
		{	// insert enumerable
		insert(_Right);
		}

	virtual generic_iterator erase_virtual(generic_iterator _Where) sealed
		= _Mycont_it::erase
		{	// erase element at _Where
		return (erase(iterator(_Where)));
		}

	virtual generic_iterator erase_virtual(generic_iterator _First,
		generic_iterator _Last) sealed
		= _Mycont_it::erase
		{	// erase [_First, _Last)
		return (erase(iterator(_First), iterator(_Last)));
		}

	virtual size_type erase_virtual(key_type _Keyval) sealed
		= _Mycont_it::erase
		{	// erase and count all that match _Keyval
		return (erase(_Keyval));
		}

	virtual void clear_virtual() sealed
		= _Mycont_it::clear
		{	// erase all
		clear();
		}

	virtual void swap_virtual(_Mycont_it^ _Right) sealed
		= _Mycont_it::swap
		{	// exchange contents with _Right
		swap(*(_Mytype_t^)_Right);
		}

	// searches
	virtual generic_iterator find_virtual(key_type _Keyval) sealed
		= _Mycont_it::find
		{	// find an element that matches _Keyval, return iterator
		return (find(_Keyval));
		}

	virtual size_type count_virtual(key_type _Keyval) sealed
		= _Mycont_it::count
		{	// count all elements that match _Keyval
		return (count(_Keyval));
		}

	virtual generic_iterator lower_bound_virtual(key_type _Keyval) sealed
		= _Mycont_it::lower_bound
		{	// find leftmost node not less than _Keyval
		return (lower_bound(_Keyval));
		}

	virtual generic_iterator upper_bound_virtual(key_type _Keyval) sealed
		= _Mycont_it::upper_bound
		{	// find leftmost node greater than _Keyval
		return (upper_bound(_Keyval));
		}

	virtual generic_pair_iter_iter equal_range_virtual(
		key_type _Keyval) sealed
			= _Mycont_it::equal_range
		{	// find range equivalent to _Keyval
		_Pairnn _Ans = equal_range_node(_Keyval);
		return (generic_pair_iter_iter(gcnew generic_iterator(_Ans.first),
			gcnew generic_iterator(_Ans.second)));
		}
	};
	}	// namespace cliext::impl
//
// TEMPLATE FUNCTION swap
//
template<typename _Traits_t> inline
	void swap(cliext::impl::hash<_Traits_t>% _Left,
		cliext::impl::hash<_Traits_t>% _Right)
	{	// swap two hash objects
	_Left.swap(_Right);
	}
}	// namespace cliext
#endif // _CLI_XHASH_

/*
 * Copyright (c) 2004-2007 by Dinkumware, Ltd.  ALL RIGHTS RESERVED.
 * Consult your license regarding permissions and restrictions.
V5.03:0009 */