Hierarchical k-ary tree in C without relying on RAM

I created a k-ary tree in C to be used as an easy and efficient way to organize "UML-like" data in embedded devices. The left node is at the lower logical level (a child) while the right node is at the same logical level but represent a different data or option (sibling).

Since it is to be used in embedded devices with possibly very low available RAM, I want to be able to instantiate the bulk statically (use ROM) and modify the tree at runtime (using RAM).

How can I make the tree:

• more efficient?

• less hungry on memory?

• more user friendly?

kary_tree.h:

```
#ifndef KARYTREE_H_
#define KARYTREE_H_

#include

typedef void (kary_Iterator)(void); / To map a function for every node's data - could add parameters or return to make it more flexible /
typedef struct kary_Node* kary_NodeHandle;

/ We're keeping the definition public to allow static global instantiation (needs definite type)/
struct kary_Node
{
void* data;
kary_NodeHandle firstKid;
kary_NodeHandle nextSibling;
}kary_Node;

kary_NodeHandle kary_createNode(void* data);
void kary_destroy(kary_NodeHandle* root);

/* This is a hierarchical tree; not an ordered tree.
* Left means its at a lower logical level (child) ; Right means its another option at the same logical level (sibling)
* Removing a node removes it's whole subtree because the sub-options don't make sense if not accessed through their direct higher logical level.
*/
kary_NodeHandle kary_insertChild(kary_NodeHandle parent, kary_NodeHandle node);
kary_NodeHandle kary_insertSibling(kary_NodeHandle leftSibling, kary_NodeHandle node);
kary_NodeHandle kary_remove(kary_NodeHandle root, kary_NodeHandle node);

/ A way to use this tree is to keep a reference to the 'current' node and navigate through the nodes /
kary_NodeHandle kary_getNode(kary_NodeHandle root, void* data);
kary_NodeHandle kary_getParent(kary_NodeHandle root, kary_NodeHandle node);
kary_NodeHandle kary_getChild(kary_NodeHandle roote, kary_NodeHandle no

...it [the program] is to be used in embedded devices with possibly very low available
RAM

In that case, we should be getting rid of everything that isn't of absolute necessity, and adding some things that are.

Overall:

-
If one provides no memory modifier (such as __flash) then many
embedded systems compilers will copy the data into RAM (even sometimes when
it is declared as const). Given that RAM is normally a much more
precious resource than flash, then this is a Very Bad Thing™. As a
result, one should give a memory specifier such as __flash to force
data to be kept in flash.

Note that the syntax for doing so
varies by compiler vendor. __flash is an GCC and IAR extension. I've also
seen __code (Keil) and __rom (Microchip), among others.

-
I should be seeing more const values in your code. This isn't just for performance, but also for maintainability.

-
Use a size specific data type such as uint8_t to represent data. Hierarchical trees can take up a lot of space. As a result, it is very important that you be aware of exactly how much space is being consumed. The best way to do this is to use the C99 data types so that you know for sure what the underlying storage unit is. As a result, if your data type is int then I'd suggest that you are doing yourself a disservice.

In kary_tree.h:

-
Do you absolutely need `? I understand that it is a small header, but it is still extra code that could be eliminated.

-
You should look into using bit fields with your structures, to reduce memory consumption.

-
typedef your struct's when you declare them.

In kary_tree.c:

-
Be very sparing in your use of malloc() and free(), since you are using them on an embedded device. The military avoids those calls completely in their code. Why avoid them? An excerpt from the link:


The use of the C runtime library’s malloc() and free() APIs, which do
the grunt work of dynamic allocation, can introduce disastrous side
effects such as memory leaks or fragmentation. Further, malloc() can
exhibit wildly unpredictable performance and become a bottleneck in
multithreaded programs on multicore systems. Due to its risk, dynamic
memory allocation is forbidden, under the DO-178B standard, in
safety-critical embedded avionics code.

-
The != NULL part in your conditional checks can be removed.

In main.c:

-
If you aren't using modifying a string as you would with printf(), then you should be using puts().

-
You don't have to return 0 at the end of main(), just like you wouldn't bother putting return; at the end of a void-returning function. The C standard knows how frequently this is used, and lets you not bother.


C99 & C11 §5.1.2.2(3)


...reaching the } that terminates the main() function returns a
value of 0`.

StackExchange Code Review Q#57973, answer score: 12