Free (GPLv2) TCP/IP stack developed by TASS Belgium
Dependents: lpc1768-picotcp-demo ZeroMQ_PicoTCP_Publisher_demo TCPSocket_HelloWorld_PicoTCP Pico_TCP_UDP_Test ... more
PicoTCP. Copyright (c) 2013 TASS Belgium NV.
Released under the GNU General Public License, version 2.
Different licensing models may exist, at the sole discretion of the Copyright holders.
Official homepage: http://www.picotcp.com
Bug tracker: https://github.com/tass-belgium/picotcp/issues
Development steps:
initial integration with mbed RTOSgeneric mbed Ethernet driverhigh performance NXP LPC1768 specific Ethernet driverMulti-threading support for mbed RTOSBerkeley sockets and integration with the New Socket APIFork of the apps running on top of the New Socket APIScheduling optimizations- Debugging/benchmarking/testing
Demo application (measuring TCP sender performance):
Import programlpc1768-picotcp-demo
A PicoTCP demo app testing the ethernet throughput on the lpc1768 mbed board.
stack/pico_tree.c@131:4758606c9316, 2013-12-16 (annotated)
- Committer:
- TASS Belgium NV
- Date:
- Mon Dec 16 11:25:54 2013 +0100
- Revision:
- 131:4758606c9316
- Parent:
- 68:0847e35d08a6
- Child:
- 149:5f4cb161cec3
Syncronized with master branch
Who changed what in which revision?
User | Revision | Line number | New contents of line |
---|---|---|---|
tass | 68:0847e35d08a6 | 1 | /********************************************************************* |
TASS Belgium NV |
131:4758606c9316 | 2 | PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved. |
TASS Belgium NV |
131:4758606c9316 | 3 | See LICENSE and COPYING for usage. |
tass | 68:0847e35d08a6 | 4 | |
TASS Belgium NV |
131:4758606c9316 | 5 | Author: Andrei Carp <andrei.carp@tass.be> |
TASS Belgium NV |
131:4758606c9316 | 6 | *********************************************************************/ |
tass | 68:0847e35d08a6 | 7 | |
tass | 68:0847e35d08a6 | 8 | #include "pico_tree.h" |
tass | 68:0847e35d08a6 | 9 | #include "pico_config.h" |
tass | 68:0847e35d08a6 | 10 | #include "pico_protocol.h" |
tass | 68:0847e35d08a6 | 11 | |
TASS Belgium NV |
131:4758606c9316 | 12 | #define RED 0 |
tass | 68:0847e35d08a6 | 13 | #define BLACK 1 |
tass | 68:0847e35d08a6 | 14 | |
TASS Belgium NV |
131:4758606c9316 | 15 | /* By default the null leafs are black */ |
tass | 68:0847e35d08a6 | 16 | struct pico_tree_node LEAF = { |
TASS Belgium NV |
131:4758606c9316 | 17 | NULL, /* key */ |
TASS Belgium NV |
131:4758606c9316 | 18 | &LEAF, &LEAF, &LEAF, /* parent, left,right */ |
TASS Belgium NV |
131:4758606c9316 | 19 | BLACK, /* color */ |
tass | 68:0847e35d08a6 | 20 | }; |
tass | 68:0847e35d08a6 | 21 | |
tass | 68:0847e35d08a6 | 22 | #define IS_LEAF(x) (x == &LEAF) |
tass | 68:0847e35d08a6 | 23 | #define IS_NOT_LEAF(x) (x != &LEAF) |
tass | 68:0847e35d08a6 | 24 | #define INIT_LEAF (&LEAF) |
tass | 68:0847e35d08a6 | 25 | |
tass | 68:0847e35d08a6 | 26 | #define AM_I_LEFT_CHILD(x) (x == x->parent->leftChild) |
tass | 68:0847e35d08a6 | 27 | #define AM_I_RIGHT_CHILD(x) (x == x->parent->rightChild) |
tass | 68:0847e35d08a6 | 28 | |
tass | 68:0847e35d08a6 | 29 | #define PARENT(x) (x->parent) |
tass | 68:0847e35d08a6 | 30 | #define GRANPA(x) (x->parent->parent) |
tass | 68:0847e35d08a6 | 31 | |
tass | 68:0847e35d08a6 | 32 | /* |
tass | 68:0847e35d08a6 | 33 | * Local Functions |
tass | 68:0847e35d08a6 | 34 | */ |
TASS Belgium NV |
131:4758606c9316 | 35 | static struct pico_tree_node *create_node(struct pico_tree *tree, void *key); |
TASS Belgium NV |
131:4758606c9316 | 36 | static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node); |
TASS Belgium NV |
131:4758606c9316 | 37 | static void rotateToRight(struct pico_tree*root, struct pico_tree_node*node); |
TASS Belgium NV |
131:4758606c9316 | 38 | static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node); |
TASS Belgium NV |
131:4758606c9316 | 39 | static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node); |
TASS Belgium NV |
131:4758606c9316 | 40 | static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB); |
tass | 68:0847e35d08a6 | 41 | |
tass | 68:0847e35d08a6 | 42 | /* |
tass | 68:0847e35d08a6 | 43 | * Exported functions |
tass | 68:0847e35d08a6 | 44 | */ |
tass | 68:0847e35d08a6 | 45 | |
TASS Belgium NV |
131:4758606c9316 | 46 | struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 47 | { |
TASS Belgium NV |
131:4758606c9316 | 48 | while(IS_NOT_LEAF(node->leftChild)) |
TASS Belgium NV |
131:4758606c9316 | 49 | node = node->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 50 | return node; |
tass | 68:0847e35d08a6 | 51 | } |
tass | 68:0847e35d08a6 | 52 | |
TASS Belgium NV |
131:4758606c9316 | 53 | struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 54 | { |
TASS Belgium NV |
131:4758606c9316 | 55 | while(IS_NOT_LEAF(node->rightChild)) |
TASS Belgium NV |
131:4758606c9316 | 56 | node = node->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 57 | return node; |
tass | 68:0847e35d08a6 | 58 | } |
tass | 68:0847e35d08a6 | 59 | |
TASS Belgium NV |
131:4758606c9316 | 60 | struct pico_tree_node *pico_tree_next(struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 61 | { |
TASS Belgium NV |
131:4758606c9316 | 62 | if(IS_NOT_LEAF(node->rightChild)) |
TASS Belgium NV |
131:4758606c9316 | 63 | { |
TASS Belgium NV |
131:4758606c9316 | 64 | node = node->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 65 | while(IS_NOT_LEAF(node->leftChild)) |
TASS Belgium NV |
131:4758606c9316 | 66 | node = node->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 67 | } |
TASS Belgium NV |
131:4758606c9316 | 68 | else |
TASS Belgium NV |
131:4758606c9316 | 69 | { |
TASS Belgium NV |
131:4758606c9316 | 70 | if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node)) |
TASS Belgium NV |
131:4758606c9316 | 71 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 72 | else { |
TASS Belgium NV |
131:4758606c9316 | 73 | while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) |
TASS Belgium NV |
131:4758606c9316 | 74 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 75 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 76 | } |
TASS Belgium NV |
131:4758606c9316 | 77 | } |
tass | 68:0847e35d08a6 | 78 | |
TASS Belgium NV |
131:4758606c9316 | 79 | return node; |
tass | 68:0847e35d08a6 | 80 | } |
tass | 68:0847e35d08a6 | 81 | |
TASS Belgium NV |
131:4758606c9316 | 82 | struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 83 | { |
TASS Belgium NV |
131:4758606c9316 | 84 | if (IS_NOT_LEAF(node->leftChild)) { |
TASS Belgium NV |
131:4758606c9316 | 85 | node = node->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 86 | while (IS_NOT_LEAF(node->rightChild)) |
TASS Belgium NV |
131:4758606c9316 | 87 | node = node->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 88 | } else { |
TASS Belgium NV |
131:4758606c9316 | 89 | if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) |
TASS Belgium NV |
131:4758606c9316 | 90 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 91 | else { |
TASS Belgium NV |
131:4758606c9316 | 92 | while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node)) |
TASS Belgium NV |
131:4758606c9316 | 93 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 94 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 95 | } |
TASS Belgium NV |
131:4758606c9316 | 96 | } |
tass | 68:0847e35d08a6 | 97 | |
TASS Belgium NV |
131:4758606c9316 | 98 | return node; |
tass | 68:0847e35d08a6 | 99 | } |
tass | 68:0847e35d08a6 | 100 | |
TASS Belgium NV |
131:4758606c9316 | 101 | void *pico_tree_insert(struct pico_tree*tree, void *key) |
TASS Belgium NV |
131:4758606c9316 | 102 | { |
tass | 68:0847e35d08a6 | 103 | |
TASS Belgium NV |
131:4758606c9316 | 104 | struct pico_tree_node *last_node = INIT_LEAF; |
TASS Belgium NV |
131:4758606c9316 | 105 | struct pico_tree_node *temp = tree->root; |
TASS Belgium NV |
131:4758606c9316 | 106 | struct pico_tree_node *insert; |
TASS Belgium NV |
131:4758606c9316 | 107 | void *LocalKey; |
TASS Belgium NV |
131:4758606c9316 | 108 | int result = 0; |
tass | 68:0847e35d08a6 | 109 | |
TASS Belgium NV |
131:4758606c9316 | 110 | LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree, key) : NULL); |
TASS Belgium NV |
131:4758606c9316 | 111 | /* if node already in, bail out */ |
TASS Belgium NV |
131:4758606c9316 | 112 | if(LocalKey) |
TASS Belgium NV |
131:4758606c9316 | 113 | return LocalKey; |
TASS Belgium NV |
131:4758606c9316 | 114 | else |
TASS Belgium NV |
131:4758606c9316 | 115 | { |
TASS Belgium NV |
131:4758606c9316 | 116 | insert = create_node(tree, key); |
TASS Belgium NV |
131:4758606c9316 | 117 | if(!insert) |
TASS Belgium NV |
131:4758606c9316 | 118 | { |
TASS Belgium NV |
131:4758606c9316 | 119 | pico_err = PICO_ERR_ENOMEM; |
TASS Belgium NV |
131:4758606c9316 | 120 | /* to let the user know that it couldn't insert */ |
TASS Belgium NV |
131:4758606c9316 | 121 | return (void *)&LEAF; |
TASS Belgium NV |
131:4758606c9316 | 122 | } |
TASS Belgium NV |
131:4758606c9316 | 123 | } |
tass | 68:0847e35d08a6 | 124 | |
TASS Belgium NV |
131:4758606c9316 | 125 | /* search for the place to insert the new node */ |
TASS Belgium NV |
131:4758606c9316 | 126 | while(IS_NOT_LEAF(temp)) |
TASS Belgium NV |
131:4758606c9316 | 127 | { |
TASS Belgium NV |
131:4758606c9316 | 128 | last_node = temp; |
TASS Belgium NV |
131:4758606c9316 | 129 | result = tree->compare(insert->keyValue, temp->keyValue); |
tass | 68:0847e35d08a6 | 130 | |
TASS Belgium NV |
131:4758606c9316 | 131 | temp = (result < 0 ? temp->leftChild : temp->rightChild); |
TASS Belgium NV |
131:4758606c9316 | 132 | } |
TASS Belgium NV |
131:4758606c9316 | 133 | /* make the needed connections */ |
TASS Belgium NV |
131:4758606c9316 | 134 | insert->parent = last_node; |
tass | 68:0847e35d08a6 | 135 | |
TASS Belgium NV |
131:4758606c9316 | 136 | if(IS_LEAF(last_node)) |
TASS Belgium NV |
131:4758606c9316 | 137 | tree->root = insert; |
TASS Belgium NV |
131:4758606c9316 | 138 | else{ |
TASS Belgium NV |
131:4758606c9316 | 139 | result = tree->compare(insert->keyValue, last_node->keyValue); |
TASS Belgium NV |
131:4758606c9316 | 140 | if(result < 0) |
TASS Belgium NV |
131:4758606c9316 | 141 | last_node->leftChild = insert; |
TASS Belgium NV |
131:4758606c9316 | 142 | else |
TASS Belgium NV |
131:4758606c9316 | 143 | last_node->rightChild = insert; |
TASS Belgium NV |
131:4758606c9316 | 144 | } |
tass | 68:0847e35d08a6 | 145 | |
TASS Belgium NV |
131:4758606c9316 | 146 | /* fix colour issues */ |
TASS Belgium NV |
131:4758606c9316 | 147 | fix_insert_collisions(tree, insert); |
tass | 68:0847e35d08a6 | 148 | |
TASS Belgium NV |
131:4758606c9316 | 149 | return NULL; |
tass | 68:0847e35d08a6 | 150 | } |
tass | 68:0847e35d08a6 | 151 | |
TASS Belgium NV |
131:4758606c9316 | 152 | struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key) |
tass | 68:0847e35d08a6 | 153 | { |
TASS Belgium NV |
131:4758606c9316 | 154 | struct pico_tree_node *found; |
tass | 68:0847e35d08a6 | 155 | |
TASS Belgium NV |
131:4758606c9316 | 156 | found = tree->root; |
tass | 68:0847e35d08a6 | 157 | |
TASS Belgium NV |
131:4758606c9316 | 158 | while(IS_NOT_LEAF(found)) |
TASS Belgium NV |
131:4758606c9316 | 159 | { |
TASS Belgium NV |
131:4758606c9316 | 160 | int result; |
TASS Belgium NV |
131:4758606c9316 | 161 | result = tree->compare(found->keyValue, key); |
TASS Belgium NV |
131:4758606c9316 | 162 | if(result == 0) |
TASS Belgium NV |
131:4758606c9316 | 163 | { |
TASS Belgium NV |
131:4758606c9316 | 164 | return found; |
TASS Belgium NV |
131:4758606c9316 | 165 | } |
TASS Belgium NV |
131:4758606c9316 | 166 | else if(result < 0) |
TASS Belgium NV |
131:4758606c9316 | 167 | found = found->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 168 | else |
TASS Belgium NV |
131:4758606c9316 | 169 | found = found->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 170 | } |
TASS Belgium NV |
131:4758606c9316 | 171 | return NULL; |
tass | 68:0847e35d08a6 | 172 | } |
tass | 68:0847e35d08a6 | 173 | |
TASS Belgium NV |
131:4758606c9316 | 174 | void *pico_tree_findKey(struct pico_tree *tree, void *key) |
tass | 68:0847e35d08a6 | 175 | { |
TASS Belgium NV |
131:4758606c9316 | 176 | struct pico_tree_node *found; |
tass | 68:0847e35d08a6 | 177 | |
tass | 68:0847e35d08a6 | 178 | |
TASS Belgium NV |
131:4758606c9316 | 179 | found = tree->root; |
tass | 68:0847e35d08a6 | 180 | |
TASS Belgium NV |
131:4758606c9316 | 181 | while(IS_NOT_LEAF(found)) |
TASS Belgium NV |
131:4758606c9316 | 182 | { |
TASS Belgium NV |
131:4758606c9316 | 183 | int result; |
tass | 68:0847e35d08a6 | 184 | |
TASS Belgium NV |
131:4758606c9316 | 185 | result = tree->compare(found->keyValue, key); |
TASS Belgium NV |
131:4758606c9316 | 186 | if(result == 0) |
TASS Belgium NV |
131:4758606c9316 | 187 | return found->keyValue; |
TASS Belgium NV |
131:4758606c9316 | 188 | else if(result < 0) |
TASS Belgium NV |
131:4758606c9316 | 189 | found = found->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 190 | else |
TASS Belgium NV |
131:4758606c9316 | 191 | found = found->leftChild; |
tass | 68:0847e35d08a6 | 192 | |
TASS Belgium NV |
131:4758606c9316 | 193 | } |
TASS Belgium NV |
131:4758606c9316 | 194 | return NULL; |
tass | 68:0847e35d08a6 | 195 | } |
tass | 68:0847e35d08a6 | 196 | |
TASS Belgium NV |
131:4758606c9316 | 197 | void *pico_tree_first(struct pico_tree *tree) |
tass | 68:0847e35d08a6 | 198 | { |
TASS Belgium NV |
131:4758606c9316 | 199 | return pico_tree_firstNode(tree->root)->keyValue; |
tass | 68:0847e35d08a6 | 200 | } |
tass | 68:0847e35d08a6 | 201 | |
TASS Belgium NV |
131:4758606c9316 | 202 | void *pico_tree_last(struct pico_tree *tree) |
tass | 68:0847e35d08a6 | 203 | { |
TASS Belgium NV |
131:4758606c9316 | 204 | return pico_tree_lastNode(tree->root)->keyValue; |
tass | 68:0847e35d08a6 | 205 | } |
tass | 68:0847e35d08a6 | 206 | |
TASS Belgium NV |
131:4758606c9316 | 207 | void *pico_tree_delete(struct pico_tree *tree, void *key) |
TASS Belgium NV |
131:4758606c9316 | 208 | { |
tass | 68:0847e35d08a6 | 209 | |
TASS Belgium NV |
131:4758606c9316 | 210 | uint8_t nodeColor; /* keeps the color of the node to be deleted */ |
TASS Belgium NV |
131:4758606c9316 | 211 | void *lkey; /* keeps a copy of the key which will be removed */ |
TASS Belgium NV |
131:4758606c9316 | 212 | struct pico_tree_node *delete; /* keeps a copy of the node to be extracted */ |
TASS Belgium NV |
131:4758606c9316 | 213 | struct pico_tree_node *temp; /* temporary */ |
TASS Belgium NV |
131:4758606c9316 | 214 | struct pico_tree_node *ltemp; /* used for switching nodes, as a copy */ |
tass | 68:0847e35d08a6 | 215 | |
TASS Belgium NV |
131:4758606c9316 | 216 | delete = pico_tree_findNode(tree, key); |
TASS Belgium NV |
131:4758606c9316 | 217 | ltemp = delete; |
tass | 68:0847e35d08a6 | 218 | |
TASS Belgium NV |
131:4758606c9316 | 219 | /* this key isn't in the tree, bail out */ |
TASS Belgium NV |
131:4758606c9316 | 220 | if(!delete) |
TASS Belgium NV |
131:4758606c9316 | 221 | return NULL; |
tass | 68:0847e35d08a6 | 222 | |
TASS Belgium NV |
131:4758606c9316 | 223 | lkey = delete->keyValue; |
TASS Belgium NV |
131:4758606c9316 | 224 | nodeColor = delete->color; |
tass | 68:0847e35d08a6 | 225 | |
TASS Belgium NV |
131:4758606c9316 | 226 | if(IS_LEAF(delete->leftChild)) |
TASS Belgium NV |
131:4758606c9316 | 227 | { |
TASS Belgium NV |
131:4758606c9316 | 228 | temp = ltemp->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 229 | switchNodes(tree, ltemp, ltemp->rightChild); |
TASS Belgium NV |
131:4758606c9316 | 230 | } |
TASS Belgium NV |
131:4758606c9316 | 231 | else |
tass | 68:0847e35d08a6 | 232 | if(IS_LEAF(delete->rightChild)) |
tass | 68:0847e35d08a6 | 233 | { |
TASS Belgium NV |
131:4758606c9316 | 234 | struct pico_tree_node *_ltemp = delete; |
TASS Belgium NV |
131:4758606c9316 | 235 | temp = _ltemp->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 236 | switchNodes(tree, _ltemp, _ltemp->leftChild); |
tass | 68:0847e35d08a6 | 237 | } |
tass | 68:0847e35d08a6 | 238 | else{ |
TASS Belgium NV |
131:4758606c9316 | 239 | struct pico_tree_node *min; |
TASS Belgium NV |
131:4758606c9316 | 240 | min = pico_tree_firstNode(delete->rightChild); |
TASS Belgium NV |
131:4758606c9316 | 241 | nodeColor = min->color; |
tass | 68:0847e35d08a6 | 242 | |
TASS Belgium NV |
131:4758606c9316 | 243 | temp = min->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 244 | if(min->parent == ltemp && IS_NOT_LEAF(temp)) |
TASS Belgium NV |
131:4758606c9316 | 245 | temp->parent = min; |
TASS Belgium NV |
131:4758606c9316 | 246 | else{ |
TASS Belgium NV |
131:4758606c9316 | 247 | switchNodes(tree, min, min->rightChild); |
TASS Belgium NV |
131:4758606c9316 | 248 | min->rightChild = ltemp->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 249 | if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min; |
TASS Belgium NV |
131:4758606c9316 | 250 | } |
TASS Belgium NV |
131:4758606c9316 | 251 | |
TASS Belgium NV |
131:4758606c9316 | 252 | switchNodes(tree, ltemp, min); |
TASS Belgium NV |
131:4758606c9316 | 253 | min->leftChild = ltemp->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 254 | if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min; |
TASS Belgium NV |
131:4758606c9316 | 255 | |
TASS Belgium NV |
131:4758606c9316 | 256 | min->color = ltemp->color; |
tass | 68:0847e35d08a6 | 257 | } |
tass | 68:0847e35d08a6 | 258 | |
TASS Belgium NV |
131:4758606c9316 | 259 | /* deleted node is black, this will mess up the black path property */ |
TASS Belgium NV |
131:4758606c9316 | 260 | if(nodeColor == BLACK) |
TASS Belgium NV |
131:4758606c9316 | 261 | fix_delete_collisions(tree, temp); |
tass | 68:0847e35d08a6 | 262 | |
TASS Belgium NV |
131:4758606c9316 | 263 | pico_free(delete); |
tass | 68:0847e35d08a6 | 264 | |
TASS Belgium NV |
131:4758606c9316 | 265 | return lkey; |
tass | 68:0847e35d08a6 | 266 | } |
tass | 68:0847e35d08a6 | 267 | |
TASS Belgium NV |
131:4758606c9316 | 268 | int pico_tree_empty(struct pico_tree *tree) |
tass | 68:0847e35d08a6 | 269 | { |
TASS Belgium NV |
131:4758606c9316 | 270 | return (!tree->root || IS_LEAF(tree->root)); |
tass | 68:0847e35d08a6 | 271 | } |
tass | 68:0847e35d08a6 | 272 | |
tass | 68:0847e35d08a6 | 273 | /* |
tass | 68:0847e35d08a6 | 274 | * Private functions |
tass | 68:0847e35d08a6 | 275 | */ |
TASS Belgium NV |
131:4758606c9316 | 276 | static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node) |
tass | 68:0847e35d08a6 | 277 | { |
TASS Belgium NV |
131:4758606c9316 | 278 | struct pico_tree_node*temp; |
tass | 68:0847e35d08a6 | 279 | |
TASS Belgium NV |
131:4758606c9316 | 280 | temp = node->rightChild; |
tass | 68:0847e35d08a6 | 281 | |
TASS Belgium NV |
131:4758606c9316 | 282 | if(temp == &LEAF) return; |
tass | 68:0847e35d08a6 | 283 | |
TASS Belgium NV |
131:4758606c9316 | 284 | node->rightChild = temp->leftChild; |
tass | 68:0847e35d08a6 | 285 | |
TASS Belgium NV |
131:4758606c9316 | 286 | if(IS_NOT_LEAF(temp->leftChild)) |
TASS Belgium NV |
131:4758606c9316 | 287 | temp->leftChild->parent = node; |
tass | 68:0847e35d08a6 | 288 | |
TASS Belgium NV |
131:4758606c9316 | 289 | temp->parent = node->parent; |
tass | 68:0847e35d08a6 | 290 | |
TASS Belgium NV |
131:4758606c9316 | 291 | if(IS_LEAF(node->parent)) |
TASS Belgium NV |
131:4758606c9316 | 292 | tree->root = temp; |
TASS Belgium NV |
131:4758606c9316 | 293 | else |
tass | 68:0847e35d08a6 | 294 | if(node == node->parent->leftChild) |
TASS Belgium NV |
131:4758606c9316 | 295 | node->parent->leftChild = temp; |
tass | 68:0847e35d08a6 | 296 | else |
TASS Belgium NV |
131:4758606c9316 | 297 | node->parent->rightChild = temp; |
tass | 68:0847e35d08a6 | 298 | |
TASS Belgium NV |
131:4758606c9316 | 299 | temp->leftChild = node; |
TASS Belgium NV |
131:4758606c9316 | 300 | node->parent = temp; |
tass | 68:0847e35d08a6 | 301 | } |
tass | 68:0847e35d08a6 | 302 | |
tass | 68:0847e35d08a6 | 303 | |
TASS Belgium NV |
131:4758606c9316 | 304 | static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 305 | { |
TASS Belgium NV |
131:4758606c9316 | 306 | struct pico_tree_node*temp; |
tass | 68:0847e35d08a6 | 307 | |
TASS Belgium NV |
131:4758606c9316 | 308 | temp = node->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 309 | node->leftChild = temp->rightChild; |
tass | 68:0847e35d08a6 | 310 | |
TASS Belgium NV |
131:4758606c9316 | 311 | if(temp == &LEAF) return; |
tass | 68:0847e35d08a6 | 312 | |
TASS Belgium NV |
131:4758606c9316 | 313 | if(IS_NOT_LEAF(temp->rightChild)) |
TASS Belgium NV |
131:4758606c9316 | 314 | temp->rightChild->parent = node; |
tass | 68:0847e35d08a6 | 315 | |
TASS Belgium NV |
131:4758606c9316 | 316 | temp->parent = node->parent; |
tass | 68:0847e35d08a6 | 317 | |
TASS Belgium NV |
131:4758606c9316 | 318 | if(IS_LEAF(node->parent)) |
TASS Belgium NV |
131:4758606c9316 | 319 | tree->root = temp; |
TASS Belgium NV |
131:4758606c9316 | 320 | else |
tass | 68:0847e35d08a6 | 321 | if(node == node->parent->rightChild) |
TASS Belgium NV |
131:4758606c9316 | 322 | node->parent->rightChild = temp; |
tass | 68:0847e35d08a6 | 323 | else |
TASS Belgium NV |
131:4758606c9316 | 324 | node->parent->leftChild = temp; |
tass | 68:0847e35d08a6 | 325 | |
TASS Belgium NV |
131:4758606c9316 | 326 | temp->rightChild = node; |
TASS Belgium NV |
131:4758606c9316 | 327 | node->parent = temp; |
TASS Belgium NV |
131:4758606c9316 | 328 | return; |
tass | 68:0847e35d08a6 | 329 | } |
tass | 68:0847e35d08a6 | 330 | |
TASS Belgium NV |
131:4758606c9316 | 331 | static struct pico_tree_node *create_node(struct pico_tree *tree, void*key) |
tass | 68:0847e35d08a6 | 332 | { |
TASS Belgium NV |
131:4758606c9316 | 333 | struct pico_tree_node *temp; |
TASS Belgium NV |
131:4758606c9316 | 334 | IGNORE_PARAMETER(tree); |
TASS Belgium NV |
131:4758606c9316 | 335 | temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node)); |
tass | 68:0847e35d08a6 | 336 | |
TASS Belgium NV |
131:4758606c9316 | 337 | if(!temp) |
TASS Belgium NV |
131:4758606c9316 | 338 | return NULL; |
tass | 68:0847e35d08a6 | 339 | |
TASS Belgium NV |
131:4758606c9316 | 340 | temp->keyValue = key; |
TASS Belgium NV |
131:4758606c9316 | 341 | temp->parent = &LEAF; |
TASS Belgium NV |
131:4758606c9316 | 342 | temp->leftChild = &LEAF; |
TASS Belgium NV |
131:4758606c9316 | 343 | temp->rightChild = &LEAF; |
TASS Belgium NV |
131:4758606c9316 | 344 | /* by default every new node is red */ |
TASS Belgium NV |
131:4758606c9316 | 345 | temp->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 346 | return temp; |
tass | 68:0847e35d08a6 | 347 | } |
tass | 68:0847e35d08a6 | 348 | |
tass | 68:0847e35d08a6 | 349 | /* |
tass | 68:0847e35d08a6 | 350 | * This function fixes the possible collisions in the tree. |
tass | 68:0847e35d08a6 | 351 | * Eg. if a node is red his children must be black ! |
tass | 68:0847e35d08a6 | 352 | */ |
TASS Belgium NV |
131:4758606c9316 | 353 | static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node) |
tass | 68:0847e35d08a6 | 354 | { |
TASS Belgium NV |
131:4758606c9316 | 355 | struct pico_tree_node*temp; |
TASS Belgium NV |
131:4758606c9316 | 356 | |
TASS Belgium NV |
131:4758606c9316 | 357 | while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node))) |
TASS Belgium NV |
131:4758606c9316 | 358 | { |
TASS Belgium NV |
131:4758606c9316 | 359 | if(AM_I_RIGHT_CHILD(node->parent)) |
TASS Belgium NV |
131:4758606c9316 | 360 | { |
TASS Belgium NV |
131:4758606c9316 | 361 | temp = GRANPA(node)->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 362 | if(temp->color == RED) { |
TASS Belgium NV |
131:4758606c9316 | 363 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 364 | temp->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 365 | GRANPA(node)->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 366 | node = GRANPA(node); |
TASS Belgium NV |
131:4758606c9316 | 367 | } |
TASS Belgium NV |
131:4758606c9316 | 368 | else if(temp->color == BLACK) { |
TASS Belgium NV |
131:4758606c9316 | 369 | if(node == node->parent->leftChild) { |
TASS Belgium NV |
131:4758606c9316 | 370 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 371 | rotateToRight(tree, node); |
TASS Belgium NV |
131:4758606c9316 | 372 | } |
tass | 68:0847e35d08a6 | 373 | |
TASS Belgium NV |
131:4758606c9316 | 374 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 375 | GRANPA(node)->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 376 | rotateToLeft(tree, GRANPA(node)); |
TASS Belgium NV |
131:4758606c9316 | 377 | } |
TASS Belgium NV |
131:4758606c9316 | 378 | } |
TASS Belgium NV |
131:4758606c9316 | 379 | else if(AM_I_LEFT_CHILD(node->parent)) |
TASS Belgium NV |
131:4758606c9316 | 380 | { |
TASS Belgium NV |
131:4758606c9316 | 381 | temp = GRANPA(node)->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 382 | if(temp->color == RED) { |
TASS Belgium NV |
131:4758606c9316 | 383 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 384 | temp->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 385 | GRANPA(node)->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 386 | node = GRANPA(node); |
TASS Belgium NV |
131:4758606c9316 | 387 | } |
TASS Belgium NV |
131:4758606c9316 | 388 | else if(temp->color == BLACK) { |
TASS Belgium NV |
131:4758606c9316 | 389 | if(AM_I_RIGHT_CHILD(node)) { |
TASS Belgium NV |
131:4758606c9316 | 390 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 391 | rotateToLeft(tree, node); |
TASS Belgium NV |
131:4758606c9316 | 392 | } |
TASS Belgium NV |
131:4758606c9316 | 393 | |
TASS Belgium NV |
131:4758606c9316 | 394 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 395 | GRANPA(node)->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 396 | rotateToRight(tree, GRANPA(node)); |
TASS Belgium NV |
131:4758606c9316 | 397 | } |
TASS Belgium NV |
131:4758606c9316 | 398 | } |
tass | 68:0847e35d08a6 | 399 | } |
TASS Belgium NV |
131:4758606c9316 | 400 | /* make sure that the root of the tree stays black */ |
TASS Belgium NV |
131:4758606c9316 | 401 | tree->root->color = BLACK; |
tass | 68:0847e35d08a6 | 402 | } |
tass | 68:0847e35d08a6 | 403 | |
TASS Belgium NV |
131:4758606c9316 | 404 | static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB) |
tass | 68:0847e35d08a6 | 405 | { |
tass | 68:0847e35d08a6 | 406 | |
TASS Belgium NV |
131:4758606c9316 | 407 | if(IS_LEAF(nodeA->parent)) |
TASS Belgium NV |
131:4758606c9316 | 408 | tree->root = nodeB; |
tass | 68:0847e35d08a6 | 409 | else |
TASS Belgium NV |
131:4758606c9316 | 410 | if(IS_NOT_LEAF(nodeA)) |
TASS Belgium NV |
131:4758606c9316 | 411 | { |
TASS Belgium NV |
131:4758606c9316 | 412 | if(AM_I_LEFT_CHILD(nodeA)) |
TASS Belgium NV |
131:4758606c9316 | 413 | nodeA->parent->leftChild = nodeB; |
TASS Belgium NV |
131:4758606c9316 | 414 | else |
TASS Belgium NV |
131:4758606c9316 | 415 | nodeA->parent->rightChild = nodeB; |
TASS Belgium NV |
131:4758606c9316 | 416 | } |
tass | 68:0847e35d08a6 | 417 | |
TASS Belgium NV |
131:4758606c9316 | 418 | if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent; |
tass | 68:0847e35d08a6 | 419 | |
tass | 68:0847e35d08a6 | 420 | } |
tass | 68:0847e35d08a6 | 421 | |
tass | 68:0847e35d08a6 | 422 | /* |
tass | 68:0847e35d08a6 | 423 | * This function fixes the possible collisions in the tree. |
tass | 68:0847e35d08a6 | 424 | * Eg. if a node is red his children must be black ! |
tass | 68:0847e35d08a6 | 425 | * In this case the function fixes the constant black path property. |
tass | 68:0847e35d08a6 | 426 | */ |
TASS Belgium NV |
131:4758606c9316 | 427 | static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node) |
tass | 68:0847e35d08a6 | 428 | { |
TASS Belgium NV |
131:4758606c9316 | 429 | struct pico_tree_node*temp; |
TASS Belgium NV |
131:4758606c9316 | 430 | |
TASS Belgium NV |
131:4758606c9316 | 431 | while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node)) |
TASS Belgium NV |
131:4758606c9316 | 432 | { |
TASS Belgium NV |
131:4758606c9316 | 433 | if(AM_I_LEFT_CHILD(node)) { |
tass | 68:0847e35d08a6 | 434 | |
TASS Belgium NV |
131:4758606c9316 | 435 | temp = node->parent->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 436 | if(temp->color == RED) |
TASS Belgium NV |
131:4758606c9316 | 437 | { |
TASS Belgium NV |
131:4758606c9316 | 438 | temp->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 439 | node->parent->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 440 | rotateToLeft(tree, node->parent); |
TASS Belgium NV |
131:4758606c9316 | 441 | temp = node->parent->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 442 | } |
TASS Belgium NV |
131:4758606c9316 | 443 | |
TASS Belgium NV |
131:4758606c9316 | 444 | if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK) |
TASS Belgium NV |
131:4758606c9316 | 445 | { |
TASS Belgium NV |
131:4758606c9316 | 446 | temp->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 447 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 448 | } |
TASS Belgium NV |
131:4758606c9316 | 449 | else |
TASS Belgium NV |
131:4758606c9316 | 450 | { |
TASS Belgium NV |
131:4758606c9316 | 451 | if(temp->rightChild->color == BLACK) |
TASS Belgium NV |
131:4758606c9316 | 452 | { |
TASS Belgium NV |
131:4758606c9316 | 453 | temp->leftChild->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 454 | temp->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 455 | rotateToRight(tree, temp); |
TASS Belgium NV |
131:4758606c9316 | 456 | temp = temp->parent->rightChild; |
TASS Belgium NV |
131:4758606c9316 | 457 | } |
tass | 68:0847e35d08a6 | 458 | |
TASS Belgium NV |
131:4758606c9316 | 459 | temp->color = node->parent->color; |
TASS Belgium NV |
131:4758606c9316 | 460 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 461 | temp->rightChild->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 462 | rotateToLeft(tree, node->parent); |
TASS Belgium NV |
131:4758606c9316 | 463 | node = tree->root; |
TASS Belgium NV |
131:4758606c9316 | 464 | } |
TASS Belgium NV |
131:4758606c9316 | 465 | } |
TASS Belgium NV |
131:4758606c9316 | 466 | else{ |
TASS Belgium NV |
131:4758606c9316 | 467 | temp = node->parent->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 468 | if(temp->color == RED) |
TASS Belgium NV |
131:4758606c9316 | 469 | { |
TASS Belgium NV |
131:4758606c9316 | 470 | temp->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 471 | node->parent->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 472 | rotateToRight(tree, node->parent); |
TASS Belgium NV |
131:4758606c9316 | 473 | temp = node->parent->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 474 | } |
TASS Belgium NV |
131:4758606c9316 | 475 | |
TASS Belgium NV |
131:4758606c9316 | 476 | if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK) |
TASS Belgium NV |
131:4758606c9316 | 477 | { |
TASS Belgium NV |
131:4758606c9316 | 478 | temp->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 479 | node = node->parent; |
TASS Belgium NV |
131:4758606c9316 | 480 | } |
TASS Belgium NV |
131:4758606c9316 | 481 | else{ |
TASS Belgium NV |
131:4758606c9316 | 482 | if(temp->leftChild->color == BLACK) |
TASS Belgium NV |
131:4758606c9316 | 483 | { |
TASS Belgium NV |
131:4758606c9316 | 484 | temp->rightChild->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 485 | temp->color = RED; |
TASS Belgium NV |
131:4758606c9316 | 486 | rotateToLeft(tree, temp); |
TASS Belgium NV |
131:4758606c9316 | 487 | temp = temp->parent->leftChild; |
TASS Belgium NV |
131:4758606c9316 | 488 | } |
TASS Belgium NV |
131:4758606c9316 | 489 | |
TASS Belgium NV |
131:4758606c9316 | 490 | temp->color = node->parent->color; |
TASS Belgium NV |
131:4758606c9316 | 491 | node->parent->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 492 | temp->leftChild->color = BLACK; |
TASS Belgium NV |
131:4758606c9316 | 493 | rotateToRight(tree, node->parent); |
TASS Belgium NV |
131:4758606c9316 | 494 | node = tree->root; |
TASS Belgium NV |
131:4758606c9316 | 495 | } |
TASS Belgium NV |
131:4758606c9316 | 496 | } |
tass | 68:0847e35d08a6 | 497 | } |
TASS Belgium NV |
131:4758606c9316 | 498 | node->color = BLACK; |
tass | 68:0847e35d08a6 | 499 | } |