xhash

C语言库函数的原型,有用的拿去

// xhash stl/clr header
#ifndef _CLI_XHASH_
 #define _CLI_XHASH_
#include <cliext/functional>	// for Binary/UnaryDelegate
#include <cliext/list>		// for the sequence container

namespace cliext {
//
// TEMPLATE FUNCTION _Hash_key_compare
//
template<typename _Key_t> inline
	bool _Hash_key_compare(_Key_t _Left, _Key_t _Right)
	{	// test if _Left <= _Right
	return (!(_Right < _Left));
	}

inline bool _Hash_key_compare(System::String^ _Left, System::String^ _Right)
	{	// test if _Left <= _Right for String
	return (!(_Right->CompareTo(_Left) < 0));
	}

//
// FUNCTION hash_value
//
inline int hash_value(System::Object^ _Key)
	{	// get hash code from object
	return (_Key->GetHashCode());
	}

	namespace impl {
//
// TEMPLATE CLASS hash
//
template<typename _Traits_t>
	ref class hash
	:	public _Traits_t,
		_STLCLR IHash<
			typename _Traits_t::key_type,
			typename _Traits_t::value_type>
	{	// hash table of elements
public:
	// types
	typedef hash<_Traits_t> _Mytype_t;
	typedef _Traits_t _Mybase_t;
	typedef typename _Traits_t::key_type _Key_t;
	typedef typename _Traits_t::value_type _Value_t;
	typedef _STLCLR IHash<_Key_t, _Value_t> _Mycont_it;
	typedef System::Collections::Generic::IEnumerable<_Value_t> _Myenum_it;
	typedef cli::array<_Value_t> _Myarray_t;

	typedef list<_Value_t> _Mylist_t;	// the controlled sequence
	typedef list_node<_Value_t> node_type;
	typedef cli::array<node_type^> _Myvector_t;	// the hash table

	typedef typename _Mylist_t::iterator
		iterator;
	typedef typename _Mylist_t::const_iterator
		const_iterator;
	typedef typename _Mylist_t::reverse_iterator
		reverse_iterator;
	typedef typename _Mylist_t::const_reverse_iterator
		const_reverse_iterator;

	typedef typename _Traits_t::key_type key_type;
	typedef typename _Traits_t::value_type value_type;
	typedef typename _Traits_t::key_compare key_compare;
	typedef typename _Traits_t::value_compare value_compare;
	typedef typename _Traits_t::hasher hasher;

	typedef int size_type;
	typedef int difference_type;
//	typedef _Value_t value_type;
	typedef value_type% reference;
	typedef value_type% const_reference;

	typedef _Mycont_it generic_container;
	typedef value_type generic_value;
	typedef _STLCLR Generic::ContainerBidirectionalIterator<_Value_t>
		generic_iterator;
	typedef typename _Mylist_t::generic_reverse_iterator
		generic_reverse_iterator;

	typedef _STLCLR GenericPair<iterator, bool> pair_iter_bool;
	typedef _STLCLR GenericPair<iterator, iterator> pair_iter_iter;
	typedef _STLCLR GenericPair<node_type^, bool> _Pairnb;
	typedef _STLCLR GenericPair<node_type^, node_type^> _Pairnn;

	typedef _STLCLR GenericPair<generic_iterator^, bool>
		generic_pair_iter_bool;
	typedef _STLCLR GenericPair<generic_iterator^, generic_iterator^>
		generic_pair_iter_iter;

	// constants
	static const int _Maxsize = MAX_CONTAINER_SIZE;
	static const int _Default_load = 4;		// default _Max_load_factor
	static const int _Default_buckets = 16;	// default table size, power of 2!

	// basics
	hash()
		{	// construct empty hash from default
		_Init(0);
		}

	hash(hash% _Right)
		:	_Mybase_t(_Right.comp, _Right.hash_fun)
		{	// construct by copying _Right
		_Init(_Right.bucket_count());
		_Mylist->insert_node(_Mylist->head_node(),
			_Right._Mylist->front_node(), _Right._Mylist->head_node());
		_Reinsert();
		}

	hash% operator=(hash% _Right)
		{	// assign
		if ((Object^)this != %_Right)
			{	// worth doing, do it
			clear();
			_Mylist->insert_node(_Mylist->head_node(),
				_Right._Mylist->front_node(), _Right._Mylist->head_node());
			_Reinsert();
			}
		return (*this);
		}

	operator _Mycont_it^()
		{	// convert to interface
		return (this);
		}

	// constructors
	explicit hash(key_compare^ _Pred)
		:	_Mybase_t(_Pred)
		{	// construct empty hash from compare
		_Init(0);
		}

	hash(key_compare^ _Pred, hasher^ _Hashfn)
		:	_Mybase_t(_Pred, _Hashfn)
		{	// construct empty hash from compare and hash
		_Init(0);
		}

	// destructor
	~hash()
		{	// destroy the object
		clear();
		_Mylist = nullptr;
		_Myvector = nullptr;
		++_Mygen;
		}

	// accessors
	unsigned long get_generation()
		{	// get underlying container generation
		return (_Mygen);
		}

	node_type^ get_node(iterator _Where)
		{	// get node from valid iterator
		return (_Mylist->get_node(_Mylist_t::iterator(_Where)));
		}

	node_type^ hash_node(size_type _Idx)
		{	// get node from hash table
		return (_Myvector[_Idx]);
		}

	void set_hash_node(size_type _Idx, node_type^ _Node)
		{	// set node from hash table
		_Myvector[_Idx] = _Node;
		}

	node_type^ front_node()
		{	// return leftmost node in list
		return (_Mylist->front_node());
		}

	node_type^ back_node()
		{	// return rightmost node in list
		return (_Mylist->back_node());
		}

	node_type^ head_node()
		{	// get head node
		return (_Mylist->head_node());
		}

//	property reference default[/* size_type */];
//	property value_type front_item;
//	property value_type back_item;
//	reference front();
//	reference back();

	// converters
	_Myarray_t^ to_array()
		{	// convert to array
		return (_Mylist->to_array());
		}

	key_compare^ key_comp() new
		{	// return object for comparing keys
		return (_Mybase_t::key_comp());
		}

	value_compare^ value_comp() new
		{	// return object for comparing keys
		return (_Mybase_t::value_comp());
		}

	hasher^ hash_delegate() new
		{	// return object for hashing key
		return (_Mybase_t::hash_delegate());
		}

	// iterator generators
	iterator make_iterator(node_type^ _Node)
		{	// return iterator for node
		return (_Mylist->make_iterator(_Node));
		}

	iterator begin()
		{	// return iterator for beginning of mutable sequence
		return (_Mylist->begin());
		}

	iterator end()
		{	// return iterator for end of mutable sequence
		return (_Mylist->end());
		}

	reverse_iterator rbegin()
		{	// return reverse iterator for beginning of mutable sequence
		return (_Mylist->rbegin());
		}

	reverse_iterator rend()
		{	// return reverse iterator for end of mutable sequence
		return (_Mylist->rend());
		}

	// size controllers
//	void reserve(size_type _Capacity);
//	size_type capacity();
//	void resize(size_type _Newsize);
//	void resize(size_type _Newsize, value_type _Val);

	size_type size()
		{	// return length of sequence
		return (_Mylist->size());
		}

	bool empty()
		{	// test if sequence is empty
		return (size() == 0);
		}

	int bucket_count()
		{	// return number of buckets in table
		return (_Maxidx);
		}

	float load_factor()
		{	// return average number of elements per bucket
		return ((float)size() / (float)bucket_count());
		}

	float max_load_factor()
		{	// return maximum number of elements per bucket
		return (_Max_load_factor);
		}

	void max_load_factor(float _Newmax)
		{	// set maximum load factor
		if (_Newmax != _Newmax	// might detect a NaN
			|| _Newmax <= 0)
			throw gcnew System::ArgumentException();

		_Max_load_factor = _Newmax;
		}

	// mutators
	void rehash(int _Buckets)
		{	// try to grow table to at least _Buckets buckets
		_Buckets = _True_buckets(_Buckets);

		if ((float)size() / (float)_Buckets <= max_load_factor())
			_Rebuild_table(_Buckets);
		}

//	void push_front(value_type _Val);
//	void pop_front();
//	void push_back(value_type _Val);
//	void pop_back();

//	void assign(size_type _Count, value_type _Val);
//	template<typename _Iter_t>
//		void assign(_Iter_t _First, _Iter_t _Last);
//	void assign(System::Collections::Generic::IEnumerable<_Value_t>^);

	pair_iter_bool insert(value_type _Val)
		{	// try to insert node with value _Val, return iterator, bool
		_Pairnb _Ans = insert_node(_Val, nullptr);

		return (pair_iter_bool(iterator(_Ans.first),
			_Ans.second));
		}

	iterator insert(iterator,
		value_type _Val)
		{	// try to insert node with value _Val at _Where, return iterator
		_Pairnb _Ans = insert_node(_Val, nullptr);

		return (make_iterator(_Ans.first));
		}

	template<typename _Iter_t>
		void insert(_Iter_t _First, _Iter_t _Last)
		{	// insert [_First, _Last) one at a time
#pragma warning(push)
#pragma warning(disable: 4127)
		if (_Iter_container(_First) != _Mylist)
			for (; _First != _Last; ++_First)
				insert_node(*_First, nullptr);
		else if (_Multi)
			{	// worth assigning to self
			for (; _First != _Last; ++_First)
				_Mylist->insert_node(_Mylist->front_node(), 1, *_First);
			_Reinsert();
			}
#pragma warning(pop)
		}

	void insert(
		_STLCLR Generic::IInputIterator<_Value_t>^ _First,
		_STLCLR Generic::IInputIterator<_Value_t>^ _Last)
		{	// insert [_First, _Last) one at a time
#pragma warning(push)
#pragma warning(disable: 4127)
		if (_First->container() != _Mylist)
			for (; !_First->equal_to(_Last); _First->next())
				insert_node((value_type%)_First->get_cref(), nullptr);
		else if (_Multi)
			{	// worth assigning to self
			for (; !_First->equal_to(_Last); _First->next())
				_Mylist->insert_node(front_node(), 1,
					(value_type%)_First->get_cref());
			_Reinsert();
			}
#pragma warning(pop)
		}

	void insert(_Myenum_it^ _Right)
		{	// insert enumerable
		for each (value_type _Val in _Right)
			_Mylist->insert_node(_Mylist->front_node(), 1, _Val);
		_Reinsert();
		}

	void insert(System::Collections::IEnumerable^ _Right)
		{	// insert enumerable
		for each (value_type _Val in _Right)
			_Mylist->insert_node(_Mylist->front_node(), 1, _Val);
		_Reinsert();
		}

//	void insert(iterator _Where, size_type _Count, value_type _Val);
//	template<typename _Iter_t>
//		void insert(iterator _Where, _Iter_t _First, _Iter_t _Last);
//	void insert(iterator _Where,
//		System::Collections::Generic::IEnumerable<_Value_t>^ _Right);

	_Pairnb insert_node(value_type _Val, list_node<value_type>^ _Newnode)
		{	// try to insert node with value _Val, return node pointer, bool
#pragma warning(push)
#pragma warning(disable: 4127)
		size_type _Bucket = _Hashval(this->get_key(_Val));
		node_type^ _Node = hash_node(_Bucket + 1);	// end node for bucket

		for (; _Node != hash_node(_Bucket); )
			if (!this->comp(this->get_key(_Val),
				this->get_key((_Node = _Node->prev_node())->_Myval)))
				;	// still too high in bucket list
			else if (_Multi
				|| !this->comp(this->get_key(_Node->_Myval),
					this->get_key(_Val)))
				{	// found insertion point, back up to it
				_Node = _Node->next_node();
				break;
				}
			else
				{	// discard new node and return existing node
				if (_Newnode != nullptr)
					_Mylist->erase_node(_Newnode);
				return (_Pairnb(_Node, false));
				}
		if (_Newnode != nullptr)
			_Mylist->splice_node((list_node<value_type>^)_Node, _Mylist,
				_Newnode, _Newnode->_Next);	// place existing node
		else
			{	// insert value to make new node
			_Mylist->insert_node((list_node<value_type>^)_Node, 1, _Val);
			_Newnode = (list_node<value_type>^)_Node->prev_node();
			}

		for (; _Node == hash_node(_Bucket); --_Bucket)
			{	// update end iterators if new first bucket element
			set_hash_node(_Bucket, _Newnode);
			if (_Bucket == 0)
				break;
			}

		if (max_load_factor() < load_factor())
			_Grow(bucket_count() + 1);
		++_Mygen;
		return (_Pairnb(_Newnode, true));	// return added node
#pragma warning(pop)
		}

	iterator erase(iterator _Where)
		{	// erase element at _Where
		return (make_iterator(erase_node(get_node(_Where))));
		}

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		node_type^ _First_node = get_node(_First);
		node_type^ _Last_node = get_node(_Last);

		if (_First_node == front_node() && _Last_node == head_node())
			clear();	// erase all
		else
			for (; _First_node != _Last_node; )
				_First_node = erase_node(_First_node);
		return (_Last);
		}

