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