opal/class/opal

/* [<][>][^][v][top][bottom][index][help] */
This source file includes following definitions.
opal_tree_item_construct
opal_tree_item_destruct
opal_tree_construct
opal_tree_destruct
opal_tree_init
count_descendants
opal_tree_get_size
opal_tree_add_child
item_in_tree
opal_tree_remove_subtree
opal_tree_remove_item
add_tree_item2buf
opal_tree_serialize
deserialize_add_tree_item
opal_tree_deserialize
opal_tree_get_key
opal_tree_dup
opal_tree_copy_subtree
opal_tree_dup_item
opal_tree_num_children
opal_tree_compare_subtrees
opal_tree_compare
find_in_descendants
opal_tree_find_with
   1 /*
   2  * Copyright (c) 2011      Oracle and/or its affiliates.  All rights reserved.
   3  * Copyright (c) 2011      Oak Ridge National Labs.  All rights reserved.
   4  * Copyright (c) 2012      The University of Tennessee and The University
   5  *                         of Tennessee Research Foundation.  All rights
   6  *                         reserved.
   7  * Copyright (c) 2013      Cisco Systems, Inc.  All rights reserved.
   8  * Copyright (c) 2014      Research Organization for Information Science
   9  *                         and Technology (RIST). All rights reserved.
  10  * $COPYRIGHT$
  11  *
  12  * Additional copyrights may follow
  13  *
  14  * $HEADER$
  15  */
  16 
  17 #include "opal_config.h"
  18 
  19 #include "opal/class/opal_tree.h"
  20 #include "opal/constants.h"
  21 
  22 /*
  23  *  List classes
  24  */
  25 
  26 static void opal_tree_item_construct(opal_tree_item_t*);
  27 static void opal_tree_item_destruct(opal_tree_item_t*);
  28 
  29 OBJ_CLASS_INSTANCE(
  30                    opal_tree_item_t,
  31                    opal_object_t,
  32                    opal_tree_item_construct,
  33                    opal_tree_item_destruct
  34                    );
  35 
  36 static void opal_tree_construct(opal_tree_t*);
  37 static void opal_tree_destruct(opal_tree_t*);
  38 
  39 OBJ_CLASS_INSTANCE(
  40                    opal_tree_t,
  41                    opal_object_t,
  42                    opal_tree_construct,
  43                    opal_tree_destruct
  44                    );
  45 
  46 
  47 /*
  48  *
  49  *      opal_tree_item_t interface
  50  *
  51  */
  52 
  53 static void opal_tree_item_construct(opal_tree_item_t *item)
  54 {
  55     item->opal_tree_parent = NULL;
  56     item->opal_tree_num_ancestors = 0;
  57     item->opal_tree_sibling_rank = 0xdeadbeef;
  58     item->opal_tree_next_sibling = item->opal_tree_prev_sibling = NULL;
  59     item->opal_tree_num_children = 0;
  60     item->opal_tree_first_child = item->opal_tree_last_child = NULL;
  61 #if OPAL_ENABLE_DEBUG
  62     item->opal_tree_item_refcount = 0;
  63     item->opal_tree_item_belong_to = NULL;
  64 #endif
  65 }
  66 
  67 static void opal_tree_item_destruct(opal_tree_item_t *item)
  68 {
  69 #if OPAL_ENABLE_DEBUG
  70     assert( 0 == item->opal_tree_item_refcount );
  71     assert( NULL == item->opal_tree_item_belong_to );
  72 #endif  /* OPAL_ENABLE_DEBUG */
  73 }
  74 
  75 
  76 /*
  77  *
  78  *      opal_tree_t interface
  79  *
  80  */
  81 
  82 static void opal_tree_construct(opal_tree_t *tree)
  83 {
  84     OBJ_CONSTRUCT( &(tree->opal_tree_sentinel), opal_tree_item_t );
  85 
  86 #if OPAL_ENABLE_DEBUG
  87     /* These refcounts should never be used in assertions because they
  88        should never be removed from this list, added to another list,
  89        etc.  So set them to sentinel values. */
  90 
  91     tree->opal_tree_sentinel.opal_tree_item_refcount  = 1;
  92     tree->opal_tree_sentinel.opal_tree_item_belong_to = tree;
  93 #endif
  94     tree->opal_tree_sentinel.opal_tree_container = tree;
  95     tree->opal_tree_sentinel.opal_tree_parent = &tree->opal_tree_sentinel;
  96     tree->opal_tree_sentinel.opal_tree_num_ancestors = -1;
  97 
  98     tree->opal_tree_sentinel.opal_tree_next_sibling =
  99         &tree->opal_tree_sentinel;
 100     tree->opal_tree_sentinel.opal_tree_prev_sibling =
 101         &tree->opal_tree_sentinel;
 102 
 103     tree->opal_tree_sentinel.opal_tree_first_child = &tree->opal_tree_sentinel;
 104     tree->opal_tree_sentinel.opal_tree_last_child = &tree->opal_tree_sentinel;
 105 
 106     tree->opal_tree_num_items = 0;
 107     tree->comp = NULL;
 108     tree->serialize = NULL;
 109     tree->deserialize = NULL;
 110     tree->get_key = NULL;
 111 }
 112 
 113 /*
 114  * Reset all the pointers to be NULL -- do not actually destroy
 115  * anything.
 116  */
 117 static void opal_tree_destruct(opal_tree_t *tree)
 118 {
 119     opal_tree_construct(tree);
 120 }
 121 
 122 /*
 123  * initialize tree container
 124  */
 125 void opal_tree_init(opal_tree_t *tree, opal_tree_comp_fn_t comp,
 126                     opal_tree_item_serialize_fn_t serialize,
 127                     opal_tree_item_deserialize_fn_t deserialize,
 128                     opal_tree_get_key_fn_t get_key)
 129 {
 130     tree->comp = comp;
 131     tree->serialize = serialize;
 132     tree->deserialize = deserialize;
 133     tree->get_key = get_key;
 134 }
 135 
 136 /*
 137  * count all the descendants from our level and below
 138  */
 139 static int count_descendants(opal_tree_item_t* item)
 140 {
 141     int current_count = 0;
 142 
 143     /* loop over all siblings for descendants to count */
 144     while (item) {
 145         current_count += count_descendants(opal_tree_get_first_child(item));
 146         current_count++; /* count ourselves */
 147         item = opal_tree_get_next_sibling(item);
 148     }
 149     return(current_count);
 150 }
 151 
 152 /*
 153  * get size of tree
 154  */
 155 size_t opal_tree_get_size(opal_tree_t* tree)
 156 {
 157 #if OPAL_ENABLE_DEBUG
 158     /* not sure if we really want this running in devel, as it does
 159      * slow things down.  Wanted for development of splice / join to
 160      * make sure length was reset properly
 161      */
 162     size_t check_len = 0;
 163     opal_tree_item_t *root;
 164 
 165     if (!opal_tree_is_empty(tree)) {
 166         /* tree has entries so count up items */
 167         root = opal_tree_get_root(tree);
 168         check_len = count_descendants(root);
 169     }
 170 
 171     if (check_len != tree->opal_tree_num_items) {
 172         fprintf(stderr," Error :: opal_tree_get_size - opal_tree_num_items does not match actual tree length\n");
 173         fflush(stderr);
 174         abort();
 175     }
 176 #endif
 177 
 178     return tree->opal_tree_num_items;
 179 }
 180 
 181 /*
 182  * add item to parent's child list
 183  */
 184 void opal_tree_add_child(opal_tree_item_t *parent_item,
 185                          opal_tree_item_t *new_item)
 186 {
 187 #if OPAL_ENABLE_DEBUG
 188     /* Spot check: ensure that this item is previously on no lists */
 189 
 190     assert(0 == new_item->opal_tree_item_refcount);
 191     assert( NULL == new_item->opal_tree_item_belong_to );
 192 #endif
 193 
 194     new_item->opal_tree_parent = parent_item;
 195     new_item->opal_tree_num_ancestors = parent_item->opal_tree_num_ancestors+1;
 196     if (parent_item->opal_tree_num_children) {
 197         /* append item to end of children and sibling lists */
 198         new_item->opal_tree_prev_sibling = parent_item->opal_tree_last_child;
 199         parent_item->opal_tree_last_child->opal_tree_next_sibling = new_item;
 200     } else {
 201         /* no children existing on parent */
 202         parent_item->opal_tree_first_child = new_item;
 203     }
 204     parent_item->opal_tree_last_child = new_item;
 205     parent_item->opal_tree_num_children++;
 206     new_item->opal_tree_container = parent_item->opal_tree_container;
 207     new_item->opal_tree_container->opal_tree_num_items++;
 208 
 209 #if OPAL_ENABLE_DEBUG
 210     /* Spot check: ensure this item is only on the list that we just
 211        appended it to */
 212 
 213     OPAL_THREAD_ADD_FETCH32( &(new_item->opal_tree_item_refcount), 1 );
 214     assert(1 == new_item->opal_tree_item_refcount);
 215     new_item->opal_tree_item_belong_to = new_item->opal_tree_container;
 216 #endif
 217 }
 218 
 219 /*
 220  * check to see if item is in tree
 221  */
 222 #if OPAL_ENABLE_DEBUG
 223 static bool item_in_tree(opal_tree_item_t *item, opal_tree_item_t *search_item)
 224 {
 225     bool result = false;
 226     opal_tree_item_t *first_child;
 227 
 228     while (!result && item) {
 229         /* check for item match */
 230         result = (item == search_item) ? true : false;
 231         if (!result && (first_child = opal_tree_get_first_child(item))) {
 232             /* search descendants for match */
 233             result = item_in_tree(first_child, search_item);
 234         }
 235         if (!result) {
 236             /* didn't find match at our node or descending so check sibling */
 237             item = opal_tree_get_next_sibling(item);
 238         }
 239     }
 240     return(result);
 241 }
 242 #endif  /* OPAL_ENABLE_DEBUG */
 243 
 244 /*
 245  * remove item and all items below it from tree and return it to the caller
 246  */
 247 opal_tree_item_t *opal_tree_remove_subtree(opal_tree_item_t *item)
 248 {
 249     opal_tree_item_t *parent_item = NULL;
 250 
 251 #if OPAL_ENABLE_DEBUG
 252     /* validate that item does exist on tree */
 253     if (NULL != item->opal_tree_container) {
 254         /* we point to a container, check if we can find item in tree */
 255         if (!item_in_tree(opal_tree_get_root(item->opal_tree_container), item)) {
 256             return(NULL);
 257         }
 258     } else {
 259         return (NULL);
 260     }
 261 #endif
 262 
 263     parent_item = item->opal_tree_parent;
 264 
 265     /* remove from parent */
 266     /* If item is the only child, set _first_child and _last_child to
 267        be item's _first_child and _last_child */
 268     if (parent_item->opal_tree_first_child == item &&
 269         parent_item->opal_tree_last_child == item) {
 270         parent_item->opal_tree_first_child = item->opal_tree_first_child;
 271         parent_item->opal_tree_last_child = item->opal_tree_last_child;
 272     } else {
 273         /* Otherwise, there are multiple children of this parent.  If
 274            this item is the first or last child of this parent, then
 275            ensure that the parent gets a valid first / last child:
 276            - If I have children, then my first/last child
 277            - If I have no children, then my immediate sibling */
 278         if (item->opal_tree_parent->opal_tree_first_child == item) {
 279             if (item->opal_tree_num_children > 0) {
 280                 parent_item->opal_tree_first_child =
 281                     item->opal_tree_next_sibling;
 282             } else {
 283                 parent_item->opal_tree_first_child =
 284                     opal_tree_get_next_sibling(item);
 285             }
 286         } else if (parent_item->opal_tree_last_child == item) {
 287             if (item->opal_tree_num_children > 0) {
 288                 parent_item->opal_tree_last_child =
 289                     item->opal_tree_last_child;
 290             } else {
 291                 parent_item->opal_tree_last_child =
 292                     opal_tree_get_prev_sibling(item);
 293             }
 294         }
 295     }
 296     item->opal_tree_parent->opal_tree_num_children--;
 297 
 298     /* remove from sibling pointers */
 299     if (NULL != item->opal_tree_prev_sibling) {
 300         item->opal_tree_prev_sibling->opal_tree_next_sibling=
 301             item->opal_tree_next_sibling;
 302     }
 303     if (NULL != item->opal_tree_next_sibling) {
 304         item->opal_tree_next_sibling->opal_tree_prev_sibling=
 305             item->opal_tree_prev_sibling;
 306     }
 307     item->opal_tree_prev_sibling = NULL;
 308     item->opal_tree_next_sibling = NULL;
 309 
 310     /* adjust items relating to container */
 311     item->opal_tree_container->opal_tree_num_items -= count_descendants(item);
 312     item->opal_tree_container = NULL;
 313 
 314     return(item);
 315 }
 316 
 317 int opal_tree_remove_item(opal_tree_t *tree,
 318                           opal_tree_item_t *item)
 319 {
 320     opal_tree_item_t *parent_item = NULL, *child = NULL;
 321 
 322     parent_item = (opal_tree_item_t*)item->opal_tree_parent;
 323 
 324     /*
 325      * Point each of my children to my parent
 326      */
 327     for(child  = opal_tree_get_first_child(item);
 328         child != NULL;
 329         child  = opal_tree_get_next_sibling(child)) {
 330         child->opal_tree_parent = parent_item;
 331         child->opal_tree_num_ancestors--;
 332 
 333         parent_item->opal_tree_num_children++;
 334     }
 335 
 336     /*
 337      * My first child points to my 'prev' sibling
 338      */
 339     child  = opal_tree_get_first_child(item);
 340     if( NULL != child ) {
 341         child->opal_tree_prev_sibling = item->opal_tree_prev_sibling;
 342     }
 343     if( NULL != item->opal_tree_prev_sibling ) {
 344         (item->opal_tree_prev_sibling)->opal_tree_next_sibling = child;
 345     }
 346 
 347     child  = opal_tree_get_last_child(item);
 348     if( NULL != child ) {
 349         child->opal_tree_next_sibling = item->opal_tree_next_sibling;
 350     }
 351     if( NULL != item->opal_tree_next_sibling ) {
 352         (item->opal_tree_next_sibling)->opal_tree_prev_sibling = child;
 353     }
 354 
 355     /*
 356      * Remove me from my parent.  If I was the only child, then make
 357      * the first child be my first child, and make the last child be
 358      * my last child.
 359      */
 360     if( parent_item->opal_tree_first_child == item &&
 361         parent_item->opal_tree_last_child == item ) {
 362         parent_item->opal_tree_first_child = opal_tree_get_first_child(item);
 363         parent_item->opal_tree_last_child = opal_tree_get_last_child(item);
 364     } else {
 365         /* There were multiple children.  If I was the first or last,
 366            then ensure the parent gets a valid first or last child:
 367            - If I have children, then my first/last
 368            - If I have no childen, then my immediate sibling */
 369         if (parent_item->opal_tree_first_child == item) {
 370             if (item->opal_tree_num_children > 0) {
 371                 parent_item->opal_tree_first_child =
 372                     item->opal_tree_first_child;
 373             } else {
 374                 parent_item->opal_tree_first_child =
 375                     opal_tree_get_next_sibling(item);
 376             }
 377         } else if (parent_item->opal_tree_last_child == item) {
 378             if (item->opal_tree_num_children > 0) {
 379                 parent_item->opal_tree_last_child =
 380                     item->opal_tree_last_child;
 381             } else {
 382                 parent_item->opal_tree_last_child =
 383                     opal_tree_get_prev_sibling(item);
 384             }
 385         }
 386     }
 387     parent_item->opal_tree_num_children--;
 388 
 389     return OPAL_SUCCESS;
 390 }
 391 
 392 /* delimeter characters that mark items in a serialized stream */
 393 static char *start_lvl = "[";
 394 static char *end_lvl = "]";
 395 static char *end_stream = "E";
 396 
 397 /*
 398  * add item to opal buffer that represents all items of a sub-tree from the
 399  * item passed in on down.  We exit out of converting tree items once we've
 400  * done the last child of the tree_item and we are at depth 1.
 401  */
 402 static int add_tree_item2buf(opal_tree_item_t *tree_item,
 403                              opal_buffer_t *buf,
 404                              opal_tree_item_serialize_fn_t fn,
 405                              int depth
 406                              )
 407 {
 408     opal_tree_item_t *first_child;
 409     int rc;
 410 
 411     do {
 412         /* add start delim to buffer */
 413         if (OPAL_SUCCESS !=
 414             (rc = opal_dss.pack(buf, &start_lvl, 1, OPAL_STRING))){
 415             return(rc);
 416         }
 417         /* add item to opal buffer from class creator */
 418         fn(tree_item, buf);
 419 
 420         if ((first_child = opal_tree_get_first_child(tree_item))) {
 421             /* add items for our children */
 422             if (OPAL_SUCCESS !=
 423                 (rc = add_tree_item2buf(first_child, buf, fn, depth+1))){
 424                 return(rc);
 425             }
 426             if (OPAL_SUCCESS !=
 427                 (rc = opal_dss.pack(buf, &end_lvl, 1, OPAL_STRING))){
 428                 return(rc);
 429             }
 430         } else {
 431             /* end item entry */
 432             if (OPAL_SUCCESS !=
 433                 (rc = opal_dss.pack(buf, &end_lvl, 1, OPAL_STRING))){
 434                 return(rc);
 435             }
 436         }
 437 
 438         /* advance to next sibling, if none we'll drop out of
 439          * loop and return to our parent
 440          */
 441         tree_item = opal_tree_get_next_sibling(tree_item);
 442     } while (tree_item && 1 < depth);
 443 
 444     return(OPAL_SUCCESS);
 445 }
 446 
 447 /*
 448  * serialize tree data
 449  */
 450 int opal_tree_serialize(opal_tree_item_t *start_item, opal_buffer_t *buffer)
 451 {
 452     int rc;
 453 
 454     if (OPAL_SUCCESS !=
 455         (rc = add_tree_item2buf(start_item, buffer,
 456                                 start_item->opal_tree_container->serialize,
 457                                 1))){
 458         return(rc);
 459     }
 460     if (OPAL_SUCCESS !=
 461         (rc = opal_dss.pack(buffer, &end_stream, 1, OPAL_STRING))){
 462         return(rc);
 463     }
 464     return(OPAL_SUCCESS);
 465 }
 466 
 467 static int deserialize_add_tree_item(opal_buffer_t *data,
 468                                      opal_tree_item_t *parent_item,
 469                                      opal_tree_item_deserialize_fn_t deserialize,
 470                                      char **curr_delim,
 471                                      int depth)
 472 {
 473     int idx = 1, rc;
 474     opal_tree_item_t *new_item = NULL;
 475     int level = 0; /* 0 - one up 1 - curr, 2 - one down */
 476 
 477     if (!*curr_delim) {
 478         if (OPAL_SUCCESS !=
 479             (rc = opal_dss.unpack(data, curr_delim, &idx, OPAL_STRING))) {
 480             return(rc);
 481         }
 482     }
 483     while(*curr_delim[0] != end_stream[0]) {
 484         if (*curr_delim[0] == start_lvl[0]) {
 485             level++;
 486         } else {
 487             level--;
 488         }
 489 
 490         switch (level) {
 491         case 0:
 492             if (1 < depth) {
 493                 /* done with this level go up one level */
 494                 return(OPAL_SUCCESS);
 495             }
 496             break;
 497         case 1:
 498             /* add found child at this level */
 499             deserialize(data, &new_item);
 500             opal_tree_add_child(parent_item, new_item);
 501             break;
 502         case 2:
 503             /* need to add child one level down */
 504             deserialize_add_tree_item(data, new_item, deserialize, curr_delim,
 505                                       depth+1);
 506             level--;
 507             break;
 508         }
 509         if (OPAL_SUCCESS !=
 510             (rc = opal_dss.unpack(data, curr_delim, &idx, OPAL_STRING))) {
 511             return(rc);
 512         }
 513     }
 514     return(OPAL_SUCCESS);
 515 }
 516 
 517 /*
 518  * deserialize tree data
 519  */
 520 int opal_tree_deserialize(opal_buffer_t *serialized_data,
 521                           opal_tree_item_t *start_item)
 522 {
 523     char * null = NULL;
 524     deserialize_add_tree_item(serialized_data,
 525                               start_item,
 526                               start_item->opal_tree_container->deserialize,
 527                               &null,
 528                               1);
 529     return OPAL_SUCCESS;
 530 }
 531 
 532 void * opal_tree_get_key(opal_tree_t *tree, opal_tree_item_t *item)
 533 {
 534     return tree->get_key(item);
 535 }
 536 
 537 int opal_tree_dup(opal_tree_t *from, opal_tree_t *to)
 538 {
 539     int ret;
 540     opal_buffer_t *buffer = NULL;
 541 
 542     opal_tree_init(to,
 543                    from->comp,
 544                    from->serialize,
 545                    from->deserialize,
 546                    from->get_key);
 547 
 548     buffer = OBJ_NEW(opal_buffer_t);
 549 
 550     opal_tree_serialize(opal_tree_get_root(from), buffer);
 551     ret = opal_tree_deserialize(buffer, opal_tree_get_root(to));
 552 
 553     OBJ_RELEASE(buffer);
 554     return ret;
 555 }
 556 
 557 int opal_tree_copy_subtree(opal_tree_t *from_tree, opal_tree_item_t *from_item,
 558                            opal_tree_t *to_tree,   opal_tree_item_t *to_parent)
 559 {
 560     int ret;
 561     opal_buffer_t *buffer = NULL;
 562 
 563     buffer = OBJ_NEW(opal_buffer_t);
 564 
 565     opal_tree_serialize(from_item, buffer);
 566     ret = opal_tree_deserialize(buffer, to_parent);
 567 
 568     OBJ_RELEASE(buffer);
 569     return ret;
 570 }
 571 
 572 opal_tree_item_t *opal_tree_dup_item(opal_tree_t *base, opal_tree_item_t *from)
 573 {
 574     opal_buffer_t *buffer = NULL;
 575     opal_tree_item_t *new_item = NULL;
 576 
 577     buffer = OBJ_NEW(opal_buffer_t);
 578 
 579     opal_tree_serialize(from, buffer);
 580 
 581     new_item = OBJ_NEW(opal_tree_item_t);
 582     opal_tree_deserialize(buffer, new_item);
 583 
 584     OBJ_RELEASE(buffer);
 585     return new_item;
 586 }
 587 
 588 int opal_tree_num_children(opal_tree_item_t *parent)
 589 {
 590     opal_tree_item_t *child = NULL;
 591     int i = 0;
 592 
 593     for(child  = opal_tree_get_first_child(parent);
 594         child != NULL;
 595         child  = opal_tree_get_next_sibling(child) ) {
 596         ++i;
 597     }
 598 
 599     return i;
 600 }
 601 
 602 static int opal_tree_compare_subtrees(opal_tree_t *tree_left, opal_tree_t *tree_right,
 603                                       opal_tree_item_t *left, opal_tree_item_t *right)
 604 {
 605     int ret;
 606     opal_tree_item_t *left_child = NULL, *right_child = NULL;
 607 
 608     /* Basecase */
 609     if( NULL == left && NULL == right ) {
 610         return 0; /* Match */
 611     }
 612 
 613     /* Compare: Depth */
 614     if( NULL == left && NULL != right ) {
 615         return -1;
 616     }
 617     else if( NULL != left && NULL == right ) {
 618         return 1;
 619     }
 620 
 621     /* Compare: Keys */
 622     if( 0 != tree_left->comp(right, opal_tree_get_key(tree_left, left)) ) {
 623         return -2;
 624     }
 625 
 626     /* Compare: Number of children */
 627     if( opal_tree_num_children(left) != opal_tree_num_children(right) ) {
 628         return 2;
 629     }
 630 
 631     /* Recursively compare all children */
 632     for(left_child  = opal_tree_get_first_child(left),        right_child  = opal_tree_get_first_child(right);
 633         left_child != NULL &&                                 right_child != NULL;
 634         left_child  = opal_tree_get_next_sibling(left_child), right_child  = opal_tree_get_next_sibling(right_child) ) {
 635         /* On first difference, return the result */
 636         if( 0 != (ret = opal_tree_compare_subtrees(tree_left, tree_right, left_child, right_child)) ) {
 637             return ret;
 638         }
 639     }
 640 
 641     return 0;
 642 }
 643 
 644 int opal_tree_compare(opal_tree_t *left, opal_tree_t *right)
 645 {
 646     return opal_tree_compare_subtrees(left, right, opal_tree_get_root(left), opal_tree_get_root(right));
 647 }
 648 
 649 /*
 650  * search myself, descendants and siblings for item matching key
 651  */
 652 static opal_tree_item_t *find_in_descendants(opal_tree_item_t* item, void *key)
 653 {
 654     opal_tree_item_t *result = NULL, *first_child;
 655 
 656     while (!result && item) {
 657         /* check for item match */
 658         result = (item->opal_tree_container->comp(item, key) == 0) ?
 659             item : NULL;
 660         if (!result && (first_child = opal_tree_get_first_child(item))) {
 661             /* search descendants for match */
 662             result = find_in_descendants(first_child, key);
 663         }
 664         if (!result) {
 665             /* didn't find match at our node or descending so check sibling */
 666             item = opal_tree_get_next_sibling(item);
 667         }
 668     }
 669     return(result);
 670 }
 671 
 672 /*
 673  * return next tree item that matches key
 674  */
 675 opal_tree_item_t *opal_tree_find_with(opal_tree_item_t *item, void *key)
 676 {
 677     opal_tree_item_t *curr_item = item, *result = NULL;
 678 
 679     if (!opal_tree_is_empty(item->opal_tree_container)) {
 680         /* check my descendant for a match */
 681         result = find_in_descendants(opal_tree_get_first_child(item), key);
 682 
 683         if (!result) {
 684             /* check my siblings for match */
 685             if (NULL != (curr_item = opal_tree_get_next_sibling(curr_item))) {
 686                 result = find_in_descendants(curr_item, key);
 687             }
 688         }
 689 
 690         /* check my ancestors (uncles) for match */
 691         curr_item = item;
 692         while (!result && curr_item && curr_item->opal_tree_num_ancestors > 0){
 693             curr_item = opal_tree_get_next_sibling(item->opal_tree_parent);
 694             while (NULL == curr_item &&
 695                    item->opal_tree_parent->opal_tree_num_ancestors > 0) {
 696                 item = item->opal_tree_parent;
 697                 curr_item = opal_tree_get_next_sibling(item->opal_tree_parent);
 698             }
 699             if (curr_item) {
 700                 /* search ancestors descendants for match */
 701                 result = find_in_descendants(curr_item, key);
 702             }
 703         }
 704     }
 705 
 706     return(result);
 707 }
/* [<][>][^][v][top][bottom][index][help] */
root/opal/class/opal_tree.c

DEFINITIONS
