Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 <stdbool.h>


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 node);
kary_NodeHandle kary_getRightSibling(kary_NodeHandle root, kary_NodeHandle node);
kary_NodeHandle kary_getLeftSibling(kary_NodeHandle root, kary_NodeHandle node);


bool kary_isLeaf(kary_NodeHandle node);
bool kary_isLowestLevel(kary_NodeHandle node);
bool kary_isChildren(kary_NodeHandle parent, kary_NodeHandle node);


/* For every node in the subtree the function fn is applied to the node's data (fn(node->data) for each node below root)
 * Can be used for whole tree or subtree (kary_forEach(kary_getNode(root, myValue)); )
 */
void kary_forEach(kary_NodeHandle root, kary_Iterator fn);

#endif /* KARYTREE_H_ */

kary_tree.c:

#include "kary_tree.h"

#include <stdlib.h> /* Malloc - Free */
#include <string.h> /* Memset */

static void destroySubtree(kary_NodeHandle* node);


kary_NodeHandle kary_createNode(void* data)
{
    kary_NodeHandle newNode = malloc(sizeof(struct kary_Node));

    newNode->data = data;
    newNode->firstKid = NULL;
    newNode->nextSibling = NULL;

    return newNode;
}

void kary_destroy(kary_NodeHandle* root)
{
    destroySubtree(root);
    free(*root);
    *root = NULL;
}

kary_NodeHandle kary_insertChild(kary_NodeHandle parent, kary_NodeHandle node)
{
    node->nextSibling = parent->firstKid;
    node->firstKid = NULL;
    parent->firstKid = node;

    return node;
}

kary_NodeHandle kary_insertSibling(kary_NodeHandle leftSibling, kary_NodeHandle node)
{
    kary_NodeHandle temp = leftSibling->nextSibling;
    leftSibling->nextSibling = node;
    node->nextSibling = temp;

    return node;
}

kary_NodeHandle kary_remove(kary_NodeHandle root, kary_NodeHandle node)
{
    destroySubtree(&node->firstKid);

    kary_NodeHandle previous = NULL;
    kary_NodeHandle nodeToRemove = kary_getParent(root, node)->firstKid;

    while(nodeToRemove != NULL){
        if(nodeToRemove->data == node->data){
            (nodeToRemove == root) ? (root = nodeToRemove->nextSibling) : (previous->nextSibling = nodeToRemove->nextSibling);
            free(nodeToRemove);
            return node;
        }
        previous = nodeToRemove;
        nodeToRemove = nodeToRemove->nextSibling;
    }
     return NULL;
}

kary_NodeHandle kary_getNode(kary_NodeHandle root, void* data)
{
    kary_NodeHandle node = NULL;

    if(root->data == data){ return root; }

    if(root->firstKid != NULL)
        node = kary_getNode(root->firstKid, data);
    if(node != NULL){return node; }

    if(root->nextSibling != NULL)
        node = kary_getNode(root->nextSibling, data);
    if(node != NULL){return node; }

    return NULL;
}

kary_NodeHandle kary_getParent(kary_NodeHandle root, kary_NodeHandle node)
{
    kary_NodeHandle parent = NULL;

    if(kary_isChildren(root, node)){ return root; }

    if(root->firstKid != NULL)
        parent = kary_getParent(root->firstKid, node);
    if(parent != NULL){return parent; }

    if(root->nextSibling != NULL)
        parent = kary_getParent(root->nextSibling, node);
    if(parent != NULL){return parent; }

    return NULL;
}

kary_NodeHandle kary_getChild(kary_NodeHandle root, kary_NodeHandle node)
{
    return node->firstKid;
}

kary_NodeHandle kary_getRightSibling(kary_NodeHandle root, kary_NodeHandle node)
{
    return node->nextSibling;
}

kary_NodeHandle kary_getLeftSibling(kary_NodeHandle root, kary_NodeHandle node)
{
    kary_NodeHandle sibling = NULL;

    if(root->nextSibling == node){ return root; }

    if(root->firstKid != NULL)
        sibling = kary_getLeftSibling(root->firstKid, node);
    if(sibling != NULL){ return sibling; }

    if(root->nextSibling != NULL)
        sibling = kary_getLeftSibling(root->nextSibling, node);
    if(sibling != NULL){ return sibling; }

    return NULL;
}

bool kary_isLeaf(kary_NodeHandle node)
{
    return (node->firstKid == NULL && node->nextSibling == NULL);
}

bool kary_isLowestLevel(kary_NodeHandle node)
{
    return (node->firstKid == NULL);
}

bool kary_isChildren(kary_NodeHandle parent, kary_NodeHandle node)
{
    kary_NodeHandle child = parent->firstKid;
    while(child != NULL){
        if(child == node){ return true; }
        child = child->nextSibling;
    }
    return false;
}

void kary_forEach(kary_NodeHandle node, kary_Iterator fn)
{
    if(node == NULL){ return; }

    if(node->firstKid != NULL)
        kary_forEach(node->firstKid, fn);
    if(node->nextSibling != NULL)
        kary_forEach(node->nextSibling, fn);

    fn(node->data);
}

