realloc: reversed pointer array?

Question

Hi, I've written a rather simple(ish) stack implementation that would automatically grow its internal array buffer if needed.

For that, I'd naturally use realloc - It works, however, all array elements are ordered reverse after the realloc() call.

The code in question:

• Header: include/pd/stack.h
• Source: src/stack/stack.c

This example will trigger said behaviour:

#include "pd/strlib.h"
#include "pd/stack.h"
#include "pd/memory.h"
#include <stdlib.h>
#include <stdio.h>

int main()
{
    int index = 0;
    char* buffer;
    pd_stack_t* stc = pd_stack_new();
    pd_stack_push(stc, "blue");
    pd_stack_push(stc, "green");
    pd_stack_push(stc, "red");
    pd_stack_push(stc, "yellow");
    pd_stack_push(stc, "pink");
    pd_stack_push(stc, "olive");
    pd_stack_push(stc, "beige");
    pd_stack_push(stc, "gold");
    pd_stack_push(stc, "grey");
    pd_stack_push(stc, "lime");
    pd_stack_push(stc, "khaki");
    while((index++) != 500)
    {
        pd_stack_push(stc, "__random_value__");
    }
    buffer = (char*)malloc(pd_stack_size(stc));
    pd_stack_dump_tomem(stc, buffer, 1);
    fprintf(stdout, "%s", buffer);
    return 0;
}

I'm really clueless about this. Help please!

Answer 1

Looks like pd_stack_dump_tomem starts its index at stack size and decrements to 0, appending the elements in reverse order.

Change it to start at 0 and iterate to stack size

(It seems realloc is unrelated)

Answer 2

You have some fundamental problems with the stack code, so I don't think the realloc() is your issue. Here are some of the things you should look into and address:

• the top item on the stack (when it's not empty) is pointed to by (gct->stackcount - 1), since in pd_stack_push() you store a new item in gct->ptr_stack[gct->stackcount] then increment stackcount. However, when you're accessing the top item, you use the incorrect offset, gct->ptr_stack[gct->stackcount] instead of gct->ptr_stack[gct->stackcount - 1]. In particular, in pd_stack_pop(), you free that item which will might be corrupting the heap since there's not a valid pointer in that stack location.

• in pd_stack_push() you call realloc() every time a new item is pushed on to the stack. This won't necessarily corrupt anything or cause a defect, but it's unnecessary - especially since you always ask for the same size allocation. In other words, your realloc() calls should be nops except for the first one.

• pd_stack_pop_index() doesn't even make sense unless you only ever pop the top item (in which case pd_stack_pop() should be used). You free something potentially in the middle of the stack, then decrement the stackcount, essentially making the top item (which is not necessarily what you've freed) inaccessible. The item in the middle of the stack that was freed will now be accessed/freed again when it's popped (assuming that pd_stack_pop() is fixed).