astobj2_rbtree.c File Reference

RBTree functions implementing astobj2 containers. More...

#include "asterisk.h"
#include "asterisk/_private.h"
#include "asterisk/astobj2.h"
#include "asterisk/utils.h"
#include "astobj2_private.h"
#include "astobj2_container_private.h"

Include dependency graph for astobj2_rbtree.c:

Go to the source code of this file.

Data Structures

struct  ao2_container_rbtree
struct  rbtree_node
struct  rbtree_traversal_state
struct  rbtree_traversal_state_check

Enumerations

enum  empty_node_direction { GO_LEFT, GO_RIGHT }
enum  equal_node_bias { BIAS_FIRST, BIAS_EQUAL, BIAS_LAST }

Functions

struct ao2_container__ao2_container_alloc_rbtree (unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
struct ao2_container__ao2_container_alloc_rbtree_debug (unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func, int ref_debug)
static struct ao2_containerrb_ao2_alloc_empty_clone (struct ao2_container_rbtree *self)
static struct ao2_containerrb_ao2_alloc_empty_clone_debug (struct ao2_container_rbtree *self, const char *tag, const char *file, int line, const char *func, int ref_debug)
static struct ao2_containerrb_ao2_container_init (struct ao2_container_rbtree *self, unsigned int options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
 Initialize a rbtree container.
static void rb_ao2_destroy (struct ao2_container_rbtree *self)
static struct rbtree_noderb_ao2_find_first (struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
static struct rbtree_noderb_ao2_find_next (struct ao2_container_rbtree *self, struct rbtree_traversal_state *state, struct rbtree_node *prev)
static enum ao2_container_insert rb_ao2_insert_node (struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_noderb_ao2_iterator_next (struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
static struct rbtree_noderb_ao2_new_node (struct ao2_container_rbtree *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
static void rb_ao2_node_destructor (void *v_doomed)
static void rb_delete_fixup (struct ao2_container_rbtree *self, struct rbtree_node *child)
static void rb_delete_node (struct ao2_container_rbtree *self, struct rbtree_node *doomed)
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)
static struct rbtree_noderb_find_initial (struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
static void rb_insert_fixup (struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_noderb_node_most_left (struct rbtree_node *node)
static struct rbtree_noderb_node_most_right (struct rbtree_node *node)
static struct rbtree_noderb_node_next (struct rbtree_node *node)
static struct rbtree_noderb_node_next_full (struct rbtree_node *node)
static struct rbtree_noderb_node_post (struct rbtree_node *node)
static struct rbtree_noderb_node_pre (struct rbtree_node *node)
static struct rbtree_noderb_node_prev (struct rbtree_node *node)
static struct rbtree_noderb_node_prev_full (struct rbtree_node *node)
static void rb_rotate_left (struct ao2_container_rbtree *self, struct rbtree_node *node)
static void rb_rotate_right (struct ao2_container_rbtree *self, struct rbtree_node *node)

Variables

static struct ao2_container_methods v_table_rbtree


Detailed Description

RBTree functions implementing astobj2 containers.

Author:
Richard Mudgett <rmudgett@digium.com>

Definition in file astobj2_rbtree.c.


Enumeration Type Documentation

Enumerator:
GO_LEFT 
GO_RIGHT 

Definition at line 107 of file astobj2_rbtree.c.

00107                           {
00108    GO_LEFT,
00109    GO_RIGHT,
00110 };

Enumerator:
BIAS_FIRST  Bias search toward first matching node in the container.
BIAS_EQUAL  Bias search toward any matching node.
BIAS_LAST  Bias search toward last matching node in the container.

Definition at line 98 of file astobj2_rbtree.c.

00098                      {
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 };


Function Documentation

struct ao2_container* __ao2_container_alloc_rbtree ( unsigned int  ao2_options,
unsigned int  container_options,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn 
) [read]

Definition at line 2063 of file astobj2_rbtree.c.

References ao2_t_alloc_options, ast_log, container_destruct(), LOG_ERROR, NULL, and rb_ao2_container_init().

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 }

struct ao2_container* __ao2_container_alloc_rbtree_debug ( unsigned int  ao2_options,
unsigned int  container_options,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn,
const char *  tag,
const char *  file,
int  line,
const char *  func,
int  ref_debug 
) [read]

Definition at line 2079 of file astobj2_rbtree.c.

References __ao2_alloc_debug(), __LOG_ERROR, ast_log, container_destruct(), container_destruct_debug(), NULL, and rb_ao2_container_init().

Referenced by rb_ao2_alloc_empty_clone_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 }

static struct ao2_container* rb_ao2_alloc_empty_clone ( struct ao2_container_rbtree self  )  [static, read]

Definition at line 556 of file astobj2_rbtree.c.

References ao2_options_get(), ao2_t_container_alloc_rbtree, is_ao2_object(), and NULL.

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 }

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 
) [static, read]

Definition at line 581 of file astobj2_rbtree.c.

References __ao2_container_alloc_rbtree_debug(), ao2_options_get(), is_ao2_object(), and NULL.

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 }

static struct ao2_container* rb_ao2_container_init ( struct ao2_container_rbtree self,
unsigned int  options,
ao2_sort_fn sort_fn,
ao2_callback_fn cmp_fn 
) [static, read]

Initialize a rbtree container.

Parameters:
self Container to initialize.
options Container behaviour options (See enum ao2_container_opts)
sort_fn Pointer to a sort function.
cmp_fn Pointer to a compare function used by ao2_find.
Returns:
A pointer to a struct container.

Definition at line 2044 of file astobj2_rbtree.c.

References ast_atomic_fetchadd_int(), and NULL.

Referenced by __ao2_container_alloc_rbtree(), and __ao2_container_alloc_rbtree_debug().

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 }

static void rb_ao2_destroy ( struct ao2_container_rbtree self  )  [static]

Definition at line 1701 of file astobj2_rbtree.c.

References ast_assert, ast_log, and LOG_ERROR.

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 }

