xhash

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

// xhash internal header
#pragma once
#ifndef _XHASH_
#define _XHASH_
#ifndef RC_INVOKED
#include <cstring>
#include <cwchar>
#include <xfunctional>
#include <list>
#include <vector>

 #pragma pack(push,_CRT_PACKING)
 #pragma warning(push,3)

 #ifndef _HAS_INCREMENTAL_HASH
  #define _HAS_INCREMENTAL_HASH	0	/* 1 for steady growth, 0 for leaps */
 #endif /* _HAS_INCREMENTAL_HASH */

#undef _HAS_STLPORT_EMULATION

 #pragma warning(disable: 4127)

namespace stdext {
using _STD basic_string;
using _STD less;
using _STD size_t;

		// TEMPLATE FUNCTION hash_value
 #define _HASH_SEED	(size_t)0xdeadbeef

template<class _Kty> inline
	size_t hash_value(const _Kty& _Keyval)
	{	// hash _Keyval to size_t value one-to-one
	return ((size_t)_Keyval ^ _HASH_SEED);
	}

template <class _InIt>
	inline size_t _Hash_value(_InIt _Begin, _InIt _End)
	{	// hash range of elements
	size_t _Val = 2166136261U;

	while (_Begin != _End)
		_Val = 16777619U * _Val ^ (size_t)*_Begin++;
	return (_Val);
	}

template<class _Elem,
	class _Traits,
	class _Alloc> inline
	size_t hash_value(const basic_string<_Elem, _Traits, _Alloc>& _Str)
	{	// hash string to size_t value
	const _Elem *_Ptr = _Str.c_str();

	return (_Hash_value(_Ptr, _Ptr + _Str.size()));
	}

inline size_t hash_value(_In_z_ const char *_Str)
	{	// hash NTBS to size_t value
	return (_Hash_value(_Str, _Str + _CSTD strlen(_Str)));
	}

inline size_t hash_value(_In_z_ const wchar_t *_Str)
	{	// hash NTWCS to size_t value
	return (_Hash_value(_Str, _Str + _CSTD wcslen(_Str)));
	}

 #ifdef _NATIVE_WCHAR_T_DEFINED
inline size_t hash_value(_In_z_ const unsigned short *_Str)
	{	// hash NTWCS to size_t value
	const unsigned short *_End = _Str;

	while (*_End != 0)
		++_End;
	return (_Hash_value(_Str, _End));
	}
 #endif /* _NATIVE_WCHAR_T_DEFINED */

		// TEMPLATE CLASS hash_compare
template<class _Kty,
	class _Pr = less<_Kty> >
	class hash_compare
	{	// traits class for hash containers
public:
	enum
		{	// parameters for hash table
		bucket_size = 1		// 0 < bucket_size
		};

	hash_compare()
		: comp()
		{	// construct with default comparator
		}

	hash_compare(_Pr _Pred)
		: comp(_Pred)
		{	// construct with _Pred comparator
		}

	size_t operator()(const _Kty& _Keyval) const
		{	// hash _Keyval to size_t value by pseudorandomizing transform
		long _Quot = (long)(hash_value(_Keyval) & LONG_MAX);
		ldiv_t _Qrem = _CSTD ldiv(_Quot, 127773);

		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
		if (_Qrem.rem < 0)
			_Qrem.rem += LONG_MAX;
		return ((size_t)_Qrem.rem);
		}

	bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const
		{	// test if _Keyval1 ordered before _Keyval2
		return (comp(_Keyval1, _Keyval2));
		}

protected:
	_Pr comp;	// the comparator object
	};
}	// namespace stdext
_STD_BEGIN
using stdext::hash_compare;
using stdext::hash_value;
_STD_END

_STD_BEGIN
		// TEMPLATE CLASS _Hash_compare
template<class _Kty,
	class _Hasher,
	class _Keyeq>
	class _Hash_compare
	{	// traits class for hash containers
public:
	typedef _Hasher hasher;
	enum
		{	// parameters for hash table
		bucket_size = 1	// 0 < bucket_size
		};

	_Hash_compare()
		{	// construct with default hasher and equality comparator
		}

	_Hash_compare(hasher _Hasharg)
		: _Hashobj(_Hasharg)
		{	// construct with hasher and default equality comparator
		}

	_Hash_compare(hasher _Hasharg, _Keyeq _Keyeqarg)
		: _Hashobj(_Hasharg), _Keyeqobj(_Keyeqarg)
		{	// construct with hasher and equality comparator
		}

	size_t operator()(const _Kty& _Keyval) const
		{	// hash _Keyval to size_t value
		return ((size_t)_Hashobj(_Keyval));
		}

	bool operator()(const _Kty& _Keyval1, const _Kty& _Keyval2) const
		{	// test if _Keyval1 NOT equal to _Keyval2
		return (!_Keyeqobj(_Keyval1, _Keyval2));
		}

	hasher _Hashobj;	// the hash object
	_Keyeq _Keyeqobj;	// the equality comparator object
	};

		// TEMPLATE CLASS _Hash
