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

Include dependency graph for rbtree_augmented.h:

This graph shows which files directly or indirectly include this file:

Classes
struct	rb_augment_callbacks

Macros
#define	RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME, RBSTRUCT, RBFIELD, RBAUGMENTED, RBCOMPUTE)

#define	RB_DECLARE_CALLBACKS_MAX(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

◆ __rb_color

#define __rb_color ( pc ) ((pc) & 1)

◆ __rb_is_black

#define __rb_is_black ( pc ) __rb_color(pc)

◆ __rb_is_red

#define __rb_is_red ( pc ) (!__rb_color(pc))

◆ __rb_parent

#define __rb_parent ( pc ) ((struct rb_node *)(pc & ~3))

◆ RB_BLACK

#define RB_BLACK 1

◆ rb_color

#define rb_color ( rb ) __rb_color((rb)->__rb_parent_color)

◆ RB_DECLARE_CALLBACKS

#define RB_DECLARE_CALLBACKS	(	RBSTATIC,
		RBNAME,
		RBSTRUCT,
		RBFIELD,
		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);   \
        if (RBCOMPUTE(node, true))              \
            break;                      \
        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;                \
    RBCOMPUTE(old, false);                      \
}                                   \
RBSTATIC const struct rb_augment_callbacks RBNAME = {           \
    .propagate = RBNAME ## _propagate,              \
    .copy = RBNAME ## _copy,                    \
    .rotate = RBNAME ## _rotate                 \
};

◆ RB_DECLARE_CALLBACKS_MAX

#define RB_DECLARE_CALLBACKS_MAX	(	RBSTATIC,
		RBNAME,
		RBSTRUCT,
		RBFIELD,
		RBTYPE,
		RBAUGMENTED,
		RBCOMPUTE
	)

Value:

static inline bool RBNAME ## _compute_max(RBSTRUCT *node, bool exit)          \
{                                         \
    RBSTRUCT *child;                              \
    RBTYPE max = RBCOMPUTE(node);                         \
    if (node->RBFIELD.rb_left) {                          \
        child = rb_entry(node->RBFIELD.rb_left, RBSTRUCT, RBFIELD);   \
        if (child->RBAUGMENTED > max)                     \
            max = child->RBAUGMENTED;                 \
    }                                     \
    if (node->RBFIELD.rb_right) {                         \
        child = rb_entry(node->RBFIELD.rb_right, RBSTRUCT, RBFIELD);  \
        if (child->RBAUGMENTED > max)                     \
            max = child->RBAUGMENTED;                 \
    }                                     \
    if (exit && node->RBAUGMENTED == max)                     \
        return true;                              \
    node->RBAUGMENTED = max;                          \
    return false;                                 \
}                                         \
RB_DECLARE_CALLBACKS(RBSTATIC, RBNAME,                        \
             RBSTRUCT, RBFIELD, RBAUGMENTED, RBNAME ## _compute_max)

◆ rb_is_black

#define rb_is_black ( rb ) __rb_is_black((rb)->__rb_parent_color)

◆ rb_is_red

#define rb_is_red ( rb ) __rb_is_red((rb)->__rb_parent_color)

◆ RB_RED

#define RB_RED 0

Function Documentation

◆ __rb_erase_color()

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

extern

◆ __rb_insert_augmented()

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