diff options
author | kaf24@scramble.cl.cam.ac.uk <kaf24@scramble.cl.cam.ac.uk> | 2004-06-10 13:21:42 +0000 |
---|---|---|
committer | kaf24@scramble.cl.cam.ac.uk <kaf24@scramble.cl.cam.ac.uk> | 2004-06-10 13:21:42 +0000 |
commit | 3e820c5daef942b7418ded75bb63a31dff7d8635 (patch) | |
tree | bfe060f3cdc8e407be6f1d611cbd47f3cae5c137 /xen/include/xen/rbtree.h | |
parent | 9e777a0acbde64bd0630b59d255894b4b7ebaec8 (diff) | |
download | xen-3e820c5daef942b7418ded75bb63a31dff7d8635.tar.gz xen-3e820c5daef942b7418ded75bb63a31dff7d8635.tar.bz2 xen-3e820c5daef942b7418ded75bb63a31dff7d8635.zip |
bitkeeper revision 1.950 (40c86066TdQwTUVQtZ0q0py10MTUgg)
Removed old I/O world and cleaned up.
Diffstat (limited to 'xen/include/xen/rbtree.h')
-rw-r--r-- | xen/include/xen/rbtree.h | 134 |
1 files changed, 0 insertions, 134 deletions
diff --git a/xen/include/xen/rbtree.h b/xen/include/xen/rbtree.h deleted file mode 100644 index bb108d7104..0000000000 --- a/xen/include/xen/rbtree.h +++ /dev/null @@ -1,134 +0,0 @@ -/* - 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 <xen/config.h> -#include <xen/lib.h> -#include <xen/module.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 */ |