root/opal/class/opal_rb_tree.c

DEFINITIONS

1. opal_rb_tree_construct
2. opal_rb_tree_destruct
3. opal_rb_tree_init
4. opal_rb_tree_insert
5. opal_rb_tree_find_with
6. opal_rb_tree_find_node
7. opal_rb_tree_delete
8. opal_rb_tree_destroy
9. btree_successor
10. btree_insert
11. btree_delete_fixup
12. inorder_destroy
13. opal_rb_tree_traverse
14. inorder_traversal
15. left_rotate
16. right_rotate
17. opal_rb_tree_size
18. inorder
19. print_inorder

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2013 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2015      Los Alamos National Security, LLC. All rights
  14  *                         reserved.
  15  * $COPYRIGHT$
  16  *
  17  * Additional copyrights may follow
  18  *
  19  * $HEADER$
  20  */
  21 /*
  22  * @file
  23  */
  24 
  25 #include "opal_config.h"
  26 
  27 #include "opal/class/opal_rb_tree.h"
  28 
  29 /* Private functions */
  30 static void btree_insert(opal_rb_tree_t *tree, opal_rb_tree_node_t * node);
  31 static void btree_delete_fixup(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
  32 static opal_rb_tree_node_t * btree_successor(opal_rb_tree_t * tree,
  33                                              opal_rb_tree_node_t * node);
  34 static opal_rb_tree_node_t * opal_rb_tree_find_node(opal_rb_tree_t *tree, void *key);
  35 static void left_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
  36 static void right_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x);
  37 static void inorder_destroy(opal_rb_tree_t *tree, opal_rb_tree_node_t * node);
  38 static void inorder_traversal(opal_rb_tree_t *tree,
  39                               opal_rb_tree_condition_fn_t cond,
  40                               opal_rb_tree_action_fn_t action,
  41                               opal_rb_tree_node_t * node);
  42 
  43 
  44 /**
  45  * the constructor function. creates the free list to get the nodes from
  46  *
  47  * @param object the tree that is to be used
  48  *
  49  * @retval NONE
  50  */
  51 static void opal_rb_tree_construct(opal_object_t * object)
  52 {
  53     opal_rb_tree_t * tree = (opal_rb_tree_t *) object;
  54     tree->root_ptr = NULL;
  55     OBJ_CONSTRUCT(&(tree->free_list), opal_free_list_t);
  56     opal_free_list_init (&(tree->free_list), sizeof(opal_rb_tree_node_t),
  57             opal_cache_line_size, OBJ_CLASS(opal_rb_tree_node_t),
  58             0,opal_cache_line_size, 0, -1 , 128, NULL, 0, NULL, NULL, NULL);
  59 }
  60 
  61 /**
  62  * the destructor function. Free the tree and destroys the free list.
  63  *
  64  * @param object the tree object
  65  */
  66 static void opal_rb_tree_destruct(opal_object_t * object)
  67 {
  68     if(NULL != ((opal_rb_tree_t *)object)->root_ptr) {
  69         opal_rb_tree_destroy((opal_rb_tree_t *) object);
  70     }
  71     OBJ_DESTRUCT(&(((opal_rb_tree_t *)object)->free_list));
  72     return;
  73 }
  74 
  75 /* declare the instance of the classes  */
  76 OBJ_CLASS_INSTANCE(opal_rb_tree_node_t, opal_free_list_item_t, NULL, NULL);
  77 OBJ_CLASS_INSTANCE(opal_rb_tree_t, opal_object_t, opal_rb_tree_construct,
  78                    opal_rb_tree_destruct);
  79 
  80 /* Create the tree */
  81 int opal_rb_tree_init(opal_rb_tree_t * tree,
  82                       opal_rb_tree_comp_fn_t comp)
  83 {
  84     opal_free_list_item_t * node;
  85     /* we need to get memory for the root pointer from the free list */
  86     node = opal_free_list_get (&(tree->free_list));
  87     tree->root_ptr = (opal_rb_tree_node_t *) node;
  88     if (NULL == node) {
  89         return OPAL_ERR_OUT_OF_RESOURCE;
  90     }
  91 
  92     node = opal_free_list_get (&(tree->free_list));
  93     if (NULL == node) {
  94         opal_free_list_return (&tree->free_list, (opal_free_list_item_t*)tree->root_ptr);
  95         return OPAL_ERR_OUT_OF_RESOURCE;
  96     }
  97     tree->nill = (opal_rb_tree_node_t *) node;
  98     /* initialize tree->nill */
  99     tree->nill->color = BLACK;
 100     tree->nill->left = tree->nill;
 101     tree->nill->right = tree->nill;
 102     tree->nill->parent = tree->nill;
 103 
 104     /* initialize the 'root' pointer */
 105     tree->root_ptr->left = tree->nill;
 106     tree->root_ptr->right = tree->nill;
 107     tree->root_ptr->parent = tree->nill;
 108     tree->root_ptr->color = BLACK;
 109 
 110     tree->comp = comp;
 111 
 112     /* set the tree size to zero */
 113     tree->tree_size = 0;
 114 
 115     return OPAL_SUCCESS;
 116 }
 117 
 118 
 119 /* This inserts a node into the tree based on the passed values. */
 120 int opal_rb_tree_insert(opal_rb_tree_t *tree, void * key, void * value)
 121 {
 122     opal_rb_tree_node_t * y;
 123     opal_rb_tree_node_t * node;
 124     opal_free_list_item_t * item;
 125 
 126     /* get the memory for a node */
 127     item = opal_free_list_get (&tree->free_list);
 128     if (NULL == item) {
 129         return OPAL_ERR_OUT_OF_RESOURCE;
 130     }
 131     node = (opal_rb_tree_node_t *) item;
 132     /* insert the data into the node */
 133     node->key = key;
 134     node->value = value;
 135 
 136     /* insert the node into the tree */
 137     btree_insert(tree, node);
 138 
 139     /*do the rotations */
 140     /* usually one would have to check for NULL, but because of the sentinal,
 141      * we don't have to   */
 142     while (node->parent->color == RED) {
 143         if (node->parent == node->parent->parent->left) {
 144             y = node->parent->parent->right;
 145             if (y->color == RED) {
 146                 node->parent->color = BLACK;
 147                 y->color = BLACK;
 148                 node->parent->parent->color = RED;
 149                 node = node->parent->parent;
 150             } else {
 151                 if (node == node->parent->right) {
 152                     node = node->parent;
 153                     left_rotate(tree, node);
 154                 }
 155                 node->parent->color = BLACK;
 156                 node->parent->parent->color = RED;
 157                 right_rotate(tree, node->parent->parent);
 158             }
 159         } else {
 160             y = node->parent->parent->left;
 161             if (y->color == RED) {
 162                 node->parent->color = BLACK;
 163                 y->color = BLACK;
 164                 node->parent->parent->color = RED;
 165                 node = node->parent->parent;
 166             } else {
 167                 if (node == node->parent->left) {
 168                     node = node->parent;
 169                     right_rotate(tree, node);
 170                 }
 171                 node->parent->color = BLACK;
 172                 node->parent->parent->color = RED;
 173                 left_rotate(tree, node->parent->parent);
 174             }
 175         }
 176     }
 177     /* after the rotations the root is black */
 178     tree->root_ptr->left->color = BLACK;
 179     return OPAL_SUCCESS;
 180 }
 181 
 182 /* Finds the node in the tree based on the key */
 183 void * opal_rb_tree_find_with(opal_rb_tree_t *tree, void *key,
 184         opal_rb_tree_comp_fn_t compfn)
 185 {
 186     opal_rb_tree_node_t * node;
 187     int compvalue;
 188 
 189     node = tree->root_ptr->left;
 190     while (node != tree->nill) {
 191         compvalue = compfn(key, node->key);
 192         /* if the result of the comparison function is 0, we found it */
 193         if (compvalue == 0) {
 194             return node->value;
 195         }
 196         /* else if it is less than 0, go left, else right */
 197         node = ((compvalue < 0) ? node->left : node->right);
 198     }
 199     /* if we didn't find anything, return NULL */
 200     return NULL;
 201 }
 202 
 203 /* Finds the node in the tree based on the key and returns a pointer
 204  * to the node. This is a bit a code duplication, but this has to be fast
 205  * so we go ahead with the duplication */
 206 static opal_rb_tree_node_t * opal_rb_tree_find_node(opal_rb_tree_t *tree, void *key)
 207 {
 208     opal_rb_tree_node_t * node;
 209     int compvalue;
 210 
 211     node = tree->root_ptr->left;
 212     while (node != tree->nill) {
 213         compvalue = tree->comp(key, node->key);
 214         /* if the result of the comparison function is 0, we found it */
 215         if (compvalue == 0) {
 216             return node;
 217         }
 218         /* else if it is less than 0, go left, else right */
 219         node = ((compvalue < 0) ? node->left : node->right);
 220     }
 221     /* if we didn't find anything, return NULL */
 222     return NULL;
 223 }
 224 
 225 /* Delete a node from the tree based on the key */
 226 int opal_rb_tree_delete(opal_rb_tree_t *tree, void *key)
 227 {
 228     opal_rb_tree_node_t * p;
 229     opal_rb_tree_node_t * todelete;
 230     opal_rb_tree_node_t * y;
 231     opal_free_list_item_t * item;
 232 
 233     p = opal_rb_tree_find_node(tree, key);
 234     if (NULL == p) {
 235         return OPAL_ERR_NOT_FOUND;
 236     }
 237     if ((p->left == tree->nill) || (p->right == tree->nill)) {
 238         todelete = p;
 239     } else {
 240         todelete = btree_successor(tree, p);
 241     }
 242 
 243     if (todelete->left == tree->nill) {
 244         y = todelete->right;
 245     } else {
 246         y = todelete->left;
 247     }
 248 
 249     y->parent = todelete->parent;
 250 
 251     if (y->parent == tree->root_ptr) {
 252         tree->root_ptr->left = y;
 253     } else {
 254         if (todelete == todelete->parent->left) {
 255          todelete->parent->left = y;
 256         } else {
 257             todelete->parent->right = y;
 258         }
 259     }
 260 
 261     if (todelete != p) {
 262         p->key = todelete->key;
 263         p->value = todelete->value;
 264     }
 265 
 266     if (todelete->color == BLACK) {
 267         btree_delete_fixup(tree, y);
 268     }
 269     item = (opal_free_list_item_t *) todelete;
 270     opal_free_list_return (&(tree->free_list), item);
 271     --tree->tree_size;
 272     return OPAL_SUCCESS;
 273 }
 274 
 275 
 276 /* Destroy the hashmap    */
 277 int opal_rb_tree_destroy(opal_rb_tree_t *tree)
 278 {
 279     opal_free_list_item_t * item;
 280     /* Recursive inorder traversal for delete    */
 281 
 282     inorder_destroy(tree, tree->root_ptr);
 283     /* Now free the root -- root does not get free'd in the above
 284      * inorder destroy    */
 285     item = (opal_free_list_item_t *) tree->root_ptr;
 286     opal_free_list_return(&(tree->free_list), item);
 287 
 288     /* free the tree->nill node */
 289     item = (opal_free_list_item_t *) tree->nill;
 290     opal_free_list_return (&(tree->free_list), item);
 291     return OPAL_SUCCESS;
 292 }
 293 
 294 
 295 /* Find the next inorder successor of a node    */
 296 
 297 static opal_rb_tree_node_t * btree_successor(opal_rb_tree_t * tree, opal_rb_tree_node_t * node)
 298 {
 299     opal_rb_tree_node_t * p;
 300 
 301     if (node->right == tree->nill) {
 302         p = node->parent;
 303         while (node == p->right) {
 304             node = p;
 305             p = p->parent;
 306         }
 307         if(p == tree->root_ptr) {
 308             return tree->nill;
 309         }
 310         return p;
 311     }
 312 
 313     p = node->right;
 314     while(p->left != tree->nill) {
 315         p = p->left;
 316     }
 317     return p;
 318 }
 319 
 320 
 321 /* Insert an element in the normal binary search tree fashion    */
 322 /* this function goes through the tree and finds the leaf where
 323  * the node will be inserted   */
 324 static void btree_insert(opal_rb_tree_t *tree, opal_rb_tree_node_t * node)
 325 {
 326     opal_rb_tree_node_t * parent = tree->root_ptr;
 327     opal_rb_tree_node_t * n = parent->left; /* the real root of the tree */
 328 
 329     /* set up initial values for the node */
 330     node->color = RED;
 331     node->parent = NULL;
 332     node->left = tree->nill;
 333     node->right = tree->nill;
 334 
 335     /* find the leaf where we will insert the node */
 336     while (n != tree->nill) {
 337         parent = n;
 338         n = ((tree->comp(node->key, n->key) <= 0) ? n->left : n->right);
 339     }
 340 
 341     /* place it on either the left or the right */
 342     if((parent == tree->root_ptr) || (tree->comp(node->key, parent->key) <= 0)) {
 343         parent->left = node;
 344     } else {
 345         parent->right = node;
 346     }
 347 
 348     /* set its parent and children */
 349     node->parent = parent;
 350     node->left = tree->nill;
 351     node->right = tree->nill;
 352     ++(tree->tree_size);
 353     return;
 354 }
 355 
 356 /* Fixup the balance of the btree after deletion    */
 357 static void btree_delete_fixup(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
 358 {
 359     opal_rb_tree_node_t * w;
 360     opal_rb_tree_node_t * root = tree->root_ptr->left;
 361     while ((x != root) && (x->color == BLACK)) {
 362         if (x == x->parent->left) {
 363             w = x->parent->right;
 364             if (w->color == RED) {
 365                 w->color = BLACK;
 366                 x->parent->color = RED;
 367                 left_rotate(tree, x->parent);
 368                 w = x->parent->right;
 369             }
 370             if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
 371                 w->color = RED;
 372                 x = x->parent;
 373             } else {
 374                 if (w->right->color == BLACK) {
 375                     w->left->color = BLACK;
 376                     w->color = RED;
 377                     right_rotate(tree, w);
 378                     w = x->parent->right;
 379                 }
 380                 w->color = x->parent->color;
 381                 x->parent->color = BLACK;
 382                 w->right->color = BLACK;
 383                 left_rotate(tree, x->parent);
 384                 x = root;
 385             }
 386         } else { /* right    */
 387 
 388             w = x->parent->left;
 389             if (w->color == RED) {
 390                 w->color = BLACK;
 391                 x->parent->color = RED;
 392                 right_rotate(tree, x->parent);
 393                 w = x->parent->left;
 394             }
 395             if ((w->right->color == BLACK) && (w->left->color == BLACK)) {
 396                 w->color = RED;
 397                 x = x->parent;
 398             } else {
 399                 if (w->left->color == BLACK) {
 400                     w->right->color = BLACK;
 401                     w->color = RED;
 402                     left_rotate(tree, w);
 403                     w = x->parent->left;
 404                 }
 405                 w->color = x->parent->color;
 406                 x->parent->color = BLACK;
 407                 w->left->color = BLACK;
 408                 right_rotate(tree, x->parent);
 409                 x = root;
 410             }
 411         }
 412     }
 413 
 414     x->color = BLACK;
 415     return;
 416 }
 417 
 418 
 419 /* Free the nodes in inorder fashion    */
 420 
 421 static void
 422 inorder_destroy(opal_rb_tree_t *tree, opal_rb_tree_node_t * node)
 423 {
 424     opal_free_list_item_t * item;
 425 
 426     if (node == tree->nill) {
 427         return;
 428     }
 429 
 430     inorder_destroy(tree, node->left);
 431 
 432     if (node->left != tree->nill) {
 433         item = (opal_free_list_item_t *) node->left;
 434         --tree->tree_size;
 435         opal_free_list_return (&tree->free_list, item);
 436     }
 437 
 438     inorder_destroy(tree, node->right);
 439     if (node->right != tree->nill) {
 440         item = (opal_free_list_item_t *) node->right;
 441         --tree->tree_size;
 442         opal_free_list_return (&tree->free_list, item);
 443     }
 444 }
 445 
 446 /* Try to access all the elements of the hashmap conditionally */
 447 
 448 int opal_rb_tree_traverse(opal_rb_tree_t *tree,
 449                           opal_rb_tree_condition_fn_t cond,
 450                           opal_rb_tree_action_fn_t action)
 451 {
 452     if ((cond == NULL) || (action == NULL)) {
 453         return OPAL_ERROR;
 454     }
 455 
 456     inorder_traversal(tree, cond, action, tree->root_ptr->left);
 457 
 458     return OPAL_SUCCESS;
 459 }
 460 
 461 
 462 static void inorder_traversal(opal_rb_tree_t *tree,
 463                               opal_rb_tree_condition_fn_t cond,
 464                               opal_rb_tree_action_fn_t action,
 465                               opal_rb_tree_node_t * node)
 466 {
 467     if (node == tree->nill) {
 468         return;
 469     }
 470 
 471     inorder_traversal(tree, cond, action, node->left);
 472 
 473     if (cond(node->value)) {
 474         action(node->key, node->value);
 475     }
 476 
 477     inorder_traversal(tree, cond, action, node->right);
 478 }
 479 
 480 /* Left rotate the tree    */
 481 /* basically what we want to do is to make x be the left child
 482  * of its right child    */
 483 static void left_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
 484 {
 485     opal_rb_tree_node_t * y;
 486 
 487     y = x->right;
 488     /* make the left child of y's parent be x if it is not the sentinal node*/
 489     if (y->left != tree->nill) {
 490         y->left->parent=x;
 491     }
 492 
 493     /* normlly we would have to check to see if we are at the root.
 494      * however, the root sentinal takes care of it for us */
 495     if (x == x->parent->left) {
 496         x->parent->left = y;
 497     } else {
 498         x->parent->right = y;
 499     }
 500     /* the old parent of x is now y's parent */
 501     y->parent = x->parent;
 502     /* x's parent is y */
 503     x->parent = y;
 504     x->right = y->left;
 505     y->left = x;
 506 
 507     return;
 508 }
 509 
 510 
 511 /* Right rotate the tree    */
 512 /* basically what we want to do is to make x be the right child
 513  * of its left child */
 514 static void right_rotate(opal_rb_tree_t *tree, opal_rb_tree_node_t * x)
 515 {
 516     opal_rb_tree_node_t * y;
 517 
 518     y = x->left;
 519 
 520     if(y->right != tree->nill) {
 521         y->right->parent = x;
 522     }
 523 
 524     if (x == x->parent->left) {
 525         x->parent->left = y;
 526     } else {
 527         x->parent->right = y;
 528     }
 529 
 530     y->parent = x->parent;
 531     x->parent = y;
 532     x->left = y->right;
 533     y->right = x;
 534 
 535     return;
 536 }
 537 
 538 
 539 /* returns the size of the tree */
 540 int opal_rb_tree_size(opal_rb_tree_t *tree)
 541 {
 542         return tree->tree_size;
 543 }
 544 
 545 /* below are a couple of debugging functions */
 546 #if 0
 547 #include <stdio.h>
 548 static void inorder(opal_rb_tree_t * tree, opal_rb_tree_node_t * node);
 549 static void print_inorder(opal_rb_tree_t * tree);
 550 
 551 void inorder(opal_rb_tree_t * tree, opal_rb_tree_node_t * node)
 552 {
 553     static int level = 0;
 554     if (node == tree->nill) {
 555         printf("nill\n");
 556         return;
 557     }
 558     level++;
 559     inorder(tree, node->left);
 560     level--;
 561     printf("%d, level: %d\n", *((int *)node->value), level);
 562     level++;
 563     inorder(tree, node->right);
 564     level--;
 565 }
 566 
 567 
 568 void print_inorder(opal_rb_tree_t *tree)
 569 {
 570     inorder(tree, tree->root_ptr->left);
 571 }
 572 
 573 #endif