Asterisk - The Open Source Telephony Project  18.5.0
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"
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, 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

◆ empty_node_direction

Enumerator
GO_LEFT 
GO_RIGHT 

Definition at line 105 of file astobj2_rbtree.c.

105  {
106  GO_LEFT,
107  GO_RIGHT,
108 };

◆ equal_node_bias

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

◆ __ao2_container_alloc_rbtree()

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 
)

Definition at line 2040 of file astobj2_rbtree.c.

References __ao2_alloc(), __LOG_ERROR, ast_log, container_destruct(), NULL, and rb_ao2_container_init().

Referenced by rb_ao2_alloc_empty_clone().

2043 {
2044  struct ao2_container_rbtree *self;
2045 
2046  if (!sort_fn) {
2047  /* Sanity checks. */
2048  ast_log(__LOG_ERROR, file, line, func, "Missing sort_fn()!\n");
2049  return NULL;
2050  }
2051 
2052  self = __ao2_alloc(sizeof(*self), container_destruct, ao2_options,
2053  tag ?: __PRETTY_FUNCTION__, file, line, func);
2054  return rb_ao2_container_init(self, container_options, sort_fn, cmp_fn);
2055 }
void container_destruct(void *_c)
void * __ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *tag, const char *file, int line, const char *func) attribute_warn_unused_result
Definition: astobj2.c:765
#define __LOG_ERROR
Definition: logger.h:284
#define NULL
Definition: resample.c:96
#define ast_log
Definition: astobj2.c:42
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)
Initialize a rbtree container.

◆ rb_ao2_alloc_empty_clone()

static struct ao2_container* rb_ao2_alloc_empty_clone ( struct ao2_container_rbtree self,
const char *  tag,
const char *  file,
int  line,
const char *  func 
)
static

Definition at line 558 of file astobj2_rbtree.c.

References __ao2_container_alloc_rbtree(), __is_ao2_object, ao2_options_get(), and NULL.

560 {
561  if (!__is_ao2_object(self, file, line, func)) {
562  return NULL;
563  }
564 
566  self->common.sort_fn, self->common.cmp_fn, tag, file, line, func);
567 }
#define __is_ao2_object(user_data, file, line, func)
struct ao2_container common
Items common to all containers.
#define NULL
Definition: resample.c:96
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)
unsigned int ao2_options_get(void *obj)
Retrieve the ao2 options used to create the object.
Definition: astobj2.c:778
ao2_callback_fn * cmp_fn

◆ rb_ao2_container_init()

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

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

Referenced by __ao2_container_alloc_rbtree().

2023 {
2024  if (!self) {
2025  return NULL;
2026  }
2027 
2028  self->common.v_table = &v_table_rbtree;
2029  self->common.sort_fn = sort_fn;
2030  self->common.cmp_fn = cmp_fn;
2031  self->common.options = options;
2032 
2033 #ifdef AO2_DEBUG
2034  ast_atomic_fetchadd_int(&ao2.total_containers, 1);
2035 #endif /* defined(AO2_DEBUG) */
2036 
2037  return (struct ao2_container *) self;
2038 }
static const struct ao2_container_methods v_table_rbtree
#define NULL
Definition: resample.c:96
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:755
Generic container type.
static struct test_options options

◆ rb_ao2_destroy()

static void rb_ao2_destroy ( struct ao2_container_rbtree self)
static

Definition at line 1680 of file astobj2_rbtree.c.

References ao2_container_count(), ARRAY_LEN, ast_assert, ast_log, rbtree_node::common, FORMAT, FORMAT2, rbtree_node::is_red, rbtree_node::left, LOG_ERROR, NULL, ao2_container_node::obj, OBJ_SEARCH_OBJECT, rbtree_node::parent, rb_node_most_left(), rb_node_next(), rb_node_pre(), and rbtree_node::right.

1681 {
1682  /* Check that the container no longer has any nodes */
1683  if (self->root) {
1684  ast_log(LOG_ERROR, "Node ref leak. Red-Black tree container still has nodes!\n");
1685  ast_assert(0);
1686  }
1687 }
struct rbtree_node * root
#define ast_assert(a)
Definition: utils.h:695
#define ast_log
Definition: astobj2.c:42
#define LOG_ERROR
Definition: logger.h:285

◆ rb_ao2_find_first()

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

Definition at line 1471 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_ref, 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.

