How should I malloc/realloc with a struct that includes an array?

Question

I'm pretty new to c, so if my steps are wrong, please let me know. Let's say that I have something like the following:

struct graphNode{
    int val;
    graphNode* parent;
    int succSize;
    int succMaxSize;
    graphNode* succ[1];
};

I will create a new node with:

graphNode *n;
n = malloc(sizeof(struct graphNode));
assert(n);
n->val = 1;
n->parent = NULL;
n->succSize = 0;
n->succMaxSize = 1;

Then, if I want to add a successor to the node

if (n->succSize == n->succMaxSize){
    n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
    n->succMaxSize *= 2;
} 
n->succ[succSize] = n2; //n2 is of type graphNode*
succSize++;

Is this correct? Do I need to realloc for the struct as well or is realloc of the array enough? Do I need to malloc for the initial array? Should the initial array size be included in my malloc call for n?

Answer 1

The usual way to define a "stretchy" array member in C is to either specify a size of 0 or no size at all, e.g.:

struct foo {
    int stuff;
    bar theBars[]; // or theBars[0]
};

With this definition, sizeof(struct foo) will include all the elements other than the array at the end, and you can allocate the right size by saying malloc(sizeof(struct foo) + numberOfBars * sizeof(bar)).

If you need to reallocate it to change the number of bar elements, then you'll use the same formula (but with a new numberOfBars).

To be clear, you can't just realloc part of a struct. You have to realloc the whole thing.

Answer 2

realloc(ptr,size) needs 2 parameters, not 1 as used in realloc(sizeof(graphNode*) * n->succMaxSize * 2)

// Something like ...
graphNode *n;
n->succSize = 0;
n->succMaxSize = 0; // set to 0
n->succ = NULL;  // Initialize to NULL

// Then, if OP wants to add a successor to the node
if (n->succSize <= n->succMaxSize){
  n->succ = realloc(n->succ, sizeof(graphNode*) * n->succMaxSize * 2);
  n->succMaxSize *= 2;
} 
n->succ[succSize++] = n2;

---

As with all memory allocations, check for NULL return. In realloc(), one should save the original value, so if the realloc() fails, the original pointer is not lost.

Answer 3

Usually when you see struct definition where the last field is an array of size 0 or 1 it means the author is going to do some subtle stuff with malloc when the struct is malloced.

For example

struct foo {
   int x;
   :
   : 
   type a[0];
};

With a malloc like

  struct foo *p = malloc(sizeof(*p) + (n * sizeof(type));

What this does is it allocates a contiguous chunk of memory for the struct and the trailing array. In this case the array size is n. So references to the array in this case are:

p->a[i] // where i >= 0 and i < n

One reason for doing this is to save memory.

I'm sure there are better explanations for this on StackOver; it's a very common C idiom.

It's generally not used when the array is dynamic. Rather, it is used when the array size is known at malloc() time. You can use dynamically, of course, but you have to realloc the entire memory chunk, not just the struct or array by itself. To increase the size to 2n you would say

  p = realloc(p, sizeof(*p) + (2 * n * sizeof(type)));

Now your array is twice is big as it was, and it's still one chunk of memory.

Answer 4

If you only want a single array, just make succ a single pointer and only use malloc/realloc etc. to allocate memory for the array.

graphNode* succ;

What you are doing is almost certain to break.

Answer 5

I too am new to C, but there's some things that I can see right off the bat. First of all, you can't re-allocate arrays. In c89, they're compile-time fixed-size. In C99 and C11, they can be dynamically allocated, but not reallocated (as far as I'm aware). So for this, you need to allocate a

graphnode *succ; 

pointer, and malloc(nodes * sizeof(node)).

graphNode* succ[1];

This creates an array of size one, not an array with a maximum index of one. So, it is the same (almost) functionally as

graphNode* succ;

except that you can't change its size once you've made it.

I think what you want is to make a tree, with a dynamically re-allocable amount of branches. In this case, you only need to reallocate the size of the graphNode* pointer, and then access each element via index as you would an array.