Problems dynamically allocating memory (in C)

Question

I am studying data structures. So I decided to implement a stack by myself using arrays. The problem is when the program tries to push an element when the stacks is full. My idea was to realloc() the existing pointer to the array, which I previously manually alocated memory with malloc() to increase the size of the stack by 1 then push the respective Item. After running the code on valgrind it shows me the error: "Invalid write of size4 ... 4 bytes before a block of size 16 alloc'd ". Noting that I am a beginner so any help is appreciated.

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;


stack* build(){
    stack *new = (stack*) malloc(sizeof(stack));
    new->v = (int*) malloc(sizeof(int) * 4);
    new->cap = 4;
    new->sz = 0;
    return new;
}

int is_empty(stack *s){
    return s->sz == 0;
}

int push( stack *s, int e )
{
    int success = 1;

    if (s->sz == s->cap){
        int*tmp =(int*)realloc(s->v,(s->cap+1)*sizeof( int));
        if (( success = tmp != NULL )){
            s->v = tmp;
            ++s->cap;
        }
    }

    if (success){
        s->v[s->sz++] = e;
    }

    return success;
}
int top(stack *s){
    return *(s->v);
}

int pop(stack *s){
    int value;

    if(is_empty(s))
        return -1;

    value = *(s->v);
    s->v--;
    s->sz--;
    return value;   
}

void destroy(stack *s){
    s->v -= s->sz + 1;
    free(s->v);
    free(s);
}

int match(char p1, char p2){
    if(p1 == '(')
        return (p1 - p2) == '(' - ')';
    else if(p1 == '[')
        return (p1 - p2) == '[' - ']';
    else
        return (p1 - p2) == '{' - '}';
}

int main(){
    int c;
    stack *s = build();
    while((c = getchar()) != EOF && c != '\n'){
        if(c == '(' || c == '[' || c == '{')
             push(s, c);
        else if(c == ')' || c == ']' || c == '}'){
            if(!match(pop(s), c)){
                printf("no\n");
                destroy(s);
                return 0;
            }
        }
    }
    puts((is_empty(s)) ? "yes" : "no");
    destroy(s);
    return 0;
}

Answer 1

This call of realloc

s->v = (int*) realloc(s->v + 1 - s->sz, sizeof(int) * (s->cap + 1));

is incorrect. The first argument of the function shall be the original pointer that points to the previously allocated memory or NULL.

Also this check within the function push

if(is_empty(s))
    *(s->v) = e;

is redundant.

The function can look the following way. Pay attention that the function should not issue any message. It is the caller of the function that will decide whether to output a message depending on whether a new item was added successfully or not.

int push( stack *s, int e )
{
    int success = 1;

    if ( s->sz == s->cap )
    {
        int *tmp = realloc( s->v, ( s->cap + 1 ) * sizeof( int ) );

        if ( ( success = tmp != NULL ) )
        {
            s->v = tmp;
            ++s->cap;
        }
    }

    if ( success )
    {          
        s->v[s->sz++] = e;
    }

    return success;
}

Here is a demonstration program that shows the usage of the function push.

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *v;
    int cap;
    int sz;
} stack; 

/* In case this is how I innitialize an array: */
stack *build() {
    stack *new = ( stack * )malloc( sizeof( stack ) );
    new->v = ( int * )malloc( sizeof( int ) * 4 );
    new->cap = 4;
    new->sz = 0;
    return new;
}

int push( stack *s, int e )
{
    int success = 1;

    if (s->sz == s->cap)
    {
        int *tmp = ( int * )realloc( s->v, ( s->cap + 1 ) * sizeof( int ) );

        if (( success = tmp != NULL ))
        {
            s->v = tmp;
            ++s->cap;
        }
    }

    if (success)
    {
        s->v[s->sz++] = e;
    }

    return success;
}

int main( void )
{
    stack *s = build();

    for (int i = 0; i < 10; i++)
    {
        if (!push( s, i ))
        {
            puts( "Error: not enough memory." );
        }
    }

    for (int i = s->sz; i != 0; )
    {
        printf( "%d ", s->v[--i] );
    }
    putchar( '\n' );
}

The program output is

9 8 7 6 5 4 3 2 1 0

Of course you will need to write yourself a function that will free all the allocated memory.

Pay attention to that it is better to define the stack as a singly-linked list.