CODEWITHSUNDEEP
cdynamic-memory-allocationrealloc
user4418808
user4418808

Reputation:

Realloc Arguments

I am implementing Stack using arrays with the below code

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

struct Stack{
int top;
int capacity;
int *array;
};

struct Stack *createStack()
{
        struct Stack *stack=malloc(sizeof(struct Stack));
        stack->top=-1;
        stack->capacity=1;
        stack->array=malloc(sizeof(sizeof(int)*stack->capacity));
}
void doubleStack(struct Stack *stack)
{
        stack->capacity=stack->capacity*2;
        stack->array=realloc(stack,stack->capacity);
}
void push( struct Stack *stack , int data)
{
        if(stack->top==(stack->capacity)-1)
                doubleStack(stack);
        stack->array[++stack->top]=data;
}

My doubt is, when doubleStack is called once the Stack is full, Should I use stack->array as the first argument of the realloc() or stack as the first argument of the realloc()?

Well I think stack->array should be passed. As we need to reallocate only that portion of the memory.

But accidentally I passed stack and that also seemed to work. Please advise.

Upvotes: 2

Views: 1478

Answers (3)

Vlad from Moscow
Vlad from Moscow

Reputation: 311088

First of all function push is wrong

void push( struct Stack *stack , int data)
{
        if(stack->top==(stack->capacity)-1)
                doubleStack(stack);
        stack->array[++stack->top]=data;
}

Initially top is set to 1 and capacity is also set to 1.

So this condition

if(stack->top==(stack->capacity)-1)

yields false and the following statement 

stack->array[++stack->top]=data;

is executed. It writes to memory stack->array[2] that is beyond the allocated array.

I think initially top should be set to 0. And the function should be defined the following way

void push( struct Stack *stack , int data )
{
        if ( stack->top != stack->capacity || doubleStack( stack ) )
        {
            stack->array[stack->top++] = data;
        } 
}

In this case you can simply define a function that reports whether a stack is empty the following way

int empty( struct Stack *stack ) { return stack->top == 0; }

As for the function doubleStack then it should be defined the following way

int doubleStack(struct Stack *stack)
{
        int success = 0;

        int new_capacity = 2 * stack->capacity;

        int *tmp = = realloc( stack->array, new_capacity * sizeof( int ) );

        if ( ( success = tmp != NULL ) ) 
        {
            stack->capacity = new_capacity;
            stack->array = tmp;
        }

        return success
}

Take into account that I changed the return type of the function from void to int. Also I used an intermediate varaible new_capacity. If the reallocation fails the current capacity will not be changed

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726987

You should pass to realloc a pointer to the array that you wish to extend. Since stack is not an array that you wish to extend, and stack->array is, you should pass stack->array as the first parameter.

However, you should store the result of realloc in a separate variable and do NULL check.

If the function fails to allocate the requested block of memory, a null pointer is returned, and the memory block pointed to by argument ptr is not deallocated (it is still valid, and with its contents unchanged).

Otherwise you risk creating a memory leak:

int *tmp = realloc(stack->array, stack->capacity);
if (tmp) {
    stack->array = tmp;
} else {
    ... // Deal with the allocation error here
}

Upvotes: 2

Sourav Ghosh
Sourav Ghosh

Reputation: 134386

As you're correctly thought,

  stack->array=realloc(stack,stack->capacity);

should atleast be

  stack->array=realloc(stack->array,stack->capacity);

Otherwise, if successful, you'll be free()-ing up stack itself and then you'll end up accessing it. That invokes undefined behaviour. Many things "seem" to work once you've got UB.

That said, from the usage point of view, 

 p = realloc(p, q);

kind of code is very bad, as if realloc() fails, it won't modify the p which has been passed as an argument, but due to the direct assignment of the return value of realloc() to p, the p will be set to NULL, losing the actual stored pointer.

Tip: Always use a temporary pointer to collect the return value of realloc(), then check for realloc() success and in case ofg success, assign the newly returned pointer to the pointer which has been passed to realloc().

Upvotes: 2

Related Questions