[people/ms/u-boot.git] / include / linux / rbtree.h

/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <andrea@suse.de>

 * SPDX-License-Identifier:	GPL-2.0+

  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)
{
	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/stddef.h>

struct rb_node
{
	unsigned long  rb_parent_color;
#define	RB_RED		0
#define	RB_BLACK	1
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
	struct rb_node *rb_node;
};


#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)

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node)	(rb_parent(node) == node)
#define RB_CLEAR_NODE(node)	(rb_set_parent(node, node))

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

/* 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 *);
extern struct rb_node *rb_last(struct rb_root *);

/* 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)
{
	node->rb_parent_color = (unsigned long )parent;
	node->rb_left = node->rb_right = NULL;

	*rb_link = node;
}

#endif	/* _LINUX_RBTREE_H */
Commit	Line	Data
7ba890bf KP	1	/*
	2	Red Black Trees
	3	(C) 1999 Andrea Arcangeli <andrea@suse.de>
	4
1a459660	5	* SPDX-License-Identifier: GPL-2.0+
7ba890bf KP	6
	7	linux/include/linux/rbtree.h
	8
	9	To use rbtrees you'll have to implement your own insert and search cores.
	10	This will avoid us to use callbacks and to drop drammatically performances.
	11	I know it's not the cleaner way, but in C (not in C++) to get
	12	performances and genericity...
	13
	14	Some example of insert and search follows here. The search is a plain
	15	normal search over an ordered tree. The insert instead must be implemented
	16	int two steps: as first thing the code must insert the element in
	17	order as a red leaf in the tree, then the support library function
	18	rb_insert_color() must be called. Such function will do the
	19	not trivial work to rebalance the rbtree if necessary.
	20
	21	-----------------------------------------------------------------------
	22	static inline struct page * rb_search_page_cache(struct inode * inode,
	23	unsigned long offset)
	24	{
	25	struct rb_node * n = inode->i_rb_page_cache.rb_node;
	26	struct page * page;
	27
	28	while (n)
	29	{
	30	page = rb_entry(n, struct page, rb_page_cache);
	31
	32	if (offset < page->offset)
	33	n = n->rb_left;
	34	else if (offset > page->offset)
	35	n = n->rb_right;
	36	else
	37	return page;
	38	}
	39	return NULL;
	40	}
	41
	42	static inline struct page * __rb_insert_page_cache(struct inode * inode,
	43	unsigned long offset,
	44	struct rb_node * node)
	45	{
	46	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
	47	struct rb_node * parent = NULL;
	48	struct page * page;
	49
	50	while (*p)
	51	{
	52	parent = *p;
	53	page = rb_entry(parent, struct page, rb_page_cache);
	54
	55	if (offset < page->offset)
	56	p = &(*p)->rb_left;
	57	else if (offset > page->offset)
	58	p = &(*p)->rb_right;
	59	else
	60	return page;
	61	}
	62
	63	rb_link_node(node, parent, p);
	64
	65	return NULL;
	66	}
	67
	68	static inline struct page * rb_insert_page_cache(struct inode * inode,
	69	unsigned long offset,
70	struct rb_node * node)
71	{
72	struct page * ret;
73	if ((ret = __rb_insert_page_cache(inode, offset, node)))
74	goto out;
75	rb_insert_color(node, &inode->i_rb_page_cache);
76	out:
77	return ret;
78	}
79	-----------------------------------------------------------------------
80	*/
81
82	#ifndef _LINUX_RBTREE_H
83	#define _LINUX_RBTREE_H
84
85	#include <linux/stddef.h>
86
87	struct rb_node
88	{
89	unsigned long rb_parent_color;
90	#define RB_RED 0
91	#define RB_BLACK 1
92	struct rb_node *rb_right;
93	struct rb_node *rb_left;
94	} __attribute__((aligned(sizeof(long))));
95	/* The alignment might seem pointless, but allegedly CRIS needs it */
96
97	struct rb_root
98	{
99	struct rb_node *rb_node;
100	};
101
102
103	#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
104	#define rb_color(r) ((r)->rb_parent_color & 1)
105	#define rb_is_red(r) (!rb_color(r))
106	#define rb_is_black(r) rb_color(r)
107	#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
108	#define rb_set_black(r) do { (r)->rb_parent_color \|= 1; } while (0)
109
110	static inline void rb_set_parent(struct rb_node rb, struct rb_node p)
111	{
112	rb->rb_parent_color = (rb->rb_parent_color & 3) \| (unsigned long)p;
113	}
114	static inline void rb_set_color(struct rb_node *rb, int color)
115	{
116	rb->rb_parent_color = (rb->rb_parent_color & ~1) \| color;
117	}
118
119	#define RB_ROOT (struct rb_root) { NULL, }
120	#define rb_entry(ptr, type, member) container_of(ptr, type, member)
121
122	#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
123	#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
124	#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
125
126	extern void rb_insert_color(struct rb_node , struct rb_root );
127	extern void rb_erase(struct rb_node , struct rb_root );
128
129	/* Find logical next and previous nodes in a tree */
130	extern struct rb_node rb_next(struct rb_node );
131	extern struct rb_node rb_prev(struct rb_node );
132	extern struct rb_node rb_first(struct rb_root );
133	extern struct rb_node rb_last(struct rb_root );
134
135	/* Fast replacement of a single node without remove/rebalance/add/rebalance */
136	extern void rb_replace_node(struct rb_node victim, struct rb_node new,
137	struct rb_root *root);
138
139	static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
140	struct rb_node ** rb_link)
141	{
142	node->rb_parent_color = (unsigned long )parent;
143	node->rb_left = node->rb_right = NULL;
144
145	*rb_link = node;
146	}
147
148	#endif /* _LINUX_RBTREE_H */