#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>

// Test list functions
//	insert at end of list
//	popd front of list
//
// NOTE:  this version uses calloc to get space for the original free list
//

union tm_tag {
    long long	tm;
    struct {
	unsigned long	hi;
	unsigned long	lo;
    }	tm2;
};

struct delay_item_tag {
    union tm_tag time;
    unsigned int buf_handle;
    unsigned int out_port;
    unsigned int qid;
    unsigned int l3_pkt_len;
    struct delay_item_tag *next;
};

struct delayq_tag {
    unsigned long		ninq;	// # in delay queue
    struct delay_item_tag	*hd;	// head ptr
    struct delay_item_tag	*tl;	// tail ptr
    struct delay_item_tag	*free_hd;	// free list
};

struct delay_item_tag * delayq_alloc( struct delayq_tag *delayq );

void delayq_free( struct delayq_tag *delayq, struct delay_item_tag *item );

struct delayq_tag delayq;		// delay queue descriptor
#define	N 5				// delay queue capacity (#items)

// insert item at end of queue
// 	return number of items if OK; else -1
int
delayq_enq(	struct delayq_tag *qptr,
		long long time,
		unsigned int buf_handle, 
		unsigned int out_port, 
		unsigned int qid, 
		unsigned int l3_pkt_len ) {
    struct delay_item_tag	*item;

    item = delayq_alloc( qptr );
    if( item == 0 )	return -1;

    item->time.tm = time;
    item->buf_handle = buf_handle;
    item->out_port = out_port;
    item->qid = qid;
    item->l3_pkt_len = l3_pkt_len;
    item->next = 0;

    if( qptr->ninq == 0 )	qptr->hd = item;
    else			qptr->tl->next = item;
    qptr->tl = item;

    ++(qptr->ninq);
    return qptr->ninq;
}

// pop front of list
int
delayq_pop( struct delayq_tag *qptr ) {
    struct delay_item_tag	*item;

    if( qptr->ninq <= 0 )	return -1;

    item = qptr->hd;
    qptr->hd = item->next;
    --(qptr->ninq);
    if( qptr->ninq == 0 )	qptr->tl = 0;
    delayq_free( qptr, item );

    return 0;
}

int
delayq_init( struct delayq_tag *qptr, unsigned short Nitems ) {
    int		i;
    struct delay_item_tag *item_ptr;

    item_ptr = (struct delay_item_tag *)
    				calloc( Nitems, sizeof(struct delay_item_tag) );
    if( item_ptr == NULL )	return -1;

    qptr->free_hd = item_ptr;
    qptr->hd = qptr->tl = 0;
    qptr->ninq = 0;

    (item_ptr+(Nitems-1))->next = 0;

    for (i=0; i<(Nitems-1); i++) {
    	item_ptr->next = item_ptr+1;
	++item_ptr;
    }

    return 0;
}

struct delay_item_tag *
delayq_alloc( struct delayq_tag *delayq ) {
    struct delay_item_tag *item;

    if( delayq->free_hd == 0 )	return 0;

    item = delayq->free_hd;
    delayq->free_hd = item->next;
    return item;
}

void
delayq_free( struct delayq_tag *delayq, struct delay_item_tag *item ) {
    if( item == 0 )	return;
    item->next = delayq->free_hd;
    delayq->free_hd = item;
}

void show_delayq( void );

int
main( ) {
    int		k = 0;
    int		i;
    int		n;
    struct delay_item_tag *x;
    int		rc;

    printf( "sizeof(struct delay_item_tag) = %d\n",
    					sizeof(struct delay_item_tag) );
    rc = delayq_init( &delayq, N );
    if( rc != 0 ) {
    	printf( "*** delayq_init failed!\n" );
	exit( 1 );
    }

    printf( "BEGIN 6 inserts\n" );
    for( i=0; i<6; i++ ) {
    	n = delayq_enq( &delayq, k, k+1, k+2, k+3, k+4 );
	if( n == -1 ) {
	    printf( "i = %d:  delayq_enq failed\n", i );
	} else {
	    printf( "i = %d:  delayq_enq rc = %d\n", i, n );
	}
	k += 10;
	show_delayq( );
    }
    printf( "\n\n" );

    printf( "\n\n" );
    printf( "BEGIN 6 pops\n" );
    for( i=0; i<6; i++ ) {
    	x = delayq.hd;
	if( x != 0 ) {
	    int	rc;
   	    printf("i = %d, head: %lld, %d, %d, %d, %d (%p)\n",	i,
			x->time,	x->buf_handle,	x->out_port,
			x->qid,		x->l3_pkt_len,	x->next );
    	    rc = delayq_pop( &delayq );
	    if( rc != 0 ) {
		printf( "\ti = %d:  delayq_pop failed\n", i );
	    }
	} else {
	    printf( "i = %d:  delayq is empty\n", i );
	}
    }

    return 0;
}

void
show_delayq( void ) {
    int		i;
    struct delay_item_tag *x;

    printf( "\n\n" );
    printf( "\t========== show_delayq (%p)\n", delayq );
    printf( "\t========== ninq = %d, hd = %p, tl = %p, free_hd = %p\n",
			delayq.ninq, delayq.hd, delayq.tl, delayq.free_hd );

    x = delayq.hd;
    for( i=0; i<N && (x != 0) ; i++) {
   	printf("\ti = %d (%p): %lld, %d, %d, %d, %d (%p)\n",
			i,		x,
			x->time,	x->buf_handle,	x->out_port,
			x->qid,		x->l3_pkt_len,	x->next );
	x = x->next;
    }

    printf( "\t==========\n" );
    printf( "\n\n" );
}