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@63:97f481e33cb2, 2013-09-19 (annotated)

Committer:
tass
Date:
Thu Sep 19 12:38:53 2013 +0000
Revision:
63:97f481e33cb2
Parent:
51:ab4529a384a6 
Update from the master branch

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