Le-Compte-est-Bon/stack.c

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <signal.h>
#include "lceb.h"

static STACK *allstacks=NULL;
static int nstacks=0;
int totalstacks=0;
int laststack=0;

void print_stack(stack, details)
    STACK *stack;
    int details;
{
    int i;

    if (details) {
        printf("Stack [%s] dump: %d/%d used\n", stack->name, stack->last, stack->size);
        //printf("\tValue: %4d\n", stack->eval);
        for (i=0; i<stack->last; ++i)
            printf("\t%02d: Val=%4d\n",
                   i, stack->stack[i]);
    } else {
        printf("Stack [%s] : ", stack->name);
        for (i=0; i<stack->last; ++i) {
            printf("%d ", stack->stack[i]);
        }
        printf("\n");
    }
}

void print_stacks()
{
    int i;
    //STACK *stack=stacks;
    printf("nstacks=%d laststack=%d totalstacks=%d\n", nstacks, laststack, totalstacks);
    //while (stack) {
    for (i=0; i<laststack; ++i) {
        printf("stack %d=", i);
//stack=stack->next;
        print_stack(nth_stack(i), 1);
        //stack=stack->next;
    }
}

STACK *new_stack(size, name, keep)
    int size;                                     /* unused */
    char *name;
    int keep;
{
    STACK *stack;
    int i;

#   ifdef DEBUG_STACK
    printf("new_stack(size=%d, name=[%s] last=%d total=%d)\n",
           size, name, laststack, totalstacks);
#   endif
    if (!allstacks) {
        totalstacks=ALLOCSIZE;
#       ifdef DEBUG_MEM
        printf("new_stack: allocating %d stacks\n", totalstacks);
#       endif
        allstacks=malloc(totalstacks*sizeof (STACK));
    }
    if (laststack==totalstacks) {
        totalstacks+=ALLOCSIZE;
#       ifdef DEBUG_MEM
        printf("new_stack: resizing stacks array to %d\n", totalstacks);
#       endif
        allstacks=realloc(allstacks, totalstacks*sizeof (STACK));
    }

    stack=allstacks+laststack;
    //printf("new_stack %d/%d: address=%p\n", laststack, totalstacks, stack);
    laststack++;
    //malloc(sizeof (STACK));
    //stack->stack=NULL;
    //stack->size=0;
    stack->last=0;
    //stack->eval=0;
    strncpy(stack->name, name? name: "No name", sizeof(stack->name));
    //if (size) {
        //pelt=malloc(size*sizeof(int));
    stack->size=size;
        //stack->stack=pelt;
    //if (keep)
    //    keep_stack(stack);
    for (i=0; i<MAXINPUT; ++i) {
        //(pelt+i)->nop=0;
        //(pelt+i)->curop=0;
        //(pelt+i)->op[0]=End;
        stack->stack[i]=-1;
        //(pelt+i)->next=i+1;
        //(pelt+i+1)->prev=i;
    }
    return stack;
}

int *push_stack(stack, val)
    STACK *stack;
    int val;
{
    int pos=stack->last;
    int size=stack->size;
    int *pelt=stack->stack+stack->last;

#   ifdef DEBUG_STACK2
    printf("push_stack(%d:[%s]): last=%d size=%d\n",
           val, stack->name, stack->last, stack->size);
#   endif

    if (pos >= size) {
        fprintf(stderr, "stack overflow: size=%d last=%d. generating core.\n", size, pos);
        raise(SIGABRT);
        return NULL;                              /* useless, we died */
    }
    //pelt->nop=0;
    //pelt->curop=0;
    //pelt->op[0]=op;
    *pelt=val;
    stack->last++;
    return pelt;
}

int *pop_stack(stack)
    STACK *stack;
{
    int pos=stack->last+1;
    int *pelt=stack->stack+stack->last;

    if (pos==0) {
#       ifdef DEBUG_STACK
        printf("pop: empty stack [%s]: size=%d last=%d\n", stack->name, stack->size, pos);
#       endif
        return NULL;
    }
    stack->last--;
    return pelt;
}

STACK *dup_stack(stack, name)
    STACK *stack;
    char *name;
{
    STACK *new;
    int *dst;
    int size=stack->size, last=stack->last, i;
    //printf("DUP: totalstacks=%d\n", totalstacks);
    new=new_stack(size, name, 0);
    new->last=stack->last;
    dst=new->stack;
    for (i=0; i<last; ++i) {
        dst[i]=stack->stack[i];
        //dst->nop=src->nop;
        //dst->curop=src->curop;
        //dst->val=src->val;
        //memcpy(dst->op, src->op, sizeof(src->op));
    }
    //stack->last++;
    return new;
}

void swap(elts, i, j)
    int *elts;
    int i, j;
{
    int tmp=elts[i];
    elts[i] = elts[j];
    elts[j] = tmp;
}

int permute_stack(array, n)
    int *array;
    int n;
{
    int i, j, start, end;

    for(i=n-2; i>-1; i--) {
        if(array[i+1] > array[i]) {
            for(j=n-1; j>i; j--){
                if(array[j] > array[i]){
                    // swap
                    swap(array, i, j);
                    // reverse
                    for (start=i+1, end=n-1; start < end; ++start, --end)
                        swap(array, start, end);
                    return 1;
                }
            }
        }
    }
    return 0;
}

void gen_stacks(stack)
    STACK *stack;
{
    char name[80];
    int last=stack->last;
    int n=1;
    int exists=1;

    printf("GEN: totalstacks=%d\n", totalstacks);

#   ifdef DEBUG_STACK
    printf("generating stacks...\n");
#   endif
    //printf("last=%d laststack=%d totalstacks=%d\n", last, laststack, totalstacks);
#   ifdef DEBUG_STACK
    printf("sorting initial stack...\n");
#   endif
    mergesort_stack(stack->stack, 0, last-1);
#   ifdef DEBUG_STACK
    print_stack(stack, 0);
#   endif
    dup_stack(stack, "Main stack");
    while (exists) {
        sprintf(name, "Stack copy %d", n);
        exists=permute_stack(stack->stack, stack->last);
        if (exists) {
            dup_stack(stack, name);
        }
        n++;
    }
}


void mergesort_stack(array, left, right)
    int *array;
    int left, right;
{
    int mid = (left+right)/2;
    int pos=0, l=left, r=mid+1, i;
    int tmp[right-left+1];

    if(left < right) {
        mergesort_stack(array, left, mid);
        mergesort_stack(array, mid+1,right);
        while (l <= mid && r <= right) {
            if (array[l] < array[r]) {
                tmp[pos++] = array[l++];
            }
            else {
                tmp[pos++] = array[r++];
            }
        }
        while (l <= mid)
            tmp[pos++] = array[l++];
        while (r <= right)
            tmp[pos++] = array[r++];
        for (i = 0; i < pos; ++i)
            array[i+left] = tmp[i];
    }
}

STACK *nth_stack(n)
    int n;
{
    //int i;
    //STACK *stack=stacks;
    //for (i=0; i<n && stack; ++i) {
    //    stack=stack->next;
    //}
    return allstacks+n;
}

int n_stacks()
{
    return laststack;
}