[GitHub/mt8127/android_kernel_alcatel_ttab.git] / include / linux / interval_tree_generic.h

/*
  Interval Trees
  (C) 2012  Michel Lespinasse <walken@google.com>

  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

  include/linux/interval_tree_generic.h
*/

#include <linux/rbtree_augmented.h>

/*
 * Template for implementing interval trees
 *
 * ITSTRUCT:   struct type of the interval tree nodes
 * ITRB:       name of struct rb_node field within ITSTRUCT
 * ITTYPE:     type of the interval endpoints
 * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
 * ITSTART(n): start endpoint of ITSTRUCT node n
 * ITLAST(n):  last endpoint of ITSTRUCT node n
 * ITSTATIC:   'static' or empty
 * ITPREFIX:   prefix to use for the inline tree definitions
 *
 * Note - before using this, please consider if non-generic version
 * (interval_tree.h) would work for you...
 */

#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE,		      \
			     ITSTART, ITLAST, ITSTATIC, ITPREFIX)	      \
									      \
/* Callbacks for augmented rbtree insert and remove */			      \
									      \
static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node)	      \
{									      \
	ITTYPE max = ITLAST(node), subtree_last;			      \
	if (node->ITRB.rb_left) {					      \
		subtree_last = rb_entry(node->ITRB.rb_left,		      \
					ITSTRUCT, ITRB)->ITSUBTREE;	      \
		if (max < subtree_last)					      \
			max = subtree_last;				      \
	}								      \
	if (node->ITRB.rb_right) {					      \
		subtree_last = rb_entry(node->ITRB.rb_right,		      \
					ITSTRUCT, ITRB)->ITSUBTREE;	      \
		if (max < subtree_last)					      \
			max = subtree_last;				      \
	}								      \
	return max;							      \
}									      \
									      \
RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,	      \
		     ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
									      \
/* Insert / remove interval nodes from the tree */			      \
									      \
ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root)	      \
{									      \
	struct rb_node **link = &root->rb_node, *rb_parent = NULL;	      \
	ITTYPE start = ITSTART(node), last = ITLAST(node);		      \
	ITSTRUCT *parent;						      \
									      \
	while (*link) {							      \
		rb_parent = *link;					      \
		parent = rb_entry(rb_parent, ITSTRUCT, ITRB);		      \
		if (parent->ITSUBTREE < last)				      \
			parent->ITSUBTREE = last;			      \
		if (start < ITSTART(parent))				      \
			link = &parent->ITRB.rb_left;			      \
		else							      \
			link = &parent->ITRB.rb_right;			      \
	}								      \
									      \
	node->ITSUBTREE = last;						      \
	rb_link_node(&node->ITRB, rb_parent, link);			      \
	rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment);	      \
}									      \
									      \
ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root)	      \
{									      \
	rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment);	      \
}									      \
									      \
/*									      \
 * Iterate over intervals intersecting [start;last]			      \
 *									      \
 * Note that a node's interval intersects [start;last] iff:		      \
 *   Cond1: ITSTART(node) <= last					      \
 * and									      \
 *   Cond2: start <= ITLAST(node)					      \
 */									      \
									      \
static ITSTRUCT *							      \
ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
{									      \
	while (true) {							      \
		/*							      \
		 * Loop invariant: start <= node->ITSUBTREE		      \
		 * (Cond2 is satisfied by one of the subtree nodes)	      \
		 */							      \
		if (node->ITRB.rb_left) {				      \
			ITSTRUCT *left = rb_entry(node->ITRB.rb_left,	      \
						  ITSTRUCT, ITRB);	      \
			if (start <= left->ITSUBTREE) {			      \
				/*					      \
				 * Some nodes in left subtree satisfy Cond2.  \
				 * Iterate to find the leftmost such node N.  \
				 * If it also satisfies Cond1, that's the     \
				 * match we are looking for. Otherwise, there \
				 * is no matching interval as nodes to the    \
				 * right of N can't satisfy Cond1 either.     \
				 */					      \
				node = left;				      \
				continue;				      \
			}						      \
		}							      \
		if (ITSTART(node) <= last) {		/* Cond1 */	      \
			if (start <= ITLAST(node))	/* Cond2 */	      \
				return node;	/* node is leftmost match */  \
			if (node->ITRB.rb_right) {			      \
				node = rb_entry(node->ITRB.rb_right,	      \
						ITSTRUCT, ITRB);	      \
				if (start <= node->ITSUBTREE)		      \
					continue;			      \
			}						      \
		}							      \
		return NULL;	/* No match */				      \
	}								      \
}									      \
									      \
