/***************************************************************************
 * 
 * Copyright (c) 2008 Baidu.com, Inc. All Rights Reserved
 * $Id: bsl_readset.h,v 1.9 2009/04/07 06:35:53 xiaowei Exp $ 
 * 
 **************************************************************************/
 
 
 
/**
 * @file bsl_readset.h
 * @author yingxiang(yingxiang@baidu.com)
 * @date 2008/08/14 13:39:16
 * @version $Revision: 1.9 $   2010/10/15 modified by zhjw(zhujianwei@baidu.com)
 * @brief A read-only hash table
 *  
 **/


#ifndef  __BSL_READSET_H_
#define  __BSL_READSET_H_

#include "bsl/alloc/bsl_alloc.h"
#include "bsl/utils/bsl_utils.h"
#include "bsl/containers/hash/bsl_hashutils.h"
#include "bsl/archive/bsl_serialization.h"
#include "bsl/exception/bsl_exception.h"
#include <string.h>
#include <algorithm>

namespace bsl{

template <class _Key,
		 class _HashFunction = xhash<_Key>,
		 class _EqualFunction = std::equal_to<_Key>,
		 class _Alloc = bsl_alloc<_Key> >
class readset{
private:
	//data structure types
	typedef _Key key_type;
	typedef size_t size_type;
	typedef size_t sign_type;//Hash signature type, generated by HashFunction
	typedef readset<_Key, _HashFunction, _EqualFunction, _Alloc> self_type;

	struct _node_type{
		size_type idx, pos, hash_value;
	}; 
public:
	enum{ DEFAULT_BUCKET_SIZE = 65535 };
	typedef key_type* iterator;
	typedef const key_type* const_iterator;
	typedef _node_type node_type;
private:
	//Allocator types
	typedef typename _Alloc::template rebind <iterator> :: other itr_alloc_type;
	typedef typename _Alloc::template rebind <key_type> :: other key_alloc_type;
	typedef typename _Alloc::template rebind <node_type> :: other node_alloc_type;
public:
	//compare functions 
	static int _cmp_hash(node_type __a, node_type __b){ 
		return __a.hash_value < __b.hash_value; 
	}
	static int _cmp_idx(node_type __a, node_type __b){ 
		return __a.idx < __b.idx; 
	}
private:
	//data
	iterator* _bucket;
	iterator _storage;
	size_type _hash_size;		/**<¹þϣͰµÄ´óС        */
	size_type _size;		  /**<¹þÏ£ÖÐÔªËصĸöÊý        */
	size_type _mem_size;	/**< ÄÚ´æ¿Õ¼ä£¬=_hash_size+1    */
	//Object Function
	_HashFunction _hashfun;
	_EqualFunction _eqfun;
	//Allocators
	itr_alloc_type _itr_alloc;
	key_alloc_type _key_alloc;
	node_alloc_type _node_alloc;
public:

	/* *
	 * @brief ĬÈϹ¹Ô캯Êý
	 * ÎÞÒì³£
	 * Ðèµ÷create
	 * */
	readset(){
		_reset();
	}

	/**
	 * @brief ´øÍ°´óСµÄ¹¹Ô캯Êý
	 *        Èç¹û¹¹Ôìʧ°Ü£¬½«Ïú»Ù¶ÔÏó
	 * Å×Òì³£
	 * ²»Ðèµ÷create         
	 * @param  [in] __bucket_size   : const size_type
	 * @param  [in] __hash_func     : const _HashFunction&
	 * @param  [in] __equal_func    : const _EqualFunction&
	 * @return
	 * @retval
	 * @see
	 * @author liaoshangbin
	 * @data 2010/08/30 15:16:58
	 **/
	readset(const size_type __bucket_size, 
			const _HashFunction& __hash_func = _HashFunction(), 
			const _EqualFunction& __equal_func = _EqualFunction()){
		_reset();
		if (create(__bucket_size,__hash_func,__equal_func) != 0) {
			destroy();
			throw BadAllocException()<<BSL_EARG
				<<"create error when create readset bitems "<<__bucket_size;
		}
	}

