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) ((struct rb_node *)((r)->rb_parent_color & ~3))
#define | rb_color(r) ((r)->rb_parent_color & 1)
#define | rb_is_red(r) (!rb_color(r))
#define | rb_is_black(r) rb_color(r)
#define | rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
#define | rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
#define | RB_ROOT { NULL, }
#define | rb_entry(ptr, type, member) container_of(ptr, type, member)
#define | RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
#define | RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define | RB_CLEAR_NODE(node) (rb_set_parent(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

## RB_CLEAR_NODE

#define RB_CLEAR_NODE | ( |  | node | ) | (rb_set_parent(node, node))

## rb_color

#define rb_color | ( |  | r | ) | ((r)->rb_parent_color & 1)

## RB_EMPTY_NODE

#define RB_EMPTY_NODE | ( |  | node | ) | (rb_parent(node) == node)

## RB_EMPTY_ROOT

#define RB_EMPTY_ROOT | ( |  | root | ) | ((root)->rb_node == NULL)

## rb_entry

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

## rb_is_black

#define rb_is_black | ( |  | r | ) | rb_color(r)

## rb_is_red

#define rb_is_red | ( |  | r | ) | (!rb_color(r))

## rb_parent

#define rb_parent | ( |  | r | ) | ((struct rb_node *)((r)->rb_parent_color & ~3))

## RB_RED

#define RB_RED 0

## RB_ROOT

#define RB_ROOT { NULL, }

## rb_set_black

#define rb_set_black | ( |  | r | ) | do { (r)->rb_parent_color |= 1; } while (0)

## rb_set_red

#define rb_set_red | ( |  | r | ) | do { (r)->rb_parent_color &= ~1; } while (0)

## 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(), node, RB_BLACK, rb_color, rb_left, rb_node::rb_left, rb_parent, rb_node::rb_right, rb_set_parent(), and subsys.

Referenced by osmo_timer_del().

## rb_first()

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

extern

References n, and subsys.

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(), node, rb_is_red, rb_node::rb_left, rb_parent, rb_node::rb_right, rb_set_black, rb_set_red, and subsys.

Referenced by __add_timer().

## rb_last()

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

extern

References n, and subsys.

## rb_link_node()

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

inline static

References node.

Referenced by __add_timer().

## rb_next()

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

extern

References node, 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 node, 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_parent, rb_node::rb_right, rb_set_parent(), and subsys.

## rb_set_color()

static 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()

static 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