template<class _Traits>
	class _Hash
		: public _Traits	// traits serves as base class
	{	// hash table -- list with vector of iterators for quick access
public:
	typedef _Hash<_Traits> _Myt;
	typedef typename _Traits::_Val_type _Val_type;

	typedef typename _Traits::key_type key_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::value_compare value_compare;
	enum
		{	// various constants
		_Bucket_size = key_compare::bucket_size,
		_Min_buckets = 8,	// min_buckets = 2 ^^ N, 0 < N
		_Multi = _Traits::_Multi};
	typedef list<typename _Traits::value_type,
		typename _Traits::allocator_type> _Mylist;

	typedef typename _Mylist::value_type value_type;
	typedef typename _Mylist::allocator_type allocator_type;
	typedef typename _Mylist::size_type size_type;
	typedef typename _Mylist::difference_type difference_type;
	typedef typename _Mylist::pointer pointer;
	typedef typename _Mylist::const_pointer const_pointer;
	typedef typename _Mylist::reference reference;
	typedef typename _Mylist::const_reference const_reference;

	typedef typename _STD tr1::conditional<
		_STD tr1::is_same<key_type, value_type>::value,
		typename _Mylist::const_iterator,
		typename _Mylist::iterator>::type iterator;
	typedef typename _Mylist::const_iterator const_iterator;

	typedef _STD reverse_iterator<iterator> reverse_iterator;
	typedef _STD reverse_iterator<const_iterator> const_reverse_iterator;

	typedef vector<iterator,
		typename allocator_type::template
			rebind<iterator>::other> _Myvec;

	typedef pair<iterator, bool> _Pairib;
	typedef pair<iterator, iterator> _Pairii;
	typedef pair<const_iterator, const_iterator> _Paircc;

	_Hash(const key_compare& _Parg,
		const allocator_type& _Al)
		: _Traits(_Parg),
			_List(_Al),

			_Vec(_Al),

			_Max_bucket_size(_Bucket_size)
		{	// construct empty hash table
		_Init();
		}

	_Hash(const value_type *_First, const value_type *_Last,
		const key_compare& _Parg, const allocator_type& _Al)
		: _Traits(_Parg),
			_List(_Al),

			_Vec(_Al),

			_Max_bucket_size(_Bucket_size)
		{	// construct hash table from [_First, _Last) array
		_Init();
		insert(_First, _Last);
		}

	_Hash(const _Myt& _Right)
		: _Traits(_Right.comp),
			_List(_Right.get_allocator()),
			_Vec(_Right.get_allocator())
		{	// construct hash table by copying right
		_Copy(_Right);
		}

	_Hash(_Myt&& _Right)
		: _Traits(_Right.comp),
			_List(_Right.get_allocator()),
			_Vec(_Right.get_allocator())
		{	// construct hash table by copying right
		_Assign_rv(_STD forward<_Myt>(_Right));
		}

	_Myt& operator=(_Myt&& _Right)
		{	// assign by moving _Right
		_Assign_rv(_STD forward<_Myt>(_Right));
		return (*this);
		}

	void _Assign_rv(_Myt&& _Right)
		{	// assign by moving _Right
		if (this == &_Right)
			;
		else if (get_allocator() != _Right.get_allocator())
			_Xinvalid_argument("invalid hash move assign");
		else
			{	// clear this and steal from _Right
			clear();
			_Swap_adl(this->comp, _Right.comp);
			this->_List.swap(_Right._List);
			this->_Vec.swap(_Right._Vec);
			_STD swap(this->_Mask, _Right._Mask);
			_STD swap(this->_Maxidx, _Right._Maxidx);
			_STD swap(this->_Max_bucket_size, _Right._Max_bucket_size);
			}
		}

	template<class _Valty>
		_Pairib insert(_Valty&& _Val)
		{	// try to insert node with value _Val
		_List.emplace_front(_STD forward<_Valty>(_Val));
		return (_Insert(_List.front(), begin()));
		}

	template<class _Valty>
		typename _STD tr1::enable_if<!_STD tr1::is_same<const_iterator,
			typename _STD tr1::remove_reference<_Valty>::type>::value,
				iterator>::type
		insert(const_iterator, _Valty&& _Val)

		{	// try to insert node with value _Val, ignore hint
		_List.emplace_front(_STD forward<_Valty>(_Val));
		return (_Insert(_List.front(), begin()).first);
		}

	template<class _Valty>
		_Pairib emplace(_Valty&& _Val)
		{	// try to insert node with value _Val...
		_List.emplace_front(_STD forward<_Valty>(_Val));
		return (_Insert(_List.front(), begin()));
		}

	template<class _Valty>
		iterator emplace_hint(const_iterator, _Valty&& _Val)
		{	// try to insert node with value _Val..., ignore hint
		_List.emplace_front(_STD forward<_Valty>(_Val));
		return (_Insert(_List.front(), begin()).first);
		}

	void swap(_Myt&& _Right)
		{	// exchange contents with movable _Right
		_Assign_rv(_STD forward<_Myt>(_Right));
		}

	~_Hash()
		{	// destroy hash table
		}

	_Myt& operator=(const _Myt& _Right)
		{	// replace contents from _Right
		if (this != &_Right)
			_Copy(_Right);
		return (*this);
		}

	iterator begin()
		{	// return iterator for beginning of mutable sequence
		return (_List.begin());
		}

	const_iterator begin() const
		{	// return iterator for beginning of nonmutable sequence
		return (_List.begin());
		}

	iterator end()
		{	// return iterator for end of mutable sequence
		return (_List.end());
		}

	const_iterator end() const
		{	// return iterator for end of nonmutable sequence
		return (_List.end());
		}

	reverse_iterator rbegin()
		{	// return iterator for beginning of reversed mutable sequence
		return (_List.rbegin());
		}

	const_reverse_iterator rbegin() const
		{	// return iterator for beginning of reversed nonmutable sequence
		return (_List.rbegin());
		}

	reverse_iterator rend()
		{	// return iterator for end of reversed mutable sequence
		return (_List.rend());
		}

	const_reverse_iterator rend() const
		{	// return iterator for end of reversed nonmutable sequence
		return (_List.rend());
		}

 #if _HAS_CPP0X
	const_iterator cbegin() const
		{	// return iterator for beginning of nonmutable sequence
		return (((const _Myt *)this)->begin());
		}

	const_iterator cend() const
		{	// return iterator for end of nonmutable sequence
		return (((const _Myt *)this)->end());
		}

	const_reverse_iterator crbegin() const
		{	// return iterator for beginning of reversed nonmutable sequence
		return (((const _Myt *)this)->rbegin());
		}

	const_reverse_iterator crend() const
		{	// return iterator for ebd of reversed nonmutable sequence
		return (((const _Myt *)this)->rend());
		}
 #endif /* _HAS_CPP0X */

	size_type size() const
		{	// return length of sequence
		return (_List.size());
		}

	size_type max_size() const
		{	// return maximum possible length of sequence
		return (_List.max_size());
		}

	bool empty() const
		{	// return true only if sequence is empty
		return (_List.empty());
		}

	allocator_type get_allocator() const
		{	// return allocator object for values
		return (_List.get_allocator());
		}

	key_compare key_comp() const
		{	// return object for comparing keys
		return (this->comp);
		}

	value_compare value_comp() const
		{	// return object for comparing values
		return (value_compare(key_comp()));
		}

// ADDED WITH TR1
	typedef iterator local_iterator;
	typedef const_iterator const_local_iterator;

	size_type bucket_count() const
		{	// return number of buckets
		return (_Maxidx);
		}

	size_type max_bucket_count() const
		{	// return maximum number of buckets
		return (_Vec.size() / 2);
		}

	size_type bucket(const key_type& _Keyval) const
		{	// return bucket corresponding to _Key
		return (_Hashval(_Keyval));
		}

	size_type bucket_size(size_type _Bucket) const
		{	// return size of bucket _Bucket
		size_type _Ans = 0;
		if (_Bucket < _Maxidx)
			for (const_iterator _Plist = _Begin(_Bucket);
				_Plist != _End(_Bucket); ++_Plist)
				++_Ans;
		return (_Ans);
		}

	local_iterator begin(size_type _Bucket)
		{	// return iterator for bucket _Bucket
		if (_Bucket < bucket_count())
			return (_Begin(_Bucket));
		else
			return (end());
		}

	const_local_iterator begin(size_type _Bucket) const
		{	// return iterator for bucket _Bucket
		if (_Bucket < bucket_count())
			return (_Begin(_Bucket));
		else
			return (end());
		}

	local_iterator end(size_type _Bucket)
		{	// return iterator for bucket following _Bucket
		if (_Bucket < bucket_count())
			return (_End(_Bucket));
		else
			return (end());
		}

	const_local_iterator end(size_type _Bucket) const
		{	// return iterator for bucket following _Bucket
		if (_Bucket < bucket_count())
			return (_End(_Bucket));
		else
			return (end());
		}

	float load_factor() const
		{	// return elements per bucket
		return ((float)size() / (float)bucket_count());
		}

	float max_load_factor() const
		{	// return maximum elements per bucket