rbtree_types.h (946B)
1/* SPDX-License-Identifier: GPL-2.0-or-later */ 2#ifndef _LINUX_RBTREE_TYPES_H 3#define _LINUX_RBTREE_TYPES_H 4 5struct rb_node { 6 unsigned long __rb_parent_color; 7 struct rb_node *rb_right; 8 struct rb_node *rb_left; 9} __attribute__((aligned(sizeof(long)))); 10/* The alignment might seem pointless, but allegedly CRIS needs it */ 11 12struct rb_root { 13 struct rb_node *rb_node; 14}; 15 16/* 17 * Leftmost-cached rbtrees. 18 * 19 * We do not cache the rightmost node based on footprint 20 * size vs number of potential users that could benefit 21 * from O(1) rb_last(). Just not worth it, users that want 22 * this feature can always implement the logic explicitly. 23 * Furthermore, users that want to cache both pointers may 24 * find it a bit asymmetric, but that's ok. 25 */ 26struct rb_root_cached { 27 struct rb_root rb_root; 28 struct rb_node *rb_leftmost; 29}; 30 31#define RB_ROOT (struct rb_root) { NULL, } 32#define RB_ROOT_CACHED (struct rb_root_cached) { {NULL, }, NULL } 33 34#endif