1472 {
1473  struct rbtree_node *node;
1474  enum equal_node_bias bias;
1475 
1476  if (self->common.destroying) {
1477  /* Force traversal to be post order for tree destruction. */
1479  }
1480 
1481  memset(state, 0, sizeof(*state));
1482  state->arg = arg;
1483  state->flags = flags;
1484 
1485  switch (flags & OBJ_SEARCH_MASK) {
1486  case OBJ_SEARCH_OBJECT:
1487  case OBJ_SEARCH_KEY:
1489  /* We are asked to do a directed search. */
1490  state->sort_fn = self->common.sort_fn;
1491  break;
1492  default:
1493  /* Don't know, let's visit all nodes */
1494  state->sort_fn = NULL;
1495  break;
1496  }
1497 
1498  if (!self->root) {
1499  /* Tree is empty. */
1500  return NULL;
1501  }
1502 
1503  /* Find first traversal node. */
1504  switch (flags & OBJ_ORDER_MASK) {
1505  default:
1506  case OBJ_ORDER_ASCENDING:
1507  if (!state->sort_fn) {
1508  /* Find left most child. */
1509  node = rb_node_most_left(self->root);
1510  if (!node->common.obj) {
1511  node = rb_node_next_full(node);
1512  if (!node) {
1513  return NULL;
1514  }
1515  }
1516  break;
1517  }
1518 
1519  /* Search for initial node. */
1523  if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1524  /* There are no duplicates allowed. */
1525  bias = BIAS_EQUAL;
1526  break;
1527  }
1528  /* Fall through */
1529  default:
1532  /* Find first duplicate node. */
1533  bias = BIAS_FIRST;
1534  break;
1535  }
1536  node = rb_find_initial(self, arg, flags, bias);
1537  if (!node) {
1538  return NULL;
1539  }
1540  break;
1541  case OBJ_ORDER_DESCENDING:
1542  if (!state->sort_fn) {
1543  /* Find right most child. */
1544  node = rb_node_most_right(self->root);
1545  if (!node->common.obj) {
1546  node = rb_node_prev_full(node);
1547  if (!node) {
1548  return NULL;
1549  }
1550  }
1551  break;
1552  }
1553 
1554  /* Search for initial node. */
1558  if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1559  /* There are no duplicates allowed. */
1560  bias = BIAS_EQUAL;
1561  break;
1562  }
1563  /* Fall through */
1564  default:
1567  /* Find last duplicate node. */
1568  bias = BIAS_LAST;
1569  break;
1570  }
1571  node = rb_find_initial(self, arg, flags, bias);
1572  if (!node) {
1573  return NULL;
1574  }
1575  break;
1576  case OBJ_ORDER_PRE:
1577  /* This is a tree structure traversal so we must visit all nodes. */
1578  state->sort_fn = NULL;
1579 
1580  node = self->root;
1581 
1582  /* Find a non-empty node. */
1583  while (!node->common.obj) {
1584  node = rb_node_pre(node);
1585  if (!node) {
1586  return NULL;
1587  }
1588  }
1589  break;
1590  case OBJ_ORDER_POST:
1591  /* This is a tree structure traversal so we must visit all nodes. */
1592  state->sort_fn = NULL;
1593 
1594  /* Find the left most childless node. */
1595  node = self->root;
1596  for (;;) {
1597  node = rb_node_most_left(node);
1598  if (!node->right) {
1599  /* This node has no children. */
1600  break;
1601  }
1602  node = node->right;
1603  }
1604 
1605  /* Find a non-empty node. */
1606  while (!node->common.obj) {
1607  node = rb_node_post(node);
1608  if (!node) {
1609  return NULL;
1610  }
1611  }
1612  break;
1613  }
1614 
1615  /* We have the first traversal node */
1616  ao2_ref(node, +1);
1617  return node;
1618 }
static struct rbtree_node * rb_node_pre(struct rbtree_node *node)
Definition: test_heap.c:38
struct rbtree_node * root
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
The arg parameter is a search key, but is not an object.
Definition: astobj2.h:1105
static struct rbtree_node * rb_node_post(struct rbtree_node *node)
Allow objects with duplicate keys in container.
Definition: astobj2.h:1185
struct rbtree_node * right
enum search_flags flags
static struct rbtree_node * rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
struct ao2_container common
Items common to all containers.
#define NULL
Definition: resample.c:96
equal_node_bias
Traverse in ascending order (First to last container object)
Definition: astobj2.h:1125
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
Definition: astobj2.h:1120
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
The ao2 container objects with duplicate keys option field mask.
Definition: astobj2.h:1181
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
#define ao2_ref(o, delta)
Definition: astobj2.h:464
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
Traverse in descending order (Last to first container object)
Definition: astobj2.h:1127
Traverse in pre-order (Node then children, for tree container)
Definition: astobj2.h:1136
unsigned int destroying
TRUE if the container is being destroyed.
struct ao2_container_node common
Items common to all container nodes.
The arg parameter is an object of the same type.
Definition: astobj2.h:1091
Replace objects with duplicate keys in container.
Definition: astobj2.h:1215
Traverse in post-order (Children then node, for tree container)
Definition: astobj2.h:1145
Reject objects with duplicate keys in container.
Definition: astobj2.h:1192
Search option field mask.
Definition: astobj2.h:1076
Reject duplicate objects in container.
Definition: astobj2.h:1205
Traverse order option field mask.
Definition: astobj2.h:1123

◆ rb_ao2_find_next()

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

Definition at line 1270 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.

1271 {
1272  struct rbtree_node *node;
1273  void *arg;
1274  enum search_flags flags;
1275  int cmp;
1276 
1277  arg = state->arg;
1278  flags = state->flags;
1279 
1280  node = prev;
1281  for (;;) {
1282  /* Find next node in traversal order. */
1283  switch (flags & OBJ_ORDER_MASK) {
1284  default:
1285  case OBJ_ORDER_ASCENDING:
1286  node = rb_node_next(node);
1287  break;
1288  case OBJ_ORDER_DESCENDING:
1289  node = rb_node_prev(node);
1290  break;
1291  case OBJ_ORDER_PRE:
1292  node = rb_node_pre(node);
1293  break;
1294  case OBJ_ORDER_POST:
1295  node = rb_node_post(node);
1296  break;
1297  }
1298  if (!node) {
1299  /* No more nodes left to traverse. */
1300  break;
1301  }
1302  if (!node->common.obj) {
1303  /* Node is empty */
1304  continue;
1305  }
1306 
1307  if (state->sort_fn) {
1308  /* Filter node through the sort_fn */
1309  cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
1310  if (cmp) {
1311  /* No more nodes in this container are possible to match. */
1312  break;
1313  }
1314  }
1315 
1316  /* We have the next traversal node */
1317  ao2_ref(node, +1);
1318 
1319  /*
1320  * Dereferencing the prev node may result in our next node
1321  * object being removed by another thread. This could happen if
1322  * the container uses RW locks and the container was read
1323  * locked.
1324  */
1325  ao2_ref(prev, -1);
1326  if (node->common.obj) {
1327  return node;
1328  }
1329  prev = node;
1330  }
1331 
1332  /* No more nodes in the container left to traverse. */
1333  ao2_ref(prev, -1);
1334  return NULL;
1335 }
static struct rbtree_node * rb_node_pre(struct rbtree_node *node)
Definition: test_heap.c:38
static struct rbtree_node * rb_node_post(struct rbtree_node *node)
enum search_flags flags
search_flags
Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
Definition: astobj2.h:1038
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
Traverse in ascending order (First to last container object)
Definition: astobj2.h:1125
#define ao2_ref(o, delta)
Definition: astobj2.h:464
Traverse in descending order (Last to first container object)
Definition: astobj2.h:1127
Traverse in pre-order (Node then children, for tree container)
Definition: astobj2.h:1136
static struct rbtree_node * rb_node_prev(struct rbtree_node *node)
struct ao2_container_node common
Items common to all container nodes.
Traverse in post-order (Children then node, for tree container)
Definition: astobj2.h:1145
Search option field mask.
Definition: astobj2.h:1076
Traverse order option field mask.
Definition: astobj2.h:1123