	/**
	 * @brief ¿½±´¹¹Ô캯Êý£¬Å×Òì³£
	 *        Èç¹û¹¹Ôìʧ°Ü£¬½«Ïú»Ù¶ÔÏó
	 *          
	 * @param  [in] other   : const readset&
	 * @return
	 * @retval
	 * @see
	 * @author liaoshangbin
	 * @data 2010/08/30 15:19:10
	 **/
	readset(const self_type& other) {
		_reset();
		if (assign(other.begin(),other.end()) != 0) {
			destroy();
			throw BadAllocException()<<BSL_EARG<<"assign readset error";
		}
	}

	/**
	 * @brief ¸³ÖµÔËËã·û
	 *        ÏÈ»ñµÃ×ÔÉíµÄÒ»¸ö¿½±´£¬Èç¹û¸³ÖµÊ§°Ü£¬½«»Ö¸´³ÉÔ­À´µÄreadset
	 *          
	 * @param  [in] other	: const readset&
	 * @return
	 * @retval
	 * @see
	 * @author liaoshangbin
	 * @data 2010/08/30 15:20:16
	 **/
	self_type& operator = (const self_type& other) {
		if (this != &other) {
			readset self_(*this);
			if (assign(other.begin(),other.end()) != 0) {
				destroy();
				*this = self_;
				throw BadAllocException()<<BSL_EARG<<"assign readset error";
			}
		}
		return *this;
	}

	/**
	 * @brief ´´½¨hash±í£¬Ö¸¶¨Í°´óСºÍhashº¯Êý¡¢±È½Ïº¯Êý
	 *
	 * @param [in] __bucket_size   : const size_type 
	 *				Í°´óС
	 * @param [in] __hash_func   : const _HashFunction& 
	 *				hashº¯Êý£¬²ÎÊýΪ__key&,·µ»ØֵΪsize_t
	 * @param [in] __equal_func   : const _EqualFunction&
	 *				±È½Ïº¯Êý£¬Ä¬ÈÏʹÓÃ==
	 * @return  int 
	 *			<li> -1£º³ö´í
	 *			<li> 0£º³É¹¦
	 * @retval   
	 * @see 
	 * @note Èç¹ûhashÍ°ÒѾ­´´½¨£¬µÚ¶þ´Îµ÷ÓÃcreateʱ»áÏÈdestroy֮ǰµÄhash±í
	 * @author yingxiang
	 * @date 2008/08/14 11:24:28
	**/
	int create(const size_type __bucket_size = size_type(DEFAULT_BUCKET_SIZE), 
			const _HashFunction& __hash_func = _HashFunction(), 
			const _EqualFunction& __equal_func = _EqualFunction()){
		if(_hash_size){
			destroy();//·ÀÖ¹Öظ´create
		}

		_itr_alloc.create();
		_key_alloc.create();
		_node_alloc.create();

		_hashfun = __hash_func;
		_eqfun = __equal_func;
		_hash_size = __bucket_size;

		if(_hash_size <= 0){
			return -1;
		}

		_mem_size = _hash_size + 1;//¿ÉÒÔÓÅ»¯²éѯËÙ¶È
		_bucket = _itr_alloc.allocate(_mem_size);
		if(0 == _bucket){
			return -1;
		}	
		return 0;
	}

    /* *
     * @brief ÅжÏreadsetÊÇ·ñÒÑcreate
     * @author zhujianwei
     * @date 2010/12/13
     * */
    bool is_created() const{
        return (_bucket != 0);
    }

