#ifndef Q_H
#define Q_H
/* $Id: q.h,v 10.1 92/10/06 23:08:55 ca Exp $ */

#include <sys/types.h>

/* Queue routines hacked from PC/IP software */

/*  Copyright 1983 by the Massachusetts Institute of Technology  */

/* Definitions for general-purpose queue manipulation package.
   Modified from Larry Allen's queue package from CSR Unix for TCP and
   tasks. */


typedef	struct	_q_elt	{		/* queue element: cast to right type */
	struct	_q_elt	*qe_next;	/* it's just a pointer to next elt */
	caddr_t qe_data;		/* Pointer to stuff being stored */
} q_elt;

typedef	struct	_queue	{		/* queue header */
	q_elt	*q_head;		/* first element in queue */
	q_elt	*q_tail;		/* last element in queue */
	int	q_len;			/* number of elements in queue */
	int	q_max;			/* maximum length */
	int	q_min;			/* minimum length */
} queue;

extern caddr_t q_deq ();
extern queue *q_create();
extern q_elt *q_find(), *q_addh(), *q_addt(), *q_adda(), *qe_find();

/* If using GCC, put the qe_deq() function inline. */
#ifdef INLINE
static inline q_elt *
qe_deq (q)

/* Dequeue and return the first element of the specified queue.  Returns
 * a pointer to the first element if any, or 0 if the queue is empty.
 *
 * Arguments:
 */

register queue	*q;
{
	register q_elt	*temp;		/* temp for result */
	
	if ((temp = q->q_head) == 0)	{	/* queue empty? */
		return (0); }	/* yes, show none */

	q->q_head = temp->qe_next;	/* else unlink */
	if (q->q_head == 0)		/* queue empty? */
		q->q_tail = 0;	/* yes, update tail pointer too */
	q->q_len--;			/* update queue length */
	if(q->q_len < q->q_min) q->q_min = q->q_len;
	return (temp);
}
#else  /* not INLINE */
q_elt *qe_deq();
#endif /* INLINE */


/* Some queue operations implemented with following macros */
/* Is the queue empty? */

#define	q_empty(q)	((q)->q_len == 0)

/* Add an element to the head of the queue */

#define	qe_addh(q, elt) 	{ \
	if ((q)->q_head == 0) (q)->q_tail = (q_elt *)(elt); \
	((q_elt *)(elt))->qe_next = (q)->q_head; \
	(q)->q_head = (q_elt *)(elt); \
	if(++((q)->q_len) > (q)->q_max) (q)->q_max = (q)->q_len; \
}

/* Add an element to the tail of a queue */

#define	qe_addt(q, elt)	{ \
	((q_elt *)(elt))->qe_next = 0; \
	if ((q)->q_head == 0) { \
		(q)->q_head = (q_elt *)(elt); \
	} else { \
		(q)->q_tail->qe_next = (q_elt *)(elt); \
	} \
	(q)->q_tail = (q_elt *)(elt); \
	if(++((q)->q_len) > (q)->q_max) (q)->q_max = (q)->q_len; \
}

/* Add an element after a specified element in the queue.  If prev == */
/* &q->q_head, can be used to add an element to the head of the queue */

#define	qe_adda(q, prev, new)	{ \
	if ((q)->q_tail == (q_elt *)(prev) || (q)->q_tail == 0) { \
		(q)->q_tail = (q_elt *)(new); \
	} \
	((q_elt *)(new))->qe_next = ((q_elt *)(prev))->qe_next; \
	((q_elt *)(prev))->qe_next = (q_elt *)(new); \
	if(++((q)->q_len) > (q)->q_max) (q)->q_max = (q)->q_len; \
}

/* Delete an element from a queue, given a pointer to the preceeding element */
/* Will delete the first element if prev == &q->q_head */

#define	qe_dela(q, prev)	{ \
	q_elt *next = ((q_elt *)(prev))->qe_next; \
	if ((q)->q_tail == next) { \
		if ((q)->q_head == next) \
			(q)->q_tail = 0; \
		else \
			(q)->q_tail = (q_elt *)(prev); \
	} \
	((q_elt *)(prev))->qe_next = next->qe_next; \
	next->qe_next = 0; \
	if(--((q)->q_len) < (q)->q_min) (q)->q_min = (q)->q_len; \
}
#endif   /* Q_H   */