static void destroySubtree(kary_NodeHandle* node)
{
    if(*node == NULL){ return; }

    destroySubtree(&(*node)->firstKid);
    destroySubtree(&(*node)->nextSibling);

    free(*node);
    *node = NULL;
}

main.c:

#include "kary_tree.h"

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


/* The tree used for tests goes as follow:
 *
 * -=Root=-
 *  (1.0.0) - (2.0.0)
 *     |
 *  (1.1.0) - (1.2.0) - (1.3.0)
 *               |
 *            (1.2.1) - (1.2.2) - (1.2.3) - (1.2.4)
 */

/* Static global instantiation is possible so we use ROM instead of RAM for embedded systems with low memory */
                                    /*  Data           Parent   Sibling  */
static struct kary_Node node8 =         {"Node 2.0.0", NULL,    NULL};
    static struct kary_Node node7 =         {"Node 1.3.0", NULL,    NULL};
        static struct kary_Node node6 =         {"Node 1.2.1", NULL,    NULL};
        static struct kary_Node node5 =         {"Node 1.2.2", NULL,    &node6};
        static struct kary_Node node4 =         {"Node 1.2.3", NULL,    &node5};
        static struct kary_Node node3 =         {"Node 1.2.4", NULL,    &node4};
    static struct kary_Node node2 =         {"Node 1.2.0", &node3,  &node7};
    static struct kary_Node node1 =         {"Node 1.1.0", NULL,    &node2};
static struct kary_Node root =          {"Node 1.0.0", &node1,  &node8};

static kary_NodeHandle pRoot = &root; /* So we can pass a reference to the reference of root in the D'tor */

/* Conforming to the Iterator prototype : void (*fn)(void*) */
void printString(void* string){
  printf("%s\n", (char*)string);
}

int main(void)
{
    /* Test dynamic instantiation */
    kary_insertChild(&node7, kary_createNode("This node is inserted at runtime with RAM memory - Trees can be static or dynamic"));

    /* Test iterator */
    printf("This is the tree you just created like a boss:\n");
    kary_forEach(&root, printString);

    /* Test valid and invalid left sibling */
    assert(kary_getLeftSibling(&root, &node7) == &node2);
    assert(kary_getLeftSibling(&root, &node4) == &node3);
    assert(kary_getLeftSibling(&root, &node1) == NULL);

    /* Test valid and invalid child */
    assert(kary_getChild(&root, &node2) == &node3);
    assert(kary_getChild(&root, &node5) == NULL);

    /* Test valid and invalid right sibling */
    assert(kary_getRightSibling(&root, &node4) == &node5);

    /* Test valid and invalid parent */
    assert(kary_getParent(&root, &node1) == &root);
    assert(kary_getParent(&root, &node6) == &node2);
    assert(kary_getParent(&root, &root) == NULL);

    /* Test node types */
    assert(kary_isLeaf(&node6));
    assert(kary_isLeaf(&node8));
    assert(kary_isLeaf(&node2) == false);

    assert(kary_isLowestLevel(&node1));
    assert(kary_isLowestLevel(&node6));
    assert(kary_isLowestLevel(&root) == false);

    assert(kary_isChildren(&node2, &node5));
    assert(kary_isChildren(&root, &node2));
    assert(kary_isChildren(&node2, &node8) == false);

    /* Test destruction */
    kary_destroy(&pRoot);
    kary_forEach(&root, printString); /* Should output nothing if properly destroyed */

    printf("\nIf I don't get printed you dereferenced a NULL pointer like a moron.\n");
    return EXIT_SUCCESS;
}
share|improve this question

3 Answers 3

up vote 11 down vote accepted

...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:

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.

share|improve this answer
1  
The only thing I might add is that the root parameter is not used in kary_getChild() or kary_getRightSibling(). One could either eliminate the parameter (at the expense of interface consistency) or omit the parameter name (which I would instead advocate) to make it clear to both compiler and human readers that it's deliberately not used. With some compilers, this will be enough to also silence a warning that would otherwise be emitted. –  Edward Jul 24 at 23:25
1  
Also, a note about not putting return 0 at the end of main(): it is common in embedded systems to use void main() (which is legal syntax for non-hosted systems last I looked) so omitting it would also lean toward compatibility with that probability also. In short, another reason it's good advice. –  Edward Jul 24 at 23:28
    
Thanks for the answer. We're using medium sized devices so we are not THAT much limited. Otherwise I couldn't even think about reusable data structures. Your answer gave me lots of insight on how I can improve the tree if I face performance issues. As for the malloc it is overridden so its 99% sure a static global will end up in the Flash but good point this doesn't guarantee anything especially on different compilers. –  Asics Jul 25 at 2:17
1  
@Asics Ahh, I didn't know how small of a device you were using. I tried to give you the best advice on increasing speed without taking away too much functionality that you had already implemented. I'm glad you enjoyed this answer, let me know if you need anything else! –  syb0rg Jul 25 at 2:19

Many of the most important points are are already answered by @syb0rg but I have enough additional detail that I thought it was worth an additional answer. Here's what I've found:

