Asterisk - The Open Source Telephony Project  21.4.1
Data Structures | Enumerations | Functions | Variables
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"

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, const char *tag, const char *file, int line, const char *func)
 
static struct ao2_containerrb_ao2_alloc_empty_clone (struct ao2_container_rbtree *self, const char *tag, const char *file, int line, const char *func)
 
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. More...
 
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 const struct ao2_container_methods v_table_rbtree
 

Detailed Description

RBTree functions implementing astobj2 containers.

Author
Richard Mudgett rmudg.nosp@m.ett@.nosp@m.digiu.nosp@m.m.co.nosp@m.m

Definition in file astobj2_rbtree.c.

Enumeration Type Documentation

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 96 of file astobj2_rbtree.c.

96  {
97  /*! Bias search toward first matching node in the container. */
98  BIAS_FIRST,
99  /*! Bias search toward any matching node. */
100  BIAS_EQUAL,
101  /*! Bias search toward last matching node in the container. */
102  BIAS_LAST,
103 };

Function Documentation

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

Initialize a rbtree container.

Parameters
selfContainer to initialize.
optionsContainer behaviour options (See enum ao2_container_opts)
sort_fnPointer to a sort function.
cmp_fnPointer to a compare function used by ao2_find.
Returns
A pointer to a struct container.

Definition at line 2003 of file astobj2_rbtree.c.

References ast_atomic_fetchadd_int(), ao2_container::cmp_fn, ao2_container::options, ao2_container::sort_fn, and v_table_rbtree.

2005 {
2006  if (!self) {
2007  return NULL;
2008  }
2009 
2010  self->common.v_table = &v_table_rbtree;
2011  self->common.sort_fn = sort_fn;
2012  self->common.cmp_fn = cmp_fn;
2013  self->common.options = options;
2014 
2015 #ifdef AO2_DEBUG
2016  ast_atomic_fetchadd_int(&ao2.total_containers, 1);
2017 #endif /* defined(AO2_DEBUG) */
2018 
2019  return (struct ao2_container *) self;
2020 }
static const struct ao2_container_methods v_table_rbtree
int ast_atomic_fetchadd_int(volatile int *p, int v)
Atomically add v to *p and return the previous value of *p.
Definition: lock.h:757
Generic container type.
ao2_callback_fn * cmp_fn
static void rb_rotate_left ( struct ao2_container_rbtree self,
struct rbtree_node node 
)
static

< Node's right child.

Definition at line 457 of file astobj2_rbtree.c.

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

458 {
459  struct rbtree_node *child; /*!< Node's right child. */
460 
461  child = node->right;
462 
463  /* Link the node's parent to the child. */
464  if (!node->parent) {
465  /* Node is the root so we get a new root node. */
466  self->root = child;
467  } else if (node->parent->left == node) {
468  /* Node is a left child. */
469  node->parent->left = child;
470  } else {
471  /* Node is a right child. */
472  node->parent->right = child;
473  }
474  child->parent = node->parent;
475 
476  /* Link node's right subtree to the child's left subtree. */
477  node->right = child->left;
478  if (node->right) {
479  node->right->parent = node;
480  }
481 
482  /* Link the node to the child's left. */
483  node->parent = child;
484  child->left = node;
485 }
struct rbtree_node * right
struct rbtree_node * parent
struct rbtree_node * left
static void rb_rotate_right ( struct ao2_container_rbtree self,
struct rbtree_node node 
)
static

< Node's left child.

Definition at line 510 of file astobj2_rbtree.c.

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

511 {
512  struct rbtree_node *child; /*!< Node's left child. */
513 
514  child = node->left;
515 
516  /* Link the node's parent to the child. */
517  if (!node->parent) {
518  /* Node is the root so we get a new root node. */
519  self->root = child;
520  } else if (node->parent->right == node) {
521  /* Node is a right child. */
522  node->parent->right = child;
523  } else {
524  /* Node is a left child. */
525  node->parent->left = child;
526  }
527  child->parent = node->parent;
528 
529  /* Link node's left subtree to the child's right subtree. */
530  node->left = child->right;
531  if (node->left) {
532  node->left->parent = node;
533  }
534 
535  /* Link the node to the child's right. */
536  node->parent = child;
537  child->right = node;
538 }
struct rbtree_node * right
struct rbtree_node * parent
struct rbtree_node * left

Variable Documentation

const struct ao2_container_methods v_table_rbtree
static

rbtree container virtual method table.

Definition at line 1978 of file astobj2_rbtree.c.

Referenced by rb_ao2_container_init().