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@1:cfe8984a32b4, 2013-05-17 (annotated)

Committer:
tass
Date:
Fri May 17 12:09:59 2013 +0000
Revision:
1:cfe8984a32b4
Parent:
libraries/picotcp/stack/pico_tree.c@0:d7f2341ab245 
Update for smaller SOCKETQ

Who changed what in which revision?

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