linux/lib/rbtree.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <[email protected]>
  (C) 2002  David Woodhouse <[email protected]>
  (C) 2012  Michel Lespinasse <[email protected]>


  linux/lib/rbtree.c
*/

#include <linux/rbtree_augmented.h>
#include <linux/export.h>

/*
 * red-black trees properties:  https://en.wikipedia.org/wiki/Rbtree
 *
 *  1) A node is either red or black
 *  2) The root is black
 *  3) All leaves (NULL) are black
 *  4) Both children of every red node are black
 *  5) Every simple path from root to leaves contains the same number
 *     of black nodes.
 *
 *  4 and 5 give the O(log n) guarantee, since 4 implies you cannot have two
 *  consecutive red nodes in a path and every red node is therefore followed by
 *  a black. So if B is the number of black nodes on every simple path (as per
 *  5), then the longest possible path due to 4 is 2B.
 *
 *  We shall indicate color with case, where black nodes are uppercase and red
 *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
 *  parentheses and have some accompanying text comment.
 */

/*
 * Notes on lockless lookups:
 *
 * All stores to the tree structure (rb_left and rb_right) must be done using
 * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
 * tree structure as seen in program order.
 *
 * These two requirements will allow lockless iteration of the tree -- not
 * correct iteration mind you, tree rotations are not atomic so a lookup might
 * miss entire subtrees.
 *
 * But they do guarantee that any such traversal will only see valid elements
 * and that it will indeed complete -- does not get stuck in a loop.
 *
 * It also guarantees that if the lookup returns an element it is the 'correct'
 * one. But not returning an element does _NOT_ mean it's not present.
 *
 * NOTE:
 *
 * Stores to __rb_parent_color are not important for simple lookups so those
 * are left undone as of now. Nor did I check for loops involving parent
 * pointers.
 */

static inline void rb_set_black(struct rb_node *rb)
{ … }

static inline struct rb_node *rb_red_parent(struct rb_node *red)
{ … }

/*
 * Helper function for rotations:
 * - old's parent and color get assigned to new
 * - old gets assigned new as a parent and 'color' as a color.
 */
static inline void
__rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
			struct rb_root *root, int color)
{ … }

static __always_inline void
__rb_insert(struct rb_node *node, struct rb_root *root,
	    void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{ … }

/*
 * Inline version for rb_erase() use - we want to be able to inline
 * and eliminate the dummy_rotate callback there
 */
static __always_inline void
____rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{ … }

/* Non-inline version for rb_erase_augmented() use */
void __rb_erase_color(struct rb_node *parent, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{ … }
EXPORT_SYMBOL(…);

/*
 * Non-augmented rbtree manipulation functions.
 *
 * We use dummy augmented callbacks here, and have the compiler optimize them
 * out of the rb_insert_color() and rb_erase() function definitions.
 */

static inline void dummy_propagate(struct rb_node *node, struct rb_node *stop) { … }
static inline void dummy_copy(struct rb_node *old, struct rb_node *new) { … }
static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) { … }

static const struct rb_augment_callbacks dummy_callbacks = …;

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

void rb_erase(struct rb_node *node, struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

/*
 * Augmented rbtree manipulation functions.
 *
 * This instantiates the same __always_inline functions as in the non-augmented
 * case, but this time with user-defined callbacks.
 */

void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
	void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
{ … }
EXPORT_SYMBOL(…);

/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(const struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

struct rb_node *rb_last(const struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

struct rb_node *rb_next(const struct rb_node *node)
{ … }
EXPORT_SYMBOL(…);

struct rb_node *rb_prev(const struct rb_node *node)
{ … }
EXPORT_SYMBOL(…);

void rb_replace_node(struct rb_node *victim, struct rb_node *new,
		     struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new,
			 struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);

static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
{ … }

struct rb_node *rb_next_postorder(const struct rb_node *node)
{ … }
EXPORT_SYMBOL(…);

struct rb_node *rb_first_postorder(const struct rb_root *root)
{ … }
EXPORT_SYMBOL(…);