Initializing constant struct containing pointer to its own type

Question

I'm having a struct like this:

typedef struct tree_s{
    struct tree_s *a;
    int b;
}tree_t;

Which, at the moment, I am initializing in this way:

tree_t branch_n = {
    .a = NULL,
    .b = 2
};

tree_t root = {
    .a = (tree_t*) &branch_n, 
    .b = 1
};

Now, it annoys me that I have to initialize the lower branches before the root because the complete structure is quite large, with the branches having branches on their own, making my code hard to manage.

What I would like to do is something like this:

tree_t root = {
    .a = 
     //The first branch
     {                 
        .a =
         //Yet another branch 
         { //Since the following is actually an array, I need the 
           // "a" above to point to the first index
             {  
                 .a = NULL,         //Maybe this will have its own branch
                 .b = 3
             },
             {
                 .a = 
                 {
                     .a = NULL,     //And this might even have its own branch
                     .b = 5
                 }
                 .b = 4  
             }
         }
        .b = 2
     }, 
    .b = 1
};

How can I achieve an initialization like this?

The main reason I want to do this is to greatly enhance the overview of my code and immediately visually see the structure of the "Tree".

Note that the structure of the complete "Tree" is know from the start which is why I consider the structure constant. The value b however may be changed at any time.

I am quite new to the C language and this is my first post on SO, so feel free to edit or ask if I havent been able to make myself clear :)

I think for this you should declare struct as typedef struct tree_s{ struct tree_s a; int b; }tree_t; — Grijesh Chauhan
– Grijesh Chauhan, Commented Jul 19, 2013 at 9:08
lulyon: Sorry, I have edited to include an actual question :). I can't make the initialization work in the way that I would like to (the example). Grijesh: I'm getting error "incomplete type is not allowed" from my compiler (IAR Embedded Workbench) :/ — iMe
– iMe, Commented Jul 19, 2013 at 9:14
You can't declare a structure as in Grijesh's comment; you can only declare a structure containing pointers to its own type. — Jonathan Leffler
– Jonathan Leffler, Commented Jul 19, 2013 at 9:18

Jonathan Leffler · Accepted Answer · 2013-07-19 10:42:05Z

4

Option 1a — An array

Your 'tree' structure seems to be stuck with a rather linear shape, but you can use an array to get around the problem:

static const tree_t oak[] =
{
    { .a = &oak[1], .b = 20 },
    { .a = &oak[2], .b = 15 },
    { .a = NULL,    .b = 10 },
};

Option 1b — A tree built from an array

Or given a binary search tree structure:

#include <stdio.h>

typedef struct bst_t bst_t;
struct bst_t
{
    int          data;
    const bst_t *left;
    const bst_t *right;
};

static const bst_t bst[] =
{
    { .data = 30, .left = &bst[1], .right = &bst[2] },
    { .data = 10, .left = &bst[3], .right = &bst[4] },
    { .data = 50, .left = &bst[5], .right = &bst[6] },
    { .data =  5, .left = &bst[7], .right = &bst[8] },
    { .data = 20, .left =       0, .right = &bst[9] },
    { .data = 40, .left =       0, .right =       0 },
    { .data = 60, .left =       0, .right =       0 },
    { .data =  2, .left =       0, .right =       0 },
    { .data =  8, .left =       0, .right =       0 },
    { .data = 28, .left =       0, .right =       0 },
};

static void print_in_order(const bst_t *bst)
{
    if (bst != 0)
    {
        printf("[");
        print_in_order(bst->left);
        printf("(%d)", bst->data);
        print_in_order(bst->right);
        printf("]");
    }
}

static void print_tree(const bst_t *bst)
{
    print_in_order(bst);
    putchar('\n');
}

int main(void)
{
    print_tree(&bst[0]);
    return 0;
}

This produces the output:

[[[[(2)](5)[(8)]](10)[(20)[(28)]]](30)[[(40)](50)[(60)]]]

Option 2a — C99 compound literals

With C99 and compound literals, you can write:

#include <stddef.h>

typedef struct tree_s{
    struct tree_s *a;
    int b;
}tree_t;

tree_t root2 =
{
    .a = &(tree_t){ .a = NULL, .b = 2 }, .b = 1
};

