Blame view
include/linux/rbtree.h
5.13 KB
1da177e4c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
/* Red Black Trees (C) 1999 Andrea Arcangeli <andrea@suse.de> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/include/linux/rbtree.h To use rbtrees you'll have to implement your own insert and search cores. This will avoid us to use callbacks and to drop drammatically performances. I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... Some example of insert and search follows here. The search is a plain normal search over an ordered tree. The insert instead must be implemented |
3e5897402
|
28 29 30 31 |
in two steps: First, the code must insert the element in order as a red leaf in the tree, and then the support library function rb_insert_color() must be called. Such function will do the not trivial work to rebalance the rbtree, if necessary. |
1da177e4c
|
32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
----------------------------------------------------------------------- static inline struct page * rb_search_page_cache(struct inode * inode, unsigned long offset) { struct rb_node * n = inode->i_rb_page_cache.rb_node; struct page * page; while (n) { page = rb_entry(n, struct page, rb_page_cache); if (offset < page->offset) n = n->rb_left; else if (offset > page->offset) n = n->rb_right; else return page; } return NULL; } static inline struct page * __rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node) { struct rb_node ** p = &inode->i_rb_page_cache.rb_node; struct rb_node * parent = NULL; struct page * page; while (*p) { parent = *p; page = rb_entry(parent, struct page, rb_page_cache); if (offset < page->offset) p = &(*p)->rb_left; else if (offset > page->offset) p = &(*p)->rb_right; else return page; } rb_link_node(node, parent, p); return NULL; } static inline struct page * rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node) { struct page * ret; if ((ret = __rb_insert_page_cache(inode, offset, node))) goto out; rb_insert_color(node, &inode->i_rb_page_cache); out: return ret; } ----------------------------------------------------------------------- */ #ifndef _LINUX_RBTREE_H #define _LINUX_RBTREE_H #include <linux/kernel.h> #include <linux/stddef.h> struct rb_node { |
2f3243aeb
|
102 |
unsigned long rb_parent_color; |
1da177e4c
|
103 104 105 106 |
#define RB_RED 0 #define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left; |
e977145ae
|
107 108 |
} __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */ |
1da177e4c
|
109 110 111 112 113 |
struct rb_root { struct rb_node *rb_node; }; |
55a981027
|
114 |
|
2f3243aeb
|
115 116 117 118 119 120 |
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) #define rb_color(r) ((r)->rb_parent_color & 1) #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) |
55a981027
|
121 122 123 |
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) { |
2f3243aeb
|
124 |
rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; |
55a981027
|
125 |
} |
2f3243aeb
|
126 |
static inline void rb_set_color(struct rb_node *rb, int color) |
55a981027
|
127 |
{ |
2f3243aeb
|
128 |
rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; |
55a981027
|
129 |
} |
b945d6b25
|
130 |
#define RB_ROOT (struct rb_root) { NULL, } |
1da177e4c
|
131 |
#define rb_entry(ptr, type, member) container_of(ptr, type, member) |
dd67d0515
|
132 |
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) |
10fd48f23
|
133 |
#define RB_EMPTY_NODE(node) (rb_parent(node) == node) |
dd67d0515
|
134 |
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) |
1da177e4c
|
135 136 |
extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *); |
b945d6b25
|
137 138 139 140 141 142 143 |
typedef void (*rb_augment_f)(struct rb_node *node, void *data); extern void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data); extern struct rb_node *rb_augment_erase_begin(struct rb_node *node); extern void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data); |
1da177e4c
|
144 |
/* Find logical next and previous nodes in a tree */ |
f4b477c47
|
145 146 147 148 |
extern struct rb_node *rb_next(const struct rb_node *); extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *); |
1da177e4c
|
149 150 151 152 153 154 155 156 |
/* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) { |
2f3243aeb
|
157 |
node->rb_parent_color = (unsigned long )parent; |
1da177e4c
|
158 159 160 161 162 163 |
node->rb_left = node->rb_right = NULL; *rb_link = node; } #endif /* _LINUX_RBTREE_H */ |