| 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 | |
|---|