◆ rb_ao2_insert_node()

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

Definition at line 1022 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_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, options, 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.

1023 {
1024  int cmp;
1025  struct rbtree_node *cur;
1026  struct rbtree_node *next;
1027  ao2_sort_fn *sort_fn;
1028  uint32_t options;
1029  enum equal_node_bias bias;
1030 
1031  if (!self->root) {
1032  /* The tree is empty. */
1033  self->root = node;
1035  }
1036 
1037  sort_fn = self->common.sort_fn;
1038  options = self->common.options;
1039  switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1040  default:
1042  if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
1043  bias = BIAS_FIRST;
1044  } else {
1045  bias = BIAS_LAST;
1046  }
1047  break;
1051  bias = BIAS_EQUAL;
1052  break;
1053  }
1054 
1055  /*
1056  * New nodes are always colored red when initially inserted into
1057  * the tree. (Except for the root which is always black.)
1058  */
1059  node->is_red = 1;
1060 
1061  /* Find node where normal insert would put a new node. */
1062  cur = self->root;
1063  for (;;) {
1064  if (!cur->common.obj) {
1065  /* Which direction do we go to insert this node? */
1066  if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_SEARCH_OBJECT, bias)
1067  == GO_LEFT) {
1068  if (cur->left) {
1069  cur = cur->left;
1070  continue;
1071  }
1072 
1073  /* Node becomes a left child */
1074  cur->left = node;
1075  node->parent = cur;
1076  rb_insert_fixup(self, node);
1078  }
1079  if (cur->right) {
1080  cur = cur->right;
1081  continue;
1082  }
1083 
1084  /* Node becomes a right child */
1085  cur->right = node;
1086  node->parent = cur;
1087  rb_insert_fixup(self, node);
1089  }
1090  cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1091  if (cmp > 0) {
1092  if (cur->left) {
1093  cur = cur->left;
1094  continue;
1095  }
1096 
1097  /* Node becomes a left child */
1098  cur->left = node;
1099  node->parent = cur;
1100  rb_insert_fixup(self, node);
1102  } else if (cmp < 0) {
1103  if (cur->right) {
1104  cur = cur->right;
1105  continue;
1106  }
1107 
1108  /* Node becomes a right child */
1109  cur->right = node;
1110  node->parent = cur;
1111  rb_insert_fixup(self, node);
1113  }
1114  switch (bias) {
1115  case BIAS_FIRST:
1116  /* Duplicate nodes unconditionally accepted. */
1117  if (cur->left) {
1118  cur = cur->left;
1119  continue;
1120  }
1121 
1122  /* Node becomes a left child */
1123  cur->left = node;
1124  node->parent = cur;
1125  rb_insert_fixup(self, node);
1127  case BIAS_EQUAL:
1128  break;
1129  case BIAS_LAST:
1130  /* Duplicate nodes unconditionally accepted. */
1131  if (cur->right) {
1132  cur = cur->right;
1133  continue;
1134  }
1135 
1136  /* Node becomes a right child */
1137  cur->right = node;
1138  node->parent = cur;
1139  rb_insert_fixup(self, node);
1141  }
1142 
1143  break;
1144  }
1145 
1146  /* Node is a dupliate */
1147  switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1148  default:
1150  ast_assert(0);/* Case already handled by BIAS_FIRST/BIAS_LAST. */
1153  /* Reject all objects with the same key. */
1156  if (cur->common.obj == node->common.obj) {
1157  /* Reject inserting the same object */
1159  }
1160  next = cur;
1161  if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
1162  /* Search to end of duplicates for the same object. */
1163  for (;;) {
1164  next = rb_node_next_full(next);
1165  if (!next) {
1166  break;
1167  }
1168  if (next->common.obj == node->common.obj) {
1169  /* Reject inserting the same object */
1171  }
1172  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1173  if (cmp) {
1174  break;
1175  }
1176  }
1177 
1178  /* Find first duplicate node. */
1179  for (;;) {
1180  next = rb_node_prev_full(cur);
1181  if (!next) {
1182  break;
1183  }
1184  if (next->common.obj == node->common.obj) {
1185  /* Reject inserting the same object */
1187  }
1188  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1189  if (cmp) {
1190  break;
1191  }
1192  cur = next;
1193  }
1194  if (!cur->left) {
1195  /* Node becomes a left child */
1196  cur->left = node;
1197  } else {
1198  /* Node becomes a right child */
1199  cur = rb_node_most_right(cur->left);
1200  cur->right = node;
1201  }
1202  } else {
1203  /* Search to beginning of duplicates for the same object. */
1204  for (;;) {
1205  next = rb_node_prev_full(next);
1206  if (!next) {
1207  break;
1208  }
1209  if (next->common.obj == node->common.obj) {
1210  /* Reject inserting the same object */
1212  }
1213  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1214  if (cmp) {
1215  break;
1216  }
1217  }
1218 
1219  /* Find last duplicate node. */
1220  for (;;) {
1221  next = rb_node_next_full(cur);
1222  if (!next) {
1223  break;
1224  }
1225  if (next->common.obj == node->common.obj) {
1226  /* Reject inserting the same object */
1228  }
1229  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1230  if (cmp) {
1231  break;
1232  }
1233  cur = next;
1234  }
1235  if (!cur->right) {
1236  /* Node becomes a right child */
1237  cur->right = node;
1238  } else {
1239  /* Node becomes a left child */
1240  cur = rb_node_most_left(cur->right);
1241  cur->left = node;
1242  }
1243  }
1244  break;
1246  SWAP(cur->common.obj, node->common.obj);
1247  ao2_ref(node, -1);
1249  }
1250 
1251  /* Complete inserting duplicate node. */
1252  node->parent = cur;
1253  rb_insert_fixup(self, node);
1255 }
struct rbtree_node * root
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
unsigned int is_red
Allow objects with duplicate keys in container.
Definition: astobj2.h:1185
struct rbtree_node * right
static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
int() ao2_sort_fn(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
Definition: astobj2.h:1280
#define ast_assert(a)
Definition: utils.h:695
#define SWAP(a, b)
Definition: utils.h:230
Insert objects at the beginning of the container. (Otherwise it is the opposite; insert at the end...
Definition: astobj2.h:1176
equal_node_bias
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
The ao2 container objects with duplicate keys option field mask.
Definition: astobj2.h:1181
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
#define ao2_ref(o, delta)
Definition: astobj2.h:464
struct rbtree_node * parent
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
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)
struct ao2_container_node common
Items common to all container nodes.
The arg parameter is an object of the same type.
Definition: astobj2.h:1091
Replace objects with duplicate keys in container.
Definition: astobj2.h:1215
struct rbtree_node * left
Reject objects with duplicate keys in container.
Definition: astobj2.h:1192
static struct test_options options
Reject duplicate objects in container.
Definition: astobj2.h:1205

◆ rb_ao2_iterator_next()

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

Definition at line 1635 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().

1636 {
1637  if (flags & AO2_ITERATOR_DESCENDING) {
1638  if (!node) {
1639  /* Find right most node. */
1640  if (!self->root) {
1641  return NULL;
1642  }
1643  node = rb_node_most_right(self->root);
1644  if (node->common.obj) {
1645  /* Found a non-empty node. */
1646  return node;
1647  }
1648  }
1649  /* Find next non-empty node. */
1650  node = rb_node_prev_full(node);
1651  } else {
1652  if (!node) {
1653  /* Find left most node. */
1654  if (!self->root) {
1655  return NULL;
1656  }
1657  node = rb_node_most_left(self->root);
1658  if (node->common.obj) {
1659  /* Found a non-empty node. */
1660  return node;
1661  }
1662  }
1663  /* Find next non-empty node. */
1664  node = rb_node_next_full(node);
1665  }
1666 
1667  return node;
1668 }
struct rbtree_node * root
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
struct ao2_container_node common
Items common to all container nodes.

◆ rb_ao2_new_node()

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

Definition at line 904 of file astobj2_rbtree.c.

References __ao2_ref(), AO2_ALLOC_OPT_LOCK_NOLOCK, AO2_ALLOC_OPT_NO_REF_DEBUG, ao2_alloc_options, rbtree_node::common, ao2_container_node::my_container, NULL, ao2_container_node::obj, and rb_ao2_node_destructor().

905 {
906  struct rbtree_node *node;
907 
908  node = ao2_alloc_options(sizeof(*node), rb_ao2_node_destructor,
910  if (!node) {
911  return NULL;
912  }
913 
914  __ao2_ref(obj_new, +1, tag ?: "Container node creation", file, line, func);
915  node->common.obj = obj_new;
916  node->common.my_container = (struct ao2_container *) self;
917 
918  return node;
919 }
static void rb_ao2_node_destructor(void *v_doomed)
Definition: test_heap.c:38
#define ao2_alloc_options(data_size, destructor_fn, options)
Definition: astobj2.h:406
#define NULL
Definition: resample.c:96
int __ao2_ref(void *o, int delta, const char *tag, const char *file, int line, const char *func)
Definition: astobj2.c:498
struct ao2_container_node common
Items common to all container nodes.
Generic container type.
struct ao2_container * my_container

◆ rb_ao2_node_destructor()

static void rb_ao2_node_destructor ( void *  v_doomed)
static

Definition at line 838 of file astobj2_rbtree.c.

References __adjust_lock(), __container_unlink_node, ao2_container_check(), AO2_LOCK_REQ_WRLOCK, AO2_UNLINK_NODE_UNLINK_OBJECT, AST_DEVMODE, ast_log, ao2_container_rbtree::common, rbtree_node::common, ao2_container::destroying, is_ao2_object, 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().

839 {
840  struct rbtree_node *doomed = v_doomed;
841 
842  if (doomed->common.is_linked) {
843  struct ao2_container_rbtree *my_container;
844 
845  /*
846  * Promote to write lock if not already there. Since
847  * adjust_lock() can potentially release and block waiting for a
848  * write lock, care must be taken to ensure that node references
849  * are released before releasing the container references.
850  *
851  * Node references held by an iterator can only be held while
852  * the iterator also holds a reference to the container. These
853  * node references must be unreferenced before the container can
854  * be unreferenced to ensure that the node will not get a
855  * negative reference and the destructor called twice for the
856  * same node.
857  */
858  my_container = (struct ao2_container_rbtree *) doomed->common.my_container;
859 #ifdef AST_DEVMODE
860  is_ao2_object(my_container);
861 #endif
862 
863  __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
864 
865 #if defined(AO2_DEBUG)
866  if (!my_container->common.destroying
868  ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
869  }
870 #endif /* defined(AO2_DEBUG) */
871  rb_delete_node(my_container, doomed);
872 #if defined(AO2_DEBUG)
873  if (!my_container->common.destroying
875  ast_log(LOG_ERROR, "Container integrity failed after node deletion.\n");
876  }
877 #endif /* defined(AO2_DEBUG) */
878  }
879 
880  /*
881  * We could have an object in the node if the container is being
882  * destroyed or the node had not been linked in yet.
883  */
884  if (doomed->common.obj) {
886  }
887 }
#define __container_unlink_node(node, flags)
#define AST_DEVMODE
Definition: buildopts.h:6
Assume that the ao2_container is already locked.
Definition: astobj2.h:1067
struct ao2_container common
Items common to all containers.
#define is_ao2_object(user_data)
int ao2_container_check(struct ao2_container *self, enum search_flags flags)
Perform an integrity check on the specified container.
#define ast_log
Definition: astobj2.c:42
static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
#define LOG_ERROR
Definition: logger.h:285
unsigned int destroying
TRUE if the container is being destroyed.
struct ao2_container_node common
Items common to all container nodes.
enum ao2_lock_req __adjust_lock(void *user_data, enum ao2_lock_req lock_how, int keep_stronger)
Definition: astobj2.c:425
struct ao2_container * my_container

◆ rb_delete_fixup()

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

Definition at line 584 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().

585 {
586  struct rbtree_node *sibling;
587 
588  while (self->root != child && !child->is_red) {
589  if (child->parent->left == child) {
590  /* Child is a left child. */
591  sibling = child->parent->right;
592  ast_assert(sibling != NULL);
593  if (sibling->is_red) {
594  /* Case 1: The child's sibling is red. */
595  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[0]);
596  sibling->is_red = 0;
597  child->parent->is_red = 1;
598  rb_rotate_left(self, child->parent);
599  sibling = child->parent->right;
600  ast_assert(sibling != NULL);
601  }
602  /*
603  * The sibling is black. A black node must have two children,
604  * or one red child, or no children.
605  */
606  if ((!sibling->left || !sibling->left->is_red)
607  && (!sibling->right || !sibling->right->is_red)) {
608  /*
609  * Case 2: The sibling is black and both of its children are black.
610  *
611  * This case handles the two black children or no children
612  * possibilities of a black node.
613  */
614  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[1]);
615  sibling->is_red = 1;
616  child = child->parent;
617  } else {
618  /* At this point the sibling has at least one red child. */
619  if (!sibling->right || !sibling->right->is_red) {
620  /*
621  * Case 3: The sibling is black, its left child is red, and its
622  * right child is black.
623  */
624  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[2]);
625  ast_assert(sibling->left != NULL);
626  ast_assert(sibling->left->is_red);
627  sibling->left->is_red = 0;
628  sibling->is_red = 1;
629  rb_rotate_right(self, sibling);
630  sibling = child->parent->right;
631  ast_assert(sibling != NULL);
632  }
633  /* Case 4: The sibling is black and its right child is red. */
634  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[3]);
635  sibling->is_red = child->parent->is_red;
636  child->parent->is_red = 0;
637  if (sibling->right) {
638  sibling->right->is_red = 0;
639  }
640  rb_rotate_left(self, child->parent);
641  child = self->root;
642  }
643  } else {
644  /* Child is a right child. */
645  sibling = child->parent->left;
646  ast_assert(sibling != NULL);
647  if (sibling->is_red) {
648  /* Case 1: The child's sibling is red. */
649  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[0]);
650  sibling->is_red = 0;
651  child->parent->is_red = 1;
652  rb_rotate_right(self, child->parent);
653  sibling = child->parent->left;
654  ast_assert(sibling != NULL);
655  }
656  /*
657  * The sibling is black. A black node must have two children,
658  * or one red child, or no children.
659  */
660  if ((!sibling->right || !sibling->right->is_red)
661  && (!sibling->left || !sibling->left->is_red)) {
662  /*
663  * Case 2: The sibling is black and both of its children are black.
664  *
665  * This case handles the two black children or no children
666  * possibilities of a black node.
667  */
668  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[1]);
669  sibling->is_red = 1;
670  child = child->parent;
671  } else {
672  /* At this point the sibling has at least one red child. */
673  if (!sibling->left || !sibling->left->is_red) {
674  /*
675  * Case 3: The sibling is black, its right child is red, and its
676  * left child is black.
677  */
678  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[2]);
679  ast_assert(sibling->right != NULL);
680  ast_assert(sibling->right->is_red);
681  sibling->right->is_red = 0;
682  sibling->is_red = 1;
683  rb_rotate_left(self, sibling);
684  sibling = child->parent->left;
685  ast_assert(sibling != NULL);
686  }
687  /* Case 4: The sibling is black and its left child is red. */
688  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[3]);
689  sibling->is_red = child->parent->is_red;
690  child->parent->is_red = 0;
691  if (sibling->left) {
692  sibling->left->is_red = 0;
693  }
694  rb_rotate_right(self, child->parent);
695  child = self->root;
696  }
697  }
698  }
699 
700  /*
701  * Case 2 could leave the child node red and it needs to leave
702  * with it black.
703  *
704  * Case 4 sets the child node to the root which of course must
705  * be black.
706  */
707  child->is_red = 0;
708 }
struct rbtree_node * root
static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
unsigned int is_red
struct rbtree_node * right
#define ast_assert(a)
Definition: utils.h:695
#define NULL
Definition: resample.c:96
struct rbtree_node * parent
#define AO2_DEVMODE_STAT(stat)
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
struct rbtree_node * left

