heap.c

基于linux环境的ns2多机并行仿真补丁

/*---------------------------------------------------------------------------*/
/* Priority queue implementation with an in-place heap.                      */
/* Author(s): Kalyan Perumalla, Richard Fujimoto.                            */
/* $Revision: 1.1 $ $Name: v26apr05 $ $Date: 2003/04/11 20:17:37 $ */
/*---------------------------------------------------------------------------*/
/**************************************************************************
 *  Priority Queue data structure, implemented by an in-place heap
 *************************************************************************/

#include <stdlib.h>
#include <stdio.h>
#include "heap.h"

#define MAX_DOUBLE 1.797693e+308

struct HEAP_NodeS
{
  int heap_index;		/* index in heap->elems array */
  KEY_TYPE Key;			/* key used for priority */
  long DataSize;		/* optional, uninterpreted field w/ size */
  long TypeOfData;		/* uninterpreted application defined type */
  void *Data;			/* application defined data */
};
 
#define KEY(e) (e->Key)

struct HEAP_Struct
{
    int inc;			/* #nodes added on expansion */
    int nelems;
    int curr_max;
    HEAP_Node *elems; /* Array [0..curr_max] of HEAP_Node */
};

#define SWAP(heap,x,y,t) { \
    t = heap->elems[x]; \
    heap->elems[x] = heap->elems[y]; \
    heap->elems[y] = t; \
    heap->elems[x]->heap_index = x; \
    heap->elems[y]->heap_index = y; \
    }

/*---------------------------------------------------------------------------*/
static void sift_down( HEAP_PQ h, int i )
{
    int n = h->nelems, k = i, j, c1, c2;
    HEAP_Node temp;

    if( n <= 1 ) return;

    /* Stops when neither child is "strictly less than" parent */
    do
    {
	j = k;
	c1 = c2 = 2*k+1;
	c2++;
	if( c1 < n && KEY(h->elems[c1]) < KEY(h->elems[k]) ) k = c1;
	if( c2 < n && KEY(h->elems[c2]) < KEY(h->elems[k]) ) k = c2;
	SWAP( h, j, k, temp );
    }while( j != k );
}

/*---------------------------------------------------------------------------*/
static void percolate_up( HEAP_PQ h, int i )
{
    int n = h->nelems, k = i, j, p;
    HEAP_Node temp;

    if( n <= 1 ) return;

    /* Stops when parent is "less than or equal to" child */
    do
    {
	j = k;
	if( (p = (k+1)/2) )
	{
	    --p;
	    if( KEY(h->elems[k]) < KEY(h->elems[p]) ) k = p;
	}
	SWAP( h, j, k, temp );
    }while( j != k );
}

/*---------------------------------------------------------------------------*/
HEAP_Node HeapPeekTop( HEAP_PQ h )
{
    return (h->nelems <= 0) ? 0 : h->elems[0];
}

/*---------------------------------------------------------------------------*/
HEAP_Node HEAP_Insert( HEAP_PQ h, KEY_TYPE key, void *data )
{
    int i;
    HEAP_Node e;

    if( h->nelems >= h->curr_max )
    {
	h->elems = (HEAP_Node *)
	    realloc(h->elems, sizeof(HEAP_Node)*(h->curr_max + h->inc));
	if( !h->elems ) {fprintf(stderr,"Can't expand heap!\n"); exit(1);}
        for (i=h->curr_max; i<h->curr_max+h->inc; i++)
        {
          h->elems[i] = (HEAP_Node) malloc (sizeof (struct HEAP_NodeS));
	  if( !h->elems[i] ) {fprintf(stderr,"Can't expand heap!\n"); exit(1);}
        }
	fprintf(stderr,"Expanded heap!\n");
	h->curr_max += h->inc;
    }

    e = h->elems[h->nelems];
    e->heap_index = h->nelems;
    e->Key = key;
    e->Data = data;
    e->DataSize = HEAP_UNDEFINED_SIZE;
    e->TypeOfData = HEAP_DEFAULT_TYPE;
    h->nelems++;
    percolate_up( h, h->nelems-1 );
    return (e);
}

