Dylan Dylan - 1 year ago 60
C Question

How do I properly allocate an array within a struct with malloc and realloc in C?

I'm trying to implement a stack in C, while also trying to learn C. My background is mostly in higher languages (like Python), so a lot of the memory allocation is new to me.

I have a program that works as expected, but throws warnings that make me believe I'm doing something wrong.

Here is the code:

typedef struct {
int num_items;
int top;
int items[];
} stack;

void push(stack *st, int n) {
st->num_items++;

int* tmp = realloc(st->items, (st->num_items) * sizeof(int));

if (tmp) {
*(st->items) = tmp;
}

st->items[st->num_items - 1] = n;
st->top = n;
}

int main() {
stack *x = malloc(sizeof(x));
x->num_items = 0;
x->top = 0;
*(x->items) = malloc(0);

push(x, 2);
push(x, 3);

printf("Stack top: %d, length: %d.\n", x->top, x->num_items);

for (int i = 0; i < x->num_items; i++) {
free(&(x->items[i]));
}
free(x->items);
free(x);
}


Here is the output:

Stack top: 3, length: 2.


Which is expected. But during compilation, I get the following errors:

> gcc -x c -o driver driver.c
driver.c: In function 'push':
driver.c:16:16: warning: assignment makes integer from pointer without a cast
*(st->items) = tmp;
...
driver.c: In function 'main':
driver.c:27:14: warning: assignment makes integer from pointer without a cast
*(x->items) = malloc(0);

Answer Source

Your belief is correct. Usually - that is almost always - warnings from C compiler are signs of grave programming errors that will cause serious problems. Quoting Shooting yourself in the foot in various programming languages:

C

  • You shoot yourself in the foot.
  • You shoot yourself in the foot and then nobody else can figure out what you did.

The problem is that you're coding as if items was a pointer to int, yet you have declared and defined it as a flexible array member (FAM), which is an entirely different beast altogether. And since assigning to an array would produce an error, i.e.

x->items = malloc(0);

would be an error, you've come up with something that compiles with just warnings. Remember that errors are better than warnings, because they stop you from shooting yourself into foot.


The solution is to declare items as a pointer to int instead:

int *items;

and use

x->items = ...;

to get the pointer behaviour you expect.

Also,

free(&(x->items[i]));

is very wrong, since you never allocated the ith integer to begin with; they were objects in the array. Also, you don't need malloc(0); just initialize with a null pointer:

x->items = NULL;

realloc and free wouldn't mind the null pointer.


The flexible array member means that the last element in the structure is an array of indefinite length, so in malloc you would reserve enough memory for it too:

stack *x = malloc(sizeof x + sizeof *x->items * n_items);

The flexible array member is used in CPython for objects like str, bytes or tuple that are of immutable length - it is slightly faster to use a FAM instead of a pointer elsewhere, and it saves memory - especially with shorter strings or tuples.


Finally, notice that your stack becomes slower the more it grows - the reason is because you're always allocating just one more element. Instead, you should scale the size of the stack by a factor (1.3, 1.5, 2.0?), so that insertions run in O(1) time as opposed to O(n); and consider what will happen should realloc fail - perhaps you should be more loud about it!

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download