static struct rbtree_node* rb_ao2_find_first ( struct ao2_container_rbtree self,
enum search_flags  flags,
void *  arg,
struct rbtree_traversal_state state 
) [static, read]

Definition at line 1492 of file astobj2_rbtree.c.

References __ao2_ref(), AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW, AO2_CONTAINER_ALLOC_OPT_DUPS_MASK, AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, rbtree_traversal_state::arg, BIAS_EQUAL, BIAS_FIRST, BIAS_LAST, rbtree_node::common, rbtree_traversal_state::flags, NULL, ao2_container_node::obj, OBJ_MULTIPLE, OBJ_NODATA, OBJ_ORDER_ASCENDING, OBJ_ORDER_DESCENDING, OBJ_ORDER_MASK, OBJ_ORDER_POST, OBJ_ORDER_PRE, OBJ_SEARCH_KEY, OBJ_SEARCH_MASK, OBJ_SEARCH_OBJECT, OBJ_SEARCH_PARTIAL_KEY, OBJ_UNLINK, rb_find_initial(), rb_node_most_left(), rb_node_most_right(), rb_node_next_full(), rb_node_post(), rb_node_pre(), rb_node_prev_full(), rbtree_node::right, and rbtree_traversal_state::sort_fn.

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 }

static struct rbtree_node* rb_ao2_find_next ( struct ao2_container_rbtree self,
struct rbtree_traversal_state state,
struct rbtree_node prev 
) [static, read]

Definition at line 1291 of file astobj2_rbtree.c.

References __ao2_ref(), rbtree_traversal_state::arg, rbtree_node::common, rbtree_traversal_state::flags, NULL, ao2_container_node::obj, OBJ_ORDER_ASCENDING, OBJ_ORDER_DESCENDING, OBJ_ORDER_MASK, OBJ_ORDER_POST, OBJ_ORDER_PRE, OBJ_SEARCH_MASK, rb_node_next(), rb_node_post(), rb_node_pre(), rb_node_prev(), and rbtree_traversal_state::sort_fn.

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 }

static enum ao2_container_insert rb_ao2_insert_node ( struct ao2_container_rbtree self,
struct rbtree_node node 
) [static]

Definition at line 1043 of file astobj2_rbtree.c.

References AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW, AO2_CONTAINER_ALLOC_OPT_DUPS_MASK, AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT, AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN, AO2_CONTAINER_INSERT_NODE_INSERTED, AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED, AO2_CONTAINER_INSERT_NODE_REJECTED, ao2_t_ref, ast_assert, BIAS_EQUAL, BIAS_FIRST, BIAS_LAST, rbtree_node::common, GO_LEFT, rbtree_node::is_red, rbtree_node::left, ao2_container_node::obj, OBJ_SEARCH_OBJECT, rbtree_node::parent, rb_find_empty_direction(), rb_insert_fixup(), rb_node_most_left(), rb_node_most_right(), rb_node_next_full(), rb_node_prev_full(), rbtree_node::right, and SWAP.

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 }

static struct rbtree_node* rb_ao2_iterator_next ( struct ao2_container_rbtree self,
struct rbtree_node node,
enum ao2_iterator_flags  flags 
) [static, read]

Definition at line 1656 of file astobj2_rbtree.c.

References AO2_ITERATOR_DESCENDING, rbtree_node::common, NULL, ao2_container_node::obj, rb_node_most_left(), rb_node_most_right(), rb_node_next_full(), and rb_node_prev_full().

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 }

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 
) [static, read]

Definition at line 922 of file astobj2_rbtree.c.

References __ao2_alloc(), __ao2_ref_debug(), AO2_ALLOC_OPT_LOCK_NOLOCK, ao2_t_ref, rbtree_node::common, ao2_container_node::my_container, NULL, ao2_container_node::obj, and rb_ao2_node_destructor().

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 }

static void rb_ao2_node_destructor ( void *  v_doomed  )  [static]

Definition at line 860 of file astobj2_rbtree.c.

References __adjust_lock(), __container_unlink_node, ao2_container_check(), AO2_LOCK_REQ_WRLOCK, AO2_UNLINK_NODE_UNLINK_OBJECT, ast_log, ao2_container_rbtree::common, rbtree_node::common, ao2_container::destroying, ao2_container_node::is_linked, LOG_ERROR, ao2_container_node::my_container, ao2_container_node::obj, OBJ_NOLOCK, and rb_delete_node().

Referenced by rb_ao2_new_node().

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 }

static void rb_delete_fixup ( struct ao2_container_rbtree self,
struct rbtree_node child 
) [static]

Definition at line 606 of file astobj2_rbtree.c.

References AO2_DEVMODE_STAT, ast_assert, rbtree_node::is_red, rbtree_node::left, NULL, rbtree_node::parent, rb_rotate_left(), rb_rotate_right(), and rbtree_node::right.

Referenced by rb_delete_node().

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 }

static void rb_delete_node ( struct ao2_container_rbtree self,
struct rbtree_node doomed 
) [static]

Definition at line 742 of file astobj2_rbtree.c.

References AO2_DEVMODE_STAT, ast_assert, rbtree_node::is_red, rbtree_node::left, NULL, rbtree_node::parent, rb_delete_fixup(), rb_node_most_left(), rbtree_node::right, and SWAP.

Referenced by rb_ao2_node_destructor().

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 }

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 
) [static]

Definition at line 357 of file astobj2_rbtree.c.

References BIAS_FIRST, BIAS_LAST, rbtree_node::common, GO_LEFT, GO_RIGHT, rbtree_node::left, ao2_container_node::obj, rbtree_node::parent, rb_node_most_left(), rb_node_most_right(), and rbtree_node::right.

Referenced by rb_ao2_insert_node(), and rb_find_initial().

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 }

static struct rbtree_node* rb_find_initial ( struct ao2_container_rbtree self,
void *  obj_right,
enum search_flags  flags,
enum equal_node_bias  bias 
) [static, read]

Definition at line 1374 of file astobj2_rbtree.c.

References BIAS_EQUAL, BIAS_FIRST, BIAS_LAST, rbtree_node::common, GO_LEFT, rbtree_node::left, NULL, ao2_container_node::obj, OBJ_SEARCH_MASK, rb_find_empty_direction(), rb_node_next_full(), rb_node_prev_full(), and rbtree_node::right.

Referenced by rb_ao2_find_first().

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 }

static void rb_insert_fixup ( struct ao2_container_rbtree self,
struct rbtree_node node 
) [static]

Definition at line 954 of file astobj2_rbtree.c.

References AO2_DEVMODE_STAT, ast_assert, rbtree_node::is_red, rbtree_node::left, NULL, rbtree_node::parent, rb_rotate_left(), rb_rotate_right(), and rbtree_node::right.

