Daniele Lacamera / PicoTCP-Experimental_CDC_ECM_Branch

Free (GPLv2) TCP/IP stack developed by TASS Belgium

Fork of PicoTCP by Daniele Lacamera

include/pico_tree.h@51:18637a3d071f, 2013-08-03 (annotated)

Committer:
daniele
Date:
Sat Aug 03 08:50:27 2013 +0000
Revision:
51:18637a3d071f
Parent:
6:55b47464d5bc 
Branch for CDC-ECM: Work in progress

Who changed what in which revision?

UserRevisionLine numberNew contents of line
tass 6:55b47464d5bc 1 /*********************************************************************
tass 6:55b47464d5bc 2 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
tass 6:55b47464d5bc 3 See LICENSE and COPYING for usage.
tass 6:55b47464d5bc 4
tass 6:55b47464d5bc 5 Author: Andrei Carp <andrei.carp@tass.be>
tass 6:55b47464d5bc 6 *********************************************************************/
tass 6:55b47464d5bc 7
tass 6:55b47464d5bc 8 #ifndef __PICO_RBTREE_H__
tass 6:55b47464d5bc 9 #define __PICO_RBTREE_H__
tass 6:55b47464d5bc 10
tass 6:55b47464d5bc 11 #include <stdint.h>
tass 6:55b47464d5bc 12 #include "pico_config.h"
tass 6:55b47464d5bc 13
tass 6:55b47464d5bc 14 // This is used to declare a new tree, leaf root by default
tass 6:55b47464d5bc 15 #define PICO_TREE_DECLARE(name,compareFunction) \
tass 6:55b47464d5bc 16 struct pico_tree name =\
tass 6:55b47464d5bc 17 { \
tass 6:55b47464d5bc 18 &LEAF, \
tass 6:55b47464d5bc 19 compareFunction \
tass 6:55b47464d5bc 20 }
tass 6:55b47464d5bc 21
tass 6:55b47464d5bc 22 struct pico_tree_node
tass 6:55b47464d5bc 23 {
tass 6:55b47464d5bc 24 void* keyValue; // generic key
tass 6:55b47464d5bc 25 struct pico_tree_node* parent;
tass 6:55b47464d5bc 26 struct pico_tree_node* leftChild;
tass 6:55b47464d5bc 27 struct pico_tree_node* rightChild;
tass 6:55b47464d5bc 28 uint8_t color;
tass 6:55b47464d5bc 29 };
tass 6:55b47464d5bc 30
tass 6:55b47464d5bc 31 struct pico_tree
tass 6:55b47464d5bc 32 {
tass 6:55b47464d5bc 33 struct pico_tree_node * root; // root of the tree
tass 6:55b47464d5bc 34
tass 6:55b47464d5bc 35 // this function directly provides the keys as parameters not the nodes.
tass 6:55b47464d5bc 36 int (*compare)(void* keyA, void* keyB);
tass 6:55b47464d5bc 37 };
tass 6:55b47464d5bc 38
tass 6:55b47464d5bc 39 extern struct pico_tree_node LEAF; // generic leaf node
tass 6:55b47464d5bc 40 /*
tass 6:55b47464d5bc 41 * Manipulation functions
tass 6:55b47464d5bc 42 */
tass 6:55b47464d5bc 43 void * pico_tree_insert(struct pico_tree * tree, void * key);
tass 6:55b47464d5bc 44 void * pico_tree_delete(struct pico_tree * tree, void * key);
tass 6:55b47464d5bc 45 void * pico_tree_findKey(struct pico_tree * tree, void * key);
tass 6:55b47464d5bc 46 void pico_tree_drop(struct pico_tree * tree);
tass 6:55b47464d5bc 47 int pico_tree_empty(struct pico_tree * tree);
tass 6:55b47464d5bc 48 struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key);
tass 6:55b47464d5bc 49
tass 6:55b47464d5bc 50 void * pico_tree_first(struct pico_tree * tree);
tass 6:55b47464d5bc 51 void * pico_tree_last(struct pico_tree * tree);
tass 6:55b47464d5bc 52 /*
tass 6:55b47464d5bc 53 * Traverse functions
tass 6:55b47464d5bc 54 */
tass 6:55b47464d5bc 55 struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node);
tass 6:55b47464d5bc 56 struct pico_tree_node * pico_tree_firstNode(struct pico_tree_node * node);
tass 6:55b47464d5bc 57 struct pico_tree_node * pico_tree_next(struct pico_tree_node * node);
tass 6:55b47464d5bc 58 struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node);
tass 6:55b47464d5bc 59
tass 6:55b47464d5bc 60 /*
tass 6:55b47464d5bc 61 * For each macros
tass 6:55b47464d5bc 62 */
tass 6:55b47464d5bc 63
tass 6:55b47464d5bc 64 #define pico_tree_foreach(idx,tree) \
tass 6:55b47464d5bc 65 for ((idx) = pico_tree_firstNode((tree)->root); \
tass 6:55b47464d5bc 66 (idx) != &LEAF; \
tass 6:55b47464d5bc 67 (idx) = pico_tree_next(idx))
tass 6:55b47464d5bc 68
tass 6:55b47464d5bc 69 #define pico_tree_foreach_reverse(idx,tree) \
tass 6:55b47464d5bc 70 for ((idx) = pico_tree_lastNode((tree)->root); \
tass 6:55b47464d5bc 71 (idx) != &LEAF; \
tass 6:55b47464d5bc 72 (idx) = pico_tree_prev(idx))
tass 6:55b47464d5bc 73
tass 6:55b47464d5bc 74 #define pico_tree_foreach_safe(idx,tree,idx2) \
tass 6:55b47464d5bc 75 for ((idx) = pico_tree_firstNode((tree)->root); \
tass 6:55b47464d5bc 76 ((idx) != &LEAF) && ((idx2) = pico_tree_next(idx), 1); \
tass 6:55b47464d5bc 77 (idx) = (idx2))
tass 6:55b47464d5bc 78
tass 6:55b47464d5bc 79 #define pico_tree_foreach_reverse_safe(idx,tree,idx2) \
tass 6:55b47464d5bc 80 for ((idx) = pico_tree_lastNode((tree)->root); \
tass 6:55b47464d5bc 81 ((idx) != &LEAF) && ((idx2) = pico_tree_prev(idx), 1); \
tass 6:55b47464d5bc 82 (idx) = (idx2))
tass 6:55b47464d5bc 83
tass 6:55b47464d5bc 84 #endif