1

With this struct:

typedef struct MyStack {
    size_t     size;      // current size of stack
    size_t     max;       // max size of stack
    Item*      data[];
} MyStack;

How do I do a proper malloc and then realloc ? For example, if I do:

MyStack* stack = malloc(sizeof(MyStack));
stack->data  = malloc(size * sizeof(Item*));
// ... and later on...
stack->data = realloc(stack->data, new_stack_size);

I get the following errors:

error: invalid use of flexible array member
error: invalid use of flexible array member (one error for each item above)

What would be the proper way to do this then? Would this be simpler using Item** data instead of Item data[] ?

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
carl.hiass
  • 1,526
  • 1
  • 6
  • 26
  • See [this answer](https://stackoverflow.com/a/19526457/841108) to a similar question. Read also [the Dragon book](https://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools) and the [GC handbook](https://gchandbook.org/) – Basile Starynkevitch Feb 01 '21 at 05:13
  • 1
    Why not just `Item* data;`? It's a pointer to `data` items. Also, why `sizeof(Item*)`? You aren't allocating space for pointers, are you? – David Schwartz Feb 01 '21 at 05:14
  • `Item` is a struct so I want an array of pointers to those `Item`. Sorry the name is so generic, I can change that to make it more clear. – carl.hiass Feb 01 '21 at 05:16
  • @carl.hiass I'm a bit puzzled. You want an array of pointers and then you'll initialize each pointer in that array to pointer to something? Where will the actual elements pointed to be? Can you show us more code -- how you plan to use an array of pointers? – David Schwartz Feb 01 '21 at 05:17
  • Just read https://en.cppreference.com/w/c/language/struct. Why don't you search for the answer first? – user14063792468 Feb 01 '21 at 05:20
  • 1
    https://stackoverflow.com/questions/12680946/allocating-struct-with-flexible-array-member/12680984#12680984 is related and may help. – Nate Eldredge Feb 01 '21 at 05:20
  • 1
    @BasileStarynkevitch I'm sorry, but how are those books even remotely related? – carl.hiass Feb 01 '21 at 06:00
  • @NateEldredge thanks for pointing that out, that's very helpful. – carl.hiass Feb 01 '21 at 06:08
  • @carl.hiass: Garbage collection techniques and terminologies are relevant to `malloc` etc.... and parsing techniques use stacks – Basile Starynkevitch Feb 01 '21 at 09:09

1 Answers1

3

No, you do not want to use a flexible array member for this (i.e. data[];). The allocation for the Item *data[] is done in the same operation that allocates the entire MyStack as Item *data[] will be located at the end of it.

However this will never work with your stack because presumably you want to hold pointers to the stack object elsewhere. When you realloc then all pointers pointing to the stack previously will become invalid (indeterminate to be precise). Otherwise all functions that change the stack must always have MyStack **stack pointer to pointer as an argument and you can only have one direct reference to it.

Thus the flexible array member is not what you'd want to use here. So yes, it would mostly be simpler to just use Item **data - or even Item *data if the data items would be contained inside the stack. This will mean double indirection as above, but it will be much simpler to handle in this case, and you can pass MyStack *stack to any functions that modify the stack.

P.S. always expand the allocation by a factor instead of a constant amount so that the amortized insertion cost is O(1) per one insertion operation instead of O(n), i.e. new_stack_size = new_stack_size * 5 / 4 + 1 or something...

Antti Haapala -- Слава Україні
  • 129,958
  • 22
  • 279
  • 321
  • thanks, could you please suggest a better approach for the above then? – carl.hiass Feb 01 '21 at 05:25
  • just to clarify -- when you say "expand by a factor" -- you just mean doing something like 100 x 2 = 200 instead of 100 + 10 = 110. Correct? – carl.hiass Feb 01 '21 at 06:00
  • 1
    @carl.hiass yes. It will work correctly in both cases but say if your stack is 1M items, and you realloc to 1M+10 items, it needs to copy these 1M items to a new memory location after every 10 items added and that will be costly. Optimal allocation size discussed at https://stackoverflow.com/q/1100311/918959 – Antti Haapala -- Слава Україні Feb 01 '21 at 06:01