ITSTATIC ITSTRUCT *							      \
ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last)      \
{									      \
	ITSTRUCT *node;							      \
									      \
	if (!root->rb_node)						      \
		return NULL;						      \
	node = rb_entry(root->rb_node, ITSTRUCT, ITRB);			      \
	if (node->ITSUBTREE < start)					      \
		return NULL;						      \
	return ITPREFIX ## _subtree_search(node, start, last);		      \
}									      \
									      \
ITSTATIC ITSTRUCT *							      \
ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last)	      \
{									      \
	struct rb_node *rb = node->ITRB.rb_right, *prev;		      \
									      \
	while (true) {							      \
		/*							      \
		 * Loop invariants:					      \
		 *   Cond1: ITSTART(node) <= last			      \
		 *   rb == node->ITRB.rb_right				      \
		 *							      \
		 * First, search right subtree if suitable		      \
		 */							      \
		if (rb) {						      \
			ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);	      \
			if (start <= right->ITSUBTREE)			      \
				return ITPREFIX ## _subtree_search(right,     \
								start, last); \
		}							      \
									      \
		/* Move up the tree until we come from a node's left child */ \
		do {							      \
			rb = rb_parent(&node->ITRB);			      \
			if (!rb)					      \
				return NULL;				      \
			prev = &node->ITRB;				      \
			node = rb_entry(rb, ITSTRUCT, ITRB);		      \
			rb = node->ITRB.rb_right;			      \
		} while (prev == rb);					      \
									      \
		/* Check if the node intersects [start;last] */		      \
		if (last < ITSTART(node))		/* !Cond1 */	      \
			return NULL;					      \
		else if (start <= ITLAST(node))		/* Cond2 */	      \
			return node;					      \
	}								      \
}
Commit	Line	Data
9826a516 ML	1	/*
	2	Interval Trees
	3	(C) 2012 Michel Lespinasse <walken@google.com>
	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	include/linux/interval_tree_generic.h
	20	*/
	21
	22	#include <linux/rbtree_augmented.h>
	23
	24	/*
	25	* Template for implementing interval trees
	26	*
	27	* ITSTRUCT: struct type of the interval tree nodes
	28	* ITRB: name of struct rb_node field within ITSTRUCT
	29	* ITTYPE: type of the interval endpoints
	30	* ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
	31	* ITSTART(n): start endpoint of ITSTRUCT node n
	32	* ITLAST(n): last endpoint of ITSTRUCT node n
	33	* ITSTATIC: 'static' or empty
	34	* ITPREFIX: prefix to use for the inline tree definitions
	35	*
	36	* Note - before using this, please consider if non-generic version
	37	* (interval_tree.h) would work for you...
	38	*/
	39
	40	#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
	41	ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
	42	\
	43	/* Callbacks for augmented rbtree insert and remove */ \
	44	\
	45	static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
	46	{ \
	47	ITTYPE max = ITLAST(node), subtree_last; \
	48	if (node->ITRB.rb_left) { \
	49	subtree_last = rb_entry(node->ITRB.rb_left, \
	50	ITSTRUCT, ITRB)->ITSUBTREE; \
	51	if (max < subtree_last) \
	52	max = subtree_last; \
	53	} \
	54	if (node->ITRB.rb_right) { \
	55	subtree_last = rb_entry(node->ITRB.rb_right, \
	56	ITSTRUCT, ITRB)->ITSUBTREE; \
	57	if (max < subtree_last) \
	58	max = subtree_last; \
	59	} \
	60	return max; \
	61	} \
	62	\
	63	RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
	64	ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \
