1 /* 2 Red Black Trees 3 (C) 1999 Andrea Arcangeli <andrea@suse.de> 4 5 * SPDX-License-Identifier: GPL-2.0+ 6 7 linux/include/linux/rbtree.h 8 9 To use rbtrees you'll have to implement your own insert and search cores. 10 This will avoid us to use callbacks and to drop drammatically performances. 11 I know it's not the cleaner way, but in C (not in C++) to get 12 performances and genericity... 13 14 Some example of insert and search follows here. The search is a plain 15 normal search over an ordered tree. The insert instead must be implemented 16 int two steps: as first thing the code must insert the element in 17 order as a red leaf in the tree, then the support library function 18 rb_insert_color() must be called. Such function will do the 19 not trivial work to rebalance the rbtree if necessary. 20 21 ----------------------------------------------------------------------- 22 static inline struct page * rb_search_page_cache(struct inode * inode, 23 unsigned long offset) 24 { 25 struct rb_node * n = inode->i_rb_page_cache.rb_node; 26 struct page * page; 27 28 while (n) 29 { 30 page = rb_entry(n, struct page, rb_page_cache); 31 32 if (offset < page->offset) 33 n = n->rb_left; 34 else if (offset > page->offset) 35 n = n->rb_right; 36 else 37 return page; 38 } 39 return NULL; 40 } 41 42 static inline struct page * __rb_insert_page_cache(struct inode * inode, 43 unsigned long offset, 44 struct rb_node * node) 45 { 46 struct rb_node ** p = &inode->i_rb_page_cache.rb_node; 47 struct rb_node * parent = NULL; 48 struct page * page; 49 50 while (*p) 51 { 52 parent = *p; 53 page = rb_entry(parent, struct page, rb_page_cache); 54 55 if (offset < page->offset) 56 p = &(*p)->rb_left; 57 else if (offset > page->offset) 58 p = &(*p)->rb_right; 59 else 60 return page; 61 } 62 63 rb_link_node(node, parent, p); 64 65 return NULL; 66 } 67 68 static inline struct page * rb_insert_page_cache(struct inode * inode, 69 unsigned long offset, 70 struct rb_node * node) 71 { 72 struct page * ret; 73 if ((ret = __rb_insert_page_cache(inode, offset, node))) 74 goto out; 75 rb_insert_color(node, &inode->i_rb_page_cache); 76 out: 77 return ret; 78 } 79 ----------------------------------------------------------------------- 80 */ 81 82 #ifndef _LINUX_RBTREE_H 83 #define _LINUX_RBTREE_H 84 85 #include <linux/stddef.h> 86 87 struct rb_node 88 { 89 unsigned long rb_parent_color; 90 #define RB_RED 0 91 #define RB_BLACK 1 92 struct rb_node *rb_right; 93 struct rb_node *rb_left; 94 } __attribute__((aligned(sizeof(long)))); 95 /* The alignment might seem pointless, but allegedly CRIS needs it */ 96 97 struct rb_root 98 { 99 struct rb_node *rb_node; 100 }; 101 102 103 #define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) 104 #define rb_color(r) ((r)->rb_parent_color & 1) 105 #define rb_is_red(r) (!rb_color(r)) 106 #define rb_is_black(r) rb_color(r) 107 #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) 108 #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) 109 110 static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) 111 { 112 rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; 113 } 114 static inline void rb_set_color(struct rb_node *rb, int color) 115 { 116 rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; 117 } 118 119 #define RB_ROOT (struct rb_root) { NULL, } 120 #define rb_entry(ptr, type, member) container_of(ptr, type, member) 121 122 #define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) 123 #define RB_EMPTY_NODE(node) (rb_parent(node) == node) 124 #define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) 125 126 extern void rb_insert_color(struct rb_node *, struct rb_root *); 127 extern void rb_erase(struct rb_node *, struct rb_root *); 128 129 /* Find logical next and previous nodes in a tree */ 130 extern struct rb_node *rb_next(struct rb_node *); 131 extern struct rb_node *rb_prev(struct rb_node *); 132 extern struct rb_node *rb_first(struct rb_root *); 133 extern struct rb_node *rb_last(struct rb_root *); 134 135 /* Fast replacement of a single node without remove/rebalance/add/rebalance */ 136 extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 137 struct rb_root *root); 138 139 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, 140 struct rb_node ** rb_link) 141 { 142 node->rb_parent_color = (unsigned long )parent; 143 node->rb_left = node->rb_right = NULL; 144 145 *rb_link = node; 146 } 147 148 #endif /* _LINUX_RBTREE_H */ 149