	size_type erase(key_type _Keyval)
		{	// erase and count all that match _Keyval
		node_type^ _First = lower_bound_node(_Keyval);
		node_type^ _Last = upper_bound_node(_Keyval);
		size_type _Num = 0;

		for (; _First != _Last; ++_Num)
			_First = erase_node(_First);	// erase an element matching key
		return (_Num);
		}

	node_type^ erase_node(node_type^ _Where)
		{	// erase node at _Where
		if (_Where->container() != _Mylist || _Where->is_head())
			throw gcnew System::InvalidOperationException();

		size_type _Bucket = _Hashval(this->get_key(_Where->_Myval));

		for (; _Where == hash_node(_Bucket); --_Bucket)
			{	// update end iterators if erasing first
			set_hash_node(_Bucket, hash_node(_Bucket)->next_node());
			if (_Bucket == 0)
				break;
			}

		++_Mygen;
		return (_Mylist->erase_node((list_node<value_type>^)_Where));
		}

	void clear()
		{	// erase all
		_Mylist->clear();
		_Rebuild_table(_Myvector->Length - 1);
		++_Mygen;
		}

	void swap(_Mytype_t% _Right)
		{	// exchange contents with _Right
		if ((Object^)this != %_Right)
			{	// worth doing, swap
			_Mylist_t^ _Tlist = _Mylist;
			_Myvector_t^ _Tvector = _Myvector;
			int _Tmask = _Mask;
			int _Tmaxidx = _Maxidx;
			float _Tmax_load_factor = _Max_load_factor;

			_Mylist = _Right._Mylist;
			_Right._Mylist = _Tlist;

			_Myvector = _Right._Myvector;
			_Right._Myvector = _Tvector;

			_Mask = _Right._Mask;
			_Right._Mask = _Tmask;

			_Maxidx = _Right._Maxidx;
			_Right._Maxidx = _Tmaxidx;

			_Max_load_factor = _Right._Max_load_factor;
			_Right._Max_load_factor = _Tmax_load_factor;
			++_Mygen;
			++_Right._Mygen;
			}
		}

	// searches
	iterator find(key_type _Keyval)
		{	// find an element that matches _Keyval, return iterator
		return (make_iterator(lower_bound_node(_Keyval)));
		}

	size_type count(key_type _Keyval)
		{	// count all elements that match _Keyval
		node_type^ _First = lower_bound_node(_Keyval);
		node_type^ _Last = upper_bound_node(_Keyval);
		size_type _Num = 0;

		for (; _First != _Last; _First = _First->next_node())
			++_Num;