rbtree_augmented.h File Reference

#include <linux/compiler.h>
#include <linux/rbtree.h>

Go to the source code of this file.

Data Structures
struct	rb_augment_callbacks

Macros
#define	RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield, rbtype, rbaugmented, rbcompute)
#define	RB_RED   0
#define	RB_BLACK   1
#define	__rb_parent(pc)   ((struct rb_node *)(pc & ~3))
#define	__rb_color(pc)   ((pc) & 1)
#define	__rb_is_black(pc)   __rb_color(pc)
#define	__rb_is_red(pc)   (!__rb_color(pc))
#define	rb_color(rb)   __rb_color((rb)->__rb_parent_color)
#define	rb_is_red(rb)   __rb_is_red((rb)->__rb_parent_color)
#define	rb_is_black(rb)   __rb_is_black((rb)->__rb_parent_color)

Functions
void	__rb_insert_augmented (struct rb_node *node, struct rb_root *root, void(*augment_rotate)(struct rb_node *old, struct rb_node *new))
void	__rb_erase_color (struct rb_node *parent, struct rb_root *root, void(*augment_rotate)(struct rb_node *old, struct rb_node *new))

Macro Definition Documentation

#define __rb_color

(

pc

)

((pc) & 1)

Definition at line 92 of file rbtree_augmented.h.

#define __rb_is_black

(

pc

)

__rb_color(pc)

Definition at line 93 of file rbtree_augmented.h.

#define __rb_is_red

(

pc

)

(!__rb_color(pc))

Definition at line 94 of file rbtree_augmented.h.

#define __rb_parent

(

pc

)

((struct rb_node *)(pc & ~3))

Definition at line 90 of file rbtree_augmented.h.

#define RB_BLACK   1

Definition at line 88 of file rbtree_augmented.h.

#define rb_color

(

rb

)

__rb_color((rb)->__rb_parent_color)

Definition at line 95 of file rbtree_augmented.h.

#define RB_DECLARE_CALLBACKS	(		rbstatic,
			rbname,
			rbstruct,
			rbfield,
			rbtype,
			rbaugmented,
			rbcompute
	)

Value:

static inline void                          \
rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)      \
{                                   \
    while (rb != stop) {                        \
        rbstruct *node = rb_entry(rb, rbstruct, rbfield);   \
        rbtype augmented = rbcompute(node);         \
        if (node->rbaugmented == augmented)         \
            break;                      \
		node->rbaugmented = augmented;                \
        rb = rb_parent(&node->rbfield);             \
    }                               \
}                                   \
static inline void                          \
rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)     \
{                                   \
    rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);        \
    rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);        \
    new->rbaugmented = old->rbaugmented;                \
}                                   \
static void                             \
rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)   \
{                                   \
    rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);        \
    rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);        \
    new->rbaugmented = old->rbaugmented;                \
    old->rbaugmented = rbcompute(old);              \
}                                   \
rbstatic const struct rb_augment_callbacks rbname = {           \
    rbname ## _propagate, rbname ## _copy, rbname ## _rotate    \
};

Definition at line 53 of file rbtree_augmented.h.

#define rb_is_black

(

rb

)

__rb_is_black((rb)->__rb_parent_color)

Definition at line 97 of file rbtree_augmented.h.

#define rb_is_red

(

rb

)

__rb_is_red((rb)->__rb_parent_color)

Definition at line 96 of file rbtree_augmented.h.

#define RB_RED   0

Definition at line 87 of file rbtree_augmented.h.

Function Documentation

void __rb_erase_color	(	struct rb_node *	parent,
		struct rb_root *	root,
		void(*)(struct rb_node *old, struct rb_node *new)	augment_rotate
	)

Definition at line 198 of file rbtree.c.

void __rb_insert_augmented	(	struct rb_node *	node,
		struct rb_root *	root,
		void(*)(struct rb_node *old, struct rb_node *new)	augment_rotate
	)

Definition at line 394 of file rbtree.c.