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									      \
45static 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									      \
63RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB,	      \
64		     ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last)    \
65									      \
66/* Insert / remove interval nodes from the tree */			      \
67									      \
68ITSTATIC 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									      \
90ITSTATIC 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									      \
104static ITSTRUCT *							      \
105ITPREFIX ## _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									      \
142ITSTATIC ITSTRUCT *							      \
143ITPREFIX ## _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									      \
155ITSTATIC ITSTRUCT *							      \
156ITPREFIX ## _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}
192