Red black Trees

Binary balanced Red-Black trees are provided using picoTCP’s own implementation. This is a very efficient structure to store data in a certain order, searching for a specific instance and removing items from it. For this reason, pico_tree is a widely used structure within picoTCP modules, so there are many examples of the usage of this tool for storing items of different types and using different ordering.
Creating a tree consists first of all in identifying the type that will be stored in each node, and providing a compare function. Nodes are generic objects that keep track of specific key values, so that the key value in a pico_tree_node can always be accessed using the keyValue pointer field. The custom compare function must return a value in the style of strcmp, that is, returning zero when the two objects are the same, a negative value when the first object should come before the second one in the order, and a positive value otherwise.
For instance, when comparing two objects of type “uint16_t” which need to be stored in an increasing order, the compare function may look like the following:

int u_compare(void *_a, void *_b) {
    uint16_t *a = (uint16_t *)_a;
    uint16_t *b = (uint16_t *)_b;
    if (*a == *b)
        return 0;
    else return (b - a);
}

Once the compare function has been defined, an empty tree can be initialized via the macro PICO_TREE_DECLARE. The first argument is the name of the tree that can be referenced by other functions later on, the second argument is in fact the compare function previously defined. From this moment on, the tree can be accessed via the API functions:

• pico_tree_insert - insert a new element in the tree, respecting the order
• pico_tree_delete - remove the given element from the tree
• pico_tree_findKey - given a sample element (which must work with your compare function) find an occurrence of an identical node in the tree
• pico_tree_drop - empty a tree by removing all its nodes
• pico_tree_empty - check if the tree is currently empty

And the following iterator macros, able to provide a loop over all the elements in a tree:

• pico_tree_foreach
• pico_tree_foreach_reverse
• pico_tree_foreach_safe
• pico_tree_foreach_reverse_safe

Respectively used to visit all the nodes in a tree in their natural order, in their reverse order, in the natural order allowing deletions along the path, and in the reverse order allowing deletions. The “safe” version of the two iterators require an additional temporary pico_tree_node argument, but will allow to call pico_tree_delete without any side effects to the iterator itself. While the non-safe versions are faster and easier to use, consider using the safe version of the macros every time your code foresees a deletion within the loop.