#ifdef DEBUG
#include <stdio.h>
#endif

/*-------------------------------------------------------------------
 *	QUEUE.C:	General purpose queue management routines:
 *
 *     Copyright (c) 1985, Allen I. Holub.  All rights reserved
 *  This program may be copied for personal, non-profit, use only.
 *-------------------------------------------------------------------
 *
 *  The QUEUE data structure. No external routine needs to know anything
 *  about how this structure is put together. These routines need only
 *  remember a pointer to the queue (in a manner similar to the FILE
 *  pointer used by the i/o routines).
 */

typedef struct
{
	char	*start;		/* Pointer to beginning of queue	*/
	int	head;		/* Index of current head	 	*/
	int	tail;		/* Index of current tail	 	*/
	int	size;		/* Max num of objects queue can hold	*/
	int	nobj;		/* Number of objects now in the queue	*/
	int	objsize;	/* Size of one element		 	*/
} QUEUE;

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

QUEUE	*makequeue( qsize, objsize )
{
	/* Make a queue of the specified size containing objects of the
	 * specified size. Return a pointer to the queue or 0 if there is
	 * not enough memory to make the queue. Queues are created using
	 * calloc(). They require sizeof(QUEUE) + (qsize * objsize) bytes.
	 */

	register QUEUE	*qp;

	if( !(qp = (QUEUE *) malloc(sizeof(QUEUE) + (qsize * objsize)) ))
		return 0;

	qp->start 	= (char *)(qp + 1); 
	qp->size 	= qsize   ;
	qp->objsize	= objsize ;

	qp->head = qp->tail = qp->nobj = 0;

	return( qp );
}

del_queue( qp )
QUEUE	*qp;
{
	/*   Delete a queue and free the memory. The queue will NOT
	 *   be deleted unless it is empty. Return 1 if the queue
	 *   was deleted, 0 otherwise. If you don't care if the queue
	 *   is actually empty, use free(qp).
	 */

	if( qp->nobj )
		return 0;

	free( qp );
	return 1;
}

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

enqueue( obj, qp )
char	*obj ;
QUEUE	*qp  ;
{
	/*	Put an object into the queue. Obj is a pointer to the
	 *	object qp is a pointer to a QUEUE. Return 1 on success,
	 *	0 if there's no more room in the queue.
	 */

	int	i;				/* Counter		*/
	char	*bp;				/* points into queue    */

	if( qp->nobj  >=  qp->size )		/* If the queue is full */
		return 0;			/* return failure.	*/

	qp->nobj++;				/* One more object in	*/
						/* the queue		*/

	bp= qp->start + (qp->objsize * qp->tail); /* Get target address */
						/* within the queue;    */
						/* then	move object 	*/
						/* into it:		*/

	for( i = qp->objsize;  --i >= 0;  *bp++ = *obj++ )
		;

	if( ++qp->tail >= qp->size) 		/* Wrap around if we've	*/
		qp->tail = 0;			/* gone off the end of	*/
						/* the queue.		*/
	return 1;
}

dequeue( obj, qp )
char	*obj ;
QUEUE	*qp  ;
{
	/*	Get an object from the queue. Qp is a pointer to a QUEUE,
	 *	The dequeued object is copied into the place pointed to by
	 *	obj. Return 0 if the queue is empty and no object was
	 *	dequeued, 1 otherwise.
	 */

	register int	i;
	register char	*bp;
	
	if( qp->nobj <= 0 )
		return 0;				/* queue empty */

	qp->nobj-- ;

	bp = qp->start + (qp->objsize * qp->head) ;

	for( i = qp->objsize; --i >= 0; *obj++ = *bp++ )
		;

	if( ++qp->head >= qp->size )
		qp->head = 0;

	return 1;
}

/*----------------------------------------------------------------------*/
/*  Little access routines:						*/
/*	Show_next returns a pointer to the object at the head of the	*/
/*	queue; sp_used returns the number of objects in the queue	*/
/*	sp_avail returns the number of slots available in the queue.	*/

char	*show_next (qp)
QUEUE	*qp;
{
	return( qp->start + (qp->head * qp->objsize)  );
}

int	sp_used    (qp)
QUEUE	*qp;
{
	return( qp->nobj );
}

int	sp_avail   (qp)
QUEUE	*qp;
{
	return( qp->size - qp->nobj );
}

#ifdef DEBUG

main()
{
	int	num, c, *ip;
	QUEUE	*qp;

	qp = makequeue( 4, sizeof(int) );

	while( 1 )
	{
		num = c = -1;

		ip = (int *)qp->start ;

		printf("\n\nqueue: %d %d %d %d\n",ip[0],ip[1],ip[2],ip[3]);
 
		printf("start	  =0x%x\n",	qp->start	);
		printf("head	  =%d\n",	qp->head	);
		printf("tail	  =%d\n",	qp->tail	);
		printf("size	  =%d\n",	qp->size	);
		printf("objsize   =%d\n",	qp->objsize 	);
		printf("nobj	  =%d\n",	qp->nobj	);

		printf("there are %d slots left in the queue\n\n",
							sp_avail(qp) );

		printf("(d/e/q) ->");
		while( c != 'e' && c != 'd' && c != 'q' )
			c = getchar();

		if( c == 'e' )
		{			
			printf("enter decimal number ->");
			scanf("%d", &num );
			printf("enqueue(%d) returned %d\n",
						num, enqueue(&num,qp) );
		}
		else if( c == 'd' )
		{
			printf( "dequeue returned %d, loaded %d\n",
						dequeue( &num, qp ), num );
		}
		else
			break;
	}

	printf(" deleting queue, queue was %sempty\n",	
					del_queue(qp) ? "" : "not " );
}

#endif