Find an array element position in compile time

Question

-- Edited --

Hi all. I've got an array of elements that will not change in all the execution of the program, and where items can have sons inside the own array. I've got to prepare the array before process it. However, because I know that the array will not change, I would like to declare it as const, and prepare all of it in compile time, so I could throw away the integers int son_id[NUM_OF_SONS], prepare_items() function and the array declaration will be, in my opinion, clearer.

#include <stdlib.h>
#include <stdio.h>

#define NUM_OF_SONS 5

struct item{
    int id;
    char *str;
    int son_id[NUM_OF_SONS];
    const struct item *son[NUM_OF_SONS];
};

const struct item *find_item(int id);

static struct item items[] = {
    {4, "FIRST ELEMENT"},
    {5, "SECOND ELM"},
    {10, "THIRD ELM"}, 
    {15, "FATHER", {5,10}},
    {0, 0 }
};

const struct item *find_item(int id){
    int i;
    for(i=0; items[i].str != NULL; ++i){
            if(items[i].id == id) return &items[i];
    }

    return NULL;
}

void fill_sons(struct item *item){
    int i;
    for(i=0;i<NUM_OF_SONS;++i){
            if(item->son_id[i]!=0)
                    item->son[i] = find_item(item->son_id[i]);
    }
}

void prepare_items(){
    int i;
    for(i=0;i<sizeof(items)/sizeof(items[0]);++i){
            fill_sons(&items[i]);
    }
}

void print_sons(const struct item *item);

void print_item(const struct item *item){
    printf("The item %d has the text %s.\n",item->id,item->str);
    print_sons(item);
}

void print_sons(const struct item *item){
    int i;
    for(i=0;i<NUM_OF_SONS;++i){
            if(NULL!=item->son[i])
                    print_item(item->son[i]);
    }
}

int main(){
    prepare_items();

    print_item(&items[0]);
    print_item(&items[3]);
}

I've though in something like this:

static struct item items[] = {
    {4, "FIRST ELEMENT"},
    {5, "SND ELM"},
    {10, "THIRD ELM"},
    {15, "FATHER", {&items[1],&items[2]}},
    {0, 0 }
};

However, there could be about 200 elements in the array, and I need to be able to insert or delete elements in the middle of it (in compile time). So &items[1],&items[2] should be ITEM_ID(5),ITEM_ID(10), some kind of preprocessor instruction. How could achieve that?

Thanks in advance, and sorry for the long post.

Answer 1

