Thread: *** Question on Data Structures ***

Greeting everybody,

I do have a question with one of the data structures that I'm trying to create (template below) -

Code:

int BCount;
int Ccount;

struct A {
    struct B* Bptrs[]; <- array of pointers to struct B
    struct C* Cptrs[]; <- array of pointers to struct C
    struct A* next;    <- pointer to next A node
} *A                       <- pointer to struct A

struct B {
    struct A* Aptr;    <- pointer to struct A
    struct C* Cptrs[]; <- array of pointers to struct C
    struct B* next;    <- pointer to next B node
} *B                       <- pointer to struct A

struct C {
    struct A* Aptr;    <- pointer to struct A
    struct B* Bptr;    <- pointer to struct B
    struct C* next;    <- pointer to next C node
} *C                       <- pointer to struct C

As you can see, the three structures are linked to one another. Now for the questions -

a. Can I setup all the nodes for one struct (leaving the pointers to other structs as NULL), and have them pointing to the correct instances, once nodes have been created for other structures (holds good for pointers in other structures as well).

b. I have an array of pointers to other structs in A and B. The length of the array (more like, number of pointers required), would be decided by the variables, BCount and CCount that would be available only during runtime. Can this be done? Dynamically creating storage for an array of pointers? If yes, please let me know.

Regards,
CT

Originally Posted by cybertaurean

a. Can I setup all the nodes for one struct (leaving the pointers to other structs as NULL), and have them pointing to the correct instances, once nodes have been created for other structures (holds good for pointers in other structures as well).

I'm not really sure what you mean by this, but I think the answer is yes. You'll have to be more clear in what you're trying to do. Try it out (it can't hurt), and if it doesn't do what you want, post your code and let us know what you want to happen and what is actually happening.

b. I have an array of pointers to other structs in A and B. The length of the array (more like, number of pointers required), would be decided by the variables, BCount and CCount that would be available only during runtime. Can this be done? Dynamically creating storage for an array of pointers? If yes, please let me know.

The feature you're looking for is called "variable length arrays" or VLAs. Unfortunately, AFAIK, they don't work inside a struct, at least inside a globally declared struct. That struct is defined at compile time, and the variables that would give the arrays inside a length have no value until run time. You would have to go old-school and malloc your own array.

The structures are all interlinked i.e. A <=> B <=> C <=> A, and I need to start with the creation of all nodes for a particular structure (A or B or C). Let's just say, I plan to create all the nodes for A. I can have all the pointers to B and C "pointing" to meaningful locations, only after I have created nodes for B and C. If you understood it the same way, and think it's possible, let me give it a try

About the next question, in the struct A, I have an array of pointers (struct B* Bptrs["??"]) pointing to B. Since the "??" is dependent on BCount, and malloc might be used, do you think I can dynamically allocate "BCount" number of cells for storing pointers to struct B??? i.e. allocate as -

Code:

malloc(BCount * size of a pointer to struct B)

I apologize if I'm just confusing you over here, but, I'm not sure how this can be explained any better.

Regards

Originally Posted by cybertaurean

The structures are all interlinked i.e. A <=> B <=> C <=> A, and I need to start with the creation of all nodes for a particular structure (A or B or C). Let's just say, I plan to create all the nodes for A. I can have all the pointers to B and C "pointing" to meaningful locations, only after I have created nodes for B and C. If you understood it the same way, and think it's possible, let me give it a try

Yes, I understood it the same way, and yes, you can only have B and C point somewhere useful once you malloc memory for them.

About the next question, in the struct A, I have an array of pointers (struct B* Bptrs["??"]) pointing to B. Since the "??" is dependent on BCount, and malloc might be used, do you think I can dynamically allocate "BCount" number of cells for storing pointers to struct B??? i.e. allocate as -

Code:

malloc(BCount * size of a pointer to struct B)

Yes, you can call malloc yourself, exactly as you wrote it. The preferred idiom is

Code:

foo = malloc(count * sizeof(*foo));

Using sizeof(*foo) makes sure the size allocated is always correct, even if foo's type changes.

Thanks a lot, anduril!!!

As for the malloc part, my understanding is that, it's used to allocate storage for data items. In this case, how would the usage differ, as we are dealing with allocating storage for pointers (I believe, pointers take up 4 bytes). Would it be something like -

Code:

foo = malloc (BCount* 4)

Pointers are a "data item". They just store the address of something else, instead of an int, float, string, struct or whatever. And it would be nothing like the example you posted. Pointers are not necessarily 4 bytes. It depends on the architecture and compiler. Beside, magic numbers (Magic number (programming) - Wikipedia, the free encyclopedia) are evil! Never guess at the size. The sizeof operator knows what you need. The code I gave you is perfect for what you want. I should have mentioned that you need to change the definition of the struct members as well:

Code:

struct A {
    struct B **Bptrs;  // This will allow you to allocate an array of pointers
    ...
};
...
a->Bptrs = malloc(BCount * sizeof(*(a->Bptrs)));

awesome!!!

Let me start working on the code. Thanks a lot, anduril

Hi anduril,

So, the following code should ideally work...

Code:

struct A {
    struct B **Bptrs;
};


A a;


a = malloc(sizeof(A));
a->Bptrs = malloc(BCount * sizeof(*(a->Bptrs)));

Have a question though. In the above case, we have already allocated a node (a) using malloc. How does the program work when the second malloc is called for allocating storage for pointers within the created node (a) ?

You should be doing a = malloc(sizeof(*a)); as well. Always take the thing on the left of the = and put it inside the sizeof operator with a * in front.

malloc works the same every time. You ask it for a certain number of bytes (sizeof(*a) or BCount*sizeof(*(a->Bptrs))). It either gives you that much memory or returns NULL. When you're done using the memory, remember that you have to call free(a->Bptrs) to free that memory before calling free(a). You free in reverse order from how you allocate.

Note that you should check the return value of malloc before carrying on. Doing a->Bptrs will likely cause a seg fault if malloc'ing a failed, so your code should be:

Code:

a = malloc(sizeof(*a));
if (a) {
    a->Bptrs = malloc(BCount * sizeof(*(a->Bptrs)));
    // if malloc'ing a->Bptrs fails, you have a serious problem
    // handle it accordingly and exit your function/program
    // make sure to free up any memory already allocated for a
}
else {
    // if malloc'ing a fails, you have a serious problem
    // handle it accordingly and exit your function/program
}

thanks much!!!