◆ rb_delete_node()

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

Definition at line 720 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().

721 {
722  struct rbtree_node *child;
723  int need_fixup;
724 
725  if (doomed->left && doomed->right) {
726  struct rbtree_node *next;
727  int is_red;
728 
729  /*
730  * The doomed node has two children.
731  *
732  * Find the next child node and swap it with the doomed node in
733  * the tree.
734  */
735  AO2_DEVMODE_STAT(++self->stats.delete_children[2]);
736  next = rb_node_most_left(doomed->right);
737  SWAP(doomed->parent, next->parent);
738  SWAP(doomed->left, next->left);
739  SWAP(doomed->right, next->right);
740  is_red = doomed->is_red;
741  doomed->is_red = next->is_red;
742  next->is_red = is_red;
743 
744  /* Link back in the next node. */
745  if (!next->parent) {
746  /* Doomed was the root so we get a new root node. */
747  self->root = next;
748  } else if (next->parent->left == doomed) {
749  /* Doomed was the left child. */
750  next->parent->left = next;
751  } else {
752  /* Doomed was the right child. */
753  next->parent->right = next;
754  }
755  next->left->parent = next;
756  if (next->right == next) {
757  /* The next node was the right child of doomed. */
758  next->right = doomed;
759  doomed->parent = next;
760  } else {
761  next->right->parent = next;
762  doomed->parent->left = doomed;
763  }
764 
765  /* The doomed node has no left child now. */
766  ast_assert(doomed->left == NULL);
767 
768  /*
769  * We don't have to link the right child back in with doomed
770  * since we are going to link it with doomed's parent anyway.
771  */
772  child = doomed->right;
773  } else {
774  /* Doomed has at most one child. */
775  child = doomed->left;
776  if (!child) {
777  child = doomed->right;
778  }
779  }
780  if (child) {
781  AO2_DEVMODE_STAT(++self->stats.delete_children[1]);
782  } else {
783  AO2_DEVMODE_STAT(++self->stats.delete_children[0]);
784  }
785 
786  need_fixup = (!doomed->is_red && !self->common.destroying);
787  if (need_fixup && !child) {
788  /*
789  * Use the doomed node as a place holder node for the
790  * nonexistent child so we also don't have to pass to the fixup
791  * routine the parent and which child the deleted node came
792  * from.
793  */
794  rb_delete_fixup(self, doomed);
795  ast_assert(doomed->left == NULL);
796  ast_assert(doomed->right == NULL);
797  ast_assert(!doomed->is_red);
798  }
799 
800  /* Link the child in place of doomed. */
801  if (!doomed->parent) {
802  /* Doomed was the root so we get a new root node. */
803  self->root = child;
804  } else if (doomed->parent->left == doomed) {
805  /* Doomed was the left child. */
806  doomed->parent->left = child;
807  } else {
808  /* Doomed was the right child. */
809  doomed->parent->right = child;
810  }
811  if (child) {
812  child->parent = doomed->parent;
813  if (need_fixup) {
814  rb_delete_fixup(self, child);
815  }
816  }
817 
818  AO2_DEVMODE_STAT(--self->common.nodes);
819 }
static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
unsigned int is_red
struct rbtree_node * right
struct ao2_container common
Items common to all containers.
#define ast_assert(a)
Definition: utils.h:695
#define SWAP(a, b)
Definition: utils.h:230
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
struct rbtree_node * parent
#define AO2_DEVMODE_STAT(stat)
struct rbtree_node * left

