Daniele Lacamera / USB_Ethernet

CDC/ECM driver for mbed, based on USBDevice by mbed-official. Uses PicoTCP to access Ethernet USB device. License: GPLv2

Dependents:   USBEthernet_TEST

Fork of USB_Ethernet by Daniele Lacamera

stack/pico_tree.c@2:540f6e142d59, 2013-08-03 (annotated)

Committer:
daniele
Date:
Sat Aug 03 13:16:14 2013 +0000
Revision:
2:540f6e142d59
Moved to single package

Who changed what in which revision?

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