nsy_heap.c

使用堆排序实现Pop, Push的算法. Push: 最小的元素永远位于堆顶

/* ********************************************************************
**  Project : DataCollector 
**
**  FileName: nsy_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
**
** *********************************************************************/
#include "stdafx.h"

#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 )


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), heap->heap_node[parent]->data > new_node->data)
         )
   {
   	// swap parent and gap
  	  heap->heap_node[gap]->data  = heap->heap_node[parent]->data; 
      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]->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 )
   {  // in the heap
   	// select the greater of the children
	  //if (heap->heap_node[child]->data < heap->heap_node[lsib_offset(child)]->data)
	  if (heap->heap_node[child]->data > heap->heap_node[lsib_offset(child)]->data)
      {
            // go for the left sibling
    		child = lsib_offset( child );
      }
	  //swap_node(heap->heap_node[gap], heap->heap_node[child]);
	  heap->heap_node[gap]->data = heap->heap_node[child]->data;
	  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]->hwnd  = heap->heap_node[lsib_offset(child)]->hwnd;
		heap->heap_node[gap]->id    = heap->heap_node[lsib_offset(child)]->id;
		gap = lsib_offset( child );
//		swap_node(heap->heap_node[gap], heap->heap_node[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])
		{
//			sprintf (stderr,"Allocate memory error!");
			return (NSY_E_NOMEM);
		}
	}

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

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

#ifndef NSY_WIN		
	pthread_mutex_lock(&heap->heap_lock);
#endif
	
	for (i = 0; i < heap->count; i++)
	{
		if (heap->heap_node[i] != NULL)
		{
			free (heap->heap_node[i]);
			heap->heap_node[i] = NULL;
		}
	}
	heap->count = 0;

#ifndef NSY_WIN		
	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
#ifndef NSY_WIN	
		pthread_mutex_lock(&heap->heap_lock);
#endif

		heap->heap_node[heap->count]->data  = node->data; 
		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);
//		heap->count++;

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

T_HEAP_NODE* heap_pop (T_HEAP *heap)
{ 
	T_HEAP_NODE   *node;

#ifndef NSY_WIN	
	pthread_mutex_lock(&heap->heap_lock);
#endif

	node = (T_HEAP_NODE *)malloc(sizeof(T_HEAP_NODE));
	node->data = heap->heap_node[0]->data;
	node->id   = heap->heap_node[0]->id;
	node->hwnd = heap->heap_node[0]->hwnd;

	heap_remove_item(heap, 0); // Pop 0st item from the heap

#ifndef NSY_WIN	
	pthread_mutex_unlock(&heap->heap_lock);
#endif
	
	return (node);

	//return (heap->heap_node[heap->count]); 
}

T_HEAP_NODE* heap_top (T_HEAP *heap)
{
	return (heap->heap_node[0]); 
}

int heap_count (T_HEAP *heap, unsigned int hwnd)
{
	int i;
	int count;
	
	count = 0;
	
	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)
		   )
		{
#ifndef NSY_WIN	
			pthread_mutex_lock(&heap->heap_lock);
#endif
			heap_remove_item(heap, i);

#ifndef NSY_WIN	
			pthread_mutex_unlock(&heap->heap_lock);
#endif
						
			return NSY_OK;
		}
	}
	
	return (NSY_E_NOFOUND);		
}

/* EOF */