diff options
Diffstat (limited to 'linux-2.4.x/include/linux/rbtree.h')
| -rw-r--r-- | linux-2.4.x/include/linux/rbtree.h | 144 |
1 files changed, 18 insertions, 126 deletions
diff --git a/linux-2.4.x/include/linux/rbtree.h b/linux-2.4.x/include/linux/rbtree.h index 96f20e1..62c407a 100644 --- a/linux-2.4.x/include/linux/rbtree.h +++ b/linux-2.4.x/include/linux/rbtree.h @@ -1,133 +1,25 @@ /* - 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. + * 2.5 compatibility + * $Id: rbtree.h,v 1.3 2003/01/14 13:56:05 dwmw2 Exp $ + */ - 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. +#ifndef __MTD_COMPAT_RBTREE_H__ +#define __MTD_COMPAT_RBTREE_H__ - 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 +#include <linux/version.h> - linux/include/linux/rbtree.h +#if LINUX_VERSION_CODE >= KERNEL_VERSION(2,5,40) +#include_next <linux/rbtree.h> +#else +#define rb_node_s rb_node +#define rb_root_s rb_root - 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... +#include <linux/rbtree-24.h> - 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. +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +#endif ------------------------------------------------------------------------ -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 */ +#endif /* __MTD_COMPAT_RBTREE_H__ */ |