1  /* SPDX-License-Identifier: GPL-2.0-or-later */
2  #ifndef _LINUX_RBTREE_TYPES_H
3  #define _LINUX_RBTREE_TYPES_H
4  
5  struct 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  
12  struct 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   */
26  struct 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
35