	/**
	 * @brief Ïòhash±íÖи³³õʼԪËØ¡£½«[start, finish)Çø¼äµÄÔªËزåÈëhash±í<br>
	 *			[start, finish)Ϊ×ó±ÕÓÒ¿ªÇø¼ä <br>
	 *			Èç¹ûassign֮ǰδÏÔʽµ÷ÓÃcreate£¬assign»á×Ô¶¯µ÷ÓÃcreate <br>
	 *
	 * @param [in] __start   : _Iterator ÆðʼλÖÃ
	 * @param [in] __finish   : _Iterator ÖÕֹλÖÃ
	 * @return  int 
	 *			<li> 0 : ³É¹¦
	 *			<li> -1 : ÆäËû´íÎó
	 * @retval   
	 * @see 
	 * @note ²åÈëµÄkeyÖµ²»¿ÉÒÔÓÐÏàͬ
	 * @author yingxiang
	 * @date 2008/08/14 11:32:20
	**/
	template <class _Iterator>
	int assign(const _Iterator __start, const _Iterator __finish){
		if(_size) {
			clear();
		}

		_size = std::distance(__start, __finish);
		
		if (_size == 0) {
			return 0;
		}
		//Èç¹ûδÏÔʾµ÷ÓÃcreate£¬Ôò×Ô¶¯´´½¨£¬Í°´óСΪ4±¶
		if(0 == _hash_size) {
			if(create(_size * 4)){
				return -1;
			}
		}

		iterator p = _key_alloc.allocate(_size);
		if(0 == p) {
			_size = 0;
			return -1;
		}
		_storage = p;

		node_type* temp = _node_alloc.allocate(_size);
		if(0 == temp) {
			_key_alloc.deallocate(p, _size);
			_size = 0;
			return -1;
		}

		_Iterator itr = __start;
		size_type i, j;
		for(i = 0; itr != __finish; ++itr, ++i){
			temp[i].idx = i;
			temp[i].hash_value = _hashfun(*itr) % _hash_size;
		}

		//Ϊÿ¸öÂܲ··ÖÅäÒ»¸ö¿Ó
		std::sort(temp, temp + _size, _cmp_hash);
		for(i = 0; i < _size; ++i){
			temp[i].pos = i;
		}

		//¼ÆËãÍ°Èë¿Ú
		for(i = 0, j = 0; j < _mem_size; ++j){
			while(i < _size && temp[i].hash_value < j){
				++i;
			}
			_bucket[j] = _storage + i;
		}

		//¿½±´ÄÚ´æµ½´æ´¢Çø
		std::sort(temp, temp + _size, _cmp_idx);
		for(i = 0, itr = __start; i < _size; ++i, ++itr){
			bsl::bsl_construct(&_storage[temp[i].pos], *itr);
		}

		_node_alloc.deallocate(temp, _size);

		return 0;
	}

	/**
	 * @brief ¸ù¾ÝKeyÖµ²éѯ
	 *
	 * @param [in] __key   : const key_type& Òª²éѯµÄKeyÖµ
	 * @return  int 
	 *			<li> HASH_EXIST : ´æÔÚ
	 *			<li> HASH_NOEXIST : ²»´æÔÚ
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 15:50:34
	**/
	int get(const key_type& __key) const{
		if(0 == _size){
			return HASH_NOEXIST;
		}
		sign_type hash_value = _hashfun(__key) % _hash_size;
		for(iterator p = _bucket[hash_value]; p < _bucket[hash_value + 1]; ++p){
			if(_eqfun(__key, *p)){
				return HASH_EXIST;
			}
		}
		return HASH_NOEXIST;
	}

	/**
	 * @brief ·µ»Øhash±íÖеÄÔªËظöÊý
	 *
	 * @return  size_type ÔªËظöÊý
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 15:53:51
	**/
	size_type size() const {
		return _size;
	}

	/**
	 * @brief ·µ»Øhash±íÍ°´óС
	 *
	 * @return  size_type Í°´óС
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 15:54:30
	**/
	size_type bucket_size() const {
		return _hash_size;
	}

	/**
	 * @brief Ïú»Ùhash±í
	 *
	 * @return  void 
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 15:54:52
	**/
	void destroy(){
		clear();
		if(_mem_size > 0 && NULL != _bucket){
			_itr_alloc.deallocate(_bucket, _mem_size);
			_mem_size = _hash_size = 0;
			_bucket = NULL;
		}
		_key_alloc.destroy();
		_itr_alloc.destroy();
		_node_alloc.destroy();
	}

	/**
	 * @brief Çå¿Õhash±íÖеÄÔªËØ
	 *
	 * @return  void 
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 15:55:07
	**/
	void clear(){
		if(_size > 0 && NULL != _storage){
			bsl::bsl_destruct(_storage, _storage + _size);
			_key_alloc.deallocate(_storage, _size);
			_size = 0;
			_storage = NULL;
		}
	}

