So I am implementing a stack in c. Now initial stack size is 5 and I double it every time it reaches the limit. I push the values from 1 to 20 in it and then pop it one by one and print it.
Here's the output: 20, 19, ..., 7, 0, 5, 4, 3, 2, 1
Notice the 0
instead of 6
Here is stack.c
:
#define INITIAL_CAPACITY 5
struct Stack
{
int size; // initial size = 5
int *data; // dynamically allocated array
int pointer; // position of the top element
};
struct Stack *create_stack()
{
int *array = calloc(INITIAL_CAPACITY, sizeof(int));
struct Stack *stack = malloc(sizeof(struct Stack));
if (array == NULL || stack == NULL)
{
printf("Memory allocation failed in create_stack");
exit(EXIT_FAILURE);
}
stack->size = INITIAL_CAPACITY;
stack->data = array;
stack->pointer = -1;
return stack;
}
static void resize(struct Stack *stack)
{
const int new_size = stack->size * 2;
stack->data = realloc(stack->data, (sizeof *stack->data) * new_size);
if (stack->data == NULL)
{
printf("Memory allocation failed in the resize function.\n");
exit(EXIT_FAILURE);
}
stack->size = new_size;
}
void push(struct Stack *stack, int element)
{
int *stack_data = stack->data; // --> I think the bug is here
stack->pointer = stack->pointer + 1;
if (stack->pointer >= stack->size)
{
printf("Stack is full. Expanding the stack size.");
resize(stack);
}
assert(stack->pointer < stack->size);
stack_data[stack->pointer] = element;
}
But when I change the push function to this everything works and the output is correct:
void push(struct Stack *stack, int element)
{
stack->pointer = stack->pointer + 1;
if (stack->pointer >= stack->size)
{
printf("Stack is full. Expanding the stack size.");
resize(stack);
}
assert(stack->pointer < stack->size);
(stack->data)[stack->pointer] = element; // <--- changed line
}
How is the output correct now? What is happening?
Here's the problem:
void push(struct Stack *stack, int element)
{
int *stack_data = stack->data;
stack->pointer = stack->pointer + 1;
if (stack->pointer >= stack->size)
{
printf("Stack is full. Expanding the stack size.");
resize(stack);
// stack_data still points to old memory allocation
}
assert(stack->pointer < stack->size);
stack_data[stack->pointer] = element;
}
Since you modified stack->data
inside resize()
, your saved pointer stack_data
may point to invalid memory locations after resize()
. You never assigned the new stack->data
to stack_data
and you're using the latter directly, which leads to memory access violation.
Your fixed version is using stack->data
consistently so the above issue doesn't exist anymore.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments