heap.c

C语言大堆排序算法,当定时器资源不足时,可用来实现软件定时器

/* ********************************************************************
**  FileName: heap.c
**  Description: The main entity for heap buffer management for NSY timer
**
**  Author: Jesse Jiang
**  Date  : July 10,2007
**  Versioin: v0.1
**
**  Version History:
**  ------------------------------------------------------------------
**   July 10, 2007   v0.1    Jesse Jiang   Initial version
**   Nov  26, 2007   v0.2    Jesse Jiang   Use struct timeval to replace
**                                         data in the structure T_HEAP_NODE
**
** *********************************************************************/
#undef NSY_WIN
#ifdef NSY_WIN
#include "stdafx.h"
#endif

#include "nsy_comm.h"
#include "nsy_heap.h"

#define parent_offset(offset)    ((offset - 1)>>1 ) // (offset - 1)/2
#define rchild_offset(offset)    ((offset + 1)<<1 ) // 2*offset + 2
#define lchild_offset(offset)    ((offset<<1) + 1 ) // 2*offset + 1
#define lsib_offset(rsib_offset) (rsib_offset + 1 )
#define rsib_offset(lsib_offset) (lsib_offset 1 1 )


static void drive_node_up(T_HEAP *heap,
                          int    top, // could be root of a subheap
                          int    gap, // insert point
                          T_HEAP_NODE *new_node)
{
   int parent;	
	
 
   while ((top < gap) && // in the heap
				  //(parent = parent_offset(gap), heap->heap_node[parent]->data > new_node->data)
				  (parent = parent_offset(gap), timeval_compare(&heap->heap_node[parent]->value, &new_node->value) > 0)
         )
   {
   	  /* swap parent and gap */
  	  //heap->heap_node[gap]->data  = heap->heap_node[parent]->data;
  	  heap->heap_node[gap]->value.tv_sec   = heap->heap_node[parent]->value.tv_sec;
  	  heap->heap_node[gap]->value.tv_usec  = heap->heap_node[parent]->value.tv_usec;
      heap->heap_node[gap]->id    = heap->heap_node[parent]->id; 
      heap->heap_node[gap]->hwnd  = heap->heap_node[parent]->hwnd; 
	  	gap       = parent;
   } 
   
   /* now fill the gap */
   //heap->heap_node[gap]->data  = new_node->data;
   heap->heap_node[gap]->value.tv_sec   = new_node->value.tv_sec;
   heap->heap_node[gap]->value.tv_usec  = new_node->value.tv_usec;
   
   heap->heap_node[gap]->id    = new_node->id; 
   heap->heap_node[gap]->hwnd  = new_node->hwnd; 

}

static int drive_gap_down(T_HEAP *heap, 
                          int gap, 
                          int end ) 
{
	/* propagate gap down to the bottom */
	int child;
	
  // while ((child = rchild_offset(gap)) < end )
  while ((child = rchild_offset(gap)) < end )
  {
		/* select the smaller of the children */
		if (heap->heap_node[child]->data > heap->heap_node[lsib_offset(child)]->data)
    {
    	/* go for the left sibling */
    	child = rsib_offset(child);
    }
	  //heap->heap_node[gap]->data = heap->heap_node[child]->data;
	  heap->heap_node[gap]->value.tv_sec  = heap->heap_node[child]->value.tv_sec;
	  heap->heap_node[gap]->value.tv_usec = heap->heap_node[child]->value.tv_usec;
	  
	  heap->heap_node[gap]->id   = heap->heap_node[child]->id;
	  heap->heap_node[gap]->hwnd = heap->heap_node[child]->hwnd;
    gap  = child;
  }
   
  /* the one case where a parent has a single (left) child */
  if (child == end)
  {
		//heap->heap_node[gap]->data  = heap->heap_node[lsib_offset(child)]->data;
		heap->heap_node[gap]->value.tv_sec   = heap->heap_node[lsib_offset(child)]->value.tv_sec;
   	heap->heap_node[gap]->value.tv_usec  = heap->heap_node[lsib_offset(child)]->value.tv_usec;
   	
		heap->heap_node[gap]->hwnd  = heap->heap_node[lsib_offset(child)]->hwnd;
		heap->heap_node[gap]->id    = heap->heap_node[lsib_offset(child)]->id;
		gap = rsib_offset( child );
   }

   return (gap);
}

static int heap_remove_item(T_HEAP *heap, int target)
{
	int gap, last;


	if (heap->count == 1)
	{
		heap->count--;
		return 0;
	}

	if ((heap->count > 0)&&
	    (target < (heap->count - 1))
	   )
	{
  		last = heap->count - 1;
		gap = drive_gap_down(heap, target, last);
  		drive_node_up(heap,
			          0,
			   		  gap,
         	          heap->heap_node[last]); 
  		heap->count--;
  
  		return(1);
  	}
  	
  	return (0);
}

// --- External interface ---
int heap_init(T_HEAP *heap, int size)
{
	int i;
	
	if ((size <= 0) || (size > HEAP_MAX_SIZE))
		return (NSY_E_INVALID);
	
	heap->size  = size;
	heap->count = 0;	

	for (i = 0; i < HEAP_MAX_SIZE; i++)
		heap->heap_node[i] = NULL;

	for (i = 0; i < size; i++)
	{
		heap->heap_node[i] = (T_HEAP_NODE *)malloc(sizeof(T_HEAP_NODE));
		memset(heap->heap_node[i], 0, sizeof(T_HEAP_NODE));
		if (NULL == heap->heap_node[i])
		{
			heap_release(heap); /* to free allocated memory */
			return (NSY_E_NOMEM);
		}
	}

	/* to initial a mutux lock for queue access */
#ifdef NSY_WIN	
	InitializeCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_init(&heap->heap_lock, NULL);
#endif
	
	return (NSY_OK); 
}

