C/C++ Interactive Reference Guide/C-C++ Interactive Reference Guide.iso/c_ref/csource3/106_01/queue.c

C/C++ Source or Header | 1980-07-09 | 4.6 KB | 216 lines

/* FIFO queue package
 (W) Copywrong 1980 Scott W. Layson

These cute little routines implement First In, First Out queues.  There
are complete sets of routines provided: one to handle integer-sized
(2-byte) objects, and the other to handle byte-sized things.

The routines are good for applications such as I/O buffering in programs
that do several things at once.  For example, consider the following
program fragment (remember that all this text is one big comment!):

#define KBD_Q_SIZE 40

struct cqueue {
    char *cruft[4], space[KBD_Q_SIZE];
    } kbd_q;

/ * This program eats command characters and does something hairy with them * /

main()
{
    <... assorted declarations ...>
    CQInit (&kbd_q, KBD_Q_SIZE);
    while (1) do
      {    cmd = get_qd_char();
        hairily_process (cmd);
      }
}

/ * Return a character off the queue if there are any, otherwise wait
   for one to be typed * /

get_qd_char()
{
    if (!CQEmpty(&kbd_q)
        return CQGrab(&kbd_q);
        else return getchar();
}

/ * If a character has been typed, queue it * /

kbd_check()
{
    if (kbhit())
        CQShove (getchar(), &kbd_q);
}


Careful scattering of calls to kbd_check throughout hairily_process()
will prevent keyboard characters from being missed no matter how far
the user types ahead (up to the KBD_Q_SIZE, of course).

Small misfeature: the queue will actually hold one fewer object than
the size allocated for it.  E.g., the above kbd_q will hold
(KBD_Q_SIZE - 1) characters.  This usually doesn't matter, as usual
practice is just to make a queue much larger than it really has to be
anyway.

************** End of comments **********************************/


struct queue {
    int *head, *tail, *top, *bottom, space;
 };


/*  Initialization routine (must be called before any operation is done
    on the queue) */

QInit(queue_p,size)
struct queue *queue_p;
int size;
{
    queue_p->head = queue_p->tail = queue_p->top = &(queue_p->space);
    queue_p->bottom = queue_p->top +size -1;
}


/* Routine to grab something off the head of a queue
   Does no error checking!  Be careful of underflow! */

QGrab(queue_p)
struct queue *queue_p;
{
    return ((queue_p->head >= queue_p->bottom) ?
        *(queue_p->head = queue_p->top) :
         *++(queue_p->head));
}


/* Routine to shove something onto the tail of a queue
   Does no error checking! BE careful of underflow! */

QShove(x,queue_p)
struct queue *queue_p;
int x;
{
    *((queue_p->tail >= queue_p->bottom) ?
         (queue_p->tail = queue_p->top) :
         ++(queue_p->tail)) = x;
}


/* Emptiness predicate */

QEmpty(queue_p)
struct queue *queue_p;
{
    return (queue_p->head == queue_p->tail);
}


/* Fullness predicate */

QFull(queue_p)
struct queue *queue_p;
{
    return((queue_p->tail+1 == queue_p->head) ||
        (queue_p->tail == queue_p->bottom &&
         queue_p->head == queue_p->top));
}


/* Peek at head of queue without disturbing it */

QPeek(queue_p)
struct queue *queue_p;
{
    return (  (queue_p->head == queue_p->bottom) ?
            *queue_p->top :
            *(queue_p->head + 1) );
}






/* Here is the same repertoire of routines, but set up for
   characters instead of integers:
*/


struct cqueue {
    char *chead, *ctail, *ctop, *cbottom, cspace;
 };


/*  Initialization routine (must be called before any operation done
    on the queue) */

CQInit(queue_p,size)
struct cqueue *queue_p;
int size;
{
    queue_p->chead = queue_p->ctail = queue_p->ctop = &(queue_p->cspace);
    queue_p->cbottom = queue_p->ctop +size -1;
}


/* Routine to grab something off the head of a queue
Does no error checking!  Be careful of underflow! */

CQGrab(queue_p)
struct cqueue *queue_p;
{
    return ((queue_p->chead >= queue_p->cbottom) ?
        *(queue_p->chead = queue_p->ctop) :
         *++(queue_p->chead));
}


/* Routine to shove something onto the tail of a queue
   Does no error checking!  Be careful of overflow! */

CQShove(x,queue_p)
struct cqueue *queue_p;
int x;
{
    *((queue_p->ctail >= queue_p->cbottom) ?
         (queue_p->ctail = queue_p->ctop) :
         ++(queue_p->ctail)) = x;
}


/* Emptiness predicate */

CQEmpty(queue_p)
struct cqueue *queue_p;
{
    return (queue_p->chead == queue_p->ctail);
}


/* Fullness predicate */

CQFull(queue_p)
struct cqueue *queue_p;
{
    return((queue_p->ctail+1 == queue_p->chead) ||
        (queue_p->ctail == queue_p->cbottom &&
         queue_p->chead == queue_p->ctop));
}


/* Peek at head of queue without disturbing it */

CQPeek(queue_p)
struct cqueue *queue_p;
{
    return ( (queue_p->chead == queue_p->cbottom)  ?
           *queue_p->ctop  :
           queue_p->chead[1] );
}