⟦b670e8f0f⟧

TextFile

\f


#ifndef lint
static char rcsid[] = "$Header: queue.c,v 1.1 89/07/05 15:36:21 hubbard Exp $";
#endif

/*
 *
 *                     Copyright 1988, 1989
 *                  PCS Computer Systeme, GmbH
 *                     Munich, West Germany
 *
 *  All rights reserved.
 * 
 *  This is unsupported software and is subject to change without notice.
 *  PCS makes no representations about the suitability of this software
 *  for any purpose. It is supplied "as is" without express or implied
 *  warranty.
 * 
 *  Permission to use, copy, modify, and distribute this software and its
 *  documentation for any purpose and without fee is hereby granted, provided
 *  that the above copyright notice appear in all copies and that both that
 *  copyright notice and this permission notice appear in supporting
 *  documentation, and that the name of PCS Computer Systeme not be used in
 *  advertising or publicity pertaining to distribution of the software
 *  without specific, written prior permission.
 *
 */

/*
 * Author:	Jordan K. Hubbard
 * For:		PCS Computer Systems, GmbH.
 * When:	April 18th, 1989.
 *
 * $Log:	queue.c,v $
 * Revision 1.1  89/07/05  15:36:21  hubbard
 * Initial revision
 * 
 * 
 */

#include "xgdb.h"

/*
 * Generic queue management functions. Given the address of a generic
 * queue and some generic pointer (which is assumed to have a LINK as
 * the first item), manipulate it. These functions should be generally
 * useful, with a little bit of surgery.
 */

/*
 * Add an entry to a queue. Entries are always added at the beginning
 * of the queue. Use PopQueueEntry() to treat a queue as either a FIFO
 * or LIFO stack.
 */
void addQueueEntry(Q, entry)
Queue *Q;
Link entry;
{
     Entry("addQueueEntry");

     ASSERT(NULLP(Q) || NULLP(entry));

     if (NULLP(HEAD(Q)))
	  HEAD(Q) = TAIL(Q) = entry;
     else {
	  NEXT(entry) = HEAD(Q);
	  PREV(NEXT(entry)) = entry;
	  HEAD(Q) = entry;
     }
     Leave_void;
}

/*
 * Select an entry from one of the two ends of a queue. If "how" is
 * set to FIFO, then the entry is selected from the end. If it's set
 * to LIFO (a stack) the top of the queue is selected. The entry
 * is removed from the queue as a side-effect.
 */
GenericPtr popQueueEntry(Q, how)
Queue *Q;
int how;
{
     Link tmp = (Link)NULL;

     Entry("popQueueEntry");

     ASSERT(NULLP(Q));

     if (queueEmpty(Q)) {
	  Leave(NULL);
     }
     else if (how == FIFO) {
	  tmp = TAIL(Q);
	  TAIL(Q) = PREV(TAIL(Q));
	  if (NULLP(TAIL(Q)))
	       HEAD(Q) = NULL;
     }
     else if (how == LIFO) {
	  tmp = HEAD(Q);
	  HEAD(Q) = NEXT(HEAD(Q));
	  if (NULLP(HEAD(Q)))
	       TAIL(Q) = NULL;
     }
     else
	  puke("Don't know how to handle queue type '%x' for queue %x",
	       how, Q);
     Leave((GenericPtr)tmp);
}

/*
 * Remove an entry from the queue. (Entry can be anywhere in the queue).
 */
