WebSVN - shark - Blame - Rev 422 - /shark/trunk/drivers/linuxc26/include/linux/rbtree.h

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

Subversion Repositories shark

(root)/shark/trunk/drivers/linuxc26/include/linux/rbtree.h - Rev 422