Daniele Lacamera / PicoTCP-Experimental_CDC_ECM_Branch

Free (GPLv2) TCP/IP stack developed by TASS Belgium

Fork of PicoTCP by Daniele Lacamera

stack/pico_tree.c@51:18637a3d071f, 2013-08-03 (annotated)

Committer:
daniele
Date:
Sat Aug 03 08:50:27 2013 +0000
Revision:
51:18637a3d071f
Parent:
6:55b47464d5bc
Child:
49:40fc4462265c
Branch for CDC-ECM: Work in progress

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 6:55b47464d5bc 70 node = node->parent;
tass 6:55b47464d5bc 71 else {
tass 6:55b47464d5bc 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 6:55b47464d5bc 84 node = node->leftChild;
tass 6:55b47464d5bc 85 while (IS_NOT_LEAF(node->rightChild))
tass 6:55b47464d5bc 86 node = node->rightChild;
tass 6:55b47464d5bc 87 } else {
tass 6:55b47464d5bc 88 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
tass 6:55b47464d5bc 89 node = node->parent;
tass 6:55b47464d5bc 90 else {
tass 6:55b47464d5bc 91 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
tass 6:55b47464d5bc 92 node = node->parent;
tass 6:55b47464d5bc 93
tass 6:55b47464d5bc 94 node = node->parent;
tass 6:55b47464d5bc 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 6:55b47464d5bc 111 return LocalKey;
tass 6:55b47464d5bc 112 else
tass 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 151 int result;
tass 6:55b47464d5bc 152 result = tree->compare(found->keyValue, key);
tass 6:55b47464d5bc 153 if(result == 0)
tass 6:55b47464d5bc 154 {
tass 6:55b47464d5bc 155 return found;
tass 6:55b47464d5bc 156 }
tass 6:55b47464d5bc 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 6:55b47464d5bc 177 int result;
tass 6:55b47464d5bc 178
tass 6:55b47464d5bc 179 result = tree->compare(found->keyValue, key);
tass 6:55b47464d5bc 180 if(result == 0)
tass 6:55b47464d5bc 181 return found->keyValue;
tass 6:55b47464d5bc 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 6:55b47464d5bc 239 temp->parent = min;
tass 6:55b47464d5bc 240 else{
tass 6:55b47464d5bc 241 switchNodes(tree, min, min->rightChild);
tass 6:55b47464d5bc 242 min->rightChild = ltemp->rightChild;
tass 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 348 while(node->parent->color == RED)
tass 6:55b47464d5bc 349 {
tass 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 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 6:55b47464d5bc 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 }