Referenced by rb_ao2_insert_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 }

static struct rbtree_node* rb_node_most_left ( struct rbtree_node node  )  [static, read]

Definition at line 139 of file astobj2_rbtree.c.

References rbtree_node::left.

Referenced by rb_ao2_find_first(), rb_ao2_insert_node(), rb_ao2_iterator_next(), rb_delete_node(), rb_find_empty_direction(), rb_node_next(), and rb_node_post().

00140 {
00141    while (node->left) {
00142       node = node->left;
00143    }
00144 
00145    return node;
00146 }

static struct rbtree_node* rb_node_most_right ( struct rbtree_node node  )  [static, read]

Definition at line 157 of file astobj2_rbtree.c.

References rbtree_node::right.

Referenced by rb_ao2_find_first(), rb_ao2_insert_node(), rb_ao2_iterator_next(), rb_find_empty_direction(), and rb_node_prev().

00158 {
00159    while (node->right) {
00160       node = node->right;
00161    }
00162 
00163    return node;
00164 }

static struct rbtree_node* rb_node_next ( struct rbtree_node node  )  [static, read]

Definition at line 176 of file astobj2_rbtree.c.

References rbtree_node::left, NULL, rbtree_node::parent, rb_node_most_left(), and rbtree_node::right.

Referenced by rb_ao2_find_next(), and rb_node_next_full().

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 }

static struct rbtree_node* rb_node_next_full ( struct rbtree_node node  )  [static, read]

Definition at line 311 of file astobj2_rbtree.c.

References rbtree_node::common, ao2_container_node::obj, and rb_node_next().

Referenced by rb_ao2_find_first(), rb_ao2_insert_node(), rb_ao2_iterator_next(), and rb_find_initial().

00312 {
00313    for (;;) {
00314       node = rb_node_next(node);
00315       if (!node || node->common.obj) {
00316          return node;
00317       }
00318    }
00319 }

static struct rbtree_node* rb_node_post ( struct rbtree_node node  )  [static, read]

Definition at line 266 of file astobj2_rbtree.c.

References rbtree_node::left, NULL, rbtree_node::parent, rb_node_most_left(), and rbtree_node::right.

Referenced by rb_ao2_find_first(), and rb_ao2_find_next().

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 }

static struct rbtree_node* rb_node_pre ( struct rbtree_node node  )  [static, read]

Definition at line 230 of file astobj2_rbtree.c.

References rbtree_node::left, NULL, rbtree_node::parent, and rbtree_node::right.

Referenced by rb_ao2_find_first(), and rb_ao2_find_next().

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 }

static struct rbtree_node* rb_node_prev ( struct rbtree_node node  )  [static, read]

Definition at line 203 of file astobj2_rbtree.c.

References rbtree_node::left, NULL, rbtree_node::parent, rb_node_most_right(), and rbtree_node::right.

Referenced by rb_ao2_find_next(), and rb_node_prev_full().

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 }

static struct rbtree_node* rb_node_prev_full ( struct rbtree_node node  )  [static, read]

Definition at line 331 of file astobj2_rbtree.c.

References rbtree_node::common, ao2_container_node::obj, and rb_node_prev().

Referenced by rb_ao2_find_first(), rb_ao2_insert_node(), rb_ao2_iterator_next(), and rb_find_initial().

00332 {
00333    for (;;) {
00334       node = rb_node_prev(node);
00335       if (!node || node->common.obj) {
00336          return node;
00337       }
00338    }
00339 }

static void rb_rotate_left ( struct ao2_container_rbtree self,
struct rbtree_node node 
) [static]

< Node's right child.

Definition at line 461 of file astobj2_rbtree.c.

References rbtree_node::left, rbtree_node::parent, and rbtree_node::right.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

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 }

static void rb_rotate_right ( struct ao2_container_rbtree self,
struct rbtree_node node 
) [static]

< Node's left child.

Definition at line 516 of file astobj2_rbtree.c.

References rbtree_node::left, rbtree_node::parent, and rbtree_node::right.

Referenced by rb_delete_fixup(), and rb_insert_fixup().

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 }


Variable Documentation

rbtree container virtual method table.

Definition at line 2017 of file astobj2_rbtree.c.


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