queue.c

CC386 is a general-purpose 32-bit C compiler. It is not an optimizing compiler but given that the co

#ifdef DEBUG
    #include <stdio.h>
#endif 

/*-------------------------------------------------------------------
 *	QUEUE.C:	General purpose queue management routines:
 *
 *     Copyright (c) 1985, Allen I. Holub.  All rights reserved
 *  This program may be copied for personal, non-profit, use only.
 *-------------------------------------------------------------------
 *
 *  The QUEUE data structure. No external routine needs to know anything
 *  about how this structure is put together. These routines need only
 *  remember a pointer to the queue (in a manner similar to the FILE
 *  pointer used by the i/o routines).
 */

typedef struct
{
    char *start; /* Pointer to beginning of queue	*/
    int head; /* Index of current head	 	*/
    int tail; /* Index of current tail	 	*/
    int size; /* Max num of objects queue can hold	*/
    int nobj; /* Number of objects now in the queue	*/
    int objsize; /* Size of one element		 	*/
} QUEUE;

/*----------------------------------------------------------------------*/

QUEUE *makequeue(qsize, objsize)
{
    /* Make a queue of the specified size containing objects of the
     * specified size. Return a pointer to the queue or 0 if there is
     * not enough memory to make the queue. Queues are created using
     * calloc(). They require sizeof(QUEUE) + (qsize * objsize) bytes.
     */

    register QUEUE *qp;

    if (!(qp = (QUEUE*)malloc(sizeof(QUEUE) + (qsize *objsize))))
        return 0;

    qp->start = (char*)(qp + 1);
    qp->size = qsize;
    qp->objsize = objsize;

    qp->head = qp->tail = qp->nobj = 0;

    return (qp);
}

//-------------------------------------------------------------------------

del_queue(qp)QUEUE *qp;
{
    /*   Delete a queue and free the memory. The queue will NOT
     *   be deleted unless it is empty. Return 1 if the queue
     *   was deleted, 0 otherwise. If you don't care if the queue
     *   is actually empty, use free(qp).
     */

    if (qp->nobj)
        return 0;

    free(qp);
    return 1;
}

/*----------------------------------------------------------------------*/

enqueue(obj, qp)char *obj;
QUEUE *qp;
{
    /*	Put an object into the queue. Obj is a pointer to the
     *	object qp is a pointer to a QUEUE. Return 1 on success,
     *	0 if there's no more room in the queue.
     */

    int i; /* Counter		*/
    char *bp; /* points into queue    */

    if (qp->nobj >= qp->size)
     /* If the queue is full */
        return 0;
     /* return failure.	*/

    qp->nobj++; /* One more object in	*/
    /* the queue		*/

    bp = qp->start + (qp->objsize *qp->tail); /* Get target address */
    /* within the queue;    */
    /* then	move object 	*/
    /* into it:		*/

    for (i = qp->objsize; --i >= 0;  *bp++ =  *obj++)
        ;

    if (++qp->tail >= qp->size)
     /* Wrap around if we've	*/
        qp->tail = 0;
     /* gone off the end of	*/
    /* the queue.		*/
    return 1;
}

//-------------------------------------------------------------------------

dequeue(obj, qp)char *obj;
QUEUE *qp;
{
    /*	Get an object from the queue. Qp is a pointer to a QUEUE,
     *	The dequeued object is copied into the place pointed to by
     *	obj. Return 0 if the queue is empty and no object was
     *	dequeued, 1 otherwise.
     */

    register int i;
    register char *bp;

    if (qp->nobj <= 0)
        return 0;
     /* queue empty */

    qp->nobj--;

    bp = qp->start + (qp->objsize *qp->head);

    for (i = qp->objsize; --i >= 0;  *obj++ =  *bp++)
        ;

    if (++qp->head >= qp->size)
        qp->head = 0;

    return 1;
}

/*----------------------------------------------------------------------*/
/*  Little access routines:						*/
/*	Show_next returns a pointer to the object at the head of the	*/
/*	queue; sp_used returns the number of objects in the queue	*/
/*	sp_avail returns the number of slots available in the queue.	*/

char *show_next(qp)QUEUE *qp;
{
    return (qp->start + (qp->head *qp->objsize));
}

//-------------------------------------------------------------------------

int sp_used(qp)QUEUE *qp;
{
    return (qp->nobj);
}

//-------------------------------------------------------------------------

int sp_avail(qp)QUEUE *qp;
{
    return (qp->size - qp->nobj);
}

//-------------------------------------------------------------------------

#ifdef DEBUG

    main()
    {
        int num, c,  *ip;
        QUEUE *qp;

        qp = makequeue(4, sizeof(int));

        while (1)
        {
            num = c =  - 1;

            ip = (int*)qp->start;

            printf("\n\nqueue: %d %d %d %d\n", ip[0], ip[1], ip[2], ip[3]);

            printf("start	  =0x%x\n", qp->start);
            printf("head	  =%d\n", qp->head);
            printf("tail	  =%d\n", qp->tail);
            printf("size	  =%d\n", qp->size);
            printf("objsize   =%d\n", qp->objsize);
            printf("nobj	  =%d\n", qp->nobj);

            printf("there are %d slots left in the queue\n\n", sp_avail(qp));

            printf("(d/e/q) ->");
            while (c != 'e' && c != 'd' && c != 'q')
                c = getchar();

            if (c == 'e')
            {
                printf("enter decimal number ->");
                scanf("%d", &num);
                printf("enqueue(%d) returned %d\n", num, enqueue(&num, qp));
            }
            else if (c == 'd')
            {
                printf("dequeue returned %d, loaded %d\n", dequeue(&num, qp),
                    num);
            }
            else
                break;
        }

        printf(" deleting queue, queue was %sempty\n", del_queue(qp) ? "" : 
            "not ");
    }

#endif