astobj2_rbtree.c

Go to the documentation of this file.
00001 /*
00002  * astobj2_hash - RBTree implementation for astobj2.
00003  *
00004  * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
00005  *
00006  * See http://www.asterisk.org for more information about
00007  * the Asterisk project. Please do not directly contact
00008  * any of the maintainers of this project for assistance;
00009  * the project provides a web site, mailing lists and IRC
00010  * channels for your use.
00011  *
00012  * This program is free software, distributed under the terms of
00013  * the GNU General Public License Version 2. See the LICENSE file
00014  * at the top of the source tree.
00015  */
00016 
00017 /*! \file
00018  *
00019  * \brief RBTree functions implementing astobj2 containers.
00020  *
00021  * \author Richard Mudgett <rmudgett@digium.com>
00022  */
00023 
00024 #include "asterisk.h"
00025 
00026 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 416807 $")
00027 
00028 #include "asterisk/_private.h"
00029 #include "asterisk/astobj2.h"
00030 #include "asterisk/utils.h"
00031 #include "astobj2_private.h"
00032 #include "astobj2_container_private.h"
00033 
00034 /*!
00035  * A structure to hold the object held by the container and
00036  * where it is located in it.
00037  *
00038  * A red-black tree has the following properties:
00039  *
00040  * 1) Every node is either black or red.
00041  *
00042  * 2) The root is black.
00043  *
00044  * 3) If a node has a NULL child, that "child" is considered
00045  * black.
00046  *
00047  * 4) If a node is red, then both of its children are black.
00048  *
00049  * 5) Every path from a node to a descendant NULL child has the
00050  * same number of black nodes.  (Including the black NULL
00051  * child.)
00052  */
00053 struct rbtree_node {
00054    /*!
00055     * \brief Items common to all container nodes.
00056     * \note Must be first in the specific node struct.
00057     */
00058    struct ao2_container_node common;
00059    /*! Parent node of this node. NULL if this is the root node. */
00060    struct rbtree_node *parent;
00061    /*! Left child node of this node.  NULL if does not have this child. */
00062    struct rbtree_node *left;
00063    /*! Right child node of this node.  NULL if does not have this child. */
00064    struct rbtree_node *right;
00065    /*! TRUE if the node is red. */
00066    unsigned int is_red:1;
00067 };
00068 
00069 /*!
00070  * A rbtree container in addition to values common to all
00071  * container types, stores the pointer to the root node of the
00072  * tree.
00073  */
00074 struct ao2_container_rbtree {
00075    /*!
00076     * \brief Items common to all containers.
00077     * \note Must be first in the specific container struct.
00078     */
00079    struct ao2_container common;
00080    /*! Root node of the tree.  NULL if the tree is empty. */
00081    struct rbtree_node *root;
00082 #if defined(AO2_DEBUG)
00083    struct {
00084       /*! Fixup insert left cases 1-3 */
00085       int fixup_insert_left[3];
00086       /*! Fixup insert right cases 1-3 */
00087       int fixup_insert_right[3];
00088       /*! Fixup delete left cases 1-4 */
00089       int fixup_delete_left[4];
00090       /*! Fixup delete right cases 1-4 */
00091       int fixup_delete_right[4];
00092       /*! Deletion of node with number of children (0-2). */
00093       int delete_children[3];
00094    } stats;
00095 #endif   /* defined(AO2_DEBUG) */
00096 };
00097 
00098 enum equal_node_bias {
00099    /*! Bias search toward first matching node in the container. */
00100    BIAS_FIRST,
00101    /*! Bias search toward any matching node. */
00102    BIAS_EQUAL,
00103    /*! Bias search toward last matching node in the container. */
00104    BIAS_LAST,
00105 };
00106 
00107 enum empty_node_direction {
00108    GO_LEFT,
00109    GO_RIGHT,
00110 };
00111 
00112 /*! Traversal state to restart a rbtree container traversal. */
00113 struct rbtree_traversal_state {
00114    /*! Active sort function in the traversal if not NULL. */
00115    ao2_sort_fn *sort_fn;
00116    /*! Saved comparison callback arg pointer. */
00117    void *arg;
00118    /*! Saved search flags to control traversing the container. */
00119    enum search_flags flags;
00120 };
00121 
00122 struct rbtree_traversal_state_check {
00123    /*
00124     * If we have a division by zero compile error here then there
00125     * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
00126     */
00127    char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct rbtree_traversal_state))];
00128 };
00129 
00130 /*!
00131  * \internal
00132  * \brief Get the most left node in the tree.
00133  * \since 12.0.0
00134  *
00135  * \param node Starting node to find the most left node.
00136  *
00137  * \return Left most node.  Never NULL.
00138  */
00139 static struct rbtree_node *rb_node_most_left(struct rbtree_node *node)
00140 {
00141    while (node->left) {
00142       node = node->left;
00143    }
00144 
00145    return node;
00146 }
00147 
00148 /*!
00149  * \internal
00150  * \brief Get the most right node in the tree.
00151  * \since 12.0.0
00152  *
00153  * \param node Starting node to find the most right node.
00154  *
00155  * \return Right most node.  Never NULL.
00156  */
00157 static struct rbtree_node *rb_node_most_right(struct rbtree_node *node)
00158 {
00159    while (node->right) {
00160       node = node->right;
00161    }
00162 
00163    return node;
00164 }
00165 
00166 /*!
00167  * \internal
00168  * \brief Get the next node in ascending sequence.
00169  * \since 12.0.0
00170  *
00171  * \param node Starting node to find the next node.
00172  *
00173  * \retval node on success.
00174  * \retval NULL if no node.
00175  */
00176 static struct rbtree_node *rb_node_next(struct rbtree_node *node)
00177 {
00178    if (node->right) {
00179       return rb_node_most_left(node->right);
00180    }
00181 
00182    /* Find the parent that the node is a left child of. */
00183    while (node->parent) {
00184       if (node->parent->left == node) {
00185          /* We are the left child.  The parent is the next node. */
00186          return node->parent;
00187       }
00188       node = node->parent;
00189    }
00190    return NULL;
00191 }
00192 
00193 /*!
00194  * \internal
00195  * \brief Get the next node in descending sequence.
00196  * \since 12.0.0
00197  *
00198  * \param node Starting node to find the previous node.
00199  *
00200  * \retval node on success.
00201  * \retval NULL if no node.
00202  */
00203 static struct rbtree_node *rb_node_prev(struct rbtree_node *node)
00204 {
00205    if (node->left) {
00206       return rb_node_most_right(node->left);
00207    }
00208 
00209    /* Find the parent that the node is a right child of. */
00210    while (node->parent) {
00211       if (node->parent->right == node) {
00212          /* We are the right child.  The parent is the previous node. */
00213          return node->parent;
00214       }
00215       node = node->parent;
00216    }
00217    return NULL;
00218 }
00219 
00220 /*!
00221  * \internal
00222  * \brief Get the next node in pre-order sequence.
00223  * \since 12.0.0
00224  *
00225  * \param node Starting node to find the next node.
00226  *
00227  * \retval node on success.
00228  * \retval NULL if no node.
00229  */
00230 static struct rbtree_node *rb_node_pre(struct rbtree_node *node)
00231 {
00232    /* Visit the children if the node has any. */
00233    if (node->left) {
00234       return node->left;
00235    }
00236    if (node->right) {
00237       return node->right;
00238    }
00239 
00240    /* Time to go back up. */
00241    for (;;) {
00242       if (!node->parent) {
00243          return NULL;
00244       }
00245       if (node->parent->left == node && node->parent->right) {
00246          /*
00247           * We came up the left child and there's a right child.  Visit
00248           * it.
00249           */
00250          return node->parent->right;
00251       }
00252       node = node->parent;
00253    }
00254 }
00255 
00256 /*!
00257  * \internal
00258  * \brief Get the next node in post-order sequence.
00259  * \since 12.0.0
00260  *
00261  * \param node Starting node to find the next node.
00262  *
00263  * \retval node on success.
00264  * \retval NULL if no node.
00265  */
00266 static struct rbtree_node *rb_node_post(struct rbtree_node *node)
00267 {
00268    /* This node's children have already been visited. */
00269    for (;;) {
00270       if (!node->parent) {
00271          return NULL;
00272       }
00273       if (node->parent->left == node) {
00274          /* We came up the left child. */
00275          node = node->parent;
00276 
00277          /*
00278           * Find the right child's left most childless node.
00279           */
00280          while (node->right) {
00281             node = rb_node_most_left(node->right);
00282          }
00283 
00284          /*
00285           * This node's left child has already been visited or it doesn't
00286           * have any children.
00287           */
00288          return node;
00289       }
00290 
00291       /*
00292        * We came up the right child.
00293        *
00294        * This node's children have already been visited.  Time to
00295        * visit the parent.
00296        */
00297       return node->parent;
00298    }
00299 }
00300 
00301 /*!
00302  * \internal
00303  * \brief Get the next non-empty node in ascending sequence.
00304  * \since 12.0.0
00305  *
00306  * \param node Starting node to find the next node.
00307  *
00308  * \retval node on success.
00309  * \retval NULL if no node.
00310  */
00311 static struct rbtree_node *rb_node_next_full(struct rbtree_node *node)
00312 {
00313    for (;;) {
00314       node = rb_node_next(node);
00315       if (!node || node->common.obj) {
00316          return node;
00317       }
00318    }
00319 }
00320 
00321 /*!
00322  * \internal
00323  * \brief Get the next non-empty node in descending sequence.
00324  * \since 12.0.0
00325  *
00326  * \param node Starting node to find the previous node.
00327  *
00328  * \retval node on success.
00329  * \retval NULL if no node.
00330  */
00331 static struct rbtree_node *rb_node_prev_full(struct rbtree_node *node)
00332 {
00333    for (;;) {
00334       node = rb_node_prev(node);
00335       if (!node || node->common.obj) {
00336          return node;
00337       }
00338    }
00339 }
00340 
00341 /*!
00342  * \internal
00343  * \brief Determine which way to go from an empty node.
00344  * \since 12.0.0
00345  *
00346  * \param empty Empty node to determine which side obj_right goes on.
00347  * \param sort_fn Sort comparison function for non-empty nodes.
00348  * \param obj_right pointer to the (user-defined part) of an object.
00349  * \param flags flags from ao2_callback()
00350  *   OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
00351  *   OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
00352  *   OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
00353  * \param bias How to bias search direction for duplicates
00354  *
00355  * \return enum empty_node_direction to proceed.
00356  */
00357 static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
00358 {
00359    int cmp;
00360    struct rbtree_node *cur;
00361    struct rbtree_node *right_most;
00362 
00363    /* Try for a quick definite go left. */
00364    if (!empty->left) {
00365       /* The empty node has no left child. */
00366       return GO_RIGHT;
00367    }
00368    right_most = rb_node_most_right(empty->left);
00369    if (right_most->common.obj) {
00370       cmp = sort_fn(right_most->common.obj, obj_right, flags);
00371       if (cmp < 0) {
00372          return GO_RIGHT;
00373       }
00374       if (cmp == 0 && bias == BIAS_LAST) {
00375          return GO_RIGHT;
00376       }
00377       return GO_LEFT;
00378    }
00379 
00380    /* Try for a quick definite go right. */
00381    if (!empty->right) {
00382       /* The empty node has no right child. */
00383       return GO_LEFT;
00384    }
00385    cur = rb_node_most_left(empty->right);
00386    if (cur->common.obj) {
00387       cmp = sort_fn(cur->common.obj, obj_right, flags);
00388       if (cmp > 0) {
00389          return GO_LEFT;
00390       }
00391       if (cmp == 0 && bias == BIAS_FIRST) {
00392          return GO_LEFT;
00393       }
00394       return GO_RIGHT;
00395    }
00396 
00397    /*
00398     * Have to scan the previous nodes from the right_most node of
00399     * the left subtree for the first non-empty node to determine
00400     * direction.
00401     */
00402    cur = right_most;
00403    for (;;) {
00404       /* Find previous node. */
00405       if (cur->left) {
00406          cur = rb_node_most_right(cur->left);
00407       } else {
00408          /* Find the parent that the node is a right child of. */
00409          for (;;) {
00410             if (cur->parent == empty) {
00411                /* The left side of the empty node is all empty nodes. */
00412                return GO_RIGHT;
00413             }
00414             if (cur->parent->right == cur) {
00415                /* We are the right child.  The parent is the previous node. */
00416                cur = cur->parent;
00417                break;
00418             }
00419             cur = cur->parent;
00420          }
00421       }
00422 
00423       if (cur->common.obj) {
00424          cmp = sort_fn(cur->common.obj, obj_right, flags);
00425          if (cmp < 0) {
00426             return GO_RIGHT;
00427          }
00428          if (cmp == 0 && bias == BIAS_LAST) {
00429             return GO_RIGHT;
00430          }
00431          return GO_LEFT;
00432       }
00433    }
00434 }
00435 
00436 /*!
00437  * \internal
00438  * \brief Tree node rotation left.
00439  * \since 12.0.0
00440  *
00441  * \param self Container holding node.
00442  * \param node Node to perform a left rotation with.
00443  *
00444  *        p                         p
00445  *        |     Left rotation       |
00446  *        N        --->             Ch
00447  *       / \                       / \
00448  *      a  Ch                     N   c
00449  *        / \                    / \
00450  *       b   c                  a   b
00451  *
00452  * N = node
00453  * Ch = child
00454  * p = parent
00455  * a,b,c = other nodes that are unaffected by the rotation.
00456  *
00457  * \note It is assumed that the node's right child exists.
00458  *
00459  * \return Nothing
00460  */
00461 static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
00462 {
00463    struct rbtree_node *child; /*!< Node's right child. */
00464 
00465    child = node->right;
00466 
00467    /* Link the node's parent to the child. */
00468    if (!node->parent) {
00469       /* Node is the root so we get a new root node. */
00470       self->root = child;
00471    } else if (node->parent->left == node) {
00472       /* Node is a left child. */
00473       node->parent->left = child;
00474    } else {
00475       /* Node is a right child. */
00476       node->parent->right = child;
00477    }
00478    child->parent = node->parent;
00479 
00480    /* Link node's right subtree to the child's left subtree. */
00481    node->right = child->left;
00482    if (node->right) {
00483       node->right->parent = node;
00484    }
00485 
00486    /* Link the node to the child's left. */
00487    node->parent = child;
00488    child->left = node;
00489 }
00490 
00491 /*!
00492  * \internal
00493  * \brief Tree node rotation right.
00494  * \since 12.0.0
00495  *
00496  * \param self Container holding node.
00497  * \param node Node to perform a right rotation with.
00498  *
00499  *        p                         p
00500  *        |     Right rotation      |
00501  *        Ch                        N
00502  *       / \       <---            / \
00503  *      a  N                      Ch  c
00504  *        / \                    / \
00505  *       b   c                  a   b
00506  *
00507  * N = node
00508  * Ch = child
00509  * p = parent
00510  * a,b,c = other nodes that are unaffected by the rotation.
00511  *
00512  * \note It is assumed that the node's left child exists.
00513  *
00514  * \return Nothing
00515  */
00516 static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
00517 {
00518    struct rbtree_node *child; /*!< Node's left child. */
00519 
00520    child = node->left;
00521 
00522    /* Link the node's parent to the child. */
00523    if (!node->parent) {
00524       /* Node is the root so we get a new root node. */
00525       self->root = child;
00526    } else if (node->parent->right == node) {
00527       /* Node is a right child. */
00528       node->parent->right = child;
00529    } else {
00530       /* Node is a left child. */
00531       node->parent->left = child;
00532    }
00533    child->parent = node->parent;
00534 
00535    /* Link node's left subtree to the child's right subtree. */
00536    node->left = child->right;
00537    if (node->left) {
00538       node->left->parent = node;
00539    }
00540 
00541    /* Link the node to the child's right. */
00542    node->parent = child;
00543    child->right = node;
00544 }
00545 
00546 /*!
00547  * \internal
00548  * \brief Create an empty copy of this container.
00549  * \since 12.0.0
00550  *
00551  * \param self Container to operate upon.
00552  *
00553  * \retval empty-clone-container on success.
00554  * \retval NULL on error.
00555  */
00556 static struct ao2_container *rb_ao2_alloc_empty_clone(struct ao2_container_rbtree *self)
00557 {
00558    if (!is_ao2_object(self)) {
00559       return NULL;
00560    }
00561 
00562    return ao2_t_container_alloc_rbtree(ao2_options_get(self), self->common.options,
00563       self->common.sort_fn, self->common.cmp_fn, "Clone rbtree container");
00564 }
00565 
00566 /*!
00567  * \internal
00568  * \brief Create an empty copy of this container. (Debug version)
00569  * \since 12.0.0
00570  *
00571  * \param self Container to operate upon.
00572  * \param tag used for debugging.
00573  * \param file Debug file name invoked from
00574  * \param line Debug line invoked from
00575  * \param func Debug function name invoked from
00576  * \param ref_debug TRUE if to output a debug reference message.
00577  *
00578  * \retval empty-clone-container on success.
00579  * \retval NULL on error.
00580  */
00581 static struct ao2_container *rb_ao2_alloc_empty_clone_debug(struct ao2_container_rbtree *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
00582 {
00583    if (!is_ao2_object(self)) {
00584       return NULL;
00585    }
00586 
00587    return __ao2_container_alloc_rbtree_debug(ao2_options_get(self), self->common.options,
00588       self->common.sort_fn, self->common.cmp_fn, tag, file, line, func, ref_debug);
00589 }
00590 
00591 /*!
00592  * \internal
00593  * \brief Fixup the rbtree after deleting a node.
00594  * \since 12.0.0
00595  *
00596  * \param self Container to operate upon.
00597  * \param child Child of the node just deleted from the container.
00598  *
00599  * \note The child must be a dummy black node if there really
00600  * was no child of the deleted node.  Otherwise, the caller must
00601  * pass in the parent node and which child was deleted.  In
00602  * addition, the fixup routine would be more complicated.
00603  *
00604  * \return Nothing
00605  */
00606 static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
00607 {
00608    struct rbtree_node *sibling;
00609 
00610    while (self->root != child && !child->is_red) {
00611       if (child->parent->left == child) {
00612          /* Child is a left child. */
00613          sibling = child->parent->right;
00614          ast_assert(sibling != NULL);
00615          if (sibling->is_red) {
00616             /* Case 1: The child's sibling is red. */
00617             AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[0]);
00618             sibling->is_red = 0;
00619             child->parent->is_red = 1;
00620             rb_rotate_left(self, child->parent);
00621             sibling = child->parent->right;
00622             ast_assert(sibling != NULL);
00623          }
00624          /*
00625           * The sibling is black.  A black node must have two children,
00626           * or one red child, or no children.
00627           */
00628          if ((!sibling->left || !sibling->left->is_red)
00629             && (!sibling->right || !sibling->right->is_red)) {
00630             /*
00631              * Case 2: The sibling is black and both of its children are black.
00632              *
00633              * This case handles the two black children or no children
00634              * possibilities of a black node.
00635              */
00636             AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[1]);
00637             sibling->is_red = 1;
00638             child = child->parent;
00639          } else {
00640             /* At this point the sibling has at least one red child. */
00641             if (!sibling->right || !sibling->right->is_red) {
00642                /*
00643                 * Case 3: The sibling is black, its left child is red, and its
00644                 * right child is black.
00645                 */
00646                AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[2]);
00647                ast_assert(sibling->left != NULL);
00648                ast_assert(sibling->left->is_red);
00649                sibling->left->is_red = 0;
00650                sibling->is_red = 1;
00651                rb_rotate_right(self, sibling);
00652                sibling = child->parent->right;
00653                ast_assert(sibling != NULL);
00654             }
00655             /* Case 4: The sibling is black and its right child is red. */
00656             AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[3]);
00657             sibling->is_red = child->parent->is_red;
00658             child->parent->is_red = 0;
00659             if (sibling->right) {
00660                sibling->right->is_red = 0;
00661             }
00662             rb_rotate_left(self, child->parent);
00663             child = self->root;
00664          }
00665       } else {
00666          /* Child is a right child. */
00667          sibling = child->parent->left;
00668          ast_assert(sibling != NULL);
00669          if (sibling->is_red) {
00670             /* Case 1: The child's sibling is red. */
00671             AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[0]);
00672             sibling->is_red = 0;
00673             child->parent->is_red = 1;
00674             rb_rotate_right(self, child->parent);
00675             sibling = child->parent->left;
00676             ast_assert(sibling != NULL);
00677          }
00678          /*
00679           * The sibling is black.  A black node must have two children,
00680           * or one red child, or no children.
00681           */
00682          if ((!sibling->right || !sibling->right->is_red)
00683             && (!sibling->left || !sibling->left->is_red)) {
00684             /*
00685              * Case 2: The sibling is black and both of its children are black.
00686              *
00687              * This case handles the two black children or no children
00688              * possibilities of a black node.
00689              */
00690             AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[1]);
00691             sibling->is_red = 1;
00692             child = child->parent;
00693          } else {
00694             /* At this point the sibling has at least one red child. */
00695             if (!sibling->left || !sibling->left->is_red) {
00696                /*
00697                 * Case 3: The sibling is black, its right child is red, and its
00698                 * left child is black.
00699                 */
00700                AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[2]);
00701                ast_assert(sibling->right != NULL);
00702                ast_assert(sibling->right->is_red);
00703                sibling->right->is_red = 0;
00704                sibling->is_red = 1;
00705                rb_rotate_left(self, sibling);
00706                sibling = child->parent->left;
00707                ast_assert(sibling != NULL);
00708             }
00709             /* Case 4: The sibling is black and its left child is red. */
00710             AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[3]);
00711             sibling->is_red = child->parent->is_red;
00712             child->parent->is_red = 0;
00713             if (sibling->left) {
00714                sibling->left->is_red = 0;
00715             }
00716             rb_rotate_right(self, child->parent);
00717             child = self->root;
00718          }
00719       }
00720    }
00721 
00722    /*
00723     * Case 2 could leave the child node red and it needs to leave
00724     * with it black.
00725     *
00726     * Case 4 sets the child node to the root which of course must
00727     * be black.
00728     */
00729    child->is_red = 0;
00730 }
00731 
00732 /*!
00733  * \internal
00734  * \brief Delete the doomed node from this container.
00735  * \since 12.0.0
00736  *
00737  * \param self Container to operate upon.
00738  * \param doomed Container node to delete from the container.
00739  *
00740  * \return Nothing
00741  */
00742 static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
00743 {
00744    struct rbtree_node *child;
00745    int need_fixup;
00746 
00747    if (doomed->left && doomed->right) {
00748       struct rbtree_node *next;
00749       int is_red;
00750 
00751       /*
00752        * The doomed node has two children.
00753        *
00754        * Find the next child node and swap it with the doomed node in
00755        * the tree.
00756        */
00757       AO2_DEVMODE_STAT(++self->stats.delete_children[2]);
00758       next = rb_node_most_left(doomed->right);
00759       SWAP(doomed->parent, next->parent);
00760       SWAP(doomed->left, next->left);
00761       SWAP(doomed->right, next->right);
00762       is_red = doomed->is_red;
00763       doomed->is_red = next->is_red;
00764       next->is_red = is_red;
00765 
00766       /* Link back in the next node. */
00767       if (!next->parent) {
00768          /* Doomed was the root so we get a new root node. */
00769          self->root = next;
00770       } else if (next->parent->left == doomed) {
00771          /* Doomed was the left child. */
00772          next->parent->left = next;
00773       } else {
00774          /* Doomed was the right child. */
00775          next->parent->right = next;
00776       }
00777       next->left->parent = next;
00778       if (next->right == next) {
00779          /* The next node was the right child of doomed. */
00780          next->right = doomed;
00781          doomed->parent = next;
00782       } else {
00783          next->right->parent = next;
00784          doomed->parent->left = doomed;
00785       }
00786 
00787       /* The doomed node has no left child now. */
00788       ast_assert(doomed->left == NULL);
00789 
00790       /*
00791        * We don't have to link the right child back in with doomed
00792        * since we are going to link it with doomed's parent anyway.
00793        */
00794       child = doomed->right;
00795    } else {
00796       /* Doomed has at most one child. */
00797       child = doomed->left;
00798       if (!child) {
00799          child = doomed->right;
00800       }
00801    }
00802    if (child) {
00803       AO2_DEVMODE_STAT(++self->stats.delete_children[1]);
00804    } else {
00805       AO2_DEVMODE_STAT(++self->stats.delete_children[0]);
00806    }
00807 
00808    need_fixup = (!doomed->is_red && !self->common.destroying);
00809    if (need_fixup && !child) {
00810       /*
00811        * Use the doomed node as a place holder node for the
00812        * nonexistent child so we also don't have to pass to the fixup
00813        * routine the parent and which child the deleted node came
00814        * from.
00815        */
00816       rb_delete_fixup(self, doomed);
00817       ast_assert(doomed->left == NULL);
00818       ast_assert(doomed->right == NULL);
00819       ast_assert(!doomed->is_red);
00820    }
00821 
00822    /* Link the child in place of doomed. */
00823    if (!doomed->parent) {
00824       /* Doomed was the root so we get a new root node. */
00825       self->root = child;
00826    } else if (doomed->parent->left == doomed) {
00827       /* Doomed was the left child. */
00828       doomed->parent->left = child;
00829    } else {
00830       /* Doomed was the right child. */
00831       doomed->parent->right = child;
00832    }
00833    if (child) {
00834       child->parent = doomed->parent;
00835       if (need_fixup) {
00836          rb_delete_fixup(self, child);
00837       }
00838    }
00839 
00840    AO2_DEVMODE_STAT(--self->common.nodes);
00841 }
00842 
00843 /*!
00844  * \internal
00845  * \brief Destroy a rbtree container node.
00846  * \since 12.0.0
00847  *
00848  * \param v_doomed Container node to destroy.
00849  *
00850  * \details
00851  * The container node unlinks itself from the container as part
00852  * of its destruction.  The node must be destroyed while the
00853  * container is already locked.
00854  *
00855  * \note The container must be locked when the node is
00856  * unreferenced.
00857  *
00858  * \return Nothing
00859  */
00860 static void rb_ao2_node_destructor(void *v_doomed)
00861 {
00862    struct rbtree_node *doomed = v_doomed;
00863 
00864    if (doomed->common.is_linked) {
00865       struct ao2_container_rbtree *my_container;
00866 
00867       /*
00868        * Promote to write lock if not already there.  Since
00869        * adjust_lock() can potentially release and block waiting for a
00870        * write lock, care must be taken to ensure that node references
00871        * are released before releasing the container references.
00872        *
00873        * Node references held by an iterator can only be held while
00874        * the iterator also holds a reference to the container.  These
00875        * node references must be unreferenced before the container can
00876        * be unreferenced to ensure that the node will not get a
00877        * negative reference and the destructor called twice for the
00878        * same node.
00879        */
00880       my_container = (struct ao2_container_rbtree *) doomed->common.my_container;
00881       __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
00882 
00883 #if defined(AO2_DEBUG)
00884       if (!my_container->common.destroying
00885          && ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
00886          ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
00887       }
00888 #endif   /* defined(AO2_DEBUG) */
00889       rb_delete_node(my_container, doomed);
00890 #if defined(AO2_DEBUG)
00891       if (!my_container->common.destroying
00892          && ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
00893          ast_log(LOG_ERROR, "Container integrity failed after node deletion.\n");
00894       }
00895 #endif   /* defined(AO2_DEBUG) */
00896    }
00897 
00898    /*
00899     * We could have an object in the node if the container is being
00900     * destroyed or the node had not been linked in yet.
00901     */
00902    if (doomed->common.obj) {
00903       __container_unlink_node(&doomed->common, AO2_UNLINK_NODE_UNLINK_OBJECT);
00904    }
00905 }
00906 
00907 /*!
00908  * \internal
00909  * \brief Create a new container node.
00910  * \since 12.0.0
00911  *
00912  * \param self Container to operate upon.
00913  * \param obj_new Object to put into the node.
00914  * \param tag used for debugging.
00915  * \param file Debug file name invoked from
00916  * \param line Debug line invoked from
00917  * \param func Debug function name invoked from
00918  *
00919  * \retval initialized-node on success.
00920  * \retval NULL on error.
00921  */
00922 static struct rbtree_node *rb_ao2_new_node(struct ao2_container_rbtree *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
00923 {
00924    struct rbtree_node *node;
00925 
00926    node = __ao2_alloc(sizeof(*node), rb_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK);
00927    if (!node) {
00928       return NULL;
00929    }
00930 
00931    if (tag) {
00932       __ao2_ref_debug(obj_new, +1, tag, file, line, func);
00933    } else {
00934       ao2_t_ref(obj_new, +1, "Container node creation");
00935    }
00936    node->common.obj = obj_new;
00937    node->common.my_container = (struct ao2_container *) self;
00938 
00939    return node;
00940 }
00941 
00942 /*!
00943  * \internal
00944  * \brief Fixup the rbtree after inserting a node.
00945  * \since 12.0.0
00946  *
00947  * \param self Container to operate upon.
00948  * \param node Container node just inserted into the container.
00949  *
00950  * \note The just inserted node is red.
00951  *
00952  * \return Nothing
00953  */
00954 static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
00955 {
00956    struct rbtree_node *g_parent; /* Grand parent node. */
00957 
00958    while (node->parent && node->parent->is_red) {
00959       g_parent = node->parent->parent;
00960 
00961       /* The grand parent must exist if the parent is red. */
00962       ast_assert(g_parent != NULL);
00963 
00964       if (node->parent == g_parent->left) {
00965          /* The parent is a left child. */
00966          if (g_parent->right && g_parent->right->is_red) {
00967             /* Case 1: Push the black down from the grand parent node. */
00968             AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[0]);
00969             g_parent->right->is_red = 0;
00970             g_parent->left->is_red = 0;
00971             g_parent->is_red = 1;
00972 
00973             node = g_parent;
00974          } else {
00975             /* The uncle node is black. */
00976             if (node->parent->right == node) {
00977                /*
00978                 * Case 2: The node is a right child.
00979                 *
00980                 * Which node is the grand parent does not change.
00981                 */
00982                AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[1]);
00983                node = node->parent;
00984                rb_rotate_left(self, node);
00985             }
00986             /* Case 3: The node is a left child. */
00987             AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[2]);
00988             node->parent->is_red = 0;
00989             g_parent->is_red = 1;
00990             rb_rotate_right(self, g_parent);
00991          }
00992       } else {
00993          /* The parent is a right child. */
00994          if (g_parent->left && g_parent->left->is_red) {
00995             /* Case 1: Push the black down from the grand parent node. */
00996             AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[0]);
00997             g_parent->left->is_red = 0;
00998             g_parent->right->is_red = 0;
00999             g_parent->is_red = 1;
01000 
01001             node = g_parent;
01002          } else {
01003             /* The uncle node is black. */
01004             if (node->parent->left == node) {
01005                /*
01006                 * Case 2: The node is a left child.
01007                 *
01008                 * Which node is the grand parent does not change.
01009                 */
01010                AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
01011                node = node->parent;
01012                rb_rotate_right(self, node);
01013             }
01014             /* Case 3: The node is a right child. */
01015             AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
01016             node->parent->is_red = 0;
01017             g_parent->is_red = 1;
01018             rb_rotate_left(self, g_parent);
01019          }
01020       }
01021    }
01022 
01023    /*
01024     * The root could be red here because:
01025     * 1) We just inserted the root node in an empty tree.
01026     *
01027     * 2) Case 1 could leave the root red if the grand parent were
01028     * the root.
01029     */
01030    self->root->is_red = 0;
01031 }
01032 
01033 /*!
01034  * \internal
01035  * \brief Insert a node into this container.
01036  * \since 12.0.0
01037  *
01038  * \param self Container to operate upon.
01039  * \param node Container node to insert into the container.
01040  *
01041  * \return enum ao2_container_insert value.
01042  */
01043 static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree *self, struct rbtree_node *node)
01044 {
01045    int cmp;
01046    struct rbtree_node *cur;
01047    struct rbtree_node *next;
01048    ao2_sort_fn *sort_fn;
01049    uint32_t options;
01050    enum equal_node_bias bias;
01051 
01052    if (!self->root) {
01053       /* The tree is empty. */
01054       self->root = node;
01055       return AO2_CONTAINER_INSERT_NODE_INSERTED;
01056    }
01057 
01058    sort_fn = self->common.sort_fn;
01059    options = self->common.options;
01060    switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
01061    default:
01062    case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
01063       if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
01064          bias = BIAS_FIRST;
01065       } else {
01066          bias = BIAS_LAST;
01067       }
01068       break;
01069    case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
01070    case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
01071    case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
01072       bias = BIAS_EQUAL;
01073       break;
01074    }
01075 
01076    /*
01077     * New nodes are always colored red when initially inserted into
01078     * the tree.  (Except for the root which is always black.)
01079     */
01080    node->is_red = 1;
01081 
01082    /* Find node where normal insert would put a new node. */
01083    cur = self->root;
01084    for (;;) {
01085       if (!cur->common.obj) {
01086          /* Which direction do we go to insert this node? */
01087          if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_SEARCH_OBJECT, bias)
01088             == GO_LEFT) {
01089             if (cur->left) {
01090                cur = cur->left;
01091                continue;
01092             }
01093 
01094             /* Node becomes a left child */
01095             cur->left = node;
01096             node->parent = cur;
01097             rb_insert_fixup(self, node);
01098             return AO2_CONTAINER_INSERT_NODE_INSERTED;
01099          }
01100          if (cur->right) {
01101             cur = cur->right;
01102             continue;
01103          }
01104 
01105          /* Node becomes a right child */
01106          cur->right = node;
01107          node->parent = cur;
01108          rb_insert_fixup(self, node);
01109          return AO2_CONTAINER_INSERT_NODE_INSERTED;
01110       }
01111       cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
01112       if (cmp > 0) {
01113          if (cur->left) {
01114             cur = cur->left;
01115             continue;
01116          }
01117 
01118          /* Node becomes a left child */
01119          cur->left = node;
01120          node->parent = cur;
01121          rb_insert_fixup(self, node);
01122          return AO2_CONTAINER_INSERT_NODE_INSERTED;
01123       } else if (cmp < 0) {
01124          if (cur->right) {
01125             cur = cur->right;
01126             continue;
01127          }
01128 
01129          /* Node becomes a right child */
01130          cur->right = node;
01131          node->parent = cur;
01132          rb_insert_fixup(self, node);
01133          return AO2_CONTAINER_INSERT_NODE_INSERTED;
01134       }
01135       switch (bias) {
01136       case BIAS_FIRST:
01137          /* Duplicate nodes unconditionally accepted. */
01138          if (cur->left) {
01139             cur = cur->left;
01140             continue;
01141          }
01142 
01143          /* Node becomes a left child */
01144          cur->left = node;
01145          node->parent = cur;
01146          rb_insert_fixup(self, node);
01147          return AO2_CONTAINER_INSERT_NODE_INSERTED;
01148       case BIAS_EQUAL:
01149          break;
01150       case BIAS_LAST:
01151          /* Duplicate nodes unconditionally accepted. */
01152          if (cur->right) {
01153             cur = cur->right;
01154             continue;
01155          }
01156 
01157          /* Node becomes a right child */
01158          cur->right = node;
01159          node->parent = cur;
01160          rb_insert_fixup(self, node);
01161          return AO2_CONTAINER_INSERT_NODE_INSERTED;
01162       }
01163 
01164       break;
01165    }
01166 
01167    /* Node is a dupliate */
01168    switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
01169    default:
01170    case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
01171       ast_assert(0);/* Case already handled by BIAS_FIRST/BIAS_LAST. */
01172       return AO2_CONTAINER_INSERT_NODE_REJECTED;
01173    case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
01174       /* Reject all objects with the same key. */
01175       return AO2_CONTAINER_INSERT_NODE_REJECTED;
01176    case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
01177       if (cur->common.obj == node->common.obj) {
01178          /* Reject inserting the same object */
01179          return AO2_CONTAINER_INSERT_NODE_REJECTED;
01180       }
01181       next = cur;
01182       if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
01183          /* Search to end of duplicates for the same object. */
01184          for (;;) {
01185             next = rb_node_next_full(next);
01186             if (!next) {
01187                break;
01188             }
01189             if (next->common.obj == node->common.obj) {
01190                /* Reject inserting the same object */
01191                return AO2_CONTAINER_INSERT_NODE_REJECTED;
01192             }
01193             cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
01194             if (cmp) {
01195                break;
01196             }
01197          }
01198 
01199          /* Find first duplicate node. */
01200          for (;;) {
01201             next = rb_node_prev_full(cur);
01202             if (!next) {
01203                break;
01204             }
01205             if (next->common.obj == node->common.obj) {
01206                /* Reject inserting the same object */
01207                return AO2_CONTAINER_INSERT_NODE_REJECTED;
01208             }
01209             cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
01210             if (cmp) {
01211                break;
01212             }
01213             cur = next;
01214          }
01215          if (!cur->left) {
01216             /* Node becomes a left child */
01217             cur->left = node;
01218          } else {
01219             /* Node becomes a right child */
01220             cur = rb_node_most_right(cur->left);
01221             cur->right = node;
01222          }
01223       } else {
01224          /* Search to beginning of duplicates for the same object. */
01225          for (;;) {
01226             next = rb_node_prev_full(next);
01227             if (!next) {
01228                break;
01229             }
01230             if (next->common.obj == node->common.obj) {
01231                /* Reject inserting the same object */
01232                return AO2_CONTAINER_INSERT_NODE_REJECTED;
01233             }
01234             cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
01235             if (cmp) {
01236                break;
01237             }
01238          }
01239 
01240          /* Find last duplicate node. */
01241          for (;;) {
01242             next = rb_node_next_full(cur);
01243             if (!next) {
01244                break;
01245             }
01246             if (next->common.obj == node->common.obj) {
01247                /* Reject inserting the same object */
01248                return AO2_CONTAINER_INSERT_NODE_REJECTED;
01249             }
01250             cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
01251             if (cmp) {
01252                break;
01253             }
01254             cur = next;
01255          }
01256          if (!cur->right) {
01257             /* Node becomes a right child */
01258             cur->right = node;
01259          } else {
01260             /* Node becomes a left child */
01261             cur = rb_node_most_left(cur->right);
01262             cur->left = node;
01263          }
01264       }
01265       break;
01266    case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
01267       SWAP(cur->common.obj, node->common.obj);
01268       ao2_t_ref(node, -1, "Don't need the new node.");
01269       return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
01270    }
01271 
01272    /* Complete inserting duplicate node. */
01273    node->parent = cur;
01274    rb_insert_fixup(self, node);
01275    return AO2_CONTAINER_INSERT_NODE_INSERTED;
01276 }
01277 
01278 /*!
01279  * \internal
01280  * \brief Find the next rbtree container node in a traversal.
01281  * \since 12.0.0
01282  *
01283  * \param self Container to operate upon.
01284  * \param state Traversal state to restart rbtree container traversal.
01285  * \param prev Previous node returned by the traversal search functions.
01286  *    The ref ownership is passed back to this function.
01287  *
01288  * \retval node-ptr of found node (Reffed).
01289  * \retval NULL when no node found.
01290  */
01291 static struct rbtree_node *rb_ao2_find_next(struct ao2_container_rbtree *self, struct rbtree_traversal_state *state, struct rbtree_node *prev)
01292 {
01293    struct rbtree_node *node;
01294    void *arg;
01295    enum search_flags flags;
01296    int cmp;
01297 
01298    arg = state->arg;
01299    flags = state->flags;
01300 
01301    node = prev;
01302    for (;;) {
01303       /* Find next node in traversal order. */
01304       switch (flags & OBJ_ORDER_MASK) {
01305       default:
01306       case OBJ_ORDER_ASCENDING:
01307          node = rb_node_next(node);
01308          break;
01309       case OBJ_ORDER_DESCENDING:
01310          node = rb_node_prev(node);
01311          break;
01312       case OBJ_ORDER_PRE:
01313          node = rb_node_pre(node);
01314          break;
01315       case OBJ_ORDER_POST:
01316          node = rb_node_post(node);
01317          break;
01318       }
01319       if (!node) {
01320          /* No more nodes left to traverse. */
01321          break;
01322       }
01323       if (!node->common.obj) {
01324          /* Node is empty */
01325          continue;
01326       }
01327 
01328       if (state->sort_fn) {
01329          /* Filter node through the sort_fn */
01330          cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
01331          if (cmp) {
01332             /* No more nodes in this container are possible to match. */
01333             break;
01334          }
01335       }
01336 
01337       /* We have the next traversal node */
01338       __ao2_ref(node, +1);
01339 
01340       /*
01341        * Dereferencing the prev node may result in our next node
01342        * object being removed by another thread.  This could happen if
01343        * the container uses RW locks and the container was read
01344        * locked.
01345        */
01346       __ao2_ref(prev, -1);
01347       if (node->common.obj) {
01348          return node;
01349       }
01350       prev = node;
01351    }
01352 
01353    /* No more nodes in the container left to traverse. */
01354    __ao2_ref(prev, -1);
01355    return NULL;
01356 }
01357 
01358 /*!
01359  * \internal
01360  * \brief Find an initial matching node.
01361  * \since 12.0.0
01362  *
01363  * \param self Container to operate upon.
01364  * \param obj_right pointer to the (user-defined part) of an object.
01365  * \param flags flags from ao2_callback()
01366  *   OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
01367  *   OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
01368  *   OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
01369  * \param bias How to bias search direction for duplicates
01370  *
01371  * \retval node on success.
01372  * \retval NULL if not found.
01373  */
01374 static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
01375 {
01376    int cmp;
01377    enum search_flags sort_flags;
01378    struct rbtree_node *node;
01379    struct rbtree_node *next = NULL;
01380    ao2_sort_fn *sort_fn;
01381 
01382    sort_flags = flags & OBJ_SEARCH_MASK;
01383    sort_fn = self->common.sort_fn;
01384 
01385    /* Find node where normal search would find it. */
01386    node = self->root;
01387    if (!node) {
01388       return NULL;
01389    }
01390    for (;;) {
01391       if (!node->common.obj) {
01392          /* Which direction do we go to find the node? */
01393          if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
01394             == GO_LEFT) {
01395             next = node->left;
01396          } else {
01397             next = node->right;
01398          }
01399          if (!next) {
01400             switch (bias) {
01401             case BIAS_FIRST:
01402                /* Check successor node for match. */
01403                next = rb_node_next_full(node);
01404                break;
01405             case BIAS_EQUAL:
01406                break;
01407             case BIAS_LAST:
01408                /* Check previous node for match. */
01409                next = rb_node_prev_full(node);
01410                break;
01411             }
01412             if (next) {
01413                cmp = sort_fn(next->common.obj, obj_right, sort_flags);
01414                if (cmp == 0) {
01415                   /* Found the first/last matching node. */
01416                   return next;
01417                }
01418                next = NULL;
01419             }
01420 
01421             /* No match found. */
01422             return next;
01423          }
01424       } else {
01425          cmp = sort_fn(node->common.obj, obj_right, sort_flags);
01426          if (cmp > 0) {
01427             next = node->left;
01428          } else if (cmp < 0) {
01429             next = node->right;
01430          } else {
01431             switch (bias) {
01432             case BIAS_FIRST:
01433                next = node->left;
01434                break;
01435             case BIAS_EQUAL:
01436                return node;
01437             case BIAS_LAST:
01438                next = node->right;
01439                break;
01440             }
01441             if (!next) {
01442                /* Found the first/last matching node. */
01443                return node;
01444             }
01445          }
01446          if (!next) {
01447             switch (bias) {
01448             case BIAS_FIRST:
01449                if (cmp < 0) {
01450                   /* Check successor node for match. */
01451                   next = rb_node_next_full(node);
01452                }
01453                break;
01454             case BIAS_EQUAL:
01455                break;
01456             case BIAS_LAST:
01457                if (cmp > 0) {
01458                   /* Check previous node for match. */
01459                   next = rb_node_prev_full(node);
01460                }
01461                break;
01462             }
01463             if (next) {
01464                cmp = sort_fn(next->common.obj, obj_right, sort_flags);
01465                if (cmp == 0) {
01466                   /* Found the first/last matching node. */
01467                   return next;
01468                }
01469             }
01470 
01471             /* No match found. */
01472             return NULL;
01473          }
01474       }
01475       node = next;
01476    }
01477 }
01478 
01479 /*!
01480  * \internal
01481  * \brief Find the first rbtree container node in a traversal.
01482  * \since 12.0.0
01483  *
01484  * \param self Container to operate upon.
01485  * \param flags search_flags to control traversing the container
01486  * \param arg Comparison callback arg parameter.
01487  * \param state Traversal state to restart rbtree container traversal.
01488  *
01489  * \retval node-ptr of found node (Reffed).
01490  * \retval NULL when no node found.
01491  */
01492 static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
01493 {
01494    struct rbtree_node *node;
01495    enum equal_node_bias bias;
01496 
01497    if (self->common.destroying) {
01498       /* Force traversal to be post order for tree destruction. */
01499       flags = OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE | OBJ_ORDER_POST;
01500    }
01501 
01502    memset(state, 0, sizeof(*state));
01503    state->arg = arg;
01504    state->flags = flags;
01505 
01506    switch (flags & OBJ_SEARCH_MASK) {
01507    case OBJ_SEARCH_OBJECT:
01508    case OBJ_SEARCH_KEY:
01509    case OBJ_SEARCH_PARTIAL_KEY:
01510       /* We are asked to do a directed search. */
01511       state->sort_fn = self->common.sort_fn;
01512       break;
01513    default:
01514       /* Don't know, let's visit all nodes */
01515       state->sort_fn = NULL;
01516       break;
01517    }
01518 
01519    if (!self->root) {
01520       /* Tree is empty. */
01521       return NULL;
01522    }
01523 
01524    /* Find first traversal node. */
01525    switch (flags & OBJ_ORDER_MASK) {
01526    default:
01527    case OBJ_ORDER_ASCENDING:
01528       if (!state->sort_fn) {
01529          /* Find left most child. */
01530          node = rb_node_most_left(self->root);
01531          if (!node->common.obj) {
01532             node = rb_node_next_full(node);
01533             if (!node) {
01534                return NULL;
01535             }
01536          }
01537          break;
01538       }
01539 
01540       /* Search for initial node. */
01541       switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
01542       case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
01543       case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
01544          if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
01545             /* There are no duplicates allowed. */
01546             bias = BIAS_EQUAL;
01547             break;
01548          }
01549          /* Fall through */
01550       default:
01551       case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
01552       case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
01553          /* Find first duplicate node. */
01554          bias = BIAS_FIRST;
01555          break;
01556       }
01557       node = rb_find_initial(self, arg, flags, bias);
01558       if (!node) {
01559          return NULL;
01560       }
01561       break;
01562    case OBJ_ORDER_DESCENDING:
01563       if (!state->sort_fn) {
01564          /* Find right most child. */
01565          node = rb_node_most_right(self->root);
01566          if (!node->common.obj) {
01567             node = rb_node_prev_full(node);
01568             if (!node) {
01569                return NULL;
01570             }
01571          }
01572          break;
01573       }
01574 
01575       /* Search for initial node. */
01576       switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
01577       case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
01578       case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
01579          if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
01580             /* There are no duplicates allowed. */
01581             bias = BIAS_EQUAL;
01582             break;
01583          }
01584          /* Fall through */
01585       default:
01586       case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
01587       case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
01588          /* Find last duplicate node. */
01589          bias = BIAS_LAST;
01590          break;
01591       }
01592       node = rb_find_initial(self, arg, flags, bias);
01593       if (!node) {
01594          return NULL;
01595       }
01596       break;
01597    case OBJ_ORDER_PRE:
01598       /* This is a tree structure traversal so we must visit all nodes. */
01599       state->sort_fn = NULL;
01600 
01601       node = self->root;
01602 
01603       /* Find a non-empty node. */
01604       while (!node->common.obj) {
01605          node = rb_node_pre(node);
01606          if (!node) {
01607             return NULL;
01608          }
01609       }
01610       break;
01611    case OBJ_ORDER_POST:
01612       /* This is a tree structure traversal so we must visit all nodes. */
01613       state->sort_fn = NULL;
01614 
01615       /* Find the left most childless node. */
01616       node = self->root;
01617       for (;;) {
01618          node = rb_node_most_left(node);
01619          if (!node->right) {
01620             /* This node has no children. */
01621             break;
01622          }
01623          node = node->right;
01624       }
01625 
01626       /* Find a non-empty node. */
01627       while (!node->common.obj) {
01628          node = rb_node_post(node);
01629          if (!node) {
01630             return NULL;
01631          }
01632       }
01633       break;
01634    }
01635 
01636    /* We have the first traversal node */
01637    __ao2_ref(node, +1);
01638    return node;
01639 }
01640 
01641 /*!
01642  * \internal
01643  * \brief Find the next non-empty iteration node in the container.
01644  * \since 12.0.0
01645  *
01646  * \param self Container to operate upon.
01647  * \param node Previous node returned by the iterator.
01648  * \param flags search_flags to control iterating the container.
01649  *   Only AO2_ITERATOR_DESCENDING is useful by the method.
01650  *
01651  * \note The container is already locked.
01652  *
01653  * \retval node on success.
01654  * \retval NULL on error or no more nodes in the container.
01655  */
01656 static struct rbtree_node *rb_ao2_iterator_next(struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
01657 {
01658    if (flags & AO2_ITERATOR_DESCENDING) {
01659       if (!node) {
01660          /* Find right most node. */
01661          if (!self->root) {
01662             return NULL;
01663          }
01664          node = rb_node_most_right(self->root);
01665          if (node->common.obj) {
01666             /* Found a non-empty node. */
01667             return node;
01668          }
01669       }
01670       /* Find next non-empty node. */
01671       node = rb_node_prev_full(node);
01672    } else {
01673       if (!node) {
01674          /* Find left most node. */
01675          if (!self->root) {
01676             return NULL;
01677          }
01678          node = rb_node_most_left(self->root);
01679          if (node->common.obj) {
01680             /* Found a non-empty node. */
01681             return node;
01682          }
01683       }
01684       /* Find next non-empty node. */
01685       node = rb_node_next_full(node);
01686    }
01687 
01688    return node;
01689 }
01690 
01691 /*!
01692  * \internal
01693  *
01694  * \brief Destroy this container.
01695  * \since 12.0.0
01696  *
01697  * \param self Container to operate upon.
01698  *
01699  * \return Nothing
01700  */
01701 static void rb_ao2_destroy(struct ao2_container_rbtree *self)
01702 {
01703    /* Check that the container no longer has any nodes */
01704    if (self->root) {
01705       ast_log(LOG_ERROR, "Node ref leak.  Red-Black tree container still has nodes!\n");
01706       ast_assert(0);
01707    }
01708 }
01709 
01710 #if defined(AO2_DEBUG)
01711 /*!
01712  * \internal
01713  * \brief Display contents of the specified container.
01714  * \since 12.0.0
01715  *
01716  * \param self Container to dump.
01717  * \param where User data needed by prnt to determine where to put output.
01718  * \param prnt Print output callback function to use.
01719  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
01720  *
01721  * \return Nothing
01722  */
01723 static void rb_ao2_dump(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
01724 {
01725 #define FORMAT  "%16s, %16s, %16s, %16s, %5s, %16s, %s\n"
01726 #define FORMAT2 "%16p, %16p, %16p, %16p, %5s, %16p, "
01727 
01728    struct rbtree_node *node;
01729 
01730    prnt(where, FORMAT, "Node", "Parent", "Left", "Right", "Color", "Obj", "Key");
01731    for (node = self->root; node; node = rb_node_pre(node)) {
01732       prnt(where, FORMAT2,
01733          node,
01734          node->parent,
01735          node->left,
01736          node->right,
01737          node->is_red ? "Red" : "Black",
01738          node->common.obj);
01739       if (node->common.obj && prnt_obj) {
01740          prnt_obj(node->common.obj, where, prnt);
01741       }
01742       prnt(where, "\n");
01743    }
01744 
01745 #undef FORMAT
01746 #undef FORMAT2
01747 }
01748 #endif   /* defined(AO2_DEBUG) */
01749 
01750 #if defined(AO2_DEBUG)
01751 /*!
01752  * \internal
01753  * \brief Display statistics of the specified container.
01754  * \since 12.0.0
01755  *
01756  * \param self Container to display statistics.
01757  * \param where User data needed by prnt to determine where to put output.
01758  * \param prnt Print output callback function to use.
01759  *
01760  * \note The container is already locked for reading.
01761  *
01762  * \return Nothing
01763  */
01764 static void rb_ao2_stats(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt)
01765 {
01766    int idx;
01767 
01768    for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_left); ++idx) {
01769       prnt(where, "Number of left insert fixups case %d: %d\n", idx + 1,
01770          self->stats.fixup_insert_left[idx]);
01771    }
01772    for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_right); ++idx) {
01773       prnt(where, "Number of right insert fixups case %d: %d\n", idx + 1,
01774          self->stats.fixup_insert_right[idx]);
01775    }
01776 
01777    for (idx = 0; idx < ARRAY_LEN(self->stats.delete_children); ++idx) {
01778       prnt(where, "Number of nodes deleted with %d children: %d\n", idx,
01779          self->stats.delete_children[idx]);
01780    }
01781    for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_left); ++idx) {
01782       prnt(where, "Number of left delete fixups case %d: %d\n", idx + 1,
01783          self->stats.fixup_delete_left[idx]);
01784    }
01785    for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_right); ++idx) {
01786       prnt(where, "Number of right delete fixups case %d: %d\n", idx + 1,
01787          self->stats.fixup_delete_right[idx]);
01788    }
01789 }
01790 #endif   /* defined(AO2_DEBUG) */
01791 
01792 #if defined(AO2_DEBUG)
01793 /*!
01794  * \internal
01795  * \brief Check the black height of the given node.
01796  * \since 12.0.0
01797  *
01798  * \param node Node to check black height.
01799  *
01800  * \retval black-height of node on success.
01801  * \retval -1 on error.  Node black height did not balance.
01802  */
01803 static int rb_check_black_height(struct rbtree_node *node)
01804 {
01805    int height_left;
01806    int height_right;
01807 
01808    if (!node) {
01809       /* A NULL child is a black node. */
01810       return 0;
01811    }
01812 
01813    height_left = rb_check_black_height(node->left);
01814    if (height_left < 0) {
01815       return -1;
01816    }
01817    height_right = rb_check_black_height(node->right);
01818    if (height_right < 0) {
01819       return -1;
01820    }
01821    if (height_left != height_right) {
01822       ast_log(LOG_ERROR,
01823          "Tree node black height of children does not match! L:%d != R:%d\n",
01824          height_left, height_right);
01825       return -1;
01826    }
01827    if (!node->is_red) {
01828       /* The node itself is black. */
01829       ++height_left;
01830    }
01831    return height_left;
01832 }
01833 
01834 #endif   /* defined(AO2_DEBUG) */
01835 
01836 #if defined(AO2_DEBUG)
01837 /*!
01838  * \internal
01839  * \brief Perform an integrity check on the specified container.
01840  * \since 12.0.0
01841  *
01842  * \param self Container to check integrity.
01843  *
01844  * \note The container is already locked for reading.
01845  *
01846  * \retval 0 on success.
01847  * \retval -1 on error.
01848  */
01849 static int rb_ao2_integrity(struct ao2_container_rbtree *self)
01850 {
01851    int res;
01852    int count_node;
01853    int count_obj;
01854    void *obj_last;
01855    struct rbtree_node *node;
01856 
01857    res = 0;
01858 
01859    count_node = 0;
01860    count_obj = 0;
01861 
01862    /*
01863     * See the properties listed at struct rbtree_node definition.
01864     *
01865     * The rbtree properties 1 and 3 are not testable.
01866     *
01867     * Property 1 is not testable because we are not rebalancing at
01868     * this time so all nodes are either red or black.
01869     *
01870     * Property 3 is not testable because it is the definition of a
01871     * NULL child.
01872     */
01873    if (self->root) {
01874       /* Check tree links. */
01875       if (self->root->parent) {
01876          if (self->root->parent == self->root) {
01877             ast_log(LOG_ERROR, "Tree root parent pointer points to itself!\n");
01878          } else {
01879             ast_log(LOG_ERROR, "Tree root is not a root node!\n");
01880          }
01881          return -1;
01882       }
01883       if (self->root->is_red) {
01884          /* Violation rbtree property 2. */
01885          ast_log(LOG_ERROR, "Tree root is red!\n");
01886          res = -1;
01887       }
01888       node = self->root;
01889       do {
01890          if (node->left) {
01891             if (node->left == node) {
01892                ast_log(LOG_ERROR, "Tree node's left pointer points to itself!\n");
01893                return -1;
01894             }
01895             if (node->left->parent != node) {
01896                ast_log(LOG_ERROR, "Tree node's left child does not link back!\n");
01897                return -1;
01898             }
01899          }
01900          if (node->right) {
01901             if (node->right == node) {
01902                ast_log(LOG_ERROR, "Tree node's right pointer points to itself!\n");
01903                return -1;
01904             }
01905             if (node->right->parent != node) {
01906                ast_log(LOG_ERROR, "Tree node's right child does not link back!\n");
01907                return -1;
01908             }
01909          }
01910 
01911          /* Check red/black node flags. */
01912          if (node->is_red) {
01913             /* A red node must have two black children or no children. */
01914             if (node->left && node->right) {
01915                /* Node has two children. */
01916                if (node->left->is_red) {
01917                   /* Violation rbtree property 4. */
01918                   ast_log(LOG_ERROR, "Tree node is red and its left child is red!\n");
01919                   res = -1;
01920                }
01921                if (node->right->is_red) {
01922                   /* Violation rbtree property 4. */
01923                   ast_log(LOG_ERROR, "Tree node is red and its right child is red!\n");
01924                   res = -1;
01925                }
01926             } else if (node->left || node->right) {
01927                /*
01928                 * Violation rbtree property 4 if the child is red.
01929                 * Violation rbtree property 5 if the child is black.
01930                 */
01931                ast_log(LOG_ERROR, "Tree node is red and it only has one child!\n");
01932                res = -1;
01933             }
01934          } else {
01935             /*
01936              * A black node must have two children, or one red child, or no
01937              * children.  If the black node has two children and only one of
01938              * them is red, that red child must have two children.
01939              */
01940             if (node->left && node->right) {
01941                /* Node has two children. */
01942                if (node->left->is_red != node->right->is_red) {
01943                   /* The children are not the same color. */
01944                   struct rbtree_node *red;
01945 
01946                   if (node->left->is_red) {
01947                      red = node->left;
01948                   } else {
01949                      red = node->right;
01950                   }
01951                   if (!red->left || !red->right) {
01952                      /* Violation rbtree property 5. */
01953                      ast_log(LOG_ERROR,
01954                         "Tree node is black and the red child does not have two children!\n");
01955                      res = -1;
01956                   }
01957                }
01958             } else if ((node->left && !node->left->is_red)
01959                || (node->right && !node->right->is_red)) {
01960                /* Violation rbtree property 5. */
01961                ast_log(LOG_ERROR, "Tree node is black and its only child is black!\n");
01962                res = -1;
01963             }
01964          }
01965 
01966          /* Count nodes and objects. */
01967          ++count_node;
01968          if (node->common.obj) {
01969             ++count_obj;
01970          }
01971 
01972          node = rb_node_pre(node);
01973       } while (node);
01974 
01975       /* Check node key sort order. */
01976       obj_last = NULL;
01977       for (node = rb_node_most_left(self->root); node; node = rb_node_next(node)) {
01978          if (!node->common.obj) {
01979             /* Node is empty. */
01980             continue;
01981          }
01982 
01983          if (obj_last) {
01984             if (self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
01985                ast_log(LOG_ERROR, "Tree nodes are out of sorted order!\n");
01986                return -1;
01987             }
01988          }
01989          obj_last = node->common.obj;
01990       }
01991 
01992       /* Completely check property 5 */
01993       if (!res && rb_check_black_height(self->root) < 0) {
01994          /* Violation rbtree property 5. */
01995          res = -1;
01996       }
01997    }
01998 
01999    /* Check total obj count. */
02000    if (count_obj != ao2_container_count(&self->common)) {
02001       ast_log(LOG_ERROR, "Total object count does not match ao2_container_count()!\n");
02002       return -1;
02003    }
02004 
02005    /* Check total node count. */
02006    if (count_node != self->common.nodes) {
02007       ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
02008          count_node, self->common.nodes);
02009       return -1;
02010    }
02011 
02012    return res;
02013 }
02014 #endif   /* defined(AO2_DEBUG) */
02015 
02016 /*! rbtree container virtual method table. */
02017 static const struct ao2_container_methods v_table_rbtree = {
02018    .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) rb_ao2_alloc_empty_clone,
02019    .alloc_empty_clone_debug =
02020       (ao2_container_alloc_empty_clone_debug_fn) rb_ao2_alloc_empty_clone_debug,
02021    .new_node = (ao2_container_new_node_fn) rb_ao2_new_node,
02022    .insert = (ao2_container_insert_fn) rb_ao2_insert_node,
02023    .traverse_first = (ao2_container_find_first_fn) rb_ao2_find_first,
02024    .traverse_next = (ao2_container_find_next_fn) rb_ao2_find_next,
02025    .iterator_next = (ao2_iterator_next_fn) rb_ao2_iterator_next,
02026    .destroy = (ao2_container_destroy_fn) rb_ao2_destroy,
02027 #if defined(AO2_DEBUG)
02028    .dump = (ao2_container_display) rb_ao2_dump,
02029    .stats = (ao2_container_statistics) rb_ao2_stats,
02030    .integrity = (ao2_container_integrity) rb_ao2_integrity,
02031 #endif   /* defined(AO2_DEBUG) */
02032 };
02033 
02034 /*!
02035  * \brief Initialize a rbtree container.
02036  *
02037  * \param self Container to initialize.
02038  * \param options Container behaviour options (See enum ao2_container_opts)
02039  * \param sort_fn Pointer to a sort function.
02040  * \param cmp_fn Pointer to a compare function used by ao2_find.
02041  *
02042  * \return A pointer to a struct container.
02043  */
02044 static struct ao2_container *rb_ao2_container_init(struct ao2_container_rbtree *self,
02045    unsigned int options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
02046 {
02047    if (!self) {
02048       return NULL;
02049    }
02050 
02051    self->common.v_table = &v_table_rbtree;
02052    self->common.sort_fn = sort_fn;
02053    self->common.cmp_fn = cmp_fn;
02054    self->common.options = options;
02055 
02056 #ifdef AO2_DEBUG
02057    ast_atomic_fetchadd_int(&ao2.total_containers, 1);
02058 #endif   /* defined(AO2_DEBUG) */
02059 
02060    return (struct ao2_container *) self;
02061 }
02062 
02063 struct ao2_container *__ao2_container_alloc_rbtree(unsigned int ao2_options, unsigned int container_options,
02064    ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
02065 {
02066    struct ao2_container_rbtree *self;
02067 
02068    if (!sort_fn) {
02069       /* Sanity checks. */
02070       ast_log(LOG_ERROR, "Missing sort_fn()!\n");
02071       return NULL;
02072    }
02073 
02074    self = ao2_t_alloc_options(sizeof(*self), container_destruct, ao2_options,
02075       "New rbtree container");
02076    return rb_ao2_container_init(self, container_options, sort_fn, cmp_fn);
02077 }
02078 
02079 struct ao2_container *__ao2_container_alloc_rbtree_debug(unsigned int ao2_options, unsigned int container_options,
02080    ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
02081    const char *tag, const char *file, int line, const char *func, int ref_debug)
02082 {
02083    struct ao2_container_rbtree *self;
02084 
02085    if (!sort_fn) {
02086       /* Sanity checks. */
02087       ast_log(__LOG_ERROR, file, line, func, "Missing sort_fn()!\n");
02088       return NULL;
02089    }
02090 
02091    self = __ao2_alloc_debug(sizeof(*self),
02092       ref_debug ? container_destruct_debug : container_destruct, ao2_options,
02093       tag, file, line, func, ref_debug);
02094    return rb_ao2_container_init(self, container_options, sort_fn, cmp_fn);
02095 }
02096 

Generated on Thu Apr 16 06:27:15 2015 for Asterisk - The Open Source Telephony Project by  doxygen 1.5.6