65	\
66	/* Insert / remove interval nodes from the tree */ \
67	\
68	ITSTATIC void ITPREFIX ## _insert(ITSTRUCT node, struct rb_root root) \
69	{ \
70	struct rb_node *link = &root->rb_node, rb_parent = NULL; \
71	ITTYPE start = ITSTART(node), last = ITLAST(node); \
72	ITSTRUCT *parent; \
73	\
74	while (*link) { \
75	rb_parent = *link; \
76	parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
77	if (parent->ITSUBTREE < last) \
78	parent->ITSUBTREE = last; \
79	if (start < ITSTART(parent)) \
80	link = &parent->ITRB.rb_left; \
81	else \
82	link = &parent->ITRB.rb_right; \
83	} \
84	\
85	node->ITSUBTREE = last; \
86	rb_link_node(&node->ITRB, rb_parent, link); \
87	rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
88	} \
89	\
90	ITSTATIC void ITPREFIX ## _remove(ITSTRUCT node, struct rb_root root) \
91	{ \
92	rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
93	} \
94	\
95	/* \
96	* Iterate over intervals intersecting [start;last] \
97	* \
98	* Note that a node's interval intersects [start;last] iff: \
99	* Cond1: ITSTART(node) <= last \
100	* and \
101	* Cond2: start <= ITLAST(node) \
102	*/ \
103	\
104	static ITSTRUCT * \
105	ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
106	{ \
107	while (true) { \
108	/* \
109	* Loop invariant: start <= node->ITSUBTREE \
110	* (Cond2 is satisfied by one of the subtree nodes) \
111	*/ \
112	if (node->ITRB.rb_left) { \
113	ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
114	ITSTRUCT, ITRB); \
115	if (start <= left->ITSUBTREE) { \
116	/* \
117	* Some nodes in left subtree satisfy Cond2. \
118	* Iterate to find the leftmost such node N. \
119	* If it also satisfies Cond1, that's the \
120	* match we are looking for. Otherwise, there \
121	* is no matching interval as nodes to the \
122	* right of N can't satisfy Cond1 either. \
123	*/ \
124	node = left; \
125	continue; \
126	} \
127	} \
128	if (ITSTART(node) <= last) { /* Cond1 */ \
129	if (start <= ITLAST(node)) /* Cond2 */ \
130	return node; /* node is leftmost match */ \
131	if (node->ITRB.rb_right) { \
132	node = rb_entry(node->ITRB.rb_right, \
133	ITSTRUCT, ITRB); \
134	if (start <= node->ITSUBTREE) \
135	continue; \
136	} \
137	} \
138	return NULL; /* No match */ \
139	} \
140	} \
141	\
142	ITSTATIC ITSTRUCT * \
143	ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \
144	{ \
145	ITSTRUCT *node; \
146	\
147	if (!root->rb_node) \
148	return NULL; \
149	node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \
150	if (node->ITSUBTREE < start) \
151	return NULL; \
152	return ITPREFIX ## _subtree_search(node, start, last); \
153	} \
154	\
155	ITSTATIC ITSTRUCT * \
156	ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
157	{ \
158	struct rb_node rb = node->ITRB.rb_right, prev; \
159	\
160	while (true) { \
161	/* \
162	* Loop invariants: \
163	* Cond1: ITSTART(node) <= last \
164	* rb == node->ITRB.rb_right \
165	* \
166	* First, search right subtree if suitable \
167	*/ \
168	if (rb) { \
169	ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
170	if (start <= right->ITSUBTREE) \
171	return ITPREFIX ## _subtree_search(right, \
172	start, last); \
173	} \
174	\
175	/* Move up the tree until we come from a node's left child */ \
176	do { \
177	rb = rb_parent(&node->ITRB); \
178	if (!rb) \
179	return NULL; \
180	prev = &node->ITRB; \
181	node = rb_entry(rb, ITSTRUCT, ITRB); \
182	rb = node->ITRB.rb_right; \
183	} while (prev == rb); \
184	\
185	/* Check if the node intersects [start;last] */ \
186	if (last < ITSTART(node)) /* !Cond1 */ \
187	return NULL; \
188	else if (start <= ITLAST(node)) /* Cond2 */ \
189	return node; \
190	} \
191	}