/*---------------------------------------------------------------------------*/
HEAP_Node HEAP_InsertWithType( HEAP_PQ h, KEY_TYPE key, void *data, long Sz, long Tp )
{
    int i;
    HEAP_Node e;
 
    if( h->nelems >= h->curr_max )
    {
        h->elems = (HEAP_Node *)
            realloc(h->elems, sizeof(HEAP_Node)*(h->curr_max + h->inc));
        if( !h->elems ) {fprintf(stderr,"Can't expand heap!\n"); exit(1);}
        for (i=h->curr_max; i<h->curr_max+h->inc; i++)
        {
          h->elems[i] = (HEAP_Node) malloc (sizeof (struct HEAP_NodeS));
          if( !h->elems[i] ) {fprintf(stderr,"Can't expand heap!\n"); exit(1);}
        }
        fprintf(stderr,"Expanded heap!\n");
        h->curr_max += h->inc;
    }
 
    e = h->elems[h->nelems];
    e->heap_index = h->nelems;
    e->Key = key;
    e->Data = data;
    e->DataSize = Sz;
    e->TypeOfData = Tp;  /* default */
    h->nelems++;
    percolate_up( h, h->nelems-1 );
    return (e);
}

/*---------------------------------------------------------------------------*/
void *HEAP_Delete( HEAP_PQ h, KEY_TYPE *key )
{
    HEAP_Node temp;

    if( h->nelems <= 0 )
	return 0;
    else
    {
        HEAP_Node e = h->elems[0];
        *key = e->Key;
        h->nelems--;
	SWAP( h, 0, h->nelems, temp );
        sift_down( h, 0 );
        return (e->Data);
    }
}

/*---------------------------------------------------------------------------*/
void *HEAP_DeleteWithType ( HEAP_PQ h, KEY_TYPE *key, long *Sz, long *Tp )
{
    HEAP_Node temp;
 
    if( h->nelems <= 0 )
        return 0;
    else
    {
        HEAP_Node e = h->elems[0];
        *key = e->Key;
        h->nelems--;
        SWAP( h, 0, h->nelems, temp );
        sift_down( h, 0 );
        *Sz = e->DataSize;
        *Tp = e->TypeOfData;
        return (e->Data);
    }
}

/*---------------------------------------------------------------------------*/
void HEAP_Dump( FILE *fp, HEAP_PQ h )
{
    int i;
    fprintf( fp, "[ " );
    for( i = 0; i < h->nelems; i++ )
    {
	fprintf( fp, "%s", ( i && i % 10 == 0 ) ? "\n\t" : "" );
	fprintf( fp, "%s%f", (i ? ", ":""), KEY(h->elems[i]) );
    }
    fprintf( fp, " ]\n" );
    fflush( fp );
}
  
/*---------------------------------------------------------------------------*/
void *HEAP_DeleteArbitrary(HEAP_PQ h, HEAP_Node victim, KEY_TYPE *key)
{
    HEAP_Node temp;
    void *retval = 0;

    int i = victim->heap_index;

    if( !(0 <= i && i < h->nelems) || (h->elems[i]->heap_index != i) )
    {
	fprintf( stderr, "Fatal: Bad node in FEL!\n" ); exit(2);
    }
    else
    {
        *key = victim->Key;
	h->nelems--;
	if( h->nelems > 0 )
	{
	    HEAP_Node successor = h->elems[h->nelems];
	    SWAP( h, i, h->nelems, temp );
	    if( KEY(successor) <= KEY(victim) ) percolate_up( h, i );
	    else sift_down( h, i );
	}
        retval = victim->Data;
    }
    return retval;
}

