Free (GPLv2) TCP/IP stack developed by TASS Belgium
Fork of PicoTCP by
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?
User | Revision | Line number | New 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 |