◆ rb_find_empty_direction()

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 355 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().

356 {
357  int cmp;
358  struct rbtree_node *cur;
359  struct rbtree_node *right_most;
360 
361  /* Try for a quick definite go left. */
362  if (!empty->left) {
363  /* The empty node has no left child. */
364  return GO_RIGHT;
365  }
366  right_most = rb_node_most_right(empty->left);
367  if (right_most->common.obj) {
368  cmp = sort_fn(right_most->common.obj, obj_right, flags);
369  if (cmp < 0) {
370  return GO_RIGHT;
371  }
372  if (cmp == 0 && bias == BIAS_LAST) {
373  return GO_RIGHT;
374  }
375  return GO_LEFT;
376  }
377 
378  /* Try for a quick definite go right. */
379  if (!empty->right) {
380  /* The empty node has no right child. */
381  return GO_LEFT;
382  }
383  cur = rb_node_most_left(empty->right);
384  if (cur->common.obj) {
385  cmp = sort_fn(cur->common.obj, obj_right, flags);
386  if (cmp > 0) {
387  return GO_LEFT;
388  }
389  if (cmp == 0 && bias == BIAS_FIRST) {
390  return GO_LEFT;
391  }
392  return GO_RIGHT;
393  }
394 
395  /*
396  * Have to scan the previous nodes from the right_most node of
397  * the left subtree for the first non-empty node to determine
398  * direction.
399  */
400  cur = right_most;
401  for (;;) {
402  /* Find previous node. */
403  if (cur->left) {
404  cur = rb_node_most_right(cur->left);
405  } else {
406  /* Find the parent that the node is a right child of. */
407  for (;;) {
408  if (cur->parent == empty) {
409  /* The left side of the empty node is all empty nodes. */
410  return GO_RIGHT;
411  }
412  if (cur->parent->right == cur) {
413  /* We are the right child. The parent is the previous node. */
414  cur = cur->parent;
415  break;
416  }
417  cur = cur->parent;
418  }
419  }
420 
421  if (cur->common.obj) {
422  cmp = sort_fn(cur->common.obj, obj_right, flags);
423  if (cmp < 0) {
424  return GO_RIGHT;
425  }
426  if (cmp == 0 && bias == BIAS_LAST) {
427  return GO_RIGHT;
428  }
429  return GO_LEFT;
430  }
431  }
432 }
struct rbtree_node * right
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
struct rbtree_node * parent
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
struct ao2_container_node common
Items common to all container nodes.
struct rbtree_node * left

