xhash.h

一些unix下的c/c++的util包

// xhash internal header
#ifndef _XHASH_H_
#define _XHASH_H_
#include <cstring>
#include <cwchar>
#include <functional>
#include <list>
#include <vector>

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

namespace nlkit
{
/* 
We start off by defining a specialisation of hash_value for stdext.
This will work for stdext::hash_map<std::string, ...
If the user is using std::hash_map, we pull the specialisation into std
as well.

This comes at the top of our file before everything else to ensure we
only pull in this one specialisation.
*/



template<class _Elem,
	class _Traits,
	class _Alloc> inline
	size_t hash_value(const ::std::basic_string<_Elem, _Traits, _Alloc>& _Str)
	{	// hash string to size_t value
	typedef typename ::std::basic_string<_Elem, _Traits, _Alloc>::size_type _Strsize;

	size_t _Val = _HASH_SEED;
	_Strsize _Size = _Str.size();
	if (0 < _Size)
		{	// add one or more elements
		_Strsize _Stride = (_Size / 16) + 1;
		_Size -= _Stride;	// protect against _Size near _Str.max_size()
		for(_Strsize _Idx = 0; _Idx <= _Size; _Idx += _Stride)
			_Val += (size_t)_Str[_Idx];
		}
	return (_Val);
	}


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);
	}

inline size_t hash_value(const char *_Str)
	{	// hash NTBS to size_t value
	typedef size_t _Strsize;

	size_t _Val = _HASH_SEED;
	_Strsize _Size = ::strlen(_Str);
	if (0 < _Size)
		{	// add one or more elements
		_Strsize _Stride = (_Size / 16) + 1;
		_Size -= _Stride;	// protect against _Size near _Str.max_size()
		for(_Strsize _Idx = 0; _Idx <= _Size; _Idx += _Stride)
			_Val += (size_t)_Str[_Idx];
		}
	return (_Val);
	}

inline size_t hash_value(const wchar_t *_Str)
	{	// hash NTWCS to size_t value
	typedef size_t _Strsize;

	size_t _Val = _HASH_SEED;
	_Strsize _Size = ::wcslen(_Str);
	if (0 < _Size)
		{	// add one or more elements
		_Strsize _Stride = (_Size / 16) + 1;
		_Size -= _Stride;	// protect against _Size near _Str.max_size()
		for(_Strsize _Idx = 0; _Idx <= _Size; _Idx += _Stride)
			_Val += (size_t)_Str[_Idx];
		}
	return (_Val);
	}

		// TEMPLATE CLASS hash_compare


template<class _Kty,
	class _Pr = ::std::less<_Kty> >
	class hash_compare
	{	// traits class for hash containers
public:
	enum
		{	// parameters for hash table
		bucket_size = 4,	// 0 < bucket_size
		min_buckets = 8};	// min_buckets = 2 ^^ N, 0 < N

	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
		return ((size_t)hash_value(_Keyval));
		}

//	size_t operator()(const _Kty& _Keyval) const
//		{	// hash _Keyval to size_t value by pseudorandomizing transform
//		ldiv_t _Qrem = ldiv((size_t)_Keyval, 127773);
//		_Qrem.rem = 16807 * _Qrem.rem - 2836 * _Qrem.quot;
//		if (_Qrem.rem < 0)
//			_Qrem.rem += 2147483647;
//		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
	};

		// 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::key_type key_type;
	typedef typename _Traits::key_compare key_compare;
	typedef typename _Traits::value_compare value_compare;
	enum
		{	// hoist constants from key_compare
		bucket_size = key_compare::bucket_size,
		min_buckets = key_compare::min_buckets,
		_Multi = _Traits::_Multi};
	typedef ::std::list<typename _Traits::value_type,
		typename _Traits::allocator_type> _Mylist;

	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 _Mylist::iterator iterator;
	typedef typename _Mylist::const_iterator const_iterator;
	typedef typename _Mylist::reverse_iterator
		reverse_iterator;
	typedef typename _Mylist::const_reverse_iterator
		const_reverse_iterator;
	typedef typename _Mylist::value_type value_type;

	/*typedef ::std::vector<iterator,
		typename allocator_type::template
			rebind<iterator>::other> _Myvec;*/
    typedef typename allocator_type::template rebind<iterator>::other otherAllocator;
    typedef ::std::vector<iterator, otherAllocator> _Myvec;			
	typedef ::std::pair<iterator, bool> _Pairib;
	typedef ::std::pair<iterator, iterator> _Pairii;
	typedef ::std::pair<const_iterator, const_iterator> _Paircc;

	_Hash(const key_compare& _Parg,
		const allocator_type& _Al)
		: _Traits(_Parg), _List(_Al),
			_Vec(min_buckets + 1, end(), _Al),
			_Mask(1), _Maxidx(1)
		{	// construct empty hash table
		}

	_Hash(const value_type *_First, const value_type *_Last,
		const key_compare& _Parg, const allocator_type& _Al)
		: _Traits(_Parg), _List(_Al),
			_Vec(min_buckets + 1, end(), _Al),
			_Mask(1), _Maxidx(1)
		{	// construct hash table from [_First, _Last) array
		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()
		{	// 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());
		}

	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()));
		}

	_Pairib insert(const value_type& _Val)
		{	// try to insert node with value _Val
		iterator _Plist, _Where;
		if (_Maxidx <= size() / bucket_size)
			{	// too dense, need to grow hash table
			if (_Vec.size() - 1 <= _Maxidx)
				{	// table full, double its size
				_Mask = ((_Vec.size() - 1) << 1) - 1;
				_Vec.resize(_Mask + 2, end());
				}
			else if (_Mask < _Maxidx)
				_Mask = (_Mask << 1) + 1;

			size_type _Bucket = _Maxidx - (_Mask >> 1) - 1;
			for (_Plist = _Vec[_Bucket]; _Plist != _Vec[_Bucket + 1]; )
				{	// split old bucket
				size_type _Newbucket =
					this->comp(this->_Kfn(*_Plist)) & _Mask;
				if (_Newbucket == _Bucket)
					++_Plist;	// leave element in old bucket
				else
					{	// move element to new bucket
					size_type _Idx;
					iterator _Pnext = _Plist;
					if (++_Pnext != end())
						{	// not at end, move it
						for (_Idx = _Bucket; _Plist == _Vec[_Idx]; --_Idx)
							{	// update end iterators if moving first
							_Vec[_Idx] = _Pnext;
							if (_Idx == 0)
								break;
							}