void removeQueueEntry(Q, entry)
Queue *Q;
Link entry;
{
     Entry("removeQueueEntry");

     ASSERT(NULLP(Q) || NULLP(entry));

     if (NULLP(HEAD(Q))) {
	  puke("Queue is empty");
	  Leave_void;
     }
     /* First handle the simple "at beginning" and "at end" cases */
     if (HEAD(Q) == entry) {
	  HEAD(Q) = NEXT(HEAD(Q));
	  if (NULLP(HEAD(Q)))
	       TAIL(Q) = NULL;
	  else
	       PREV(HEAD(Q)) = NULL;
     }
     else if (TAIL(Q) == entry) {
	  TAIL(Q) = PREV(TAIL(Q));
	  if (NULLP(TAIL(Q)))
	       HEAD(Q) = NULL;
	  else
	       NEXT(TAIL(Q)) = NULL;
     }
     else {
	  Link tmp;

	  tmp = HEAD(Q);
	  while (tmp) {
	       if (tmp == entry) {
		    PREV(NEXT(tmp)) = PREV(tmp);
		    NEXT(PREV(tmp)) = NEXT(tmp);
		    break;
	       }
	       tmp = NEXT(tmp);
	  }
	  if (!tmp)
	       puke("Can't find entry %x", entry);
	  Leave_void;
     }
}

/*
 * Return TRUE if the queue contains any entries. FALSE if not.
 */
Boolean queueActive(Q)
Queue *Q;
{
     Entry("queueActive");

     ASSERT(NULLP(Q));

     if (HEAD(Q) && TAIL(Q)) {
	  Leave(TRUE);
     }
     else if (NULLP(HEAD(Q)) && NULLP(TAIL(Q))) {
	  Leave(FALSE);
     }
     else { /* doesn't hurt to check */
	  puke("Queue %x munged! Head = %x, Tail = %x\n",
	       HEAD(Q), TAIL(Q));
	  Leave(FALSE);
     }
}

/*
 * Counterpart to above. Returns TRUE if the queue is empty, FALSE if not.
 */
Boolean queueEmpty(Q)
Queue *Q;
{
     Entry("queueEmpty");

     ASSERT(NULLP(Q));

     if (NULLP(HEAD(Q)) && NULLP(TAIL(Q))) {
	  Leave(TRUE);
     }
     else if (HEAD(Q) && TAIL(Q)) {
	  Leave(FALSE);
     }
     else { /* Be paranoid */
	  puke("Queue %x is hosed! Head = %x, Tail = %x\n",
	       HEAD(Q), TAIL(Q));
	  Leave(FALSE);
     }
}

/*
 * Returns TRUE if a given entry is on the queue, FALSE if not.
 */
Boolean entryOnQueue(Q, entry)
Queue *Q;
Link entry;
{
     Entry("entryOnQueue");

     ASSERT(NULLP(Q) || NULLP(entry));

     if (!queueActive(Q)) {
	  Leave(FALSE);
     }
     else {
	  Link tmp;

	  tmp = HEAD(Q);
	  while (tmp) {
	       if (tmp == entry) {
		    Leave(TRUE);
	       }
	       else
		    tmp = NEXT(tmp);
	  }
     }
     Leave(FALSE);
}

/*
 * Replace entry p1 with p2, maintaining the order in the queue.
 * Thus p2 will occupy the same position p1, with p1 being removed from
 * the queue. If p2 is found to already be on the queue, it is moved from
 * its current position.
 */
void replaceQueueEntry(Q, p1, p2)
Queue *Q;
Link p1, p2;
{
     Entry("replaceQueueEntry");

     ASSERT(NULLP(Q) || NULLP(p1) || NULLP(p2));

     if (queueEmpty(Q)) {
	  puke("Queue is empty");
	  Leave_void;
     }
     /* If p2 is on the queue, remove it */
     if (entryOnQueue(Q, p2))
	  removeQueueEntry(Q, p2);
     if (HEAD(Q) == p1)
	  HEAD(Q) = p2;
     if (TAIL(Q) == p1)
	  TAIL(Q) = p2;
     /* Make everybody that used to point to p1 point to p2 and vica versa */
     NEXT(p2) = NEXT(p1);
     PREV(p2) = PREV(p1);
     if (PREV(p2))
	  NEXT(PREV(p2)) = p2;
     if (NEXT(p2))
	  PREV(NEXT(p2)) = p2;
     Leave_void;
}
DataMuseum.dk

DKUUG/EUUG Conference tapes

⟦b670e8f0f⟧ TextFile

Derivation

TextFile
