Loading...
Searching...
No Matches
linuxrbtree.h File Reference
`#include <stdlib.h>`

Go to the source code of this file.

## Data Structures

struct | rb_node
struct | rb_root

## Macros

#define | RB_RED 0
#define | RB_BLACK 1
#define | rb_parent(r)
#define | rb_color(r)
#define | rb_is_red(r)
#define | rb_is_black(r)
#define | rb_set_red(r)
#define | rb_set_black(r)
#define | RB_ROOT { NULL, }
#define | rb_entry(ptr, type, member)
#define | RB_EMPTY_ROOT(root)
#define | RB_EMPTY_NODE(node)
#define | RB_CLEAR_NODE(node)

## Functions

struct rb_node | __attribute__ ((aligned(sizeof(long))))
static void | rb_set_parent (struct rb_node *rb, struct rb_node *p)
static void | rb_set_color (struct rb_node *rb, int color)
void | rb_insert_color (struct rb_node *, struct rb_root *)
void | rb_erase (struct rb_node *, struct rb_root *)
struct rb_node * | rb_next (const struct rb_node *)
struct rb_node * | rb_prev (const struct rb_node *)
struct rb_node * | rb_first (const struct rb_root *)
struct rb_node * | rb_last (const struct rb_root *)
void | rb_replace_node (struct rb_node *victim, struct rb_node *_new, struct rb_root *root)
static void | rb_link_node (struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link)

## Variables

unsigned long | rb_parent_color
struct rb_node * | rb_right
struct rb_node * | rb_left
struct rb_root | __attribute__

## Macro Definition Documentation

## RB_BLACK

#define RB_BLACK 1

Referenced by rb_erase().

## RB_CLEAR_NODE

#define RB_CLEAR_NODE | ( |  | node | ) |

Value:
(rb_set_parent(node, node))
node
struct cmd_node * node
rb_set_parent
static void rb_set_parent(struct rb_node *rb, struct rb_node *p)
Definition linuxrbtree.h:117

## rb_color

#define rb_color | ( |  | r | ) |

Value:
((r)->rb_parent_color & 1)

Referenced by __rb_erase_color(), and rb_erase().

## RB_EMPTY_NODE

#define RB_EMPTY_NODE | ( |  | node | ) |

Value:
(rb_parent(node) == node)
rb_parent
#define rb_parent(r)
Definition linuxrbtree.h:110

## RB_EMPTY_ROOT

#define RB_EMPTY_ROOT | ( |  | root | ) |

Value:
((root)->rb_node == NULL)

## rb_entry

#define rb_entry | ( |  | ptr,
|  |  | type,
|  |  | member )

Value:
container_of(ptr, type, member)
container_of
#define container_of(ptr, type, member)
Cast a member of a structure out to the containing structure.
Definition linuxlist.h:32
type
uint8_t type

## rb_is_black

#define rb_is_black | ( |  | r | ) |

Value:
rb_color(r)
rb_color
#define rb_color(r)
Definition linuxrbtree.h:111

Referenced by __rb_erase_color().

## rb_is_red

#define rb_is_red | ( |  | r | ) |

Value:
(!rb_color(r))

Referenced by __rb_erase_color(), and rb_insert_color().

## rb_parent

#define rb_parent | ( |  | r | ) |

Value:
((struct rb_node *)((r)->rb_parent_color & ~3))
rb_node
Definition linuxrbtree.h:95

Referenced by __rb_erase_color(), __rb_rotate_left(), __rb_rotate_right(), rb_erase(), rb_insert_color(), rb_next(), rb_prev(), and rb_replace_node().

## RB_RED

#define RB_RED 0

## RB_ROOT

#define RB_ROOT { NULL, }

## rb_set_black

#define rb_set_black | ( |  | r | ) |

Value:
do { (r)->rb_parent_color |= 1; } while (0)
rb_parent_color
unsigned long rb_parent_color
Definition linuxrbtree.h:0

Referenced by __rb_erase_color(), and rb_insert_color().

## rb_set_red

#define rb_set_red | ( |  | r | ) |

Value:
do { (r)->rb_parent_color &= ~1; } while (0)

Referenced by __rb_erase_color(), and rb_insert_color().

## Function Documentation

## __attribute__()

struct rb_node __attribute__ | ( | (aligned(sizeof(long))) |  | ) |

## rb_erase()

void rb_erase | ( | struct rb_node * | node,
|  | struct rb_root * | root )

extern

References __rb_erase_color(), color(), RB_BLACK, rb_color, rb_left, rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_parent_color, rb_node::rb_right, and rb_set_parent().

Referenced by osmo_timer_del().

## rb_first()

struct rb_node * rb_first | ( | const struct rb_root * | root | ) |

extern

References rb_root::rb_node.

Referenced by osmo_timers_check(), osmo_timers_prepare(), and osmo_timers_update().

## rb_insert_color()

void rb_insert_color | ( | struct rb_node * | node,
|  | struct rb_root * | root )

extern

References __rb_rotate_left(), __rb_rotate_right(), rb_is_red, rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_right, rb_set_black, and rb_set_red.

Referenced by __add_timer().

## rb_last()

struct rb_node * rb_last | ( | const struct rb_root * | root | ) |

extern

References rb_root::rb_node.

## rb_link_node()

void rb_link_node | ( | struct rb_node * | node,
|  | struct rb_node * | parent,
|  | struct rb_node ** | rb_link )

inline static

Referenced by __add_timer().

## rb_next()

struct rb_node * rb_next | ( | const struct rb_node * | node | ) |

extern

References rb_parent, and rb_node::rb_right.

Referenced by osmo_timers_check(), and osmo_timers_update().

## rb_prev()

struct rb_node * rb_prev | ( | const struct rb_node * | node | ) |

extern

References rb_node::rb_left, and rb_parent.

## rb_replace_node()

void rb_replace_node | ( | struct rb_node * | victim,
|  | struct rb_node * | _new,
|  | struct rb_root * | root )

extern

References rb_node::rb_left, rb_root::rb_node, rb_parent, rb_node::rb_right, and rb_set_parent().

## rb_set_color()

void rb_set_color | ( | struct rb_node * | rb,
|  | int | color )

inline static

References color(), and rb_node::rb_parent_color.

Referenced by __rb_erase_color().

## rb_set_parent()

void rb_set_parent | ( | struct rb_node * | rb,
|  | struct rb_node * | p )

inline static

References rb_node::rb_parent_color.

Referenced by __rb_rotate_left(), __rb_rotate_right(), rb_erase(), and rb_replace_node().

## Variable Documentation

## __attribute__

struct rb_root __attribute__

## rb_left

struct rb_node* rb_left

Referenced by rb_erase().

## rb_parent_color

unsigned long rb_parent_color

## rb_right

struct rb_node* rb_right