◆ rb_find_initial()

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

Definition at line 1353 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().

1354 {
1355  int cmp;
1356  enum search_flags sort_flags;
1357  struct rbtree_node *node;
1358  struct rbtree_node *next = NULL;
1359  ao2_sort_fn *sort_fn;
1360 
1361  sort_flags = flags & OBJ_SEARCH_MASK;
1362  sort_fn = self->common.sort_fn;
1363 
1364  /* Find node where normal search would find it. */
1365  node = self->root;
1366  if (!node) {
1367  return NULL;
1368  }
1369  for (;;) {
1370  if (!node->common.obj) {
1371  /* Which direction do we go to find the node? */
1372  if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
1373  == GO_LEFT) {
1374  next = node->left;
1375  } else {
1376  next = node->right;
1377  }
1378  if (!next) {
1379  switch (bias) {
1380  case BIAS_FIRST:
1381  /* Check successor node for match. */
1382  next = rb_node_next_full(node);
1383  break;
1384  case BIAS_EQUAL:
1385  break;
1386  case BIAS_LAST:
1387  /* Check previous node for match. */
1388  next = rb_node_prev_full(node);
1389  break;
1390  }
1391  if (next) {
1392  cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1393  if (cmp == 0) {
1394  /* Found the first/last matching node. */
1395  return next;
1396  }
1397  next = NULL;
1398  }
1399 
1400  /* No match found. */
1401  return next;
1402  }
1403  } else {
1404  cmp = sort_fn(node->common.obj, obj_right, sort_flags);
1405  if (cmp > 0) {
1406  next = node->left;
1407  } else if (cmp < 0) {
1408  next = node->right;
1409  } else {
1410  switch (bias) {
1411  case BIAS_FIRST:
1412  next = node->left;
1413  break;
1414  case BIAS_EQUAL:
1415  return node;
1416  case BIAS_LAST:
1417  next = node->right;
1418  break;
1419  }
1420  if (!next) {
1421  /* Found the first/last matching node. */
1422  return node;
1423  }
1424  }
1425  if (!next) {
1426  switch (bias) {
1427  case BIAS_FIRST:
1428  if (cmp < 0) {
1429  /* Check successor node for match. */
1430  next = rb_node_next_full(node);
1431  }
1432  break;
1433  case BIAS_EQUAL:
1434  break;
1435  case BIAS_LAST:
1436  if (cmp > 0) {
1437  /* Check previous node for match. */
1438  next = rb_node_prev_full(node);
1439  }
1440  break;
1441  }
1442  if (next) {
1443  cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1444  if (cmp == 0) {
1445  /* Found the first/last matching node. */
1446  return next;
1447  }
1448  }
1449 
1450  /* No match found. */
1451  return NULL;
1452  }
1453  }
1454  node = next;
1455  }
1456 }
Definition: test_heap.c:38
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
struct rbtree_node * right
int() ao2_sort_fn(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
Definition: astobj2.h:1280
search_flags
Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
Definition: astobj2.h:1038
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
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)
struct ao2_container_node common
Items common to all container nodes.
struct rbtree_node * left
Search option field mask.
Definition: astobj2.h:1076

