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

Text File | 1992-07-21 | 5.7 KB | 275 lines

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

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "stack.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 */

stack stk_new (int obj_len)
{
        register stack s;

        s = malloc(sizeof(struct stack));

        if ( s == NULL )
                return NULL;

        s->top      = NULL;
        s->obj_size = obj_len;

        return s;
}

void stk_free (stack s)
{
        stk_clear(s);
        free(s);
}

void stk_clear (stack s)
{
        link this_entry = s->top;
        link next_entry;

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

        s->top = NULL;
}

int stk_copy (stack s1, const stack s2)
{
        link p;
        link new;
        link last;
        int size;

        if ( s1->obj_size != s2->obj_size )
                return ERR;

        stk_clear(s1);

        last = (link)s1;
        size = s2->obj_size;

        for ( p = s2->top; p != NULL; p = p->next )
        {
                new = malloc(sizeof(struct link) - 1 + size);
                if ( new == NULL )
                {
                        stk_clear(s1);
                        return ERR;
                }
                last->next = new;
                memcpy(new->data,p->data,size);
                last = new;
        }

        last->next = NULL;
        return OK;
}

int stk_equal (const stack s1, const stack s2)
{
        int size;
        link p1;
        link p2;

        if ( s1->obj_size != s2->obj_size )
                return 0;

        size = s1->obj_size;

        for
        (
                p1 = s1->top, p2 = s2->top;
                p1 != NULL && p2 != NULL;
                p1 = p1->next, p2 = p2->next
        )
        {
                if ( memcmp(p1->data,p2->data,size) != 0 )
                        return 0;
        }

        return ( p1 == p2 );
}

int stk_empty (const stack s)
{
        return ( s->top == NULL );
}

int stk_size (const stack s)
{
        int i = 0;
        link p;

        for ( p = s->top; p != NULL; p = p->next )
                ++i;

        return i;
}

int stk_iterate (const stack s, int (*process)(void *))
{
        int ret = 0;
        link p;

        for ( p = s->top; 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 );
}

/* stack-specific routines */

int stk_push (stack s, const void *object)
{
        link new;

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

        if ( new == NULL )
                return ERR;

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

        new->next = s->top;
        s->top = new;

        return OK;
}

int stk_pop (stack s)
{
        link p;

        if ( s->top == NULL )
                return ERR;

        p = s->top;

        s->top = p->next;
        free(p);

        return OK;
}

void *stk_top (const stack s)
{
        if ( s->top == NULL )
                return NULL;

        return ((link)s->top)->data;
}

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

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

void stk_dump (stack s)
{
        printf("Stack: ");
        stk_iterate(s,print);
        putchar('\n');
}
#endif

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

#ifdef test

#define BUFLEN 255

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

        for ( i = 0; i < 10; ++i )
                s[i] = stk_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 )
                        stk_clear(s[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        stk_copy(s[i],s[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(stk_equal(s[i],s[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(stk_empty(s[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",stk_size(s[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        stk_dump(s[i]);
                else if ( sscanf(buf,"push %1d %d",&i,&num) == 2 )
                        stk_push(s[i],&num);
                else if ( sscanf(buf,"top %1d",&i) == 1 )
                {
                        int *p = stk_top(s[i]);
                        if ( p == NULL )
                                printf("Empty\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( sscanf(buf,"pop %1d",&i) == 1 )
                        stk_pop(s[i]);
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

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

        return 0;
}

#endif