	/**
	 * @brief ´æ´¢ÇøµÄÍ·²¿Ö¸Õë¡£ÓÃÓÚ±éÀúhash±íÖеÄÔªËØ¡£½öÓÃÓÚ·ÃÎʲÙ×÷
	 *
	 * @return  const iterator Í·²¿Ö¸Õë¡£¿ÕÈÝÆ÷·µ»ØNULL
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/21 15:01:53
	**/
	iterator begin(){
		return _storage;
	}

	/**
	 * @brief ´æ´¢ÇøµÄÍ·²¿Ö¸Õë
	 */
	const_iterator begin() const {
		return _storage;
	}

	/**
	 * @brief ´æ´¢ÇøµÄβ²¿Ö¸Õë
	 *
	 * @return  const iterator β²¿Ö¸Õ루ָÏòµÄÄÚ´æµ¥Ôª²»¿ÉÒÔ±»·ÃÎÊ© 
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/21 15:02:31
	**/
	iterator end(){
		return _storage + size();
	}
	
	/**
	 * @brief ´æ´¢ÇøµÄβ²¿Ö¸Õë
	 */
	const_iterator end() const {
		return _storage + size();
	}

	~readset(){
		destroy();
	}

	/**
	 * @brief ´®Ðл¯¡£½«hash±í´®Ðл¯µ½Ö¸¶¨µÄÁ÷
	 *
	 * @param [in/out] ar   : _Archive& ´®Ðл¯Á÷
	 * @return  int 
	 *			<li> 0 : ³É¹¦
	 *			<li> -1 : ʧ°Ü
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 16:08:11
	**/
	template <class _Archive>
	int serialization(_Archive & ar) {
		if(bsl::serialization(ar, _hash_size) != 0){
			goto _ERR_S;
		}
		if(bsl::serialization(ar, _size) != 0) {
			goto _ERR_S;
		}
		size_type i;
		for(i = 0; i < _size; ++i){
			if(bsl::serialization(ar, _storage[i]) != 0){
				goto _ERR_S;
			}
		}
		return 0;
_ERR_S:
		return -1;
	}

	/**
	 * @brief ·´´®Ðл¯¡£´Ó´®Ðл¯Á÷ÖлñÈ¡Êý¾ÝÖؽ¨hash±í
	 *
	 * @param [in] ar   : _Archive& ´®Ðл¯Á÷
	 * @return  int 
     *          <li> 0 : ³É¹¦
     *          <li> -1 : ʧ°Ü
	 * @retval   
	 * @see 
	 * @author yingxiang
	 * @date 2008/08/14 16:08:19
	**/
	template <class _Archive>
	int deserialization(_Archive & ar){
		size_type fsize, hashsize, i;
		iterator tmp_storage = NULL;

		destroy();

		if(bsl::deserialization(ar, hashsize) != 0){
			goto _ERR_DS;
		}
		if(bsl::deserialization(ar, fsize) != 0){
			goto _ERR_DS;
		}
		if(hashsize <= 0 || fsize <= 0) {
			goto _ERR_DS;
		}

		if(create(hashsize) != 0){
			goto _ERR_DS;
		}

		tmp_storage = _key_alloc.allocate(fsize);
		if(NULL == tmp_storage){ 
			goto _ERR_DS;
		}

		for(i = 0; i < fsize; ++i){
			bsl::bsl_construct(&tmp_storage[i]);
		}

		for(i = 0; i < fsize; ++i){
			if(bsl::deserialization(ar, tmp_storage[i]) != 0){
				goto _ERR_DS;
			}
		}

		if(assign(tmp_storage, tmp_storage + fsize) != 0){
			goto _ERR_DS;
		}

		bsl::bsl_destruct(tmp_storage, tmp_storage + fsize);
		_key_alloc.deallocate(tmp_storage, fsize);
		return 0;
_ERR_DS:
		if(NULL != tmp_storage){
			bsl::bsl_destruct(tmp_storage, tmp_storage + fsize);
			_key_alloc.deallocate(tmp_storage, fsize);
		}
		destroy();
		return -1;
	}
private:
	void _reset(){
		_bucket = NULL;
		_storage = NULL;
		_hash_size = 0;
		_mem_size = 0;
		_size = 0;
	}

};//class readset

}//namespace bsl






#endif  //__BSL_READSET_H_

/* vim: set ts=4 sw=4 sts=4 tw=100 noet: */