CDC/ECM driver for mbed, based on USBDevice by mbed-official. Uses PicoTCP to access Ethernet USB device. License: GPLv2
Fork of USB_Ethernet by
pico_tree.c
00001 /********************************************************************* 00002 PicoTCP. Copyright (c) 2012 TASS Belgium NV. Some rights reserved. 00003 See LICENSE and COPYING for usage. 00004 00005 Author: Andrei Carp <andrei.carp@tass.be> 00006 *********************************************************************/ 00007 00008 #include "pico_tree.h" 00009 #include "pico_config.h" 00010 00011 #define RED 0 00012 #define BLACK 1 00013 00014 // By default the null leafs are black 00015 struct pico_tree_node LEAF = { 00016 NULL, // key 00017 &LEAF, &LEAF, &LEAF, // parent, left,right 00018 BLACK, // color 00019 }; 00020 00021 #define IS_LEAF(x) (x == &LEAF) 00022 #define IS_NOT_LEAF(x) (x != &LEAF) 00023 #define INIT_LEAF (&LEAF) 00024 00025 #define AM_I_LEFT_CHILD(x) (x == x->parent->leftChild) 00026 #define AM_I_RIGHT_CHILD(x) (x == x->parent->rightChild) 00027 00028 #define PARENT(x) (x->parent) 00029 #define GRANPA(x) (x->parent->parent) 00030 00031 /* 00032 * Local Functions 00033 */ 00034 static struct pico_tree_node * create_node(struct pico_tree * tree,void *key); 00035 static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node); 00036 static void rotateToRight(struct pico_tree* root, struct pico_tree_node* node); 00037 static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node); 00038 static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node); 00039 static void switchNodes(struct pico_tree* tree, struct pico_tree_node* nodeA, struct pico_tree_node* nodeB); 00040 00041 /* 00042 * Exported functions 00043 */ 00044 00045 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node * node) 00046 { 00047 while(IS_NOT_LEAF(node->leftChild)) 00048 node = node->leftChild; 00049 return node; 00050 } 00051 00052 struct pico_tree_node * pico_tree_lastNode(struct pico_tree_node * node) 00053 { 00054 while(IS_NOT_LEAF(node->rightChild)) 00055 node = node->rightChild; 00056 return node; 00057 } 00058 00059 struct pico_tree_node * pico_tree_next(struct pico_tree_node * node) 00060 { 00061 if(IS_NOT_LEAF(node->rightChild)) 00062 { 00063 node = node->rightChild; 00064 while(IS_NOT_LEAF(node->leftChild)) 00065 node = node->leftChild; 00066 } 00067 else 00068 { 00069 if (IS_NOT_LEAF(node->parent) && AM_I_LEFT_CHILD(node)) 00070 node = node->parent; 00071 else { 00072 while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) 00073 node = node->parent; 00074 00075 node = node->parent; 00076 } 00077 } 00078 return node; 00079 } 00080 00081 struct pico_tree_node * pico_tree_prev(struct pico_tree_node * node) 00082 { 00083 if (IS_NOT_LEAF(node->leftChild)) { 00084 node = node->leftChild; 00085 while (IS_NOT_LEAF(node->rightChild)) 00086 node = node->rightChild; 00087 } else { 00088 if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node)) 00089 node = node->parent; 00090 else { 00091 while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node)) 00092 node = node->parent; 00093 00094 node = node->parent; 00095 } 00096 } 00097 return node; 00098 } 00099 00100 void * pico_tree_insert(struct pico_tree* tree, void * key){ 00101 00102 struct pico_tree_node * last_node = INIT_LEAF; 00103 struct pico_tree_node * temp = tree->root; 00104 struct pico_tree_node * insert; 00105 void * LocalKey; 00106 int result = 0; 00107 00108 LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree,key) : NULL); 00109 // if node already in, bail out 00110 if(LocalKey) 00111 return LocalKey; 00112 else 00113 insert = create_node(tree,key); 00114 00115 // search for the place to insert the new node 00116 while(IS_NOT_LEAF(temp)) 00117 { 00118 last_node = temp; 00119 result = tree->compare(insert->keyValue,temp->keyValue); 00120 00121 temp = (result < 0 ? temp->leftChild : temp->rightChild); 00122 } 00123 00124 // make the needed connections 00125 insert->parent = last_node; 00126 00127 if(IS_LEAF(last_node)) 00128 tree->root = insert; 00129 else{ 00130 result = tree->compare(insert->keyValue,last_node->keyValue); 00131 if(result < 0) 00132 last_node->leftChild = insert; 00133 else 00134 last_node->rightChild = insert; 00135 } 00136 00137 // fix colour issues 00138 fix_insert_collisions(tree, insert); 00139 00140 return NULL; 00141 } 00142 00143 struct pico_tree_node * pico_tree_findNode(struct pico_tree * tree, void * key) 00144 { 00145 struct pico_tree_node *found; 00146 00147 found = tree->root; 00148 00149 while(IS_NOT_LEAF(found)) 00150 { 00151 int result; 00152 result = tree->compare(found->keyValue, key); 00153 if(result == 0) 00154 { 00155 return found; 00156 } 00157 else if(result < 0) 00158 found = found->rightChild; 00159 else 00160 found = found->leftChild; 00161 } 00162 00163 00164 00165 return NULL; 00166 } 00167 00168 void * pico_tree_findKey(struct pico_tree * tree, void * key) 00169 { 00170 struct pico_tree_node *found; 00171 00172 00173 found = tree->root; 00174 00175 while(IS_NOT_LEAF(found)) 00176 { 00177 int result; 00178 00179 result = tree->compare(found->keyValue, key); 00180 if(result == 0) 00181 return found->keyValue; 00182 else if(result < 0) 00183 found = found->rightChild; 00184 else 00185 found = found->leftChild; 00186 00187 } 00188 00189 return NULL; 00190 } 00191 00192 void * pico_tree_first(struct pico_tree * tree) 00193 { 00194 return pico_tree_firstNode(tree->root)->keyValue; 00195 } 00196 00197 void * pico_tree_last(struct pico_tree * tree) 00198 { 00199 return pico_tree_lastNode(tree->root)->keyValue; 00200 } 00201 00202 void * pico_tree_delete(struct pico_tree * tree, void * key){ 00203 00204 uint8_t nodeColor; // keeps the color of the node to be deleted 00205 void * lkey; // keeps a copy of the key which will be removed 00206 struct pico_tree_node * delete; // keeps a copy of the node to be extracted 00207 struct pico_tree_node * temp; // temporary 00208 struct pico_tree_node * ltemp; // used for switching nodes, as a copy 00209 00210 delete = pico_tree_findNode(tree, key); 00211 ltemp = delete; 00212 00213 // this key isn't in the tree, bail out 00214 if(!delete) 00215 return NULL; 00216 00217 lkey = delete->keyValue; 00218 nodeColor = delete->color; 00219 00220 if(IS_LEAF(delete->leftChild)) 00221 { 00222 temp = ltemp->rightChild; 00223 switchNodes(tree, ltemp, ltemp->rightChild); 00224 } 00225 else 00226 if(IS_LEAF(delete->rightChild)) 00227 { 00228 struct pico_tree_node * ltemp = delete; 00229 temp = ltemp->leftChild; 00230 switchNodes(tree, ltemp, ltemp->leftChild); 00231 } 00232 else{ 00233 struct pico_tree_node * min; 00234 min = pico_tree_firstNode(delete->rightChild); 00235 nodeColor = min->color; 00236 00237 temp = min->rightChild; 00238 if(min->parent == ltemp && IS_NOT_LEAF(temp)) 00239 temp->parent = min; 00240 else{ 00241 switchNodes(tree, min, min->rightChild); 00242 min->rightChild = ltemp->rightChild; 00243 if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min; 00244 } 00245 switchNodes(tree, ltemp, min); 00246 min->leftChild = ltemp->leftChild; 00247 if(IS_NOT_LEAF(min->leftChild)) min->leftChild->parent = min; 00248 min->color = ltemp->color; 00249 } 00250 00251 // deleted node is black, this will mess up the black path property 00252 if(nodeColor == BLACK) 00253 fix_delete_collisions(tree, temp); 00254 00255 pico_free(delete); 00256 00257 return lkey; 00258 } 00259 00260 int pico_tree_empty(struct pico_tree * tree) 00261 { 00262 return (!tree->root || IS_LEAF(tree->root)); 00263 } 00264 00265 /* 00266 * Private functions 00267 */ 00268 static void rotateToLeft(struct pico_tree* tree, struct pico_tree_node* node) 00269 { 00270 struct pico_tree_node* temp; 00271 00272 temp = node->rightChild; 00273 00274 if(temp == &LEAF) return; 00275 00276 node->rightChild = temp->leftChild; 00277 00278 if(IS_NOT_LEAF(temp->leftChild)) 00279 temp->leftChild->parent = node; 00280 00281 temp->parent = node->parent; 00282 00283 if(IS_LEAF(node->parent)) 00284 tree->root = temp; 00285 else 00286 if(node == node->parent->leftChild) 00287 node->parent->leftChild = temp; 00288 else 00289 node->parent->rightChild = temp; 00290 00291 temp->leftChild = node; 00292 node->parent = temp; 00293 } 00294 00295 00296 static void rotateToRight(struct pico_tree * tree, struct pico_tree_node * node) 00297 { 00298 struct pico_tree_node* temp; 00299 00300 temp = node->leftChild; 00301 node->leftChild = temp->rightChild; 00302 00303 if(temp == &LEAF) return; 00304 00305 if(IS_NOT_LEAF(temp->rightChild)) 00306 temp->rightChild->parent = node; 00307 00308 temp->parent = node->parent; 00309 00310 if(IS_LEAF(node->parent)) 00311 tree->root = temp; 00312 else 00313 if(node == node->parent->rightChild) 00314 node->parent->rightChild = temp; 00315 else 00316 node->parent->leftChild = temp; 00317 00318 temp->rightChild = node; 00319 node->parent = temp; 00320 return; 00321 } 00322 00323 static struct pico_tree_node * create_node(struct pico_tree * tree, void* key) 00324 { 00325 struct pico_tree_node *temp; 00326 temp = (struct pico_tree_node *)pico_zalloc(sizeof(struct pico_tree_node)); 00327 00328 if(!temp) 00329 return NULL; 00330 00331 temp->keyValue = key; 00332 temp->parent = &LEAF; 00333 temp->leftChild = &LEAF; 00334 temp->rightChild = &LEAF; 00335 // by default every new node is red 00336 temp->color = RED; 00337 return temp; 00338 } 00339 00340 /* 00341 * This function fixes the possible collisions in the tree. 00342 * Eg. if a node is red his children must be black ! 00343 */ 00344 static void fix_insert_collisions(struct pico_tree* tree, struct pico_tree_node* node) 00345 { 00346 struct pico_tree_node* temp; 00347 00348 while(node->parent->color == RED) 00349 { 00350 if(AM_I_RIGHT_CHILD(node->parent)) 00351 { 00352 temp = GRANPA(node)->leftChild; 00353 if(temp->color == RED){ 00354 node->parent->color = BLACK; 00355 temp->color = BLACK; 00356 GRANPA(node)->color = RED; 00357 node = GRANPA(node); 00358 } 00359 else if(temp->color == BLACK){ 00360 if(node == node->parent->leftChild){ 00361 node = node->parent; 00362 rotateToRight(tree, node); 00363 } 00364 node->parent->color = BLACK; 00365 GRANPA(node)->color = RED; 00366 rotateToLeft(tree, GRANPA(node)); 00367 } 00368 } 00369 else if(AM_I_LEFT_CHILD(node->parent)) 00370 { 00371 temp = GRANPA(node)->rightChild; 00372 if(temp->color == RED){ 00373 node->parent->color = BLACK; 00374 temp->color = BLACK; 00375 GRANPA(node)->color = RED; 00376 node = GRANPA(node); 00377 } 00378 else if(temp->color == BLACK){ 00379 if(AM_I_RIGHT_CHILD(node)){ 00380 node = node->parent; 00381 rotateToLeft(tree, node); 00382 } 00383 node->parent->color = BLACK; 00384 GRANPA(node)->color = RED; 00385 rotateToRight(tree, GRANPA(node)); 00386 } 00387 } 00388 } 00389 00390 // make sure that the root of the tree stays black 00391 tree->root->color = BLACK; 00392 } 00393 00394 static void switchNodes(struct pico_tree* tree, struct pico_tree_node* nodeA, struct pico_tree_node* nodeB) 00395 { 00396 00397 if(IS_LEAF(nodeA->parent)) 00398 tree->root = nodeB; 00399 else 00400 if(IS_NOT_LEAF(nodeA)) 00401 { 00402 if(AM_I_LEFT_CHILD(nodeA)) 00403 nodeA->parent->leftChild = nodeB; 00404 else 00405 nodeA->parent->rightChild = nodeB; 00406 } 00407 00408 if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent; 00409 00410 } 00411 00412 /* 00413 * This function fixes the possible collisions in the tree. 00414 * Eg. if a node is red his children must be black ! 00415 * In this case the function fixes the constant black path property. 00416 */ 00417 static void fix_delete_collisions(struct pico_tree* tree, struct pico_tree_node * node) 00418 { 00419 struct pico_tree_node* temp; 00420 00421 while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node)) 00422 { 00423 if(AM_I_LEFT_CHILD(node)){ 00424 00425 temp = node->parent->rightChild; 00426 if(temp->color == RED) 00427 { 00428 temp->color = BLACK; 00429 node->parent->color = RED; 00430 rotateToLeft(tree, node->parent); 00431 temp = node->parent->rightChild; 00432 } 00433 if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK) 00434 { 00435 temp->color = RED; 00436 node = node->parent; 00437 } 00438 else 00439 { 00440 if(temp->rightChild->color == BLACK) 00441 { 00442 temp->leftChild->color = BLACK; 00443 temp->color = RED; 00444 rotateToRight(tree, temp); 00445 temp = temp->parent->rightChild; 00446 } 00447 temp->color = node->parent->color; 00448 node->parent->color = BLACK; 00449 temp->rightChild->color = BLACK; 00450 rotateToLeft(tree, node->parent); 00451 node = tree->root; 00452 } 00453 } 00454 else{ 00455 temp = node->parent->leftChild; 00456 if(temp->color == RED) 00457 { 00458 temp->color = BLACK; 00459 node->parent->color = RED; 00460 rotateToRight(tree, node->parent); 00461 temp = node->parent->leftChild; 00462 } 00463 if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK) 00464 { 00465 temp->color = RED; 00466 node = node->parent; 00467 } 00468 else{ 00469 if(temp->leftChild->color == BLACK) 00470 { 00471 temp->rightChild->color = BLACK; 00472 temp->color = RED; 00473 rotateToLeft(tree, temp); 00474 temp = temp->parent->leftChild; 00475 } 00476 temp->color = node->parent->color; 00477 node->parent->color = BLACK; 00478 temp->leftChild->color = BLACK; 00479 rotateToRight(tree, node->parent); 00480 node = tree->root; 00481 } 00482 } 00483 } 00484 00485 node->color = BLACK; 00486 }
Generated on Wed Jul 13 2022 02:20:46 by 1.7.2