include/linux/rbtree_types.h

0001 /* SPDX-License-Identifier: GPL-2.0-or-later */
0002 #ifndef _LINUX_RBTREE_TYPES_H
0003 #define _LINUX_RBTREE_TYPES_H
0004
0005 struct rb_node {
0006     unsigned long  __rb_parent_color;
0007     struct rb_node *rb_right;
0008     struct rb_node *rb_left;
0009 } __attribute__((aligned(sizeof(long))));
0010 /* The alignment might seem pointless, but allegedly CRIS needs it */
0011
0012 struct rb_root {
0013     struct rb_node *rb_node;
0014 };
0015
0016 /*
0017  * Leftmost-cached rbtrees.
0018  *
0019  * We do not cache the rightmost node based on footprint
0020  * size vs number of potential users that could benefit
0021  * from O(1) rb_last(). Just not worth it, users that want
0022  * this feature can always implement the logic explicitly.
0023  * Furthermore, users that want to cache both pointers may
0024  * find it a bit asymmetric, but that's ok.
0025  */
0026 struct rb_root_cached {
0027     struct rb_root rb_root;
0028     struct rb_node *rb_leftmost;
0029 };
0030
0031 #define RB_ROOT (struct rb_root) { NULL, }
0032 #define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL }
0033
0034 #endif