Be aware of ROM versus RAM implications

You have a static tree structure and have said in the description that you'd like for it to be in ROM. However, the way non-const static data is initialized is typically that is is copied from ROM to RAM by the startup code before your main starts to run. That's convenient, and necessary if you're planning on dynamically adding nodes as in this example, but there's a potential problem. When you delete the tree, only the dynamically allocated nodes (in this case just the one) are actually allocated by malloc and will be freed correctly. The rest of the tree which was simply copied by the startup code cannot be reliably de-allocated by a call to free because it was never allocd to begin with.

The simplest fix would be to add a data member bool isDynamic to the node struct that is set to false for ROM-copied member and explicitly set to true from within kary_createNode(). Then everywhere you call free on a node, only actually call free if the flag is set.

Consider a more general iterator

A frequently useful piece of data for use in a tree iterator is the level at which the node is placed within the tree. For that reason, I'd recommend that you change to

typedef void (*kary_Iterator)(void*, int);

So that the second argument can be the node level. An example iterator is then:

void printString(void* string, int level){
  while (level--) printf("\t");
  printf("%s\n", (char*)string);
}

Consider in-order, pre-order and post-order iterators

There are three general ways to walk through all nodes of a tree, but this implementation only implements one. It would be quite simple to modify the code to do each of the the three. For example to print the nodes more nicely, I re-implemented your kary_forEach() as a pre-order traveral:

void kary_forEach(kary_NodeHandle node, kary_Iterator fn, int level)
{
    if(node == NULL){ return; }

    fn(node->data, level);
    if(node->firstKid != NULL)
        kary_forEach(node->firstKid, fn, level+1);
    if(node->nextSibling != NULL)
        kary_forEach(node->nextSibling, fn, level);
}

I used this modified version, calling it like so:

kary_forEach(&root, printString, 0);

And the result looks like this:

Node 1.0.0
    Node 1.1.0
    Node 1.2.0
        Node 1.2.1
        Node 1.2.2
        Node 1.2.3
        Node 1.2.4
    Node 1.3.0
        This node is inserted at runtime with RAM memory - Trees can be static or dynamic
Node 2.0.0

Make sure your comments don't mislead

The code currently includes this very helpful diagram for the static nodes:

/* The tree used for tests goes as follow:
 *
 * -=Root=-
 *  (1.0.0) - (2.0.0)
 *     |
 *  (1.1.0) - (1.2.0) - (1.3.0)
 *               |
 *            (1.2.1) - (1.2.2) - (1.2.3) - (1.2.4)
 */

Unfortunately, it doesn't actually match the code. If you look carefully, you'll see that the 1.2.1 through 1.2.4 series is actually reversed in the code. I fixed it in my local version which is why the tree printed in the previous point actually matches this structure.

Consider what happens when you run out of memory

The code currently contains this:

kary_NodeHandle kary_createNode(void* data)
{
    kary_NodeHandle newNode = malloc(sizeof(struct kary_Node));

    newNode->data = data;
    /* and so on... */
}

However, if the malloc fails, the very next line will assure that you compound the problem by attempting to dereference NULL. Better would be to consider what should happen in the case that malloc fails, and then code appropriately. In embedded systems, there's no single right answer for this.

Be consistent when freeing memory

The code currently contains this function:

void kary_destroy(kary_NodeHandle* root)
{
    destroySubtree(root);
    free(*root);
    *root = NULL;
}

However, the call to destroySubtree already does the same things that the last two lines redundantly do. Best would be to delete those two lines and leave it solely to destroySubtree(). Even better would be to eliminate the kary_destroy() routine since it is functionally identical to the better-named destroySubtree().

share|improve this answer
1  
I was hoping you would take those comments from my answer and put them into your own. +1 –  syb0rg Jul 25 at 4:16
    
Wow these are all simple but highly effective changes to make it more user friendly. Might make the difference between my supervisor going "Meh" or "Nice" during the code review. –  Asics Jul 25 at 12:26
  • Small functions (such as kary_getChild etc) should be declared static inline.

  • Any tree traversal code is greatly simplified if testing for null is delegated to the callee, rather than performed in caller.

Compare:

kary_getNode(kary_NodeHandle root, void * data)
{
    kary_NodeHandle node;
    if (root == NULL) return NULL;
    if (root->data == data) return root;
    if ((node = kary_getNode(root->firstKid, data)) != NULL)
        return node;
    return kary_getNode(root->nextSibling, data);
}

BTW, now a tail recursive call is trivially eliminated:

kary_getNode(kary_NodeHandle root, void * data)
{
    kary_NodeHandle node;
    while (root) {
        if (root->data == data) break;
        if ((node = kary_getNode(root->firstKid, data)) != NULL)
            return node;
        root = root->nextSibling;
    }
    return root;
}

Same exercise is applicable to kary_GetParent and kary_getLeftSibling as well.

  • kary_getParent and kary_getLeftSibling look suspiciously similar. In fact, they are doing the same job, just returning different things. I'd go an extra mile to unify them.
share|improve this answer
    
Thanks I'll look how I can merge the 2 functions. –  Asics Jul 25 at 2:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.