home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
The C Users' Group Library 1994 August
/
wc-cdrom-cusersgrouplibrary-1994-08.iso
/
vol_100
/
106_01
/
queue.c
< prev
next >
Wrap
Text File
|
1980-07-09
|
5KB
|
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] );
}