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
	)

References __rb_erase_color(), color(), node, 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

)

References n, and 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
	)

References __rb_rotate_left(), __rb_rotate_right(), node, 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

)

References n, and rb_root::rb_node.

rb_link_node()

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

inlinestatic

References node.

Referenced by __add_timer().

rb_next()

struct rb_node * rb_next

(

const struct rb_node *

node

)

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

)

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
	)

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

rb_set_color()

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

inlinestatic

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  )

inlinestatic

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