pico_tree.c

00001 /*********************************************************************
00002    PicoTCP. Copyright (c) 2012-2015 Altran Intelligent Systems. 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 #include "pico_protocol.h"
00011 #include "pico_mm.h"
00012 
00013 #define RED     0
00014 #define BLACK 1
00015 
00016 /* By default the null leafs are black */
00017 struct pico_tree_node LEAF = {
00018     NULL, /* key */
00019     &LEAF, &LEAF, &LEAF, /* parent, left,right */
00020     BLACK, /* color */
00021 };
00022 
00023 #define IS_LEAF(x) (x == &LEAF)
00024 #define IS_NOT_LEAF(x) (x != &LEAF)
00025 #define INIT_LEAF (&LEAF)
00026 
00027 #define AM_I_LEFT_CHILD(x) (x == x->parent->leftChild)
00028 #define AM_I_RIGHT_CHILD(x) (x == x->parent->rightChild)
00029 
00030 #define PARENT(x) (x->parent)
00031 #define GRANPA(x) (x->parent->parent)
00032 
00033 /*
00034  * Local Functions
00035  */
00036 static struct pico_tree_node *create_node(struct pico_tree *tree, void *key, uint8_t allocator);
00037 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node);
00038 static void rotateToRight(struct pico_tree*root, struct pico_tree_node*node);
00039 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node);
00040 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node);
00041 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB);
00042 void *pico_tree_insert_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
00043 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator);
00044 
00045 #ifdef PICO_SUPPORT_MM
00046 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
00047  * These nodes should be placed in the manager page which is in a different memory region then the nodes
00048  * which are used for the pico stack in general.
00049  * Therefore the following 2 functions are created so that pico_tree can use them to to put these nodes
00050  * into the correct memory regions.
00051  * If pico_tree_insert is called from the memory manager module, then create_node should use
00052  * pico_mem_page0_zalloc to create a node. The same for pico_tree_delete.
00053  */
00054 extern void*pico_mem_page0_zalloc(size_t len);
00055 extern void pico_mem_page0_free(void*ptr);
00056 #endif  /* PICO_SUPPORT_MM */
00057 
00058 /*
00059  * Exported functions
00060  */
00061 
00062 struct pico_tree_node *pico_tree_firstNode(struct pico_tree_node *node)
00063 {
00064     while(IS_NOT_LEAF(node->leftChild))
00065         node = node->leftChild;
00066     return node;
00067 }
00068 
00069 struct pico_tree_node *pico_tree_lastNode(struct pico_tree_node *node)
00070 {
00071     while(IS_NOT_LEAF(node->rightChild))
00072         node = node->rightChild;
00073     return node;
00074 }
00075 
00076 struct pico_tree_node *pico_tree_next(struct pico_tree_node *node)
00077 {
00078     if(IS_NOT_LEAF(node->rightChild))
00079     {
00080         node = node->rightChild;
00081         while(IS_NOT_LEAF(node->leftChild))
00082             node = node->leftChild;
00083     }
00084     else
00085     {
00086         if (IS_NOT_LEAF(node->parent) &&  AM_I_LEFT_CHILD(node))
00087             node = node->parent;
00088         else {
00089             while (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
00090                 node = node->parent;
00091             node = node->parent;
00092         }
00093     }
00094 
00095     return node;
00096 }
00097 
00098 struct pico_tree_node *pico_tree_prev(struct pico_tree_node *node)
00099 {
00100     if (IS_NOT_LEAF(node->leftChild)) {
00101         node = node->leftChild;
00102         while (IS_NOT_LEAF(node->rightChild))
00103             node = node->rightChild;
00104     } else {
00105         if (IS_NOT_LEAF(node->parent) && AM_I_RIGHT_CHILD(node))
00106             node = node->parent;
00107         else {
00108             while (IS_NOT_LEAF(node) && AM_I_LEFT_CHILD(node))
00109                 node = node->parent;
00110             node = node->parent;
00111         }
00112     }
00113 
00114     return node;
00115 }
00116 
00117 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
00118  * These nodes should be placed in the manager page which is in a different memory region then the nodes
00119  * which are used for the pico stack in general.
00120  * Therefore the following wrapper for pico_tree_insert is created.
00121  * The actual implementation can be found in pico_tree_insert_implementation.
00122  */
00123 void *pico_tree_insert(struct pico_tree *tree, void *key)
00124 {
00125     return pico_tree_insert_implementation(tree, key, USE_PICO_ZALLOC);
00126 }
00127 
00128 void *pico_tree_insert_implementation(struct pico_tree *tree, void *key, uint8_t allocator)
00129 {
00130     struct pico_tree_node *last_node = INIT_LEAF;
00131     struct pico_tree_node *temp = tree->root;
00132     struct pico_tree_node *insert;
00133     void *LocalKey;
00134     int result = 0;
00135 
00136     LocalKey = (IS_NOT_LEAF(tree->root) ? pico_tree_findKey(tree, key) : NULL);
00137     
00138     /* if node already in, bail out */
00139     if(LocalKey) {
00140         return LocalKey;
00141     }
00142     else
00143     {
00144         if(allocator == USE_PICO_PAGE0_ZALLOC)
00145             insert = create_node(tree, key, USE_PICO_PAGE0_ZALLOC);
00146         else
00147             insert = create_node(tree, key, USE_PICO_ZALLOC);
00148 
00149         if(!insert)
00150         {
00151             pico_err = PICO_ERR_ENOMEM;
00152             /* to let the user know that it couldn't insert */
00153             return (void *)&LEAF;
00154         }
00155     }
00156 
00157     /* search for the place to insert the new node */
00158     while(IS_NOT_LEAF(temp))
00159     {
00160         last_node = temp;
00161         result = tree->compare(insert->keyValue, temp->keyValue);
00162 
00163         temp = (result < 0) ? (temp->leftChild) : (temp->rightChild);
00164     }
00165     /* make the needed connections */
00166     insert->parent = last_node;
00167 
00168     if(IS_LEAF(last_node))
00169         tree->root = insert;
00170     else{
00171         result = tree->compare(insert->keyValue, last_node->keyValue);
00172         if(result < 0)
00173             last_node->leftChild = insert;
00174         else
00175             last_node->rightChild = insert;
00176     }
00177 
00178     /* fix colour issues */
00179     fix_insert_collisions(tree, insert);
00180 
00181     return NULL;
00182 }
00183 
00184 struct pico_tree_node *pico_tree_findNode(struct pico_tree *tree, void *key)
00185 {
00186     struct pico_tree_node *found;
00187 
00188     found = tree->root;
00189 
00190     while(IS_NOT_LEAF(found))
00191     {
00192         int result;
00193         result = tree->compare(found->keyValue, key);
00194         if(result == 0)
00195         {
00196             return found;
00197         }
00198         else if(result < 0)
00199             found = found->rightChild;
00200         else
00201             found = found->leftChild;
00202     }
00203     return NULL;
00204 }
00205 
00206 void *pico_tree_findKey(struct pico_tree *tree, void *key)
00207 {
00208     struct pico_tree_node *found;
00209 
00210 
00211     found = tree->root;
00212     while(IS_NOT_LEAF(found))
00213     {
00214         int result;
00215 
00216         result = tree->compare(found->keyValue, key);
00217         if(result == 0)
00218             return found->keyValue;
00219         else if(result < 0)
00220             found = found->rightChild;
00221         else
00222             found = found->leftChild;
00223 
00224     }
00225     return NULL;
00226 }
00227 
00228 void *pico_tree_first(struct pico_tree *tree)
00229 {
00230     return pico_tree_firstNode(tree->root)->keyValue;
00231 }
00232 
00233 void *pico_tree_last(struct pico_tree *tree)
00234 {
00235     return pico_tree_lastNode(tree->root)->keyValue;
00236 }
00237 
00238 static uint8_t pico_tree_delete_node(struct pico_tree *tree, struct pico_tree_node *d, struct pico_tree_node **temp)
00239 {
00240     struct pico_tree_node *min;
00241     struct pico_tree_node *ltemp = d;
00242     uint8_t nodeColor;
00243     min = pico_tree_firstNode(d->rightChild);
00244     nodeColor = min->color;
00245 
00246     *temp = min->rightChild;
00247     if(min->parent == ltemp && IS_NOT_LEAF(*temp))
00248         (*temp)->parent = min;
00249     else{
00250         switchNodes(tree, min, min->rightChild);
00251         min->rightChild = ltemp->rightChild;
00252         if(IS_NOT_LEAF(min->rightChild)) min->rightChild->parent = min;
00253     }
00254 
00255     switchNodes(tree, ltemp, min);
00256     min->leftChild = ltemp->leftChild;
00257 
00258     if(IS_NOT_LEAF(min->leftChild))
00259         min->leftChild->parent = min;
00260 
00261     min->color = ltemp->color;
00262     return nodeColor;
00263 }
00264 
00265 static uint8_t pico_tree_delete_check_switch(struct pico_tree *tree, struct pico_tree_node *delete, struct pico_tree_node **temp)
00266 {
00267     struct pico_tree_node *ltemp = delete;
00268     uint8_t nodeColor = delete->color;
00269     if(IS_LEAF(delete->leftChild))
00270     {
00271         *temp = ltemp->rightChild;
00272         switchNodes(tree, ltemp, ltemp->rightChild);
00273     }
00274     else
00275     if(IS_LEAF(delete->rightChild))
00276     {
00277         struct pico_tree_node *_ltemp = delete;
00278         *temp = _ltemp->leftChild;
00279         switchNodes(tree, _ltemp, _ltemp->leftChild);
00280     }
00281     else{
00282         nodeColor = pico_tree_delete_node(tree, delete, temp);
00283     }
00284 
00285     return nodeColor;
00286 
00287 }
00288 
00289 /* The memory manager also uses the pico_tree to keep track of all the different slab sizes it has.
00290  * These nodes should be placed in the manager page which is in a different memory region then the nodes
00291  * which are used for the pico stack in general.
00292  * Therefore the following wrapper for pico_tree_delete is created.
00293  * The actual implementation can be found in pico_tree_delete_implementation.
00294  */
00295 void *pico_tree_delete(struct pico_tree *tree, void *key)
00296 {
00297     return pico_tree_delete_implementation(tree, key, USE_PICO_ZALLOC);
00298 }
00299 
00300 static inline void if_nodecolor_black_fix_collisions(struct pico_tree *tree, struct pico_tree_node *temp, uint8_t nodeColor)
00301 {
00302     /* deleted node is black, this will mess up the black path property */
00303     if(nodeColor == BLACK) 
00304         fix_delete_collisions(tree, temp);
00305 }
00306 
00307 void *pico_tree_delete_implementation(struct pico_tree *tree, void *key, uint8_t allocator)
00308 {
00309     struct pico_tree_node *temp;
00310     uint8_t nodeColor; /* keeps the color of the node to be deleted */
00311     void *lkey; /* keeps a copy of the key which will be removed */
00312     struct pico_tree_node *delete;  /* keeps a copy of the node to be extracted */
00313     if (!key)
00314         return NULL;
00315     delete = pico_tree_findNode(tree, key);
00316 
00317     /* this key isn't in the tree, bail out */
00318     if(!delete) 
00319         return NULL;
00320     
00321     lkey = delete->keyValue;
00322     nodeColor = pico_tree_delete_check_switch(tree, delete, &temp);
00323 
00324     if_nodecolor_black_fix_collisions(tree, temp, nodeColor);
00325 
00326     if(allocator == USE_PICO_ZALLOC)
00327         PICO_FREE(delete);
00328 
00329 #ifdef PICO_SUPPORT_MM
00330     else
00331         pico_mem_page0_free(delete);
00332 #endif
00333     return lkey;
00334 }
00335 
00336 int pico_tree_empty(struct pico_tree *tree)
00337 {
00338     return (!tree->root || IS_LEAF(tree->root));
00339 }
00340 
00341 /*
00342  * Private functions
00343  */
00344 static void rotateToLeft(struct pico_tree*tree, struct pico_tree_node*node)
00345 {
00346     struct pico_tree_node*temp;
00347 
00348     temp = node->rightChild;
00349 
00350     if(temp == &LEAF) return;
00351 
00352     node->rightChild = temp->leftChild;
00353 
00354     if(IS_NOT_LEAF(temp->leftChild))
00355         temp->leftChild->parent = node;
00356 
00357     temp->parent = node->parent;
00358 
00359     if(IS_LEAF(node->parent))
00360         tree->root = temp;
00361     else
00362     if(node == node->parent->leftChild)
00363         node->parent->leftChild = temp;
00364     else
00365         node->parent->rightChild = temp;
00366 
00367     temp->leftChild = node;
00368     node->parent = temp;
00369 }
00370 
00371 
00372 static void rotateToRight(struct pico_tree *tree, struct pico_tree_node *node)
00373 {
00374     struct pico_tree_node*temp;
00375 
00376     temp = node->leftChild;
00377     node->leftChild = temp->rightChild;
00378 
00379     if(temp == &LEAF) return;
00380 
00381     if(IS_NOT_LEAF(temp->rightChild))
00382         temp->rightChild->parent = node;
00383 
00384     temp->parent = node->parent;
00385 
00386     if(IS_LEAF(node->parent))
00387         tree->root = temp;
00388     else
00389     if(node == node->parent->rightChild)
00390         node->parent->rightChild = temp;
00391     else
00392         node->parent->leftChild = temp;
00393 
00394     temp->rightChild = node;
00395     node->parent = temp;
00396     return;
00397 }
00398 
00399 static struct pico_tree_node *create_node(struct pico_tree *tree, void*key, uint8_t allocator)
00400 {
00401     struct pico_tree_node *temp = NULL;
00402     IGNORE_PARAMETER(tree);
00403     if(allocator == USE_PICO_ZALLOC)
00404         temp = (struct pico_tree_node *)PICO_ZALLOC(sizeof(struct pico_tree_node));
00405 
00406 #ifdef PICO_SUPPORT_MM
00407     else
00408         temp = (struct pico_tree_node *)pico_mem_page0_zalloc(sizeof(struct pico_tree_node));
00409 #endif
00410 
00411     if(!temp)
00412         return NULL;
00413 
00414     temp->keyValue = key;
00415     temp->parent = &LEAF;
00416     temp->leftChild = &LEAF;
00417     temp->rightChild = &LEAF;
00418     /* by default every new node is red */
00419     temp->color = RED;
00420     return temp;
00421 }
00422 
00423 /*
00424  * This function fixes the possible collisions in the tree.
00425  * Eg. if a node is red his children must be black !
00426  */
00427 static void fix_insert_collisions(struct pico_tree*tree, struct pico_tree_node*node)
00428 {
00429     struct pico_tree_node*temp;
00430 
00431     while(node->parent->color == RED && IS_NOT_LEAF(GRANPA(node)))
00432     {
00433         if(AM_I_RIGHT_CHILD(node->parent))
00434         {
00435             temp = GRANPA(node)->leftChild;
00436             if(temp->color == RED) {
00437                 node->parent->color = BLACK;
00438                 temp->color = BLACK;
00439                 GRANPA(node)->color = RED;
00440                 node = GRANPA(node);
00441             }
00442             else if(temp->color == BLACK) {
00443                 if(node == node->parent->leftChild) {
00444                     node = node->parent;
00445                     rotateToRight(tree, node);
00446                 }
00447 
00448                 node->parent->color = BLACK;
00449                 GRANPA(node)->color = RED;
00450                 rotateToLeft(tree, GRANPA(node));
00451             }
00452         }
00453         else if(AM_I_LEFT_CHILD(node->parent))
00454         {
00455             temp = GRANPA(node)->rightChild;
00456             if(temp->color == RED) {
00457                 node->parent->color = BLACK;
00458                 temp->color = BLACK;
00459                 GRANPA(node)->color = RED;
00460                 node = GRANPA(node);
00461             }
00462             else if(temp->color == BLACK) {
00463                 if(AM_I_RIGHT_CHILD(node)) {
00464                     node = node->parent;
00465                     rotateToLeft(tree, node);
00466                 }
00467 
00468                 node->parent->color = BLACK;
00469                 GRANPA(node)->color = RED;
00470                 rotateToRight(tree, GRANPA(node));
00471             }
00472         }
00473     }
00474     /* make sure that the root of the tree stays black */
00475     tree->root->color = BLACK;
00476 }
00477 
00478 static void switchNodes(struct pico_tree*tree, struct pico_tree_node*nodeA, struct pico_tree_node*nodeB)
00479 {
00480 
00481     if(IS_LEAF(nodeA->parent))
00482         tree->root = nodeB;
00483     else
00484     if(IS_NOT_LEAF(nodeA))
00485     {
00486         if(AM_I_LEFT_CHILD(nodeA))
00487             nodeA->parent->leftChild = nodeB;
00488         else
00489             nodeA->parent->rightChild = nodeB;
00490     }
00491 
00492     if(IS_NOT_LEAF(nodeB)) nodeB->parent = nodeA->parent;
00493 
00494 }
00495 
00496 /*
00497  * This function fixes the possible collisions in the tree.
00498  * Eg. if a node is red his children must be black !
00499  * In this case the function fixes the constant black path property.
00500  */
00501 static void fix_delete_collisions(struct pico_tree*tree, struct pico_tree_node *node)
00502 {
00503     struct pico_tree_node*temp;
00504 
00505     while( node != tree->root && node->color == BLACK && IS_NOT_LEAF(node))
00506     {
00507         if(AM_I_LEFT_CHILD(node)) {
00508 
00509             temp = node->parent->rightChild;
00510             if(temp->color == RED)
00511             {
00512                 temp->color = BLACK;
00513                 node->parent->color = RED;
00514                 rotateToLeft(tree, node->parent);
00515                 temp = node->parent->rightChild;
00516             }
00517 
00518             if(temp->leftChild->color == BLACK && temp->rightChild->color == BLACK)
00519             {
00520                 temp->color = RED;
00521                 node = node->parent;
00522             }
00523             else
00524             {
00525                 if(temp->rightChild->color == BLACK)
00526                 {
00527                     temp->leftChild->color = BLACK;
00528                     temp->color = RED;
00529                     rotateToRight(tree, temp);
00530                     temp = temp->parent->rightChild;
00531                 }
00532 
00533                 temp->color = node->parent->color;
00534                 node->parent->color = BLACK;
00535                 temp->rightChild->color = BLACK;
00536                 rotateToLeft(tree, node->parent);
00537                 node = tree->root;
00538             }
00539         }
00540         else{
00541             temp = node->parent->leftChild;
00542             if(temp->color == RED)
00543             {
00544                 temp->color = BLACK;
00545                 node->parent->color = RED;
00546                 rotateToRight(tree, node->parent);
00547                 temp = node->parent->leftChild;
00548             }
00549 
00550             if(temp->rightChild->color == BLACK && temp->leftChild->color == BLACK)
00551             {
00552                 temp->color = RED;
00553                 node = node->parent;
00554             }
00555             else{
00556                 if(temp->leftChild->color == BLACK)
00557                 {
00558                     temp->rightChild->color = BLACK;
00559                     temp->color = RED;
00560                     rotateToLeft(tree, temp);
00561                     temp = temp->parent->leftChild;
00562                 }
00563 
00564                 temp->color = node->parent->color;
00565                 node->parent->color = BLACK;
00566                 temp->leftChild->color = BLACK;
00567                 rotateToRight(tree, node->parent);
00568                 node = tree->root;
00569             }
00570         }
00571     }
00572     node->color = BLACK;
00573 }