[原]利用最小堆管理事件超时

长平狐 发布于 2012/11/14 12:20
阅读 120
收藏 1

引言:前面的一系列文章都在说了事件模型,也就是简单的做一个介绍,然后贴出了一些代码作为Demo,上次说到了在反应堆中的超时管理。今天就来说说关于利用最小堆来管理超时的问题。

NOTICE:判断一个事件是否超时的方法是, 事件超时时间 减  当前时间 ,如果大于零,说明没有超时,如果小于零,说明该事件超时了。

一般做法是怎样来管理所有的超时事件呢?以前的用法都是利用链表来保存所有的超时事件,轮训查看是否事件超时,若超时就采取相应的措施,比如移除事件等。后来的Nginx和libevent采取了更好的措施,Nginx是利用红黑树来管理,而libevent是利用最小堆来管理。

今天的主题是最小堆,所以下面的内容都是围绕最小堆来展开。

这里说说最小堆的好处,然后接着说明为什么要利用最小堆来管理超时事件。

最小堆的好处:

(1)最小堆的设计简单,易于实现

(2)插入和删除操作都是在log(n)基础上完成

(3)获取最小值是O(1)

为什么要利用最小堆:

大家都知道在IO多路复用中比如 select() 和 epoll() 都有一个超时的最大时间,也就是说,如果没有监听到事件,最大的阻塞时间就是这参数。

当我们在Reactor中加入了一个超时事件的时候,我们就利用这个最小堆中的根节点的时间减去当前时间作为select/epoll超时的最大值。所以,当select/epoll返回的时候得到函数执行的消耗的时间,查看最小堆的根是否超时(NOTICE),如果没有超时,我们继续正常步骤,如果超时就采取相应措施,比如超时事件的回调函数等,然后继续查看新的堆结构的根节点,直到处理不超时的情况出现,因为堆是自适应的,所以根部必然是值最小的,如果这个事件没有超时,就可以停止超时事件的处理 了。

所以总体来看,每次都会找到最小堆中最小的元素作为比较,事件复杂度是O(1)

最小堆的性质:

所有父节点总是小于或等于所有的子节点(递归定义),看做二叉树的话是完全二叉树

看看最小堆的实现:

结构表示:

typedef struct heap_node_s
{
	int   index;
	int   key  ;
}mc_minheap_node_t ;

typedef struct min_heap_s
{
	mc_minheap_node_t   *node_list ;
	int				     headindex ;
	int 			     lastindex ;
	size_t			     max_num   ;
}mc_minheap_t;

几个宏:

#define MAX_INT    0x0fffffff
#define PARENT(i) 		((i)/(2))
#define LEFTCHILD(i)	((i)*(2))
#define RIGHTCHILD(i)	(((i)*(2))+(1))

插入:

每次插入到堆的末尾,然后逐层比较,直到大于父节点。

int mc_minheap_insert( mc_minheap_t *mh ,int key )
{
	if( mh == NULL )
		return -1;
	int lastindex = mh->lastindex;
	mh->node_list[lastindex].key = key ;
	mh->node_list[lastindex].index = lastindex ;
	int tindex = lastindex ;
	
	//heap top
	if( lastindex == 1 )
	{
		mh->lastindex++ ;
		return 1;
	}
	else
	{
		if( lastindex >= mh->max_num -1 )
			return -1;
		while( tindex  != 1 )
		{
			if( key < mh->node_list[PARENT( tindex )].key )
			{
				swap_node( &(mh->node_list[tindex]),  &(mh->node_list[PARENT( tindex )]) );
			}
			tindex = PARENT( tindex );

		}		
	}
	mh->lastindex++ ;
	return 1;
}

删除:

删除的时候,把需要删除的节点与堆的最后一个节点交换,删除这个节点。然后交换后的这个节点与子节点中较小的一个比较,如果大于它就交换,如果小于就结束,直到没有子节点。

int mc_minheap_rm( mc_minheap_t *mh )
{
	if( mh == NULL )
		return -1;
	int ret = mh->node_list[1].key  ;
	mh->node_list[1].key = MAX_INT ;
	mc_minheap_node_t * pnode = &(mh->node_list[1]) ;
	mc_minheap_node_t *minnode ;
	swap_node( pnode , &(mh->node_list[mh->lastindex]));
	
	int i = 1 ;
	for( ; i < mh->lastindex ; i++ )
	{
		minnode = mh->node_list[LEFTCHILD(i)].key <= mh->node_list[RIGHTCHILD(i)].key ? &(mh->node_list[LEFTCHILD(i)]) : &(mh->node_list[RIGHTCHILD(i)]);
		
		if( i == mh->max_num -1 )
			break ;
		if( minnode->key == MAX_INT )
			break ;
		if( pnode.key > minnode.key ) 
			swap_node( pnode , minnode );
		else
			break;
		pnode = minnode ;
	}
	mh->lastindex-- ;
	return ret ;
}


int mc_minheap_rm_index( mc_minheap_t *mh ,int index )
{
	if( mh == NULL )
		return -1;
	if( index > mh->lastindex )
		return -1;
	int ret = mh->node_list[index].key  ;
	mh->node_list[index].key = MAX_INT ;
	mc_minheap_node_t * pnode = &(mh->node_list[index]) ;
	mc_minheap_node_t *minnode ;
	swap_node( pnode , &(mh->node_list[mh->lastindex]));
	
	int i = index ;
	for( ; i < mh->lastindex ; i++ )
	{
		minnode = mh->node_list[LEFTCHILD(i)].key <= mh->node_list[RIGHTCHILD(i)].key ? &(mh->node_list[LEFTCHILD(i)]) : &(mh->node_list[RIGHTCHILD(i)]);
		
		if( i == mh->max_num -1 )
			break ;
		if( minnode->key == MAX_INT )
			break ;
		if( pnode.key > minnode.key ) 
			swap_node( pnode , minnode );
		else
			break;
		pnode = minnode ;
	}
	mh->lastindex-- ;
	return ret ;
}

初始化和交换节点:

mc_minheap_t * mc_minheap_ini(int nodenum )
{
	int  i = 0 ;
	if(  nodenum <= 0 )
		return NULL;
	mc_minheap_t * mh = ( mc_minheap_t *)malloc( sizeof( mc_minheap_t ));
	if( mh == NULL )
	{
		return NULL;
	}
	mh->node_list = (mc_minheap_node_t  *)malloc( sizeof(mc_minheap_node_t )*nodenum );
	mh->headindex = 1 ;
	mh->lastindex= 1 ;
	for( i = 0 ; i < nodenum ; i++ )
	{
		mh->node_list[i].key = MAX_INT ;
		mh->node_list[i].index = i+1;
	}
	mh->max_num = nodenum ;
	return mh;
}

static int swap_node( mc_minheap_node_t * n1 , mc_minheap_node_t *n2 )
{
	if( n1 == NULL || n2 == NULL )
		return -1;
	mc_minheap_node_t temp;
	
	
	temp.key = n1->key ;

	n1->key = n2->key;
	
	n2->key = temp.key ;
}

总结:最小堆的设计方式比较简单,但是功能不错,有一个缺点就是初始化的时候需要固定大小的节点个数,如果超时事件过多,需要采取一定的措施来保证堆的代码质量。或许可以采用多个对的方式,然后比较每一个堆的最小值,这样也就是O(N)复杂度,N= 堆的个数,这里是我的一厢情愿罢了..

文章如有错误请指正,我会在收到留言的第一时间修改。欢迎交流


原文链接:http://www.cnblogs.com/Bozh/archive/2012/04/30/2477122.html
加载中
返回顶部
顶部