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@51:ab4529a384a6, 2013-09-02 (annotated)

Committer:
tass
Date:
Mon Sep 02 08:02:21 2013 +0000
Revision:
51:ab4529a384a6
Parent:
48:40fc4462265c
Child:
63:97f481e33cb2
Updated from masterbranch

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