Inside a structure how can I define an array (dynamic) of structures with the same type as the structure itself.

Question

The objective is to build a "infinite" tree using dynamic arrays.

items[3]
- MENUITEM
  - items[2]
    - MENUITEM
      -items[0]
    - MENUITEM
      - items[0]
- MENUITEM
  - items[0]
- MENUITEM
  - items[2]
    - MENUITEM
      - items[0]
    - MENUITEM
      - items[0]

I define the structure:

typedef struct MENUITEM {
    char id, count;
    char *description;
};

And I can allocated items dynamically with:

char count;
MENUITEM items[], *items_ptr;

count++;
realloc( items_ptr, count * sizeof(struct MENUITEM) );

The problem is that inside the structure I cannot assign again the structure itself like:

typedef struct MENUITEM {
    char id, count;
    char *description;

    MENUITEM items[], *items_ptr;
};

The compiler outputs: error: field ‘items’ has incomplete type; what am I doing wrong here ? Thanks for any help provided.

Answer 1

You need to use struct MENUITEM *items_ptr;. Note the use of the word struct.

Why do you have MENUITEM items[]? It's not used for anything.

Do this instead:

typedef struct MENUITEM {
    char id, count;
    char *description;

    struct MENUITEM *items;
} MENUITEM;

void foo() {
    MENUITEM *root = (MENUITEM*)malloc(sizeof(MENUITEM));

    root->id = 87;
    root->count = 5;

    root->items = (MENUITEM*)malloc(sizeof(MENUITEM)*root->count);
}

Answer 2

Change the MenuItem structure to hold a pointer to MENUITEM

typedef struct MENUITEM {
    char id, count;
    char *description;

    MENUITEM *items_ptr;
};

Not alone that the allocation is not good either - it would be much slower doing this

count++;
realloc( items_ptr, count * sizeof(struct MENUITEM) );

You would be better off allocating a block of memory say to hold 50 entries, when the limit has reached, realloc it with twice the block size and please ensure that you do not clobber the result like this:

Correct:

MENUITEM *temp_items_ptr;
temp_items_ptr = realloc( items_ptr, count * sizeof(struct MENUITEM) );
if (temp_items_ptr != NULL){
   items_ptr = temp_items_ptr;
}else{
   /* Handle the out of memory situtation */
}

Wrong:

items_ptr = realloc( items_ptr, count * sizeof(struct MENUITEM) );

The wrong approach is a recipe for disaster and say hello to leaked memory!