pico_tree.h

00001 /*********************************************************************
00002    PicoTCP. Copyright (c) 2012-2015 Altran Intelligent Systems. 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 "pico_config.h"
00012 
00013 /* This is used to declare a new tree, leaf root by default */
00014 #define PICO_TREE_DECLARE(name, compareFunction) \
00015     struct pico_tree name = \
00016     { \
00017         &LEAF, \
00018         compareFunction \
00019     }
00020 
00021 #define USE_PICO_PAGE0_ZALLOC (1)
00022 #define USE_PICO_ZALLOC (2)
00023 
00024 struct pico_tree_node
00025 {
00026     void*keyValue; /* generic key */
00027     struct pico_tree_node*parent;
00028     struct pico_tree_node*leftChild;
00029     struct pico_tree_node*rightChild;
00030     uint8_t color;
00031 };
00032 
00033 struct pico_tree
00034 {
00035     struct pico_tree_node *root;  /* root of the tree */
00036 
00037     /* this function directly provides the keys as parameters not the nodes. */
00038     int (*compare)(void*keyA, void*keyB);
00039 };
00040 
00041 extern struct pico_tree_node LEAF; /* generic leaf node */
00042 
00043 #ifdef PICO_SUPPORT_MM
00044 void *pico_tree_insert_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
00045 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
00046 #endif
00047 
00048 
00049 /*
00050  * Manipulation functions
00051  */
00052 void *pico_tree_insert(struct pico_tree *tree, void *key);
00053 void *pico_tree_delete(struct pico_tree *tree, void *key);
00054 void *pico_tree_findKey(struct pico_tree *tree, void *key);
00055 void    pico_tree_drop(struct pico_tree *tree);
00056 int     pico_tree_empty(struct pico_tree *tree);
00057 struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key);
00058 
00059 void *pico_tree_first(struct pico_tree *tree);
00060 void *pico_tree_last(struct pico_tree *tree);
00061 /*
00062  * Traverse functions
00063  */
00064 struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node);
00065 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node);
00066 struct pico_tree_node *pico_tree_next(struct pico_tree_node *node);
00067 struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node);
00068 
00069 /*
00070  * For each macros
00071  */
00072 
00073 #define pico_tree_foreach(idx, tree) \
00074     for ((idx) = pico_tree_firstNode((tree)->root); \
00075          (idx) != &LEAF; \
00076          (idx) = pico_tree_next(idx))
00077 
00078 #define pico_tree_foreach_reverse(idx, tree) \
00079     for ((idx) = pico_tree_lastNode((tree)->root); \
00080          (idx) != &LEAF; \
00081          (idx) = pico_tree_prev(idx))
00082 
00083 #define pico_tree_foreach_safe(idx, tree, idx2) \
00084     for ((idx) = pico_tree_firstNode((tree)->root); \
00085          ((idx) != &LEAF) && ((idx2) = pico_tree_next(idx), 1); \
00086          (idx) = (idx2))
00087 
00088 #define pico_tree_foreach_reverse_safe(idx, tree, idx2) \
00089     for ((idx) = pico_tree_lastNode((tree)->root); \
00090          ((idx) != &LEAF) && ((idx2) = pico_tree_prev(idx), 1); \
00091          (idx) = (idx2))
00092 
00093 #endif