pico_tree.h

00001 /*********************************************************************
00002 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
00003 See LICENSE and COPYING for usage.
00004 
00005 Author: Andrei Carp <andrei.carp@tass.be>
00006 *********************************************************************/
00007 
00008 #ifndef __PICO_RBTREE_H__
00009 #define __PICO_RBTREE_H__
00010 
00011 #include <stdint.h>
00012 #include "pico_config.h"
00013 
00014 // This is used to declare a new tree, leaf root by default
00015 #define PICO_TREE_DECLARE(name,compareFunction) \
00016     struct pico_tree name =\
00017     { \
00018         &LEAF, \
00019         compareFunction \
00020     }
00021 
00022 struct pico_tree_node
00023 {
00024   void* keyValue; // generic key
00025   struct pico_tree_node* parent;
00026   struct pico_tree_node* leftChild;
00027   struct pico_tree_node* rightChild;
00028   uint8_t color;
00029 };
00030 
00031 struct pico_tree
00032 {
00033     struct pico_tree_node * root; // root of the tree
00034 
00035     // this function directly provides the keys as parameters not the nodes.
00036   int (*compare)(void* keyA, void* keyB);
00037 };
00038 
00039 extern struct pico_tree_node LEAF; // generic leaf node
00040 /*
00041  * Manipulation functions
00042  */
00043 void * pico_tree_insert(struct pico_tree * tree, void * key);
00044 void * pico_tree_delete(struct pico_tree * tree, void * key);
00045 void * pico_tree_findKey(struct pico_tree * tree, void * key);
00046 void     pico_tree_drop(struct pico_tree * tree);
00047 int     pico_tree_empty(struct pico_tree * tree);
00048 struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key);
00049 
00050 void * pico_tree_first(struct pico_tree * tree);
00051 void * pico_tree_last(struct pico_tree * tree);
00052 /*
00053  * Traverse functions
00054  */
00055 struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node);
00056 struct pico_tree_node * pico_tree_firstNode(struct pico_tree_node * node);
00057 struct pico_tree_node * pico_tree_next(struct pico_tree_node * node);
00058 struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node);
00059 
00060 /*
00061  * For each macros
00062  */
00063 
00064 #define pico_tree_foreach(idx,tree) \
00065         for ((idx) = pico_tree_firstNode((tree)->root); \
00066              (idx) != &LEAF; \
00067              (idx) = pico_tree_next(idx))
00068 
00069 #define pico_tree_foreach_reverse(idx,tree) \
00070         for ((idx) = pico_tree_lastNode((tree)->root); \
00071              (idx) != &LEAF; \
00072              (idx) = pico_tree_prev(idx))
00073 
00074 #define pico_tree_foreach_safe(idx,tree,idx2) \
00075         for ((idx) = pico_tree_firstNode((tree)->root);    \
00076              ((idx) != &LEAF) && ((idx2) = pico_tree_next(idx), 1); \
00077               (idx) = (idx2))
00078 
00079 #define pico_tree_foreach_reverse_safe(idx,tree,idx2) \
00080         for ((idx) = pico_tree_lastNode((tree)->root); \
00081                 ((idx) != &LEAF) && ((idx2) = pico_tree_prev(idx), 1); \
00082                  (idx) = (idx2))
00083 
00084 #endif