◆ rb_insert_fixup()

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

Definition at line 933 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().

934 {
935  struct rbtree_node *g_parent; /* Grand parent node. */
936 
937  while (node->parent && node->parent->is_red) {
938  g_parent = node->parent->parent;
939 
940  /* The grand parent must exist if the parent is red. */
941  ast_assert(g_parent != NULL);
942 
943  if (node->parent == g_parent->left) {
944  /* The parent is a left child. */
945  if (g_parent->right && g_parent->right->is_red) {
946  /* Case 1: Push the black down from the grand parent node. */
947  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[0]);
948  g_parent->right->is_red = 0;
949  g_parent->left->is_red = 0;
950  g_parent->is_red = 1;
951 
952  node = g_parent;
953  } else {
954  /* The uncle node is black. */
955  if (node->parent->right == node) {
956  /*
957  * Case 2: The node is a right child.
958  *
959  * Which node is the grand parent does not change.
960  */
961  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[1]);
962  node = node->parent;
963  rb_rotate_left(self, node);
964  }
965  /* Case 3: The node is a left child. */
966  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[2]);
967  node->parent->is_red = 0;
968  g_parent->is_red = 1;
969  rb_rotate_right(self, g_parent);
970  }
971  } else {
972  /* The parent is a right child. */
973  if (g_parent->left && g_parent->left->is_red) {
974  /* Case 1: Push the black down from the grand parent node. */
975  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[0]);
976  g_parent->left->is_red = 0;
977  g_parent->right->is_red = 0;
978  g_parent->is_red = 1;
979 
980  node = g_parent;
981  } else {
982  /* The uncle node is black. */
983  if (node->parent->left == node) {
984  /*
985  * Case 2: The node is a left child.
986  *
987  * Which node is the grand parent does not change.
988  */
989  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
990  node = node->parent;
991  rb_rotate_right(self, node);
992  }
993  /* Case 3: The node is a right child. */
994  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
995  node->parent->is_red = 0;
996  g_parent->is_red = 1;
997  rb_rotate_left(self, g_parent);
998  }
999  }
1000  }
1001 
1002  /*
1003  * The root could be red here because:
1004  * 1) We just inserted the root node in an empty tree.
1005  *
1006  * 2) Case 1 could leave the root red if the grand parent were
1007  * the root.
1008  */
1009  self->root->is_red = 0;
1010 }
static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
unsigned int is_red
struct rbtree_node * right
#define ast_assert(a)
Definition: utils.h:695
#define NULL
Definition: resample.c:96
struct rbtree_node * parent
#define AO2_DEVMODE_STAT(stat)
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
struct rbtree_node * left

