Variable sized self references in struct

Question

I am trying to implement something that requires a structure like this:

struct abc
{  
  int size;
  struct abc *links[size];
}

Here, I want size to change at runtime, not just merely be different for each instance of abc, and instances of abc have varying number of links depending on the program. How do I create/manage/allocate memory for such a data structure? Is it even possible in C?

Answer 1

Easyest way would be to change your structure like this:

struct abc
{  
  int size;
  struct abc **links;
}

and calloc the array dynamically:

abc.links = (struct abc **)calloc(abc.size, sizeof(void *));

Then you can address the elements of the links array this way:

struct abc a,b,c, ...;
int n;
...
a.links = (struct abc **)calloc(a.size, sizeof(void *);
a.links[n] = &b;
struct abc *z = a.links[n];

Be careful of not trying to access elements outside the boundaries of the calloc'ed array or you will get memory exceptions and unexpected behavior. Remember also to free(abc.links) for each allocated structure to prevent memory leaks...

Hope this helps

Answer 2

The C standard (C99 and following) foresees the following construct to deal with such a situation, called flexible array member:

struct abc
{  
  size_t size;
  struct abc *links[];
};

You'd allocate such a beast with malloc:

struct abc * a = malloc(sizeof(struct abc) + sizeof(struct abc*[n]));
a.size = n;
for(size_t i = 0; i < n; ++i) a.links[i] = 0;
.
free(a);

Answer 3

You can do this, but it's not automatic. I would do it with some kind of initialization routine:

struct *abc abc_init(int size)
{
    struct abc *abc = calloc(1, sizeof(*abc));
    abc->size = size;
    abc->links = calloc(1, sizeof(*(abc->links)) * size);

    return abc;
}

Then you could also have a free routine:

void abc_free(struct abc *abc)
{
    for (int i = 0; i < abc->size; i++) {
        abc_free(abc->links[i]);
    }
    free(abc->links);
    free(abc);
}

Note that abc_free() calls itself for each element in links in this example, so you have to watch our for recursion here. Also note that all error checking (e.g. NULL checking) is missing here, for compactness.

These routines simplify creating and freeing your structs, then all you need to do is access/set them.

Answer 4

There is a possibility if you don't want to have to remember to call free(abc.links) and if size won't change during the lifetime of the object:

struct abc
{  
    int size;
    struct abc *links[0]; // use 1 if your compiler complains
}

(Note: This special zero-length array must be the last member of the struct)

How can a zero-length array help, you might ask? It works if you allocate abc with

 struct abc * a = malloc(sizeof(abc)+ size * sizeof(struct abc *));

This deliberately creates too much memory such that we can then use a->links[3] or a->link[4] safely (as long as we remember to respect the size. We can then simply use free(a), we don't need to (and cannot) free(a->links);.

In either case, don't forget to free each of the a->links[0] and a->links[1] and so on to a->links[a->size - 1] before attempting to free a.

Answer 5

There are people who will write this:

struct abc
{  
  size_t size;
  struct abc *links[1];
};

struct abc* abc_create(size_t size)
{
   struct abc* abc = calloc(1, sizeof(struct abc) + (size - 1) * sizeof(struct abc*));
   abc->size = size;
   return abc;
 }