The nearest equivalent to templates in C (that I know of) is X-Macros. I think you can achieve this result, but it will require introducing another identifier for each struct (actually it doesn't -- scroll down to the "Edit"!) which we can sync with the array by declaring these identifiers in an enum.

To start with, we change the initializer elements to be in the form of macro calls. For the style I prefer, the name of this macro is not important, so I'll call it _. All calls will need the same number of elements, so add an empty list where necessary. And the whole thing is wrapped in one big macro. This big macro will receive another macro as an argument which it calls for each element.

#define DATA(_) \
    _(4, "FIRST_ELEMENT", {}) \
    _(6, "SECOND_ELEMENT", {}) \
    _(10, "FATHER ELEMENT", {15, 20}) \
    _(15, "SON ELEMENT 1", {}) \
    _(20, "SON ELEMENT 2", {}) \
    _(0, NULL, {})

Now we can declare the array data by defining a usage macro that emit the arguments in the correct form for the array declaration.

#define CREATE_ARRAY(a, b, c) \
    {a, b, c},

struct item items[] = {
DATA(CREATE_ARRAY)
}

So far we've just achieved the same result. But now it's in a more flexible form. The next step is adding the new IDs.

#define DATA(_) \
    _(FIRST, 4, "FIRST_ELEMENT", {}) \
    _(SECOND, 6, "SECOND_ELEMENT", {}) \
    _(FATHER, 10, "FATHER ELEMENT", {15, 20}) \
    _(SON1, 15, "SON ELEMENT 1", {}) \
    _(SON2, 20, "SON ELEMENT 2", {}) \
    _(END, 0, NULL, {})

And adjust the CREATE_ARRAY macro to account for the new argument.

#define CREATE_ARRAY(a, b, c, d) \
    {b, c, d},

struct item items[] = {
DATA(CREATE_ARRAY)
};

Now the fun part. We make another macro to generate the IDs as enum values.

#define CREATE_IDS(a, b, c, d) \
    a,

enum identifiers {
DATA(CREATE_IDS)
};

Now the data can use these identifiers to index the array.

#define DATA(_) \
    _(FIRST, 4, "FIRST_ELEMENT", {}) \
    _(SECOND, 6, "SECOND_ELEMENT", {}) \
    _(FATHER, 10, "FATHER ELEMENT", {SON1, SON2}) \
    _(SON1, 15, "SON ELEMENT 1", {}) \
    _(SON2, 20, "SON ELEMENT 2", {}) \
    _(END, 0, NULL, {})

And, of course, remove the child_id member from the struct, since our new identifiers are the desired array indices, directly.

---

Edit. Wait a moment. You have identifiers already. And they're already unique. So we don't need to introduce new ones. We can simply mangle them! __VA_ARGS__ is also needed to handle the possible embedded commas in the child list.

#define CREATE_ARRAY(a, b, ...) \
    {a, b, __VA_ARGS__ },

#define ID_(x) ID ## x
#define CREATE_IDS(a, b, ...) \
    ID_(a),


#define DATA(_) \
    _(4, "FIRST_ELEMENT", {}) \
    _(6, "SECOND_ELEMENT", {}) \
    _(10, "FATHER ELEMENT", {ID15, ID20}) \
    _(15, "SON ELEMENT 1", {}) \
    _(20, "SON ELEMENT 2", {}) \
    _(0, NULL, {}) 

enum identifiers {
DATA(CREATE_IDS)
};

struct item items[] = { 
DATA(CREATE_ARRAY)
};

cpp -P output (linebreaks added):

enum identifiers {
ID4, ID6, ID10, ID15, ID20, ID0,
};
struct item items[] = {
{4, "FIRST_ELEMENT", {} }, 
{6, "SECOND_ELEMENT", {} }, 
{10, "FATHER ELEMENT", {ID15, ID20} }, 
{15, "SON ELEMENT 1", {} }, 
{20, "SON ELEMENT 2", {} }, 
{0, NULL, {} },
};

---

For more about X-macros, see the answers to this question (one of which I wrote :P).

Answer 2

About the best I can offer--because C is absolutely not designed to keep track of this sort of metadata--is the __LINE__ constant.

__LINE__ inserts the current line number into the program, which you can use as a field in the struct item. Obviously, you need to also commit to not having any blank spaces in your definition of items and also know where items starts in the file. The latter, you can do with something like:

int first_line = __LINE__ + 2;
const struct item items[] = {
    {4, "FIRST_ELEMENT", __LINE__},

And then remember to subtract first_line from your line_id (or whatever you want to call it) field.

It's not a good solution, but I think it's about the best that C is going to do without writing code to load the contents of one array into another and keep track of the metadata during the move.

Answer 3

First things first, you have to know that once you declare items as an array to constant item structures, which you do when you write const struct item items[];, you then won't be able to change the contents of those structures after initialization.

So, for example, you won't be able to assign anything to any of the elements of the child array inside any one of the structures inside the items array. Woah, that was big, let's give a code example:

items[2].child[0] = &( items[3] );
// or just ... items + 3;
// you won't be able to do this because items[2] is defined as a constant

I couldn't really understand what your objective is, but here's one thing that possibly maybe help you out. You can do the following:

#include <stdio.h>
#define MaximumChildCount 5 // personal preference, easier to read, change as you wish

typedef struct item{
    int id;
    char *str;
    // I left the childs_id out, since you've implied that you'd like that out
    struct item *child[MaximumChildCount];
};

int main( ){

    const struct item sons[] = {
        { 15, "SON ELEMENT 1" },
        { 20, "SON ELEMENT 2" }
    };
    // creating sons before the parent, biologically nonsense?
    // well, if you want to keep the record of child elements inside parent
    // and make them all constants, then you need to have children before

    const struct item items[] = {
        { 4, "FIRST_ELEMENT" },
        { 6, "SECOND_ELEMENT" },
        { 10, "FATHER ELEMENT", { sons, sons + 1 } },
        // sons points to first son, sons + 1 points to the second one
        // assigned them at initialization, just like you had with { 15, 20 }
        { 0, NULL }
    };

    printf( "%s", items[2].child[1]->str );

    return 0;
}

This prints "SON ELEMENT 2". You can very well make sons in the following way:

const struct item son1 = { 15, "SON ELEMENT 1" };
const struct item son2 = { 20, "SON ELEMENT 2" };

And then assign them during initialization like this:

... = {
    ...
    ...
    { ..., ..., { &son1, &son2 } },

    ...
};

I'm sorry if this was not the thing you were looking for. I really am having hard times on understanding the cause.