The Datafile PD-CD 4/DATAFILE_PDCD4.iso/unix/unixtools/util/c/queue

Text File | 1992-07-21 | 5.9 KB | 288 lines

/*      > C.Queue - Queue data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "queue.h"

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

struct link
{
        struct link *next;
        char data[1];
};

typedef struct link *link;

/* Return values from functions */

#define OK      1
#define ERR     0

/* General component routines */

queue Q_new (int obj_len)
{
        register queue q;

        q = malloc(sizeof(struct queue));

        if ( q == NULL )
                return NULL;

        q->head     = NULL;
        q->tail     = NULL;
        q->obj_size = obj_len;

        return q;
}

void Q_free (queue q)
{
        Q_clear(q);
        free(q);
}

void Q_clear (queue q)
{
        link this_entry = q->head;
        link next_entry;

        while ( this_entry != NULL )
        {
                next_entry = this_entry->next;
                free(this_entry);
                this_entry = next_entry;
        }

        q->head = q->tail = NULL;
}

int Q_copy (queue q1, const queue q2)
{
        link p;
        link new;
        link last;
        int size;

        if ( q1->obj_size != q2->obj_size )
                return ERR;

        Q_clear(q1);

        last = (link)q1;
        size = q2->obj_size;

        for ( p = q2->head; p != NULL; p = p->next )
        {
                new = malloc(sizeof(struct link) - 1 + size);
                if ( new == NULL )
                {
                        Q_clear(q1);
                        return ERR;
                }
                last->next = new;
                memcpy(new->data,p->data,size);
                last = new;
        }

        last->next = NULL;
        q1->tail = last;

        return OK;
}

int Q_equal (const queue q1, const queue q2)
{
        int size;
        link p1;
        link p2;

        if ( q1->obj_size != q2->obj_size )
                return 0;

        size = q1->obj_size;

        for
        (
                p1 = q1->head, p2 = q2->head;
                p1 != NULL && p2 != NULL;
                p1 = p1->next, p2 = p2->next
        )
        {
                if ( memcmp(p1->data,p2->data,size) != 0 )
                        return 0;
        }

        return ( p1 == p2 );
}

int Q_empty (const queue q)
{
        return ( q->head == NULL );
}

int Q_size (const queue q)
{
        int i = 0;
        link p;

        for ( p = q->head; p != NULL; p = p->next )
                ++i;

        return i;
}

int Q_iterate (const queue q, int (*process)(void *))
{
        int ret = 0;
        link p;

        for ( p = q->head; p != NULL; p = p->next )
        {
                ret = (*process)(p->data);

                /* Non-zero => stop processing here */

                if ( ret != 0 )
                        break;
        }

        /* Negative => Abnormal (error) termination */

        return ( ret >= 0 );
}

/* queue-specific routines */

int Q_add (queue q, const void *object)
{
        link new;

        new = malloc(sizeof(struct link) - 1 + q->obj_size);

        if ( new == NULL )
                return ERR;

        memcpy(new->data,object,q->obj_size);

        new->next = NULL;

        if ( q->tail != NULL )
                ((link)q->tail)->next = new;

        q->tail = new;

        if ( q->head == NULL )
                q->head = new;

        return OK;
}

int Q_remove (queue q)
{
        link p;

        if ( q->head == NULL )
                return ERR;

        p = q->head;

        q->head = p->next;
        free(p);

        if ( q->head == NULL )
                q->tail = NULL;

        return OK;
}

void *Q_head (const queue q)
{
        if ( q->head == NULL )
                return NULL;

        return ((link)q->head)->data;
}

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

#ifdef test
int print (void *ptr)
{
        printf("%d ",*(int *)ptr);
        return STATUS_CONTINUE;
}

void Q_dump (queue q)
{
        printf("queue: ");
        Q_iterate(q,print);
        putchar('\n');
}
#endif

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

#ifdef test

#define BUFLEN 255

int main (void)
{
        char buf[BUFLEN];
        int i, j, num;
        queue q[10];

        for ( i = 0; i < 10; ++i )
                q[i] = Q_new(sizeof(int));

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                if ( buf[0] == '\n' || buf[0] == '\0' )
                        continue;
                else if ( sscanf(buf,"clear %1d",&i) == 1 )
                        Q_clear(q[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        Q_copy(q[i],q[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(Q_equal(q[i],q[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(Q_empty(q[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",Q_size(q[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        Q_dump(q[i]);
                else if ( sscanf(buf,"add %1d %d",&i,&num) == 2 )
                        Q_add(q[i],&num);
                else if ( sscanf(buf,"remove %1d",&i) == 1 )
                        Q_remove(q[i]);
                else if ( sscanf(buf,"head %1d",&i) == 1 )
                {
                        int *p = Q_head(q[i]);
                        if ( p == NULL )
                                printf("Empty\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        printf("Deleting q[0-9]\n");
        for ( i = 0; i < 10; ++i )
                Q_free(q[i]);

        return 0;
}

#endif