diff options
Diffstat (limited to 'linux-2.4.x/include/linux/rbtree-24.h')
-rw-r--r-- | linux-2.4.x/include/linux/rbtree-24.h | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/linux-2.4.x/include/linux/rbtree-24.h b/linux-2.4.x/include/linux/rbtree-24.h new file mode 100644 index 0000000..f007490 --- /dev/null +++ b/linux-2.4.x/include/linux/rbtree-24.h @@ -0,0 +1,133 @@ +/* + 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 + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, 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. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + rb_node_t * 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, + rb_node_t * node) +{ + rb_node_t ** p = &inode->i_rb_page_cache.rb_node; + rb_node_t * 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, + rb_node_t * 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> + +typedef struct rb_node_s +{ + struct rb_node_s * rb_parent; + int rb_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node_s * rb_right; + struct rb_node_s * rb_left; +} +rb_node_t; + +typedef struct rb_root_s +{ + struct rb_node_s * rb_node; +} +rb_root_t; + +#define RB_ROOT (rb_root_t) { NULL, } +#define rb_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + +extern void rb_insert_color(rb_node_t *, rb_root_t *); +extern void rb_erase(rb_node_t *, rb_root_t *); + +static inline void rb_link_node(rb_node_t * node, rb_node_t * parent, rb_node_t ** rb_link) +{ + node->rb_parent = parent; + node->rb_color = RB_RED; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ |