xhash.h

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

                        _List.splice(end(), _List, _Plist, _Pnext);
						//_List._Splice(end(), _List, _Plist, _Pnext, 0);
						_Plist = --end();
						_Vec[_Maxidx + 1] = end();
						}

					for (_Idx = _Maxidx; _Bucket < _Idx; --_Idx)
						{	// update end iterators if new bucket filled
						if (_Vec[_Idx] != end())
							break;
						_Vec[_Idx] = _Plist;
						}

					if (_Pnext == end())
						break;
					else
						_Plist = _Pnext;
					}
				}
			++_Maxidx;	// open new bucket for hash lookup
			}

		size_type _Bucket = _Hashval(this->_Kfn(_Val));
		for (_Plist = _Vec[_Bucket + 1]; _Plist != _Vec[_Bucket]; )
			if (this->comp(this->_Kfn(_Val), this->_Kfn(*--_Plist)))
				;	// still too high in bucket list
			else if (this->comp(this->_Kfn(*_Plist), this->_Kfn(_Val)))
				{	// found insertion point, back up to it
				++_Plist;
				break;
				}
			else if (_Multi)
				break;	// equivalent, insert only if multi
			else
				return (_Pairib(_Plist, false));	// already present

		_Where = _List.insert(_Plist, _Val);	// insert new element
		for (; _Plist == _Vec[_Bucket]; --_Bucket)
			{	// update end iterators if new first bucket element
			_Vec[_Bucket] = _Where;
			if (_Bucket == 0)
				break;
			}

		return (_Pairib(_Where, true));	// return iterator for new element
		}

	iterator insert(iterator, const value_type& _Val)
		{	// try to insert node with value _Val, ignore hint
		return (insert(_Val).first);
		}

	template<class _Iter>
		void insert(_Iter _First, _Iter _Last)
		{	// insert [_First, _Last) one at a time
		for (; _First != _Last; ++_First)
			insert(*_First);
		}

	iterator erase(iterator _Where)
		{	// erase element at _Where
		size_type _Bucket = _Hashval(this->_Kfn(*_Where));
		for (; _Where == _Vec[_Bucket]; --_Bucket)
			{	// update end iterators if erasing first
			++_Vec[_Bucket];
			if (_Bucket == 0)
				break;
			}
		return (_List.erase(_Where));
		}

	iterator erase(iterator _First, iterator _Last)
		{	// erase [_First, _Last)
		if (_First == begin() && _Last == end())
			{	// erase all
			clear();
			return (begin());
			}
		else
			{	// partial erase, one at a time
			while (_First != _Last)
				erase(_First++);
			return (_First);
			}
		}

	size_type erase(const key_type& _Keyval)
		{	// erase and count all that match _Keyval
		_Pairii _Where = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Where.first, _Where.second, _Num);
		erase(_Where.first, _Where.second);
		return (_Num);
		}

	void erase(const key_type *_First,
		const key_type *_Last)
		{	// erase all that match array of keys [_First, _Last)
		for (; _First != _Last; ++_First)
			erase(*_First);
		}

	void clear()
		{	// erase all
		_List.clear();
		_Vec.assign(min_buckets + 1, end());
		_Mask = 1;
		_Maxidx = 1;
		}

	iterator find(const key_type& _Keyval)
		{	// find an element in mutable hash table that matches _Keyval
		return (lower_bound(_Keyval));
		}

	const_iterator find(const key_type& _Keyval) const
		{	// find an element in nonmutable hash table that matches _Keyval
		return (lower_bound(_Keyval));
		}

	size_type count(const key_type& _Keyval) const
		{	// count all elements that match _Keyval
		_Paircc _Ans = equal_range(_Keyval);
		size_type _Num = 0;
		_Distance(_Ans.first, _Ans.second, _Num);
		return (_Num);
		}

	iterator lower_bound(const key_type& _Keyval)
		{	// find leftmost not less than _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		iterator _Where;
		for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				return (this->comp(_Keyval,
					this->_Kfn(*_Where)) ? end() : _Where);
		return (end());
		}

	const_iterator lower_bound(const key_type& _Keyval) const
		{	// find leftmost not less than _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		const_iterator _Where;
		for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				return (this->comp(_Keyval,
					this->_Kfn(*_Where)) ? end() : _Where);
		return (end());
		}

	iterator upper_bound(const key_type& _Keyval)
		{	// find leftmost not greater than _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		iterator _Where;
		for (_Where = _Vec[_Bucket + 1]; _Where != _Vec[_Bucket]; )
			if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
				return (this->comp(this->_Kfn(*_Where),
					_Keyval) ? end() : ++_Where);
		return (end());
		}

	const_iterator upper_bound(const key_type& _Keyval) const
		{	// find leftmost not greater than _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		const_iterator _Where;
		for (_Where = _Vec[_Bucket + 1]; _Where != _Vec[_Bucket]; )
			if (!this->comp(_Keyval, this->_Kfn(*--_Where)))
				return (this->comp(this->_Kfn(*_Where),
					_Keyval) ? end() : ++_Where);
		return (end());
		}

	_Pairii equal_range(const key_type& _Keyval)
		{	// find range equivalent to _Keyval in mutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		iterator _First, _Where;
		for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				{	// found _First, look for end of range
				for (_First = _Where; _Where != _Vec[_Bucket + 1]; ++_Where)
					if (this->comp(_Keyval, this->_Kfn(*_Where)))
						break;
				if (_First == _Where)
					break;
				return (_Pairii(_First, _Where));
				}
		return (_Pairii(end(), end()));
		}

	_Paircc equal_range(const key_type& _Keyval) const
		{	// find range equivalent to _Keyval in nonmutable hash table
		size_type _Bucket = _Hashval(_Keyval);
		iterator _First, _Where;
		for (_Where = _Vec[_Bucket]; _Where != _Vec[_Bucket + 1]; ++_Where)
			if (!this->comp(this->_Kfn(*_Where), _Keyval))
				{	// found _First, look for end of range
				for (_First = _Where; _Where != _Vec[_Bucket + 1]; ++_Where)
					if (this->comp(_Keyval, this->_Kfn(*_Where)))
						break;
				if (_First == _Where)
					break;
				return (_Paircc(_First, _Where));
				}
		return (_Paircc(end(), end()));
		}

	void swap(_Myt& _Right)
		{	// exchange contents with _Right
		if (get_allocator() == _Right.get_allocator())
			{	// same allocator, swap control information
			_List.swap(_Right._List);
			std::swap(_Vec, _Right._Vec);
			std::swap(_Mask, _Right._Mask);
			std::swap(_Maxidx, _Right._Maxidx);
			std::swap(this->comp, _Right.comp);
			}
		else
			{	// different allocator, do multiple assigns
			_Myt _Tmp = *this; *this = _Right, _Right = _Tmp;
			}
		}

protected:
	void _Copy(const _Myt& _Right)
		{	// copy entire hash table
		_Vec.resize(_Right._Vec.size(), end());
		_Mask = _Right._Mask;
		_Maxidx = _Right._Maxidx;
		_List.clear();

		try
		{
		_List.insert(end(), _Right._List.begin(), _Right._List.end());
		this->comp = _Right.comp;
		}
		catch(...)
		{
		_List.clear();	// list or compare copy failed, bail out
		fill(_Vec.begin(), _Vec.end(), end());
		throw;
		}

		iterator _Whereto = begin();
		const_iterator _Wherefrom = _Right.begin();
		for (size_type _Bucket = 0; _Bucket < _Vec.size(); )
			if (_Wherefrom == _Right._Vec[_Bucket])
				_Vec[_Bucket] = _Whereto, ++_Bucket;
			else
				++_Whereto, ++_Wherefrom;
		}

	size_type _Hashval(const key_type& _Keyval) const
		{	// return hash value, masked and wrapped to current table size
		size_type _Num = this->comp(_Keyval) & _Mask;
		if (_Maxidx <= _Num)
			_Num -= (_Mask >> 1) + 1;
		return (_Num);
		}

	_Mylist _List;	// the list of elements, must initialize before _Vec
	_Myvec _Vec;	// the vector of list iterators
	size_type _Mask;	// the key mask
	size_type _Maxidx;	// current maximum key value
	};

		// _Hash TEMPLATE OPERATORS
template<class _Ty> inline
	bool operator==(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test for hash table equality
	return (_Left.size() == _Right.size()
		&& equal(_Left.begin(), _Left.end(), _Right.begin()));
	}

template<class _Ty> inline
	bool operator!=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test for hash table inequality
	return (!(_Left == _Right));
	}

template<class _Ty> inline
	bool operator<(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left < _Right for hash tables
	return (lexicographical_compare(_Left.begin(), _Left.end(),
		_Right.begin(), _Right.end()));
	}

template<class _Ty> inline
	bool operator>(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left > _Right for hash tables
	return (_Right < _Left);
	}

template<class _Ty> inline
	bool operator<=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left <= _Right for hash tables
	return (!(_Right < _Left));
	}

template<class _Ty> inline
	bool operator>=(const _Hash<_Ty>& _Left, const _Hash<_Ty>& _Right)
	{	// test if _Left >= _Right for hash tables
	return (!(_Left < _Right));
	}
}
#endif /* _XHASH_H_ */