void heap_empty(T_HEAP *heap)
{

	if (heap == NULL)
		return;

#ifdef NSY_WIN		
	EnterCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_lock(&heap->heap_lock);
#endif	
	
	while (heap->count > 0)
		heap_remove_item(heap, 0);

#ifdef NSY_WIN		
	LeaveCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_unlock(&heap->heap_lock);
#endif	
}

void heap_release(T_HEAP *heap)
{
	int i;
	
	if (heap == NULL)
		return;

#ifdef NSY_WIN		
	EnterCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_lock(&heap->heap_lock);
#endif

	for (i = 0; i < heap->size; i++)
	{
		if (heap->heap_node[i] != NULL)
		{
			free (heap->heap_node[i]);
			heap->heap_node[i] = NULL;
		}
	}
	heap->count = 0;

#ifdef NSY_WIN		
	LeaveCriticalSection(&heap->heap_lock);
#else	
	pthread_mutex_unlock(&heap->heap_lock);
#endif	
}

int heap_push(T_HEAP *heap, T_HEAP_NODE *node)
{
	if (heap->count < heap->size)
	{ /* Add the node to the heap */

#ifdef NSY_WIN	
		EnterCriticalSection(&heap->heap_lock);
#else
		pthread_mutex_lock(&heap->heap_lock);
#endif

		heap->heap_node[heap->count]->value.tv_sec  = node->value.tv_sec;
		heap->heap_node[heap->count]->value.tv_usec = node->value.tv_usec;
		
		heap->heap_node[heap->count]->id    = node->id; 
		heap->heap_node[heap->count]->hwnd  = node->hwnd; 
		heap->count++;

		drive_node_up(heap, 0, heap->count-1, node);

#ifdef NSY_WIN	
		LeaveCriticalSection(&heap->heap_lock);
#else
		pthread_mutex_unlock(&heap->heap_lock);
#endif		
	}
	else
	{
		return NSY_E_OVERFLOW;
	}
	
	return NSY_OK;
}

/*
 * to pop 0st item from the heap
 */
T_HEAP_NODE* heap_pop (T_HEAP *heap)
{  
	T_HEAP_NODE   *node;

#ifdef NSY_WIN	
	EnterCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_lock(&heap->heap_lock);
#endif	

	node = (T_HEAP_NODE *)malloc(sizeof(T_HEAP_NODE));
	node->value.tv_sec  = heap->heap_node[0]->value.tv_sec;
	node->value.tv_usec = heap->heap_node[0]->value.tv_usec;
	
	node->id   = heap->heap_node[0]->id;
	node->hwnd = heap->heap_node[0]->hwnd;

	heap_remove_item(heap, 0); 

#ifdef NSY_WIN	
	LeaveCriticalSection(&heap->heap_lock);
#else
	pthread_mutex_unlock(&heap->heap_lock);
#endif	
	
	return (node);
}

/* 
 * return a pointer to the 0st node in the heap
 *
 * Note: the invoker shall never attemp to free
 *       the memory pointed by the returned pointer
 */
T_HEAP_NODE* heap_top (T_HEAP *heap)
{
	return (heap->heap_node[0]); 
}

/*
 * hwnd : 0, return the heap count
 *        others, reture matched hwnd count in the heap
 */
int heap_count (T_HEAP *heap, unsigned int hwnd)
{
	int i;
	int count;
	
	count = 0;
	
	if (hwnd == HWND_ALL)
		return (heap->count);
		
	for (i = 0; i < heap->count; i++)
	{
		if (heap->heap_node[i]->hwnd == hwnd)
			count++;
	}
			
	return (count);
}

/*
 * Remove the first matched node in the heap
 */
int heap_remove (T_HEAP *heap, unsigned int hwnd, int id)
{
	int i;
	
	for (i = 0; i < heap->count; i++)
	{
		if ((heap->heap_node[i]->id   == id) &&
		    (heap->heap_node[i]->hwnd == hwnd)
		   )
		{
#ifdef NSY_WIN	
			EnterCriticalSection(&heap->heap_lock);
#else
			pthread_mutex_lock(&heap->heap_lock);
#endif			
			heap_remove_item(heap, i);
#ifdef NSY_WIN	
			LeaveCriticalSection(&heap->heap_lock);
#else
			pthread_mutex_unlock(&heap->heap_lock);
#endif						
			return NSY_OK;
		}
	}
	
	return (NSY_E_NOFOUND);		
}

long timeval_compare(struct timeval *first_val, struct timeval *second_val)
{
	long val_ms;
	
	val_ms = ((first_val->tv_sec  - second_val->tv_sec ) * 1000) +
	         ((first_val->tv_usec - second_val->tv_usec) / 1000);
	
	return val_ms;
}

void timeval_add (struct timeval *value, int val_ms)
{
	long usecond;

	usecond = value->tv_usec + val_ms * 1000;

	value->tv_usec = usecond%1000000;
	value->tv_sec  += usecond/1000000;
	
	return;
}

/* EOF */