include/linux/rbtree_types.h

   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