/* $Id: q.c,v 10.1 92/10/06 23:10:40 ca Exp $ */

/* Queue routines from PC/IP  (modified) */
/*LINTLIBRARY*/


/* q.c */

/* General-purpose queue manipulation routines.  Contains the following
 * routines:
 *	q{e}_deq	dequeue and return first element from queue
 *	q{e}_del	delete element from queue
 *	q_find		determine whether an element is in a queue
 *	q_create	create a queue
 *	q_addh, q_addt	add to head or tail of queue
 *	q_adda		add to a queue after an element
 *	q_obliterate	Wipe out a queue
 */

#include <sys/types.h>
#include "sim.h"
#include "q.h"

extern char *sim_calloc(), *sim_malloc();

/* If using GCC, this function is declared inline in q.h. */
#ifndef 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);
}
#endif	/* INLINE */

caddr_t
q_deq(q)
     register queue *q;
{
  caddr_t data;
  register q_elt *head;

  head = qe_deq(q);
  if (!head)
    return(NULL);
  data = head->qe_data;
  free((char *)head);
  return(data);
}


qe_del (q, elt)

/* Delete the specified element from the queue.  This requires scanning
 * the queue from the top to find and remove the element, so it takes
 * O(queue length) time to execute.  Note that this routine must not
 * run at interrupt level.
 */

register queue	*q;			/* the queue */
register q_elt *elt;			/* element to delete */
{
	register q_elt	**tmp;		/* temp for chaining */
	
	for (tmp = &q->q_head; *tmp; tmp = &((*tmp)->qe_next))
	  if (*tmp == elt)  {
	    if (q->q_tail == *tmp) {	/* at end of queue? */
		if (tmp == &q->q_head)	/* yes; if first elt, zero out tail */
		  q->q_tail = 0;
		else			/* otherwise tail is previous elt */
		  q->q_tail = (q_elt *)tmp;
	      }
	    *tmp = (*tmp)->qe_next;	/* link it out of the queue */
	    q->q_len--;			/* update element count */
	    if(q->q_len < q->q_min) q->q_min = q->q_len;
	    return TRUE;
	  }

	return 0;		/* not in queue, fail */
}

q_del(q, elt)
     register queue *q;
     register caddr_t elt;
{
	register q_elt	**tmp, *qe;		/* temps for chaining */

	for (tmp = &q->q_head; *tmp; tmp = &((*tmp)->qe_next))
	  if ((*tmp)->qe_data == elt)  {
	    qe = *tmp;
	    if (q->q_tail == qe) {	/* at end of queue? */
		if (tmp == &q->q_head)	/* yes; if first elt, zero out tail */
		  q->q_tail = 0;
		else			/* otherwise tail is previous elt */
		  q->q_tail = (q_elt *)tmp;
	      }
	    *tmp = (*tmp)->qe_next;	/* link it out of the queue */
	    q->q_len--;			/* update element count */
	    if(q->q_len < q->q_min) q->q_min = q->q_len;
	    free((char *)qe);
	    return TRUE;
	  }

	return 0;		/* not in queue, fail */
}

  
queue *q_create()
{
  return((queue *)sim_calloc(1, sizeof(queue)));
}


/* Search the queue for a particular q_elt. */
q_elt *
qe_find(q, qe)
     register queue *q;
     register q_elt *qe;
{
  register q_elt *tmp;

  for (tmp = q->q_head; tmp; tmp = tmp->qe_next)
    if (tmp == qe)
      return(qe);

  return(NULL);
}


/* Procedure to determine if an element is in a queue.
   Returns NULL if not found, and the pointer if it is found. */
q_elt *q_find(q, qe)
     register queue *q;
     register caddr_t qe;
{
	register q_elt *tmp;		/* temp for chaining */
	
	for (tmp = q->q_head; !tmp || tmp->qe_data != qe; tmp = tmp->qe_next)
		if (tmp == 0)
			return NULL;		/* if not in queue, punt */
	return(tmp);
}


/* Addh, addt, & adda.  These are now all procedures instead of macros
   because I didn't want to sim_malloc() from a macro.
*/

q_elt *
q_addh(q, elt)
     register queue *q;
     register caddr_t elt;
{
  register q_elt *new = (q_elt *)sim_calloc(1, sizeof(q_elt));

  new->qe_data = elt;

  if (!q->q_head)
    q->q_tail = new;
  new->qe_next = q->q_head;
  q->q_head = new;
  if (++q->q_len > q->q_max)
    q->q_max = q->q_len;

  return(new);
}

q_elt *
q_addt(q, elt)
     register queue *q;
     register caddr_t elt;
{
  register q_elt *new = (q_elt *)sim_calloc(1, sizeof(q_elt));

  new->qe_data = elt;

  if (!q->q_head)
    q->q_head = new;
  else
    q->q_tail->qe_next = new;
  q->q_tail = new;
  if (++q->q_len > q->q_max)
    q->q_max = q->q_len;

  return(new);
}

/* q_adda and q_dela are both O(n) */

/* If prev == NULL, then new is added to the head of the queue. */
q_elt *
q_adda(q, prev, new)
     register queue *q;
     register caddr_t prev, new;
{
  register q_elt *found, *newqe;

  if (prev)  {
    /* First find data in the queue */
    if (!(found = q_find(q, prev)))
      return(NULL);		/* Abort if not found */
  }

  newqe = (q_elt *)sim_calloc(1, sizeof(q_elt));
  newqe->qe_data = new;

  if (prev)  {
    qe_adda(q, found, newqe);  /* Now add it in */
  } else {
    qe_addh(q, newqe);
  }

  return(newqe);
}


/*  Routine to wipe out a queue and **ALL** the data in it. */
void q_obliterate(q)
     register queue *q;
{
  register q_elt *qe, *next;

  for (qe = q->q_head; qe; qe = next)  {
    next = qe->qe_next;
    free((char *)qe->qe_data);
    free((char *)qe);
  }
  free((char *)q);
}