◆ rb_node_most_left()

static struct rbtree_node* rb_node_most_left ( struct rbtree_node node)
static

Definition at line 137 of file astobj2_rbtree.c.

References rbtree_node::left.

Referenced by rb_ao2_destroy(), 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().

138 {
139  while (node->left) {
140  node = node->left;
141  }
142 
143  return node;
144 }
struct rbtree_node * left

◆ rb_node_most_right()

static struct rbtree_node* rb_node_most_right ( struct rbtree_node node)
static

Definition at line 155 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().

156 {
157  while (node->right) {
158  node = node->right;
159  }
160 
161  return node;
162 }
struct rbtree_node * right

◆ rb_node_next()

static struct rbtree_node* rb_node_next ( struct rbtree_node node)
static

Definition at line 174 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_destroy(), rb_ao2_find_next(), and rb_node_next_full().

175 {
176  if (node->right) {
177  return rb_node_most_left(node->right);
178  }
179 
180  /* Find the parent that the node is a left child of. */
181  while (node->parent) {
182  if (node->parent->left == node) {
183  /* We are the left child. The parent is the next node. */
184  return node->parent;
185  }
186  node = node->parent;
187  }
188  return NULL;
189 }
struct rbtree_node * right
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
struct rbtree_node * parent
struct rbtree_node * left

◆ rb_node_next_full()

static struct rbtree_node* rb_node_next_full ( struct rbtree_node node)
static

Definition at line 309 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().

310 {
311  for (;;) {
312  node = rb_node_next(node);
313  if (!node || node->common.obj) {
314  return node;
315  }
316  }
317 }
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
struct ao2_container_node common
Items common to all container nodes.

◆ rb_node_post()

static struct rbtree_node* rb_node_post ( struct rbtree_node node)
static

Definition at line 264 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().

265 {
266  /* This node's children have already been visited. */
267  for (;;) {
268  if (!node->parent) {
269  return NULL;
270  }
271  if (node->parent->left == node) {
272  /* We came up the left child. */
273  node = node->parent;
274 
275  /*
276  * Find the right child's left most childless node.
277  */
278  while (node->right) {
279  node = rb_node_most_left(node->right);
280  }
281 
282  /*
283  * This node's left child has already been visited or it doesn't
284  * have any children.
285  */
286  return node;
287  }
288 
289  /*
290  * We came up the right child.
291  *
292  * This node's children have already been visited. Time to
293  * visit the parent.
294  */
295  return node->parent;
296  }
297 }
struct rbtree_node * right
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
struct rbtree_node * parent
struct rbtree_node * left

◆ rb_node_pre()

static struct rbtree_node* rb_node_pre ( struct rbtree_node node)
static

Definition at line 228 of file astobj2_rbtree.c.

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

Referenced by rb_ao2_destroy(), rb_ao2_find_first(), and rb_ao2_find_next().

229 {
230  /* Visit the children if the node has any. */
231  if (node->left) {
232  return node->left;
233  }
234  if (node->right) {
235  return node->right;
236  }
237 
238  /* Time to go back up. */
239  for (;;) {
240  if (!node->parent) {
241  return NULL;
242  }
243  if (node->parent->left == node && node->parent->right) {
244  /*
245  * We came up the left child and there's a right child. Visit
246  * it.
247  */
248  return node->parent->right;
249  }
250  node = node->parent;
251  }
252 }
struct rbtree_node * right
#define NULL
Definition: resample.c:96
struct rbtree_node * parent
struct rbtree_node * left

◆ rb_node_prev()

static struct rbtree_node* rb_node_prev ( struct rbtree_node node)
static

Definition at line 201 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().

202 {
203  if (node->left) {
204  return rb_node_most_right(node->left);
205  }
206 
207  /* Find the parent that the node is a right child of. */
208  while (node->parent) {
209  if (node->parent->right == node) {
210  /* We are the right child. The parent is the previous node. */
211  return node->parent;
212  }
213  node = node->parent;
214  }
215  return NULL;
216 }
struct rbtree_node * right
#define NULL
Definition: resample.c:96
struct rbtree_node * parent
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
struct rbtree_node * left

◆ rb_node_prev_full()

static struct rbtree_node* rb_node_prev_full ( struct rbtree_node node)
static

Definition at line 329 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().

330 {
331  for (;;) {
332  node = rb_node_prev(node);
333  if (!node || node->common.obj) {
334  return node;
335  }
336  }
337 }
static struct rbtree_node * rb_node_prev(struct rbtree_node *node)
struct ao2_container_node common
Items common to all container nodes.

◆ rb_rotate_left()

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

< Node's right child.

Definition at line 459 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().

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

◆ rb_rotate_right()

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

< Node's left child.

Definition at line 514 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().

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

Variable Documentation

◆ v_table_rbtree

const struct ao2_container_methods v_table_rbtree
static

rbtree container virtual method table.

Definition at line 1996 of file astobj2_rbtree.c.

Referenced by rb_ao2_container_init().