rbtree.h File Reference

#include <linux/container_of.h>
#include <linux/rbtree_types.h>
#include <linux/stddef.h>
#include <linux/rcupdate.h>

Include dependency graph for rbtree.h:

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

Go to the source code of this file.

Macros
#define	rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
#define	rb_entry(ptr, type, member)   container_of(ptr, type, member)
#define	RB_EMPTY_ROOT(root)   (READ_ONCE((root)->rb_node) == NULL)
#define	RB_EMPTY_NODE(node)    ((node)->__rb_parent_color == (uintptr_t)(node))
#define	RB_CLEAR_NODE(node)    ((node)->__rb_parent_color = (uintptr_t)(node))
#define	RB_EMPTY_LINKED_NODE(lnode)   RB_EMPTY_NODE(&(lnode)->node)
#define	RB_CLEAR_LINKED_NODE(lnode)
#define	rb_entry_safe(ptr, type, member)
#define	rbtree_postorder_for_each_entry_safe(pos, n, root, field)
#define	rb_first_cached(root)   (root)->rb_leftmost
#define	__node_2_linked_node(_n)    rb_entry((_n), struct rb_node_linked, node)
#define	rb_for_each(node, key, tree, cmp)

Functions
void	rb_insert_color (struct rb_node *, struct rb_root *)
void	rb_erase (struct rb_node *, struct rb_root *)
bool	rb_erase_linked (struct rb_node_linked *, struct rb_root_linked *)
struct rb_node *	rb_next (const struct rb_node *)
struct rb_node *	rb_prev (const struct rb_node *)
struct rb_node *	rb_first_postorder (const struct rb_root *)
struct rb_node *	rb_next_postorder (const struct rb_node *)
void	rb_replace_node (struct rb_node *victim, struct rb_node *new, struct rb_root *root)
void	rb_replace_node_rcu (struct rb_node *victim, struct rb_node *new, struct rb_root *root)

Macro Definition Documentation

__node_2_linked_node

#define __node_2_linked_node

(

_n

)

rb_entry((_n), struct rb_node_linked, node)

RB_CLEAR_LINKED_NODE

#define RB_CLEAR_LINKED_NODE

(

lnode

)

Value:

    ({                  \
    RB_CLEAR_NODE(&(lnode)->node);                  \
    (lnode)->prev = (lnode)->next = NULL;               \
})

RB_CLEAR_NODE

#define RB_CLEAR_NODE

(

node

)

((node)->__rb_parent_color = (uintptr_t)(node))

RB_EMPTY_LINKED_NODE

#define RB_EMPTY_LINKED_NODE

(

lnode

)

RB_EMPTY_NODE(&(lnode)->node)

RB_EMPTY_NODE

#define RB_EMPTY_NODE

(

node

)

((node)->__rb_parent_color == (uintptr_t)(node))

RB_EMPTY_ROOT

#define RB_EMPTY_ROOT

(

root

)

(READ_ONCE((root)->rb_node) == NULL)

rb_entry

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

rb_entry_safe

#define rb_entry_safe	(		ptr,
			type,
			member
	)

Value:

    ({ typeof(ptr) ____ptr = (ptr); \
       ____ptr ? rb_entry(____ptr, type, member) : NULL; \
    })

rb_first_cached

#define rb_first_cached

(

root

)

(root)->rb_leftmost

rb_for_each

#define rb_for_each	(		node,
			key,
			tree,
			cmp
	)

Value:

    for ((node) = rb_find_first((key), (tree), (cmp)); \
         (node); (node) = rb_next_match((key), (node), (cmp)))

rb_for_each() - iterates a subtree matching @key @node: iterator @key: key to match @tree: tree to search @cmp: operator defining node order

rb_parent

#define rb_parent

(

r

)

((struct rb_node *)((r)->__rb_parent_color & ~3))

rbtree_postorder_for_each_entry_safe

#define rbtree_postorder_for_each_entry_safe	(		pos,
			n,
			root,
			field
	)

Value:

    for (pos = rb_entry_safe(rb_first_postorder(root), typeof(*pos), field); \
         pos && ({ n = rb_entry_safe(rb_next_postorder(&pos->field), \
            typeof(*pos), field); 1; }); \
         pos = n)

rbtree_postorder_for_each_entry_safe - iterate in post-order over rb_root of given type allowing the backing memory of @pos to be invalidated

@pos: the 'type *' to use as a loop cursor.
: another 'type *' to use as temporary storage @root: 'rb_root *' of the rbtree. @field: the name of the rb_node field within 'type'.

rbtree_postorder_for_each_entry_safe() provides a similar guarantee as list_for_each_entry_safe() and allows the iteration to continue independent of changes to @pos by the body of the loop.

Note, however, that it cannot handle other modifications that re-order the rbtree it is iterating over. This includes calling rb_erase() on @pos, as rb_erase() may rebalance the tree, causing us to miss some nodes.

Function Documentation

rb_erase()

void rb_erase ( struct rb_node *  , struct rb_root *    )

extern

rb_erase_linked()

bool rb_erase_linked ( struct rb_node_linked *  , struct rb_root_linked *    )

extern

rb_first_postorder()

struct rb_node * rb_first_postorder ( const struct rb_root *  )

extern

rb_insert_color()

void rb_insert_color ( struct rb_node *  , struct rb_root *    )

extern

rb_next()

struct rb_node * rb_next ( const struct rb_node *  )

extern

rb_next_postorder()

struct rb_node * rb_next_postorder ( const struct rb_node *  )

extern

rb_prev()

struct rb_node * rb_prev ( const struct rb_node *  )

extern

rb_replace_node()

void rb_replace_node ( struct rb_node *  victim, struct rb_node *  new, struct rb_root *  root  )

extern

rb_replace_node_rcu()

void rb_replace_node_rcu ( struct rb_node *  victim, struct rb_node *  new, struct rb_root *  root  )

extern