tree_t root3 =
{
    .a = &(tree_t){ .a = &(tree_t){ .a = NULL, .b = 3 }, .b = 2 }, .b = 1
};

I'm not sure that it is legible, but it compiles OK. On the whole, I prefer the array notation, though.

This is the primary answer that the OP wanted/used.

Option 2b — Failed attempt to get array into initialization

Attempting to adapt the revised data structure in question (bearing in mind that the 'tree' that can be created with the data structure is only a singly-linked list), you can almost (but not quite) do it with this:

tree_t root4 =
{
    .a = &(tree_t)
    {                 
        .a = (tree_t [])
        { 
            (tree_t){  
                .a = NULL,
                .b = 3
            },
            (tree_t){
                .a = &(tree_t)
                {
                    .a = NULL,
                    .b = 5
                },
                .b = 4  
            },
        },  // Line 47
        .b = 2
    }, 
    .b = 1
};

GCC (i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)) on Mac OS X 10.8.4 complains:

tree.c:47: error: initializer element is not constant
tree.c:47: error: (near initialization for ‘(anonymous)’)

Where line 47 is marked — it is the end of the array of structures. I may be missing something obvious. I did try &(test_t[]){ ... }[0], but that got the same warning.

I'm not at all sure how you could tell that the particular pointer was a pointer to the start of an array rather than a single tree_t element, unless you add another field to indicate the difference (or the b field is somehow encoded to indicate whether the a is a pointer to a single item or a pointer to an array).

edited Jul 19, 2013 at 10:42

answered Jul 19, 2013 at 9:16

Jonathan Leffler

759k145 gold badges961 silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

iMe Over a year ago

Hello Jonathan, great example. How would I then initialize if I wanted "a" to have their own "a" (I see now that I would have been better off calling this a "child" :P). I mean, how would I init the grandchildren of "oak", without having to declare them before the oak.

Jonathan Leffler Over a year ago

Does the BST example help at all? Do you need the different nodes to have their own names?

iMe Over a year ago

I'm not sure if I haven't been able to make myself clear or that I just don't understand the example, I appreciate your time very much tho :). I have updated the example in my question to try and make it clearer. Yes your last example would probably work since it looks like the way I am currently doing it, but it means that I have to declare the members by them selves making it impossible to overview the structure of the final tree since it includes quite a number of children/grand children/great grand children.

Jonathan Leffler Over a year ago

Your revised example is similar to the root3 example in mine; I've just formatted the structure differently. However, your initialization also has issues at the inner levels; you've lost some .a / .b notations (designated initializers).

iMe Over a year ago

Ahh yeah I see now, this is exactly what I want to do. Thank you so much, you wouldn't believe how much time I've spent struggling with this :)! Actually, may I suggest that the answer is only the typedef of the struct and the init of root3 (lines 3 to 6 + 24 to 27), this is all I need to know to solve my problem. I'll accept this as the answer in case you choose not to simplify - again thank you so much, Jonathan :)

lulyon · Accepted Answer · 2013-07-19 09:46:08Z

0

I do not think this code:

tree_t root = {
    .a = 
     //The first branch
     {                 
        .a = NULL,       //Maybe another branch instead of NULL
        .b = 2
     }, 
    .b = 1
};

will successfully initialize the tree_t root.

The {} is for initializing a struct, not a pointer. But root->a is defined to be a pointer. You might get compiling error by this.

The branch could be defined and initialized outside the above code, and set the pointer root->a point to it.

answered Jul 19, 2013 at 9:46

lulyon

7,3657 gold badges35 silver badges49 bronze badges

1 Comment

iMe Over a year ago

Yes, you are right, but this is my problem, I would like to initialize the inner "tree_t" -inside- the root. It messes up the flow of code init'ing all the inner "tree_t"s first and then putting them all inside my root. I only want to do this to make my code more clean, easier to overview and maintain :)

Collectives™ on Stack Overflow

Initializing constant struct containing pointer to its own type

2 Answers 2

Option 1a — An array

Option 1b — A tree built from an array

Option 2a — C99 compound literals

Option 2b — Failed attempt to get array into initialization

5 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Option 1a — An array

Option 1b — A tree built from an array

Option 2a — C99 compound literals

Option 2b — Failed attempt to get array into initialization

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related