Allocating memory to my stack dynamically (only if needed)

Question

I need to allocate memory to an array inside my struct, this array has no defined size at the beginning when i define the struct:

typedef struct stacks {
    int size; // Stores the size of my -values- array
    int sp; //points to the top of the stack, my stackpointer
    int *values;
} STACKS;

So, to initialize my struct i wrote this function, that allocates (using calloc?) memory to my array, and i put inside SIZE variable, the new size of my array .

#define MAXIMUM 10

int initStacks(STACKS *s){
    s->values = calloc(MAXIMUM,sizeof(int));
    s->size = MAXIMUM;
    s->sp = 0;
    return 0;
}

Now, if i want to push something to the top of the stack (LIFO) i use this:

int pushs(STACKS *s, int x){
    if (s->sp==s->size) {
        realloc(s->values, MAXIMUM * sizeof(int));
        s->size*=2;
    }

    s->values[s->sp]=x;
    s->sp++;
}

Is this the correct way of doing this?

Is realloc working as it should in my function?

Thank you very much for your help!

EDIT:

would this make more sense? This way, i really don't need to declare the value of the array, being that defined with #define maximum 10

typedef struct stacks {
    int size; // guarda o tamanho do array valores
    int sp;
    int *values;
} STACKS;


int initStacks(STACKS *s){
    s->values = calloc(1,sizeof(int));
    s->size = 1;
    s->sp = 0;
    return 0;
}

int isEmptys(STACKS *s){
    return((s->sp)==0);
}

int pushs(STACKS *s, int x){
    s->size++;
    realloc(s->values, s->size * sizeof(int));
    s->values[s->sp]=x;
    s->sp++;
}

Answer 1

Assuming you have an original size factor (the name capacity would be as-appropriate, if not more so), your original code lacks several things:

• Compares the size against a constant, rather than the current sp against the stack current size.
• Does not save nor test the return result of realloc
• Does not actually double the allocation (you're missing the 2x in the realloc expression.
• Declares an int return result, but no such return exists.
• Has no way of communicating back to the caller the push result (success or not). That missing return result would be ideal for this, btw.

Addressing all of these:

int pushs(STACKS *s, int x)
{
    if (s->sp == s->size) 
    {
        void *pv = realloc(s->values, 2 * s->size * sizeof *(s->values));
        if (pv != NULL)
        {
            s->values = pv;
            s->size *= 2;
        }
        else
        {
            fprintf(stderr, "Failed to resize stack\n");
            return -1;
        }
    }

    s->values[s->sp++] = x;
    return 0;
}

Untested, but hopefully close enough.

Best of luck

Answer 2

Although not directly an answer to the actual question, but more to the general problem, I post this as it does not fit into a comment.

If you expect excessive push/pop operations and memory usage, the following might be an alternative:

typedef struct SubStack_s {
    struct SubStack_s *prev;
    int data[ENTRIES_PER_SEGMENT];
} SubStack;

typedef struct {
    SubStack *tos;    // init to NULL
    size_t sp;        // init to 0
} Stack;

The basic idea is to push elements onto each substack until full (as you already do). If the current one is full, you alloc a new one, chain them (new->prev = old) and continue with the new one (storing new to Stack.tos)

Pop works similar, free'ing each substack once it is not used anymore.

That concept is called "fragmented stack". It is much more efficient than the realloc-approach (it avoids copying) and does not fragment RAM as all block are of equal size. Oh, and it allows to have pointers into the stack, which the realloc-varaint does not, because the address of the stack can change.