/*---------------------------------------------------------------------------*/
void *HEAP_DeleteArbitraryWithType(HEAP_PQ h, HEAP_Node victim, KEY_TYPE *key,
						long *Sz, long *Tp)
{
    HEAP_Node temp;
    void *retval = 0;
 
    int i = victim->heap_index;
 
    if( !(0 <= i && i < h->nelems) || (h->elems[i]->heap_index != i) )
    {
        fprintf( stderr, "Fatal: Bad node in FEL!\n" ); exit(2);
    }
    else
    {
        *key = victim->Key;
        h->nelems--;
        if( h->nelems > 0 )
        {
            HEAP_Node successor = h->elems[h->nelems];
            SWAP( h, i, h->nelems, temp );
            if( KEY(successor) <= KEY(victim) ) percolate_up( h, i );
            else sift_down( h, i );
        }
        *Sz = victim->DataSize;
        *Tp = victim->TypeOfData;
        retval = victim->Data;
    }
    return retval;
}

/*---------------------------------------------------------------------------*/
HEAP_PQ HEAP_Create( int max_elems, int increment )
{
    int i;

    HEAP_PQ h = (HEAP_PQ)malloc(sizeof(struct HEAP_Struct));
    if( !h ) { fprintf( stderr, "Failed to create heap\n" ); exit(1); }
    h->inc = increment;
    h->nelems = 0;
    h->curr_max = max_elems;

    fprintf( stdout, "Allocating a heap of max %d elements.\n", max_elems );
    fflush( stdout );

    h->elems = (HEAP_Node *)malloc(sizeof(HEAP_Node)*h->curr_max);
    if( !h->elems ) { fprintf( stderr, "Failed to create heap\n" ); exit(1); }

    for (i=0; i<max_elems; i++)
    {
      h->elems[i] = (HEAP_Node) malloc (sizeof (struct HEAP_NodeS));
      if(!h->elems[i]){fprintf(stderr,"Failed to create heap\n"); exit(1);}
    }

    return (h);
}

/*---------------------------------------------------------------------------*/
KEY_TYPE HEAP_Min(HEAP_PQ h)
{
    HEAP_Node e = HeapPeekTop( h );
    KEY_TYPE retval = e ? KEY(e) : MAX_DOUBLE;
    return retval;
}

/*---------------------------------------------------------------------------*/
void *HEAP_First( HEAP_PQ h, KEY_TYPE *key )
{
    if( h->nelems <= 0 )
    {
        *key = MAX_DOUBLE;
	return 0;
    }
    else
    {
        HEAP_Node e = h->elems[0];
        *key = e->Key;
        return (e->Data);
    }
}

/*---------------------------------------------------------------------------*/
int HEAP_Count( HEAP_PQ h )
{
   return h->nelems ;
}

/*---------------------------------------------------------------------------*/
#if 0 /*TEST*/
main()
{
  HEAP_PQ MyHeap;
  int i;
  double ts;
  HEAP_Node s;

  MyHeap = HEAP_Create (10, 5);

  ts = 100.0;
  for (i=0; i<25; i++)
  {
    if (i == 20) s = HEAP_Insert (MyHeap, ts, NULL);
    else HEAP_Insert (MyHeap, ts, NULL);
    ts = ts+10.0;
  }

  ts = 0.0;
  for (i=0; i<25; i++)
  {
    HEAP_Insert (MyHeap, ts, NULL);
    ts = ts+2.0;
  }
  HEAP_DeleteArbitrary (MyHeap, s, &ts);
  printf ("Delete ts=%f\n", ts);


  for (i=0; i<24; i++)
  {
    HEAP_Delete (MyHeap, &ts);
    printf ("%f  ", ts);
  }
  printf ("\n");

  for (i=0; i<25; i++)
  {
    HEAP_Delete (MyHeap, &ts);
    printf ("%f  ", ts);
  }
  printf ("\n");
}

#endif /*TEST*/

/*---------------------------------------------------------------------------*/