Asterisk - The Open Source Telephony Project GIT-master-0bf3178
Data Fields
rbtree_node Struct Reference
Collaboration diagram for rbtree_node:
Collaboration graph
[legend]

Data Fields

struct ao2_container_node common
 Items common to all container nodes. More...
 
unsigned int is_red:1
 
struct rbtree_nodeleft
 
struct rbtree_nodeparent
 
struct rbtree_noderight
 

Detailed Description

A structure to hold the object held by the container and where it is located in it.

A red-black tree has the following properties:

1) Every node is either black or red.

2) The root is black.

3) If a node has a NULL child, that "child" is considered black.

4) If a node is red, then both of its children are black.

5) Every path from a node to a descendant NULL child has the same number of black nodes. (Including the black NULL child.)

Definition at line 51 of file astobj2_rbtree.c.

Field Documentation

◆ common

struct ao2_container_node common

Items common to all container nodes.

Note
Must be first in the specific node struct.

Definition at line 56 of file astobj2_rbtree.c.

Referenced by rb_ao2_insert_node(), rb_ao2_node_destructor(), rb_find_empty_direction(), and rb_find_initial().

◆ is_red

unsigned int is_red

TRUE if the node is red.

Definition at line 64 of file astobj2_rbtree.c.

Referenced by rb_delete_fixup(), rb_delete_node(), and rb_insert_fixup().

◆ left

struct rbtree_node* left

Left child node of this node. NULL if does not have this child.

Definition at line 60 of file astobj2_rbtree.c.

Referenced by rb_ao2_insert_node(), rb_delete_fixup(), rb_delete_node(), rb_find_empty_direction(), rb_insert_fixup(), and rb_rotate_left().

◆ parent

struct rbtree_node* parent

Parent node of this node. NULL if this is the root node.

Definition at line 58 of file astobj2_rbtree.c.

Referenced by rb_delete_fixup(), rb_delete_node(), rb_find_empty_direction(), rb_rotate_left(), and rb_rotate_right().

◆ right

struct rbtree_node* right

Right child node of this node. NULL if does not have this child.

Definition at line 62 of file astobj2_rbtree.c.

Referenced by rb_ao2_insert_node(), rb_delete_fixup(), rb_delete_node(), rb_find_empty_direction(), rb_insert_fixup(), and rb_rotate_right().


The documentation for this struct was generated from the following file: