Daniele Lacamera / PicoTCP Featured

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 RTOS
  • generic mbed Ethernet driver
  • high performance NXP LPC1768 specific Ethernet driver
  • Multi-threading support for mbed RTOS
  • Berkeley sockets and integration with the New Socket API
  • Fork of the apps running on top of the New Socket API
  • Scheduling 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.

Last commit 17 May 2013 by TASS Belgium

stack/pico_tree.c@101:37763e3777a7, 2013-10-18 (annotated)

Committer:
tass
Date:
Fri Oct 18 09:41:50 2013 +0000
Revision:
101:37763e3777a7
Parent:
68:0847e35d08a6
Child:
131:4758606c9316
merge with mainline Issue #39

Who changed what in which revision?

UserRevisionLine numberNew contents of line
tass 68:0847e35d08a6 1 /*********************************************************************
tass 68:0847e35d08a6 2 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved.
tass 68:0847e35d08a6 3 See LICENSE and COPYING for usage.
tass 68:0847e35d08a6 4
tass 68:0847e35d08a6 5 Author: Andrei Carp <andrei.carp@tass.be>
tass 68:0847e35d08a6 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 68:0847e35d08a6 12 #define RED 0
tass 68:0847e35d08a6 13 #define BLACK 1
tass 68:0847e35d08a6 14
tass 68:0847e35d08a6 15 // By default the null leafs are black
tass 68:0847e35d08a6 16 struct pico_tree_node LEAF = {
tass 68:0847e35d08a6 17 NULL, // key
tass 68:0847e35d08a6 18 &LEAF, &LEAF, &LEAF, // parent, left,right
tass 68:0847e35d08a6 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 68:0847e35d08a6 35 static struct pico_tree_node * create_node(struct pico_tree * tree,void *key);
tass 68:0847e35d08a6 36 static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node);
tass 68:0847e35d08a6 37 static void rotateToRight(struct pico_tree* root, struct pico_tree_node* node);
tass 68:0847e35d08a6 38 static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node);
tass 68:0847e35d08a6 39 static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node);
tass 68:0847e35d08a6 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 68:0847e35d08a6 46 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node * node)
tass 68:0847e35d08a6 47 {
tass 68:0847e35d08a6 48 while(IS_NOT_LEAF(node->leftChild))
tass 68:0847e35d08a6 49 node = node->leftChild;
tass 68:0847e35d08a6 50 return node;
tass 68:0847e35d08a6 51 }
tass 68:0847e35d08a6 52
tass 68:0847e35d08a6 53 struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node)
tass 68:0847e35d08a6 54 {
tass 68:0847e35d08a6 55 while(IS_NOT_LEAF(node->rightChild))
tass 68:0847e35d08a6 56 node = node->rightChild;
tass 68:0847e35d08a6 57 return node;
tass 68:0847e35d08a6 58 }
tass 68:0847e35d08a6 59
tass 68:0847e35d08a6 60 struct pico_tree_node * pico_tree_next(struct pico_tree_node * node)
tass 68:0847e35d08a6 61 {
tass 68:0847e35d08a6 62 if(IS_NOT_LEAF(node->rightChild))
tass 68:0847e35d08a6 63 {
tass 68:0847e35d08a6 64 node = node->rightChild;
tass 68:0847e35d08a6 65 while(IS_NOT_LEAF(node->leftChild))
tass 68:0847e35d08a6 66 node = node->leftChild;
tass 68:0847e35d08a6 67 }
tass 68:0847e35d08a6 68 else
tass 68:0847e35d08a6 69 {
tass 68:0847e35d08a6 70 if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node))
tass 68:0847e35d08a6 71 node = node->parent;
tass 68:0847e35d08a6 72 else {
tass 68:0847e35d08a6 73 while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
tass 68:0847e35d08a6 74 node = node->parent;
tass 68:0847e35d08a6 75
tass 68:0847e35d08a6 76 node = node->parent;
tass 68:0847e35d08a6 77 }
tass 68:0847e35d08a6 78 }
tass 68:0847e35d08a6 79 return node;
tass 68:0847e35d08a6 80 }
tass 68:0847e35d08a6 81
tass 68:0847e35d08a6 82 struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node)
tass 68:0847e35d08a6 83 {
tass 68:0847e35d08a6 84 if (IS_NOT_LEAF(node->leftChild)) {
tass 68:0847e35d08a6 85 node = node->leftChild;
tass 68:0847e35d08a6 86 while (IS_NOT_LEAF(node->rightChild))
tass 68:0847e35d08a6 87 node = node->rightChild;
tass 68:0847e35d08a6 88 } else {
tass 68:0847e35d08a6 89 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
tass 68:0847e35d08a6 90 node = node->parent;
tass 68:0847e35d08a6 91 else {
tass 68:0847e35d08a6 92 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
tass 68:0847e35d08a6 93 node = node->parent;
tass 68:0847e35d08a6 94
tass 68:0847e35d08a6 95 node = node->parent;
tass 68:0847e35d08a6 96 }
tass 68:0847e35d08a6 97 }
tass 68:0847e35d08a6 98 return node;
tass 68:0847e35d08a6 99 }
tass 68:0847e35d08a6 100
tass 68:0847e35d08a6 101 void * pico_tree_insert(struct pico_tree* tree, void * key){
tass 68:0847e35d08a6 102
tass 68:0847e35d08a6 103 struct pico_tree_node * last_node = INIT_LEAF;
tass 68:0847e35d08a6 104 struct pico_tree_node * temp = tree->root;
tass 68:0847e35d08a6 105 struct pico_tree_node * insert;
tass 68:0847e35d08a6 106 void * LocalKey;
tass 68:0847e35d08a6 107 int result = 0;
tass 68:0847e35d08a6 108
tass 68:0847e35d08a6 109 LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL);
tass 68:0847e35d08a6 110 // if node already in, bail out
tass 68:0847e35d08a6 111 if(LocalKey)
tass 68:0847e35d08a6 112 return LocalKey;
tass 68:0847e35d08a6 113 else
tass 68:0847e35d08a6 114 {
tass 68:0847e35d08a6 115 insert = create_node(tree,key);
tass 68:0847e35d08a6 116 if(!insert)
tass 68:0847e35d08a6 117 {
tass 68:0847e35d08a6 118 pico_err = PICO_ERR_ENOMEM;
tass 68:0847e35d08a6 119 // to let the user know that it couldn't insert
tass 68:0847e35d08a6 120 return (void *)&LEAF;
tass 68:0847e35d08a6 121 }
tass 68:0847e35d08a6 122 }
tass 68:0847e35d08a6 123
tass 68:0847e35d08a6 124 // search for the place to insert the new node
tass 68:0847e35d08a6 125 while(IS_NOT_LEAF(temp))
tass 68:0847e35d08a6 126 {
tass 68:0847e35d08a6 127 last_node = temp;
tass 68:0847e35d08a6 128 result = tree->compare(insert->keyValue,temp->keyValue);
tass 68:0847e35d08a6 129
tass 68:0847e35d08a6 130 temp = (result < 0 ? temp->leftChild : temp->rightChild);
tass 68:0847e35d08a6 131 }
tass 68:0847e35d08a6 132
tass 68:0847e35d08a6 133 // make the needed connections
tass 68:0847e35d08a6 134 insert->parent = last_node;
tass 68:0847e35d08a6 135
tass 68:0847e35d08a6 136 if(IS_LEAF(last_node))
tass 68:0847e35d08a6 137 tree->root = insert;
tass 68:0847e35d08a6 138 else{
tass 68:0847e35d08a6 139 result = tree->compare(insert->keyValue,last_node->keyValue);
tass 68:0847e35d08a6 140 if(result < 0)
tass 68:0847e35d08a6 141 last_node->leftChild = insert;
tass 68:0847e35d08a6 142 else
tass 68:0847e35d08a6 143 last_node->rightChild = insert;
tass 68:0847e35d08a6 144 }
tass 68:0847e35d08a6 145
tass 68:0847e35d08a6 146 // fix colour issues
tass 68:0847e35d08a6 147 fix_insert_collisions(tree, insert);
tass 68:0847e35d08a6 148
tass 68:0847e35d08a6 149 return NULL;
tass 68:0847e35d08a6 150 }
tass 68:0847e35d08a6 151
tass 68:0847e35d08a6 152 struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key)
tass 68:0847e35d08a6 153 {
tass 68:0847e35d08a6 154 struct pico_tree_node *found;
tass 68:0847e35d08a6 155
tass 68:0847e35d08a6 156 found = tree->root;
tass 68:0847e35d08a6 157
tass 68:0847e35d08a6 158 while(IS_NOT_LEAF(found))
tass 68:0847e35d08a6 159 {
tass 68:0847e35d08a6 160 int result;
tass 68:0847e35d08a6 161 result = tree->compare(found->keyValue, key);
tass 68:0847e35d08a6 162 if(result == 0)
tass 68:0847e35d08a6 163 {
tass 68:0847e35d08a6 164 return found;
tass 68:0847e35d08a6 165 }
tass 68:0847e35d08a6 166 else if(result < 0)
tass 68:0847e35d08a6 167 found = found->rightChild;
tass 68:0847e35d08a6 168 else
tass 68:0847e35d08a6 169 found = found->leftChild;
tass 68:0847e35d08a6 170 }
tass 68:0847e35d08a6 171
tass 68:0847e35d08a6 172
tass 68:0847e35d08a6 173
tass 68:0847e35d08a6 174 return NULL;
tass 68:0847e35d08a6 175 }
tass 68:0847e35d08a6 176
tass 68:0847e35d08a6 177 void * pico_tree_findKey(struct pico_tree * tree, void * key)
tass 68:0847e35d08a6 178 {
tass 68:0847e35d08a6 179 struct pico_tree_node *found;
tass 68:0847e35d08a6 180
tass 68:0847e35d08a6 181
tass 68:0847e35d08a6 182 found = tree->root;
tass 68:0847e35d08a6 183
tass 68:0847e35d08a6 184 while(IS_NOT_LEAF(found))
tass 68:0847e35d08a6 185 {
tass 68:0847e35d08a6 186 int result;
tass 68:0847e35d08a6 187
tass 68:0847e35d08a6 188 result = tree->compare(found->keyValue, key);
tass 68:0847e35d08a6 189 if(result == 0)
tass 68:0847e35d08a6 190 return found->keyValue;
tass 68:0847e35d08a6 191 else if(result < 0)
tass 68:0847e35d08a6 192 found = found->rightChild;
tass 68:0847e35d08a6 193 else
tass 68:0847e35d08a6 194 found = found->leftChild;
tass 68:0847e35d08a6 195
tass 68:0847e35d08a6 196 }
tass 68:0847e35d08a6 197
tass 68:0847e35d08a6 198 return NULL;
tass 68:0847e35d08a6 199 }
tass 68:0847e35d08a6 200
tass 68:0847e35d08a6 201 void * pico_tree_first(struct pico_tree * tree)
tass 68:0847e35d08a6 202 {
tass 68:0847e35d08a6 203 return pico_tree_firstNode(tree->root)->keyValue;
tass 68:0847e35d08a6 204 }
tass 68:0847e35d08a6 205
tass 68:0847e35d08a6 206 void * pico_tree_last(struct pico_tree * tree)
tass 68:0847e35d08a6 207 {
tass 68:0847e35d08a6 208 return pico_tree_lastNode(tree->root)->keyValue;
tass 68:0847e35d08a6 209 }
tass 68:0847e35d08a6 210
tass 68:0847e35d08a6 211 void * pico_tree_delete(struct pico_tree * tree, void * key){
tass 68:0847e35d08a6 212
tass 68:0847e35d08a6 213 uint8_t nodeColor; // keeps the color of the node to be deleted
tass 68:0847e35d08a6 214 void * lkey; // keeps a copy of the key which will be removed
tass 68:0847e35d08a6 215 struct pico_tree_node * delete; // keeps a copy of the node to be extracted
tass 68:0847e35d08a6 216 struct pico_tree_node * temp; // temporary
tass 68:0847e35d08a6 217 struct pico_tree_node * ltemp; // used for switching nodes, as a copy
tass 68:0847e35d08a6 218
tass 68:0847e35d08a6 219 delete = pico_tree_findNode(tree, key);
tass 68:0847e35d08a6 220 ltemp = delete;
tass 68:0847e35d08a6 221
tass 68:0847e35d08a6 222 // this key isn't in the tree, bail out
tass 68:0847e35d08a6 223 if(!delete)
tass 68:0847e35d08a6 224 return NULL;
tass 68:0847e35d08a6 225
tass 68:0847e35d08a6 226 lkey = delete->keyValue;
tass 68:0847e35d08a6 227 nodeColor = delete->color;
tass 68:0847e35d08a6 228
tass 68:0847e35d08a6 229 if(IS_LEAF(delete->leftChild))
tass 68:0847e35d08a6 230 {
tass 68:0847e35d08a6 231 temp = ltemp->rightChild;
tass 68:0847e35d08a6 232 switchNodes(tree, ltemp, ltemp->rightChild);
tass 68:0847e35d08a6 233 }
tass 68:0847e35d08a6 234 else
tass 68:0847e35d08a6 235 if(IS_LEAF(delete->rightChild))
tass 68:0847e35d08a6 236 {
tass 68:0847e35d08a6 237 struct pico_tree_node * _ltemp = delete;
tass 68:0847e35d08a6 238 temp = _ltemp->leftChild;
tass 68:0847e35d08a6 239 switchNodes(tree, _ltemp, _ltemp->leftChild);
tass 68:0847e35d08a6 240 }
tass 68:0847e35d08a6 241 else{
tass 68:0847e35d08a6 242 struct pico_tree_node * min;
tass 68:0847e35d08a6 243 min = pico_tree_firstNode(delete->rightChild);
tass 68:0847e35d08a6 244 nodeColor = min->color;
tass 68:0847e35d08a6 245
tass 68:0847e35d08a6 246 temp = min->rightChild;
tass 68:0847e35d08a6 247 if(min->parent == ltemp && IS_NOT_LEAF(temp))
tass 68:0847e35d08a6 248 temp->parent = min;
tass 68:0847e35d08a6 249 else{
tass 68:0847e35d08a6 250 switchNodes(tree, min, min->rightChild);
tass 68:0847e35d08a6 251 min->rightChild = ltemp->rightChild;
tass 68:0847e35d08a6 252 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
tass 68:0847e35d08a6 253 }
tass 68:0847e35d08a6 254 switchNodes(tree, ltemp, min);
tass 68:0847e35d08a6 255 min->leftChild = ltemp->leftChild;
tass 68:0847e35d08a6 256 if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min;
tass 68:0847e35d08a6 257 min->color = ltemp->color;
tass 68:0847e35d08a6 258 }
tass 68:0847e35d08a6 259
tass 68:0847e35d08a6 260 // deleted node is black, this will mess up the black path property
tass 68:0847e35d08a6 261 if(nodeColor == BLACK)
tass 68:0847e35d08a6 262 fix_delete_collisions(tree, temp);
tass 68:0847e35d08a6 263
tass 68:0847e35d08a6 264 pico_free(delete);
tass 68:0847e35d08a6 265
tass 68:0847e35d08a6 266 return lkey;
tass 68:0847e35d08a6 267 }
tass 68:0847e35d08a6 268
tass 68:0847e35d08a6 269 int pico_tree_empty(struct pico_tree * tree)
tass 68:0847e35d08a6 270 {
tass 68:0847e35d08a6 271 return (!tree->root || IS_LEAF(tree->root));
tass 68:0847e35d08a6 272 }
tass 68:0847e35d08a6 273
tass 68:0847e35d08a6 274 /*
tass 68:0847e35d08a6 275 * Private functions
tass 68:0847e35d08a6 276 */
tass 68:0847e35d08a6 277 static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node)
tass 68:0847e35d08a6 278 {
tass 68:0847e35d08a6 279 struct pico_tree_node* temp;
tass 68:0847e35d08a6 280
tass 68:0847e35d08a6 281 temp = node->rightChild;
tass 68:0847e35d08a6 282
tass 68:0847e35d08a6 283 if(temp == &LEAF) return;
tass 68:0847e35d08a6 284
tass 68:0847e35d08a6 285 node->rightChild = temp->leftChild;
tass 68:0847e35d08a6 286
tass 68:0847e35d08a6 287 if(IS_NOT_LEAF(temp->leftChild))
tass 68:0847e35d08a6 288 temp->leftChild->parent = node;
tass 68:0847e35d08a6 289
tass 68:0847e35d08a6 290 temp->parent = node->parent;
tass 68:0847e35d08a6 291
tass 68:0847e35d08a6 292 if(IS_LEAF(node->parent))
tass 68:0847e35d08a6 293 tree->root = temp;
tass 68:0847e35d08a6 294 else
tass 68:0847e35d08a6 295 if(node == node->parent->leftChild)
tass 68:0847e35d08a6 296 node->parent->leftChild = temp;
tass 68:0847e35d08a6 297 else
tass 68:0847e35d08a6 298 node->parent->rightChild = temp;
tass 68:0847e35d08a6 299
tass 68:0847e35d08a6 300 temp->leftChild = node;
tass 68:0847e35d08a6 301 node->parent = temp;
tass 68:0847e35d08a6 302 }
tass 68:0847e35d08a6 303
tass 68:0847e35d08a6 304
tass 68:0847e35d08a6 305 static void rotateToRight(struct pico_tree * tree, struct pico_tree_node * node)
tass 68:0847e35d08a6 306 {
tass 68:0847e35d08a6 307 struct pico_tree_node* temp;
tass 68:0847e35d08a6 308
tass 68:0847e35d08a6 309 temp = node->leftChild;
tass 68:0847e35d08a6 310 node->leftChild = temp->rightChild;
tass 68:0847e35d08a6 311
tass 68:0847e35d08a6 312 if(temp == &LEAF) return;
tass 68:0847e35d08a6 313
tass 68:0847e35d08a6 314 if(IS_NOT_LEAF(temp->rightChild))
tass 68:0847e35d08a6 315 temp->rightChild->parent = node;
tass 68:0847e35d08a6 316
tass 68:0847e35d08a6 317 temp->parent = node->parent;
tass 68:0847e35d08a6 318
tass 68:0847e35d08a6 319 if(IS_LEAF(node->parent))
tass 68:0847e35d08a6 320 tree->root = temp;
tass 68:0847e35d08a6 321 else
tass 68:0847e35d08a6 322 if(node == node->parent->rightChild)
tass 68:0847e35d08a6 323 node->parent->rightChild = temp;
tass 68:0847e35d08a6 324 else
tass 68:0847e35d08a6 325 node->parent->leftChild = temp;
tass 68:0847e35d08a6 326
tass 68:0847e35d08a6 327 temp->rightChild = node;
tass 68:0847e35d08a6 328 node->parent = temp;
tass 68:0847e35d08a6 329 return;
tass 68:0847e35d08a6 330 }
tass 68:0847e35d08a6 331
tass 68:0847e35d08a6 332 static struct pico_tree_node * create_node(struct pico_tree * tree, void* key)
tass 68:0847e35d08a6 333 {
tass 68:0847e35d08a6 334 struct pico_tree_node *temp;
tass 68:0847e35d08a6 335 IGNORE_PARAMETER(tree);
tass 68:0847e35d08a6 336 temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node));
tass 68:0847e35d08a6 337
tass 68:0847e35d08a6 338 if(!temp)
tass 68:0847e35d08a6 339 return NULL;
tass 68:0847e35d08a6 340
tass 68:0847e35d08a6 341 temp->keyValue = key;
tass 68:0847e35d08a6 342 temp->parent = &LEAF;
tass 68:0847e35d08a6 343 temp->leftChild = &LEAF;
tass 68:0847e35d08a6 344 temp->rightChild = &LEAF;
tass 68:0847e35d08a6 345 // by default every new node is red
tass 68:0847e35d08a6 346 temp->color = RED;
tass 68:0847e35d08a6 347 return temp;
tass 68:0847e35d08a6 348 }
tass 68:0847e35d08a6 349
tass 68:0847e35d08a6 350 /*
tass 68:0847e35d08a6 351 * This function fixes the possible collisions in the tree.
tass 68:0847e35d08a6 352 * Eg. if a node is red his children must be black !
tass 68:0847e35d08a6 353 */
tass 68:0847e35d08a6 354 static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node)
tass 68:0847e35d08a6 355 {
tass 68:0847e35d08a6 356 struct pico_tree_node* temp;
tass 68:0847e35d08a6 357
tass 68:0847e35d08a6 358 while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)) )
tass 68:0847e35d08a6 359 {
tass 68:0847e35d08a6 360 if(AM_I_RIGHT_CHILD(node->parent))
tass 68:0847e35d08a6 361 {
tass 68:0847e35d08a6 362 temp = GRANPA(node)->leftChild;
tass 68:0847e35d08a6 363 if(temp->color == RED){
tass 68:0847e35d08a6 364 node->parent->color = BLACK;
tass 68:0847e35d08a6 365 temp->color = BLACK;
tass 68:0847e35d08a6 366 GRANPA(node)->color = RED;
tass 68:0847e35d08a6 367 node = GRANPA(node);
tass 68:0847e35d08a6 368 }
tass 68:0847e35d08a6 369 else if(temp->color == BLACK){
tass 68:0847e35d08a6 370 if(node == node->parent->leftChild){
tass 68:0847e35d08a6 371 node = node->parent;
tass 68:0847e35d08a6 372 rotateToRight(tree, node);
tass 68:0847e35d08a6 373 }
tass 68:0847e35d08a6 374 node->parent->color = BLACK;
tass 68:0847e35d08a6 375 GRANPA(node)->color = RED;
tass 68:0847e35d08a6 376 rotateToLeft(tree, GRANPA(node));
tass 68:0847e35d08a6 377 }
tass 68:0847e35d08a6 378 }
tass 68:0847e35d08a6 379 else if(AM_I_LEFT_CHILD(node->parent))
tass 68:0847e35d08a6 380 {
tass 68:0847e35d08a6 381 temp = GRANPA(node)->rightChild;
tass 68:0847e35d08a6 382 if(temp->color == RED){
tass 68:0847e35d08a6 383 node->parent->color = BLACK;
tass 68:0847e35d08a6 384 temp->color = BLACK;
tass 68:0847e35d08a6 385 GRANPA(node)->color = RED;
tass 68:0847e35d08a6 386 node = GRANPA(node);
tass 68:0847e35d08a6 387 }
tass 68:0847e35d08a6 388 else if(temp->color == BLACK){
tass 68:0847e35d08a6 389 if(AM_I_RIGHT_CHILD(node)){
tass 68:0847e35d08a6 390 node = node->parent;
tass 68:0847e35d08a6 391 rotateToLeft(tree, node);
tass 68:0847e35d08a6 392 }
tass 68:0847e35d08a6 393 node->parent->color = BLACK;
tass 68:0847e35d08a6 394 GRANPA(node)->color = RED;
tass 68:0847e35d08a6 395 rotateToRight(tree, GRANPA(node));
tass 68:0847e35d08a6 396 }
tass 68:0847e35d08a6 397 }
tass 68:0847e35d08a6 398 }
tass 68:0847e35d08a6 399
tass 68:0847e35d08a6 400 // make sure that the root of the tree stays black
tass 68:0847e35d08a6 401 tree->root->color = BLACK;
tass 68:0847e35d08a6 402 }
tass 68:0847e35d08a6 403
tass 68:0847e35d08a6 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 68:0847e35d08a6 407 if(IS_LEAF(nodeA->parent))
tass 68:0847e35d08a6 408 tree->root = nodeB;
tass 68:0847e35d08a6 409 else
tass 68:0847e35d08a6 410 if(IS_NOT_LEAF(nodeA))
tass 68:0847e35d08a6 411 {
tass 68:0847e35d08a6 412 if(AM_I_LEFT_CHILD(nodeA))
tass 68:0847e35d08a6 413 nodeA->parent->leftChild = nodeB;
tass 68:0847e35d08a6 414 else
tass 68:0847e35d08a6 415 nodeA->parent->rightChild = nodeB;
tass 68:0847e35d08a6 416 }
tass 68:0847e35d08a6 417
tass 68:0847e35d08a6 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 68:0847e35d08a6 427 static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node)
tass 68:0847e35d08a6 428 {
tass 68:0847e35d08a6 429 struct pico_tree_node* temp;
tass 68:0847e35d08a6 430
tass 68:0847e35d08a6 431 while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
tass 68:0847e35d08a6 432 {
tass 68:0847e35d08a6 433 if(AM_I_LEFT_CHILD(node)){
tass 68:0847e35d08a6 434
tass 68:0847e35d08a6 435 temp = node->parent->rightChild;
tass 68:0847e35d08a6 436 if(temp->color == RED)
tass 68:0847e35d08a6 437 {
tass 68:0847e35d08a6 438 temp->color = BLACK;
tass 68:0847e35d08a6 439 node->parent->color = RED;
tass 68:0847e35d08a6 440 rotateToLeft(tree, node->parent);
tass 68:0847e35d08a6 441 temp = node->parent->rightChild;
tass 68:0847e35d08a6 442 }
tass 68:0847e35d08a6 443 if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
tass 68:0847e35d08a6 444 {
tass 68:0847e35d08a6 445 temp->color = RED;
tass 68:0847e35d08a6 446 node = node->parent;
tass 68:0847e35d08a6 447 }
tass 68:0847e35d08a6 448 else
tass 68:0847e35d08a6 449 {
tass 68:0847e35d08a6 450 if(temp->rightChild->color == BLACK)
tass 68:0847e35d08a6 451 {
tass 68:0847e35d08a6 452 temp->leftChild->color = BLACK;
tass 68:0847e35d08a6 453 temp->color = RED;
tass 68:0847e35d08a6 454 rotateToRight(tree, temp);
tass 68:0847e35d08a6 455 temp = temp->parent->rightChild;
tass 68:0847e35d08a6 456 }
tass 68:0847e35d08a6 457 temp->color = node->parent->color;
tass 68:0847e35d08a6 458 node->parent->color = BLACK;
tass 68:0847e35d08a6 459 temp->rightChild->color = BLACK;
tass 68:0847e35d08a6 460 rotateToLeft(tree, node->parent);
tass 68:0847e35d08a6 461 node = tree->root;
tass 68:0847e35d08a6 462 }
tass 68:0847e35d08a6 463 }
tass 68:0847e35d08a6 464 else{
tass 68:0847e35d08a6 465 temp = node->parent->leftChild;
tass 68:0847e35d08a6 466 if(temp->color == RED)
tass 68:0847e35d08a6 467 {
tass 68:0847e35d08a6 468 temp->color = BLACK;
tass 68:0847e35d08a6 469 node->parent->color = RED;
tass 68:0847e35d08a6 470 rotateToRight(tree, node->parent);
tass 68:0847e35d08a6 471 temp = node->parent->leftChild;
tass 68:0847e35d08a6 472 }
tass 68:0847e35d08a6 473 if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
tass 68:0847e35d08a6 474 {
tass 68:0847e35d08a6 475 temp->color = RED;
tass 68:0847e35d08a6 476 node = node->parent;
tass 68:0847e35d08a6 477 }
tass 68:0847e35d08a6 478 else{
tass 68:0847e35d08a6 479 if(temp->leftChild->color == BLACK)
tass 68:0847e35d08a6 480 {
tass 68:0847e35d08a6 481 temp->rightChild->color = BLACK;
tass 68:0847e35d08a6 482 temp->color = RED;
tass 68:0847e35d08a6 483 rotateToLeft(tree, temp);
tass 68:0847e35d08a6 484 temp = temp->parent->leftChild;
tass 68:0847e35d08a6 485 }
tass 68:0847e35d08a6 486 temp->color = node->parent->color;
tass 68:0847e35d08a6 487 node->parent->color = BLACK;
tass 68:0847e35d08a6 488 temp->leftChild->color = BLACK;
tass 68:0847e35d08a6 489 rotateToRight(tree, node->parent);
tass 68:0847e35d08a6 490 node = tree->root;
tass 68:0847e35d08a6 491 }
tass 68:0847e35d08a6 492 }
tass 68:0847e35d08a6 493 }
tass 68:0847e35d08a6 494
tass 68:0847e35d08a6 495 node->color = BLACK;
tass 68:0847e35d08a6 496 }