Cregit: Linux 6.9: rbtree

Contributors: 7
Author	Tokens	Token Proportion	Commits	Commit Proportion
David Woodhouse	23	31.08%	3	33.33%
Linus Torvalds	21	28.38%	1	11.11%
Davidlohr Bueso A	19	25.68%	1	11.11%
Sebastian Andrzej Siewior	8	10.81%	1	11.11%
Michel Lespinasse	1	1.35%	1	11.11%
Peter Zijlstra	1	1.35%	1	11.11%
Thomas Gleixner	1	1.35%	1	11.11%
Total	74		9

/* SPDX-License-Identifier: GPL-2.0-or-later */
#ifndef _LINUX_RBTREE_TYPES_H
#define _LINUX_RBTREE_TYPES_H

struct rb_node {
	unsigned long  __rb_parent_color;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root {
	struct rb_node *rb_node;
};

/*
 * Leftmost-cached rbtrees.
 *
 * We do not cache the rightmost node based on footprint
 * size vs number of potential users that could benefit
 * from O(1) rb_last(). Just not worth it, users that want
 * this feature can always implement the logic explicitly.
 * Furthermore, users that want to cache both pointers may
 * find it a bit asymmetric, but that's ok.
 */
struct rb_root_cached {
	struct rb_root rb_root;
	struct rb_node *rb_leftmost;
};

#define RB_ROOT (struct rb_root) { NULL, }
#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }

#endif

rbtree_types.h