xref: /OK3568_Linux_fs/kernel/include/linux/interval_tree.h (revision 4882a59341e53eb6f0b4789bf948001014eff981) 
1*4882a593Smuzhiyun /* SPDX-License-Identifier: GPL-2.0 */
2*4882a593Smuzhiyun #ifndef _LINUX_INTERVAL_TREE_H
3*4882a593Smuzhiyun #define _LINUX_INTERVAL_TREE_H
4*4882a593Smuzhiyun 
5*4882a593Smuzhiyun #include <linux/rbtree.h>
6*4882a593Smuzhiyun 
7*4882a593Smuzhiyun struct interval_tree_node {
8*4882a593Smuzhiyun 	struct rb_node rb;
9*4882a593Smuzhiyun 	unsigned long start;	/* Start of interval */
10*4882a593Smuzhiyun 	unsigned long last;	/* Last location _in_ interval */
11*4882a593Smuzhiyun 	unsigned long __subtree_last;
12*4882a593Smuzhiyun };
13*4882a593Smuzhiyun 
14*4882a593Smuzhiyun extern void
15*4882a593Smuzhiyun interval_tree_insert(struct interval_tree_node *node,
16*4882a593Smuzhiyun 		     struct rb_root_cached *root);
17*4882a593Smuzhiyun 
18*4882a593Smuzhiyun extern void
19*4882a593Smuzhiyun interval_tree_remove(struct interval_tree_node *node,
20*4882a593Smuzhiyun 		     struct rb_root_cached *root);
21*4882a593Smuzhiyun 
22*4882a593Smuzhiyun extern struct interval_tree_node *
23*4882a593Smuzhiyun interval_tree_iter_first(struct rb_root_cached *root,
24*4882a593Smuzhiyun 			 unsigned long start, unsigned long last);
25*4882a593Smuzhiyun 
26*4882a593Smuzhiyun extern struct interval_tree_node *
27*4882a593Smuzhiyun interval_tree_iter_next(struct interval_tree_node *node,
28*4882a593Smuzhiyun 			unsigned long start, unsigned long last);
29*4882a593Smuzhiyun 
30*4882a593Smuzhiyun #endif	/* _LINUX_INTERVAL_TREE_H */
31