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 }