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@48:40fc4462265c, 2013-08-02 (annotated)

Committer:
tass
Date:
Fri Aug 02 07:28:05 2013 +0000
Revision:
48:40fc4462265c
Parent:
6:55b47464d5bc
Child:
51:ab4529a384a6
Fixes for issues #8,#9,#10 from github.

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 6:55b47464d5bc 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 6:55b47464d5bc 47 while(IS_NOT_LEAF(node->leftChild))
tass 6:55b47464d5bc 48 node = node->leftChild;
tass 6:55b47464d5bc 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 6:55b47464d5bc 54 while(IS_NOT_LEAF(node->rightChild))
tass 6:55b47464d5bc 55 node = node->rightChild;
tass 6:55b47464d5bc 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 6:55b47464d5bc 61 if(IS_NOT_LEAF(node->rightChild))
tass 6:55b47464d5bc 62 {
tass 6:55b47464d5bc 63 node = node->rightChild;
tass 6:55b47464d5bc 64 while(IS_NOT_LEAF(node->leftChild))
tass 6:55b47464d5bc 65 node = node->leftChild;
tass 6:55b47464d5bc 66 }
tass 6:55b47464d5bc 67 else
tass 6:55b47464d5bc 68 {
tass 6:55b47464d5bc 69 if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node))
tass 48:40fc4462265c 70 node = node->parent;
tass 6:55b47464d5bc 71 else {
tass 48:40fc4462265c 72 while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
tass 6:55b47464d5bc 73 node = node->parent;
tass 6:55b47464d5bc 74
tass 6:55b47464d5bc 75 node = node->parent;
tass 6:55b47464d5bc 76 }
tass 6:55b47464d5bc 77 }
tass 6:55b47464d5bc 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 6:55b47464d5bc 83 if (IS_NOT_LEAF(node->leftChild)) {
tass 48:40fc4462265c 84 node = node->leftChild;
tass 48:40fc4462265c 85 while (IS_NOT_LEAF(node->rightChild))
tass 48:40fc4462265c 86 node = node->rightChild;
tass 6:55b47464d5bc 87 } else {
tass 48:40fc4462265c 88 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
tass 48:40fc4462265c 89 node = node->parent;
tass 48:40fc4462265c 90 else {
tass 48:40fc4462265c 91 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
tass 48:40fc4462265c 92 node = node->parent;
tass 6:55b47464d5bc 93
tass 48:40fc4462265c 94 node = node->parent;
tass 48:40fc4462265c 95 }
tass 6:55b47464d5bc 96 }
tass 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 108 LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL);
tass 6:55b47464d5bc 109 // if node already in, bail out
tass 6:55b47464d5bc 110 if(LocalKey)
tass 48:40fc4462265c 111 return LocalKey;
tass 6:55b47464d5bc 112 else
tass 48:40fc4462265c 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 6:55b47464d5bc 118 last_node = temp;
tass 6:55b47464d5bc 119 result = tree->compare(insert->keyValue,temp->keyValue);
tass 6:55b47464d5bc 120
tass 6:55b47464d5bc 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 48:40fc4462265c 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 6:55b47464d5bc 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 6:55b47464d5bc 145 struct pico_tree_node *found;
tass 6:55b47464d5bc 146
tass 6:55b47464d5bc 147 found = tree->root;
tass 6:55b47464d5bc 148
tass 6:55b47464d5bc 149 while(IS_NOT_LEAF(found))
tass 6:55b47464d5bc 150 {
tass 48:40fc4462265c 151 int result;
tass 48:40fc4462265c 152 result = tree->compare(found->keyValue, key);
tass 48:40fc4462265c 153 if(result == 0)
tass 48:40fc4462265c 154 {
tass 48:40fc4462265c 155 return found;
tass 48:40fc4462265c 156 }
tass 48:40fc4462265c 157 else if(result < 0)
tass 6:55b47464d5bc 158 found = found->rightChild;
tass 6:55b47464d5bc 159 else
tass 6:55b47464d5bc 160 found = found->leftChild;
tass 6:55b47464d5bc 161 }
tass 6:55b47464d5bc 162
tass 6:55b47464d5bc 163
tass 6:55b47464d5bc 164
tass 6:55b47464d5bc 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 48:40fc4462265c 177 int result;
tass 6:55b47464d5bc 178
tass 48:40fc4462265c 179 result = tree->compare(found->keyValue, key);
tass 48:40fc4462265c 180 if(result == 0)
tass 48:40fc4462265c 181 return found->keyValue;
tass 48:40fc4462265c 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 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 206 struct pico_tree_node * delete; // keeps a copy of the node to be extracted
tass 6:55b47464d5bc 207 struct pico_tree_node * temp; // temporary
tass 6:55b47464d5bc 208 struct pico_tree_node * ltemp; // used for switching nodes, as a copy
tass 6:55b47464d5bc 209
tass 6:55b47464d5bc 210 delete = pico_tree_findNode(tree, key);
tass 6:55b47464d5bc 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 6:55b47464d5bc 228 struct pico_tree_node * ltemp = delete;
tass 6:55b47464d5bc 229 temp = ltemp->leftChild;
tass 6:55b47464d5bc 230 switchNodes(tree, ltemp, ltemp->leftChild);
tass 6:55b47464d5bc 231 }
tass 6:55b47464d5bc 232 else{
tass 6:55b47464d5bc 233 struct pico_tree_node * min;
tass 6:55b47464d5bc 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 48:40fc4462265c 239 temp->parent = min;
tass 6:55b47464d5bc 240 else{
tass 48:40fc4462265c 241 switchNodes(tree, min, min->rightChild);
tass 48:40fc4462265c 242 min->rightChild = ltemp->rightChild;
tass 48:40fc4462265c 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 6:55b47464d5bc 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 6:55b47464d5bc 287 node->parent->leftChild = temp;
tass 6:55b47464d5bc 288 else
tass 6:55b47464d5bc 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 48:40fc4462265c 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 48:40fc4462265c 348 while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)) )
tass 6:55b47464d5bc 349 {
tass 48:40fc4462265c 350 if(AM_I_RIGHT_CHILD(node->parent))
tass 6:55b47464d5bc 351 {
tass 6:55b47464d5bc 352 temp = GRANPA(node)->leftChild;
tass 6:55b47464d5bc 353 if(temp->color == RED){
tass 6:55b47464d5bc 354 node->parent->color = BLACK;
tass 6:55b47464d5bc 355 temp->color = BLACK;
tass 6:55b47464d5bc 356 GRANPA(node)->color = RED;
tass 6:55b47464d5bc 357 node = GRANPA(node);
tass 6:55b47464d5bc 358 }
tass 6:55b47464d5bc 359 else if(temp->color == BLACK){
tass 6:55b47464d5bc 360 if(node == node->parent->leftChild){
tass 6:55b47464d5bc 361 node = node->parent;
tass 6:55b47464d5bc 362 rotateToRight(tree, node);
tass 6:55b47464d5bc 363 }
tass 6:55b47464d5bc 364 node->parent->color = BLACK;
tass 6:55b47464d5bc 365 GRANPA(node)->color = RED;
tass 6:55b47464d5bc 366 rotateToLeft(tree, GRANPA(node));
tass 6:55b47464d5bc 367 }
tass 6:55b47464d5bc 368 }
tass 48:40fc4462265c 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 6:55b47464d5bc 373 node->parent->color = BLACK;
tass 6:55b47464d5bc 374 temp->color = BLACK;
tass 6:55b47464d5bc 375 GRANPA(node)->color = RED;
tass 6:55b47464d5bc 376 node = GRANPA(node);
tass 6:55b47464d5bc 377 }
tass 6:55b47464d5bc 378 else if(temp->color == BLACK){
tass 6:55b47464d5bc 379 if(AM_I_RIGHT_CHILD(node)){
tass 6:55b47464d5bc 380 node = node->parent;
tass 6:55b47464d5bc 381 rotateToLeft(tree, node);
tass 6:55b47464d5bc 382 }
tass 6:55b47464d5bc 383 node->parent->color = BLACK;
tass 6:55b47464d5bc 384 GRANPA(node)->color = RED;
tass 6:55b47464d5bc 385 rotateToRight(tree, GRANPA(node));
tass 48:40fc4462265c 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 6:55b47464d5bc 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 48:40fc4462265c 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 48:40fc4462265c 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 6:55b47464d5bc 428 temp->color = BLACK;
tass 6:55b47464d5bc 429 node->parent->color = RED;
tass 6:55b47464d5bc 430 rotateToLeft(tree, node->parent);
tass 6:55b47464d5bc 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 6:55b47464d5bc 435 temp->color = RED;
tass 6:55b47464d5bc 436 node = node->parent;
tass 6:55b47464d5bc 437 }
tass 6:55b47464d5bc 438 else
tass 6:55b47464d5bc 439 {
tass 6:55b47464d5bc 440 if(temp->rightChild->color == BLACK)
tass 6:55b47464d5bc 441 {
tass 6:55b47464d5bc 442 temp->leftChild->color = BLACK;
tass 6:55b47464d5bc 443 temp->color = RED;
tass 6:55b47464d5bc 444 rotateToRight(tree, temp);
tass 6:55b47464d5bc 445 temp = temp->parent->rightChild;
tass 6:55b47464d5bc 446 }
tass 6:55b47464d5bc 447 temp->color = node->parent->color;
tass 6:55b47464d5bc 448 node->parent->color = BLACK;
tass 6:55b47464d5bc 449 temp->rightChild->color = BLACK;
tass 6:55b47464d5bc 450 rotateToLeft(tree, node->parent);
tass 6:55b47464d5bc 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 6:55b47464d5bc 458 temp->color = BLACK;
tass 6:55b47464d5bc 459 node->parent->color = RED;
tass 6:55b47464d5bc 460 rotateToRight(tree, node->parent);
tass 6:55b47464d5bc 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 6:55b47464d5bc 465 temp->color = RED;
tass 6:55b47464d5bc 466 node = node->parent;
tass 6:55b47464d5bc 467 }
tass 6:55b47464d5bc 468 else{
tass 6:55b47464d5bc 469 if(temp->leftChild->color == BLACK)
tass 6:55b47464d5bc 470 {
tass 6:55b47464d5bc 471 temp->rightChild->color = BLACK;
tass 6:55b47464d5bc 472 temp->color = RED;
tass 6:55b47464d5bc 473 rotateToLeft(tree, temp);
tass 6:55b47464d5bc 474 temp = temp->parent->leftChild;
tass 6:55b47464d5bc 475 }
tass 6:55b47464d5bc 476 temp->color = node->parent->color;
tass 6:55b47464d5bc 477 node->parent->color = BLACK;
tass 6:55b47464d5bc 478 temp->leftChild->color = BLACK;
tass 6:55b47464d5bc 479 rotateToRight(tree, node->parent);
tass 6:55b47464d5bc 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 }