src/lib/ecore/ecore_tree.c

   1 #include "ecore_private.h"
   2 #include "Ecore.h"
   3 #include "Ecore_Data.h"
   4
   5 /* A macro for determining the highest node at given branch */
   6 #define MAX_HEIGHT(node) (node ? MAX(node->max_left, node->max_right) : 0)
   7
   8 /* Utility functions for searching the tree and returning a node, or its
   9  * parent */
  10 static Ecore_Tree_Node *tree_node_find(Ecore_Tree * tree, const void *key);
  11 static Ecore_Tree_Node *tree_node_find_parent(Ecore_Tree * tree, const void *key);
  12
  13 /* Balancing functions, keep the tree balanced within a one node height
  14  * difference */
  15 static int tree_node_balance(Ecore_Tree * Tree, Ecore_Tree_Node * top_node);
  16 static int tree_node_rotate_right(Ecore_Tree * tree, Ecore_Tree_Node * top_node);
  17 static int tree_node_rotate_left(Ecore_Tree * tree, Ecore_Tree_Node * top_node);
  18
  19 /* Fucntions for executing a specified function on each node of a tree */
  20 static int tree_for_each_node(Ecore_Tree_Node * node, Ecore_For_Each for_each_func,
  21                               void *user_data);
  22 static int tree_for_each_node_value(Ecore_Tree_Node * node,
  23                                     Ecore_For_Each for_each_func, void *user_data);
  24
  25 /**
  26  * @brief Allocate a new tree structure.
  27  * @param compare_func: function used to compare the two values
  28  * @return Returns NULL if the operation fails, otherwise the new tree
  29  */
  30 EAPI Ecore_Tree *
  31 ecore_tree_new(Ecore_Compare_Cb compare_func)
  32 {
  33    Ecore_Tree *new_tree;
  34
  35    new_tree = ECORE_TREE(malloc(sizeof(Ecore_Tree)));
  36    if (!new_tree)
  37      return NULL;
  38
  39    if (!ecore_tree_init(new_tree, compare_func))
  40      {
  41         IF_FREE(new_tree);
  42         return NULL;
  43      }
  44
  45    return new_tree;
  46 }
  47
  48 /**
  49  * @brief Initialize a tree structure to some sane initial values
  50  * @param new_tree: the new tree structure to be initialized
  51  * @param compare_func: the function used to compare node keys
  52  * @return Returns TRUE on successful initialization, FALSE on an error
  53  */
  54 EAPI int
  55 ecore_tree_init(Ecore_Tree *new_tree, Ecore_Compare_Cb compare_func)
  56 {
  57    CHECK_PARAM_POINTER_RETURN("new_tree", new_tree, FALSE);
  58
  59    memset(new_tree, 0, sizeof(Ecore_Tree));
  60
  61    if (!compare_func)
  62      new_tree->compare_func = ecore_direct_compare;
  63    else
  64      new_tree->compare_func = compare_func;
  65
  66    return TRUE;
  67 }
  68
  69 /*
  70  * @brief Add a function to be called at node destroy time
  71  * @param tree: the tree that will use this function when nodes are destroyed
  72  * @param free_func: the function that will be passed the node being freed
  73  * @return Returns TRUE on successful set, FALSE otherwise.
  74  */
  75 EAPI int
  76 ecore_tree_free_value_cb_set(Ecore_Tree *tree, Ecore_Free_Cb free_value)
  77 {
  78    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
  79
  80    tree->free_value = free_value;
  81
  82    return TRUE;
  83 }
  84
  85 /*
  86  * @brief Add a function to be called at node destroy time
  87  * @param tree: the tree that will use this function when nodes are destroyed
  88  * @param free_key: the function that will be passed the node being freed
  89  * @return Returns TRUE on successful set, FALSE otherwise.
  90  */
  91 EAPI int
  92 ecore_tree_free_key_cb_set(Ecore_Tree *tree, Ecore_Free_Cb free_key)
  93 {
  94    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
  95
  96    tree->free_key = free_key;
  97
  98    return TRUE;
  99 }
 100
 101 /*
 102  * @brief Initialize a new tree node
 103  * @return Returns FALSE if the operation fails, otherwise TRUE
 104  */
 105 EAPI int
 106 ecore_tree_node_init(Ecore_Tree_Node *new_node)
 107 {
 108    CHECK_PARAM_POINTER_RETURN("new_node", new_node, FALSE);
 109
 110    new_node->key = NULL;
 111    new_node->value = NULL;
 112
 113    new_node->parent = NULL;
 114    new_node->right_child = NULL;
 115    new_node->left_child = NULL;
 116
 117    new_node->max_left = new_node->max_right = 0;
 118
 119    return TRUE;
 120 }
 121
 122 /*
 123  * @brief Allocate a new tree node
 124  * @return Returns NULL if the operation fails, otherwise the new node.
 125  */
 126 EAPI Ecore_Tree_Node *
 127 ecore_tree_node_new()
 128 {
 129    Ecore_Tree_Node *new_node;
 130
 131    new_node = ECORE_TREE_NODE(malloc(sizeof(Ecore_Tree_Node)));
 132    if (!new_node)
 133      return NULL;
 134
 135    if (!ecore_tree_node_init(new_node))
 136      {
 137         IF_FREE(new_node);
 138         return NULL;
 139      }
 140
 141    return new_node;
 142 }
 143
 144 /*
 145  * @brief Free a tree node and it's children.
 146  * @param node: tree node to be free()'d
 147  * @param data_free: callback for destroying the data held in node
 148  * @return Returns TRUE if the node is destroyed successfully, FALSE if not.
 149  *
 150  * If you don't want the children free'd then you need to remove the node first.
 151  */
 152 EAPI int
 153 ecore_tree_node_destroy(Ecore_Tree_Node *node, Ecore_Free_Cb value_free, Ecore_Free_Cb key_free)
 154 {
 155    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 156
 157    if (key_free)
 158      key_free(node->key);
 159    if (value_free)
 160      value_free(node->value);
 161
 162    FREE(node);
 163
 164    return TRUE;
 165 }
 166
 167 /*
 168  * @brief Set the value of the node to value
 169  * @param node: the node to be set
 170  * @param value: the value to set the node to.
 171  * @return Returns TRUE if the node is set successfully, FALSE if not.
 172  */
 173 EAPI int
 174 ecore_tree_node_value_set(Ecore_Tree_Node *node, void *value)
 175 {
 176    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 177
 178    node->value = value;
 179
 180    return TRUE;
 181 }
 182
 183 /*
 184  * @brief Get the value of the node
 185  * @param node: the node that contains the desired value
 186  * @return Returns NULL if an error, otherwise the value associated with node
 187  */
 188 EAPI void *
 189 ecore_tree_node_value_get(Ecore_Tree_Node *node)
 190 {
 191    void *ret;
 192
 193    CHECK_PARAM_POINTER_RETURN("node", node, NULL);
 194    ret = node->value;
 195
 196    return ret;
 197 }
 198
 199 /*
 200  * @brief Set the value of the node's key  to key
 201  * @param node: the node to be set
 202  * @param key: the value to set it's key to.
 203  * @return Returns TRUE if the node is set successfully, FALSE if not.
 204  */
 205 EAPI int
 206 ecore_tree_node_key_set(Ecore_Tree_Node *node, void *key)
 207 {
 208    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 209
 210    node->key = key;
 211
 212    return TRUE;
 213 }
 214
 215 /*
 216  * @brief Get the value of the node's key
 217  * @param node: the node that contains the desired key
 218  *
 219  * @return Returns NULL if an error occurs, otherwise the key is returned
 220  */
 221 EAPI void *
 222 ecore_tree_node_key_get(Ecore_Tree_Node *node)
 223 {
 224    void *ret;
 225
 226    CHECK_PARAM_POINTER_RETURN("node", node, NULL);
 227    ret = node->key;
 228
 229    return ret;
 230 }
 231
 232 /**
 233  * @brief Free the tree and it's stored data
 234  * @param tree: the tree to destroy
 235  *
 236  * @return Returns TRUE if tree destroyed successfully, FALSE if not.
 237  */
 238 EAPI int
 239 ecore_tree_destroy(Ecore_Tree *tree)
 240 {
 241    Ecore_Tree_Node *node;
 242
 243    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 244
 245    while ((node = tree->tree))
 246      {
 247         ecore_tree_node_remove(tree, node);
 248         ecore_tree_node_destroy(node, tree->free_value, tree->free_key);
 249      }
 250
 251    FREE(tree);
 252
 253    return TRUE;
 254 }
 255
 256 /**
 257  * @brief Return the node corresponding to key
 258  * @param tree: the tree to search
 259  * @param key: the key to search for in the tree
 260  *
 261  * @return Returns the node corresponding to the key if found, otherwise NULL.
 262  */
 263 EAPI Ecore_Tree_Node *
 264 ecore_tree_get_node(Ecore_Tree *tree, const void *key)
 265 {
 266    Ecore_Tree_Node *ret;
 267
 268    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 269
 270    ret = tree_node_find(tree, key);
 271
 272    return ret;
 273 }
 274
 275 /**
 276  * @brief Return the value corresponding to key
 277  * @param tree: the tree to search
 278  * @param key: the key to search for in @a tree
 279  * @return Returns the value corresponding to the key if found, otherwise NULL.
 280  */
 281 EAPI void *
 282 ecore_tree_get(Ecore_Tree *tree, const void *key)
 283 {
 284    void *ret;
 285    Ecore_Tree_Node *node;
 286
 287    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 288
 289    node = tree_node_find(tree, key);
 290    ret = (node ? node->value : NULL);
 291
 292    return ret;
 293 }
 294
 295 /**
 296  * @brief Find the closest value greater than or equal to the key.
 297  * @param  tree The tree to search.
 298  * @param  key  The key to search for in @a tree.
 299  * @return NULL if no valid nodes, otherwise the node greater than or
 300  *         equal to the key
 301  */
 302 EAPI void *
 303 ecore_tree_closest_larger_get(Ecore_Tree *tree, const void *key)
 304 {
 305    Ecore_Tree_Node *node;
 306
 307    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 308
 309    node = tree_node_find(tree, key);
 310    if (node)
 311      return node;
 312
 313    node = tree_node_find_parent(tree, key);
 314    if (!node)
 315      return NULL;
 316
 317    if (tree->compare_func(node->key, key) < 0)
 318      return NULL;
 319
 320    return node;
 321 }
 322
 323 /**
 324  * @brief Find the closest value <= key
 325  * @param tree the tree to search
 326  * @param key  the key to search for in tree
 327  * @return Returns NULL if no valid nodes, otherwise the node <= key
 328  */
 329 EAPI void *
 330 ecore_tree_closest_smaller_get(Ecore_Tree *tree, const void *key)
 331 {
 332    Ecore_Tree_Node *node;
 333
 334    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 335
 336    node = tree_node_find(tree, key);
 337    if (node)
 338      return node;
 339
 340    node = tree_node_find_parent(tree, key);
 341    if (node)
 342      node = node->right_child;
 343
 344    return node;
 345 }
 346
 347 /**
 348  * Set the value associated with key to @a value.
 349  * @param  tree  The tree that contains the key/value pair.
 350  * @param  key   The key to identify which node to set a value.
 351  * @param  value Value to set the found node.
 352  * @return TRUE if successful, FALSE if not.
 353  */
 354 EAPI int
 355 ecore_tree_set(Ecore_Tree *tree, void *key, void *value)
 356 {
 357    Ecore_Tree_Node *node = NULL;
 358
 359    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 360
 361    node = tree_node_find(tree, key);
 362    if (!node)
 363      {
 364         node = ecore_tree_node_new();
 365         ecore_tree_node_key_set(node, key);
 366         if (!ecore_tree_node_add(tree, node))
 367           return FALSE;
 368      }
 369    else
 370      {
 371         if (tree->free_key)
 372           tree->free_key(key);
 373         if (node->value && tree->free_value)
 374           tree->free_value(node->value);
 375      }
 376
 377    ecore_tree_node_value_set(node, value);
 378
 379    for (; node; node = node->parent)
 380      tree_node_balance(tree, node);
 381
 382    return TRUE;
 383 }
 384
 385 /**
 386  * Place a node in the tree.
 387  * @param tree The tree to add @a node.
 388  * @param node The node to add to @a tree.
 389  * @return TRUE on a successful add, FALSE otherwise.
 390  */
 391 EAPI int
 392 ecore_tree_node_add(Ecore_Tree *tree, Ecore_Tree_Node *node)
 393 {
 394    Ecore_Tree_Node *travel = NULL;
 395
 396    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 397    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 398
 399    /* Find where to put this new node. */
 400    if (!tree->tree)
 401      tree->tree = node;
 402    else
 403      {
 404         travel = tree_node_find_parent(tree, node->key);
 405         node->parent = travel;
 406
 407         /* The node is less than travel */
 408         if (tree->compare_func(node->key, travel->key) < 0)
 409           {
 410              travel->right_child = node;
 411              travel->max_left = 1;
 412              /* The node is greater than travel */
 413           }
 414         else
 415           {
 416              travel->left_child = node;
 417              travel->max_right = 1;
 418           }
 419      }
 420
 421    return TRUE;
 422 }
 423
 424 /**
 425  * Remove the node from the tree.
 426  * @param  tree The tree to remove @a node from.
 427  * @param  node The node to remove from @a tree.
 428  * @return TRUE on a successful remove, FALSE otherwise.
 429  */
 430 EAPI int
 431 ecore_tree_node_remove(Ecore_Tree *tree, Ecore_Tree_Node *node)
 432 {
 433    Ecore_Tree_Node *traverse;
 434
 435    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 436    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 437
 438    /*
 439     * Find the nearest value to the balanced one.
 440     */
 441    if (node->left_child)
 442      {
 443         traverse = node->left_child;
 444
 445         /* Now work our way down right side of the traverse node.
 446          * This will give us the node with the next closest value
 447          * to the current node. If traverse had no right node, then
 448          * this will stop at node's left node. */
 449         while (traverse->right_child)
 450           {
 451              traverse = traverse->right_child;
 452           }
 453
 454         /*
 455          * Hook any dropped leaves into the moved nodes spot
 456          */
 457         if (traverse->parent)
 458           traverse->parent->left_child = traverse->left_child;
 459      }
 460    else if (node->right_child)
 461      {
 462         traverse = node->right_child;
 463
 464         /* Now work our way down left side of the traverse node.
 465          * This will give us the node with the next closest value
 466          * to the current node. If traverse had no left node, then
 467          * this will stop at node's right node. */
 468         while (traverse->left_child)
 469           {
 470              traverse = traverse->left_child;
 471           }
 472
 473         /*
 474          * Hook any dropped leaves into the moved nodes spot
 475          */
 476         if (traverse->right_child)
 477           traverse->right_child->parent = traverse->parent;
 478
 479         if (traverse->parent)
 480           traverse->parent->right_child = traverse->right_child;
 481         else
 482           tree->tree = traverse->right_child;
 483      }
 484    else
 485      traverse = NULL;
 486
 487    if (traverse)
 488      {
 489
 490         /*
 491          * Ensure that we don't get a recursive reference.
 492          */
 493         if (node->right_child && node->right_child != traverse)
 494           {
 495              node->right_child->parent = traverse;
 496              traverse->right_child = node->right_child;
 497           }
 498
 499         if (node->left_child && node->left_child != traverse)
 500           {
 501              node->left_child->parent = traverse;
 502              traverse->left_child = node->left_child;
 503           }
 504
 505         /*
 506          * Unlink the node to be moved from it's parent.
 507          */
 508         if (traverse->parent)
 509           {
 510              if (traverse->parent->left_child == traverse)
 511                traverse->parent->left_child = NULL;
 512              else
 513                traverse->parent->right_child = NULL;
 514           }
 515         traverse->parent = node->parent;
 516      }
 517
 518    if (node->parent)
 519      {
 520         if (node == node->parent->left_child)
 521           node->parent->left_child = traverse;
 522         else
 523           node->parent->right_child = traverse;
 524      }
 525
 526    if (tree->tree == node)
 527      tree->tree = traverse;
 528
 529    node->parent = node->left_child = node->right_child = NULL;
 530
 531    /*
 532     * Rebalance the tree to ensure short search paths.
 533     */
 534    while (traverse)
 535      {
 536         tree_node_balance(tree, traverse);
 537         traverse = traverse->parent;
 538      }
 539
 540    return TRUE;
 541 }
 542
 543 /**
 544  * Remove the key from the tree.
 545  * @param  tree The tree to remove @a key.
 546  * @param  key  The key to remove from @a tree.
 547  * @return TRUE on a successful remove, FALSE otherwise.
 548  */
 549 EAPI int
 550 ecore_tree_remove(Ecore_Tree *tree, const void *key)
 551 {
 552    Ecore_Tree_Node *node;
 553
 554    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 555    if (!tree->tree)
 556      return FALSE;
 557
 558    /* Find the node we need to remove */
 559    node = tree_node_find(tree, key);
 560    if (!node)
 561      return FALSE;
 562
 563    if (!ecore_tree_node_remove(tree, node))
 564      return FALSE;
 565
 566    ecore_tree_node_destroy(node, tree->free_value, tree->free_key);
 567
 568    return TRUE;
 569 }
 570
 571 /**
 572  * @brief Test to see if the tree has any nodes
 573  * @param tree: the tree to check for nodes
 574  * @return Returns TRUE if no nodes exist, FALSE otherwise
 575  */
 576 EAPI int
 577 ecore_tree_empty_is(Ecore_Tree *tree)
 578 {
 579    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 580
 581    if (!tree->tree)
 582      return TRUE;
 583
 584    return FALSE;
 585 }
 586
 587 /**
 588  * @brief Execute function for each value in the tree
 589  * @param tree: the tree to traverse
 590  * @param for_each_func: the function to execute for each value in the tree
 591  * @param user_data: data passed to each for_each_func call
 592  * @return Returns TRUE on success, FALSE on failure.
 593  */
 594 EAPI int
 595 ecore_tree_for_each_node_value(Ecore_Tree *tree, Ecore_For_Each for_each_func, void *user_data)
 596 {
 597    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 598    CHECK_PARAM_POINTER_RETURN("for_each_func", for_each_func, FALSE);
 599
 600    if (!tree->tree)
 601      return FALSE;
 602
 603    return tree_for_each_node_value(tree->tree, for_each_func, user_data);
 604 }
 605
 606 /**
 607  * @brief Execute the function for each node in the tree
 608  * @param tree: the tree to traverse
 609  * @param for_each_func: the function to execute for each node
 610  * @param user_data: data passed to each for_each_func call
 611  * @return Returns TRUE on success, FALSE on failure.
 612  */
 613 EAPI int
 614 ecore_tree_for_each_node(Ecore_Tree *tree, Ecore_For_Each for_each_func, void *user_data)
 615 {
 616    CHECK_PARAM_POINTER_RETURN("tree", tree, FALSE);
 617    CHECK_PARAM_POINTER_RETURN("for_each_func", for_each_func, FALSE);
 618
 619    if (!tree->tree)
 620      return FALSE;
 621
 622    return tree_for_each_node(tree->tree, for_each_func, user_data);
 623 }
 624
 625 /* Find the parent for the key */
 626 static Ecore_Tree_Node *
 627 tree_node_find_parent(Ecore_Tree *tree, const void *key)
 628 {
 629    Ecore_Tree_Node *parent, *travel;
 630
 631    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 632
 633    parent = tree_node_find(tree, key);
 634    if (parent)
 635      parent = parent->parent;
 636
 637    travel = tree->tree;
 638    if (!travel)
 639      return NULL;
 640
 641    while (!parent)
 642      {
 643         int compare;
 644
 645         if ((compare = tree->compare_func(key, travel->key)) < 0)
 646           {
 647              if (!travel->right_child)
 648                parent = travel;
 649              travel = travel->right_child;
 650           }
 651         else
 652           {
 653              if (!travel->left_child)
 654                parent = travel;
 655              travel = travel->left_child;
 656           }
 657      }
 658
 659    return parent;
 660 }
 661
 662 /* Search for the node with a specified key */
 663 static Ecore_Tree_Node *
 664 tree_node_find(Ecore_Tree *tree, const void *key)
 665 {
 666    int compare;
 667    Ecore_Tree_Node *node;
 668
 669    CHECK_PARAM_POINTER_RETURN("tree", tree, NULL);
 670
 671    node = tree->tree;
 672    while (node && (compare = tree->compare_func(key, node->key)) != 0)
 673      {
 674
 675         if (compare < 0)
 676           {
 677              if (!node->right_child)
 678                return NULL;
 679
 680              node = node->right_child;
 681           }
 682         else
 683           {
 684              if (!node->left_child)
 685                return NULL;
 686
 687              node = node->left_child;
 688           }
 689      }
 690
 691    return node;
 692 }
 693
 694 /* Balance the tree with respect to node */
 695 static int
 696 tree_node_balance(Ecore_Tree *tree, Ecore_Tree_Node *top_node)
 697 {
 698    int balance;
 699
 700    CHECK_PARAM_POINTER_RETURN("top_node", top_node, FALSE);
 701
 702    /* Get the height of the left branch. */
 703    if (top_node->right_child)
 704      top_node->max_left = MAX_HEIGHT(top_node->right_child) + 1;
 705    else
 706      top_node->max_left = 0;
 707
 708    /* Get the height of the right branch. */
 709    if (top_node->left_child)
 710      top_node->max_right = MAX_HEIGHT(top_node->left_child) + 1;
 711    else
 712      top_node->max_right = 0;
 713
 714    /* Determine which side has a larger height. */
 715    balance = top_node->max_right - top_node->max_left;
 716
 717    /* if the left side has a height advantage >1 rotate right */
 718    if (balance < -1)
 719      tree_node_rotate_right(tree, top_node);
 720    /* else if the left side has a height advantage >1 rotate left */
 721    else if (balance > 1)
 722      tree_node_rotate_left(tree, top_node);
 723
 724    return TRUE;
 725 }
 726
 727 /* Tree is overbalanced to the left, so rotate nodes to the right. */
 728 static int
 729 tree_node_rotate_right(Ecore_Tree *tree, Ecore_Tree_Node *top_node)
 730 {
 731    Ecore_Tree_Node *temp;
 732
 733    CHECK_PARAM_POINTER_RETURN("top_node", top_node, FALSE);
 734
 735    /* The left branch's right branch becomes the nodes left branch,
 736     * the left branch becomes the top node, and the node becomes the
 737     * right branch. */
 738    temp = top_node->right_child;
 739    top_node->right_child = temp->left_child;
 740    temp->left_child = top_node;
 741
 742    /* Make sure the nodes know who their new parents are and the tree
 743     * structure knows the start of the tree. */
 744    temp->parent = top_node->parent;
 745    if (temp->parent == NULL)
 746      tree->tree = temp;
 747    else
 748      {
 749         if (temp->parent->left_child == top_node)
 750           temp->parent->left_child = temp;
 751         else
 752           temp->parent->right_child = temp;
 753      }
 754    top_node->parent = temp;
 755
 756    /* And recalculate node heights */
 757    tree_node_balance(tree, top_node);
 758    tree_node_balance(tree, temp);
 759
 760    return TRUE;
 761 }
 762
 763 /* The tree is overbalanced to the right, so we rotate nodes to the left */
 764 static int
 765 tree_node_rotate_left(Ecore_Tree *tree, Ecore_Tree_Node *top_node)
 766 {
 767    Ecore_Tree_Node *temp;
 768
 769    CHECK_PARAM_POINTER_RETURN("top_node", top_node, FALSE);
 770
 771    /*
 772     * The right branch's left branch becomes the nodes right branch,
 773     * the right branch becomes the top node, and the node becomes the
 774     * left branch.
 775     */
 776    temp = top_node->left_child;
 777    top_node->left_child = temp->right_child;
 778    temp->right_child = top_node;
 779
 780    /* Make sure the nodes know who their new parents are. */
 781    temp->parent = top_node->parent;
 782    if (temp->parent == NULL)
 783      tree->tree = temp;
 784    else
 785      {
 786         if (temp->parent->left_child == top_node)
 787           temp->parent->left_child = temp;
 788         else
 789           temp->parent->right_child = temp;
 790      }
 791    top_node->parent = temp;
 792
 793    /* And recalculate node heights */
 794    tree_node_balance(tree, top_node);
 795    tree_node_balance(tree, temp);
 796
 797    return TRUE;
 798 }
 799
 800 /*
 801  * @brief Execute a function for each node below this point in the tree.
 802  * @param node: the highest node in the tree the function will be executed for
 803  * @param for_each_func: the function to pass the nodes as data into
 804  * @param user_data: data passed to each for_each_func call
 805  * @return Returns FALSE if an error condition occurs, otherwise TRUE
 806  */
 807 static int
 808 tree_for_each_node(Ecore_Tree_Node * node, Ecore_For_Each for_each_func, void *user_data)
 809 {
 810    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 811
 812    if (node->right_child)
 813      tree_for_each_node(node->right_child, for_each_func, user_data);
 814
 815    if (node->left_child)
 816      tree_for_each_node(node->left_child, for_each_func, user_data);
 817
 818    for_each_func(node, user_data);
 819
 820    return TRUE;
 821 }
 822
 823 /*
 824  * @brief Execute a function for each node below this point in the tree.
 825  * @param node: the highest node in the tree the function will be executed for
 826  * @param for_each_func: the function to pass the nodes values as data
 827  * @return Returns FALSE if an error condition occurs, otherwise TRUE
 828  */
 829 static int
 830 tree_for_each_node_value(Ecore_Tree_Node *node, Ecore_For_Each for_each_func, void *user_data)
 831 {
 832    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 833
 834    if (node->right_child)
 835      tree_for_each_node_value(node->right_child, for_each_func, user_data);
 836
 837    if (node->left_child)
 838      tree_for_each_node_value(node->left_child, for_each_func, user_data);
 839
 840    for_each_func(node->value, user_data);
 841
 842    return TRUE;
 843 }