Click here to Skip to main content
15,845,436 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Hello forum,

is it possible to create a tree data structure in pure C?
This is not about a binary tree but every node shall have 0-n children.

The tree shall never be changed at runtime. Since this is for an embedded (Microchip Pic32) project, RAM is an issue. So I'd like to store the whole thing in code memory. Usually that's given for everything "const".

This is what I tried:
C
/* Header */
typedef struct TreeNode TreeNode;

/* Source */
struct TreeNode{
    int id;
    char* text;
    TreeNode* children[]; // List of child nodes
};

void DoSth(void)
{
    static const TreeNode tree = {
        0, "hidden", (TreeNode[3]){
            (TreeNode){1, "child", NULL},           // (1)
            (TreeNode){2, "secondChild", NULL},     // (1)
            (TreeNode){3, "thirdChild", NULL}       // (1)
	}
    };                                              // (2)

    // Code that's actually using the data
}
I know for sure that within the struct definition, children has to be referred to by pointers since TreeNode itself is not fully defined at that time.

But Compiler complains (numbering by me)
(1) non-static initialization of a flexible array member
(2) initializer element is not constant

(1) How should that not be static? Everything is given for the initialization.

(2) Same question as (1). Why is that not constant? And this is especially important given the embedded low RAM environment.
Posted
Updated 5-May-15 23:46pm
v2

You are trying to mix static and dynamic data, so the compiler does not know how much space to reserve. You probably need a different structure for child nodes that do not themselves have children. You cannot declare an array as NULL as you have tried to do in your child nodes.
 
Share this answer
 
Comments
lukeer 7-May-15 2:06am    
Ok, so let's for now forget the static data part.
A pointer to an array of child nodes should be possible. How to initialize that?

And then back to the reason for the static part. How to keep the completely initialized data off RAM and store it in flash? Is it even possible to store pointer stuff in flash?
Richard MacCutchan 7-May-15 4:03am    
Yes it is all possible, but in order to create the information at compile time you must use fixed sizes for every item. And you cannot declare an array of pointers as NULL, you muse declare a value for each item. You possibly need to create the tree in reverse, starting with the lowest child elements, and then each successive parent has a single pointer to the chain of children. Alternatively (probably not feasible in your case), make everything dynamic and create it at run time.

Don't know about flash memory or how to initialise it.
As Richard said it is not possible to make what you want with incomplete types and variable lenght arrays, but ...
If you don't dislike the dark side of the C, there is a workaround:
C++
typedef struct _TreeNode{
    int id;
    char* text;
    struct _TreeNode* children[1]; // List of child nodes
} TreeNode;

static TreeNode tree1 = {1, "child",       {0}};
static TreeNode tree2 = {2, "secondChild", {0}};
static TreeNode tree3 = {3, "thirdChild",  {0}};
static TreeNode tree4 = {4, "fourthchild", {0}};

void *FakeTree[] = {
                     (void *)0,
                     (void *)"hidden",
                     (void *)&tree1,
                     (void *)&tree2,
                     (void *)&tree3,
                     (void *)&tree4
                    };

void DoSth(void)
{
	TreeNode *tree = (TreeNode *)&FakeTree;

	// Code that's actually using the data
	// Please remember that you must access the structure always as a
	// pointer to it. I.e.
	for (int i=0; i<4; i++)
	{
		printf("id=%x, name=\"%s\"\n", pTree->children[i]->id, pTree->children[i]->text);
	}
}

The only limit is that it is mandatory that the integers and the pointers of the machine where you'll use the code have the same size.
Last advice: this could be dangerous for your code, don't make it at home! Jocking, this is how you don't have to make programs, but if it is necessary...
I hope this solves your problem ;)
 
Share this answer
 
v4

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900