1 /*
2  * Copyright (c) 2013, Cisco Systems, Inc. All rights reserved.
3  *
4  * This software is available to you under a choice of one of two
5  * licenses.  You may choose to be licensed under the terms of the GNU
6  * General Public License (GPL) Version 2, available from the file
7  * COPYING in the main directory of this source tree, or the
8  * BSD license below:
9  *
10  *     Redistribution and use in source and binary forms, with or
11  *     without modification, are permitted provided that the following
12  *     conditions are met:
13  *
14  *      - Redistributions of source code must retain the above
15  *        copyright notice, this list of conditions and the following
16  *        disclaimer.
17  *
18  *      - Redistributions in binary form must reproduce the above
19  *        copyright notice, this list of conditions and the following
20  *        disclaimer in the documentation and/or other materials
21  *        provided with the distribution.
22  *
23  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
24  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
25  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
26  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
27  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
28  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
29  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30  * SOFTWARE.
31  *
32  */
33 
34 #ifndef USNIC_UIOM_INTERVAL_TREE_H_
35 #define USNIC_UIOM_INTERVAL_TREE_H_
36 
37 #include <linux/rbtree.h>
38 
39 struct usnic_uiom_interval_node {
40 	struct rb_node			rb;
41 	struct list_head		link;
42 	unsigned long			start;
43 	unsigned long			last;
44 	unsigned long			__subtree_last;
45 	unsigned int			ref_cnt;
46 	int				flags;
47 };
48 
49 extern void
50 usnic_uiom_interval_tree_insert(struct usnic_uiom_interval_node *node,
51 					struct rb_root_cached *root);
52 extern void
53 usnic_uiom_interval_tree_remove(struct usnic_uiom_interval_node *node,
54 					struct rb_root_cached *root);
55 extern struct usnic_uiom_interval_node *
56 usnic_uiom_interval_tree_iter_first(struct rb_root_cached *root,
57 					unsigned long start,
58 					unsigned long last);
59 extern struct usnic_uiom_interval_node *
60 usnic_uiom_interval_tree_iter_next(struct usnic_uiom_interval_node *node,
61 			unsigned long start, unsigned long last);
62 /*
63  * Inserts {start...last} into {root}.  If there are overlaps,
64  * nodes will be broken up and merged
65  */
66 int usnic_uiom_insert_interval(struct rb_root_cached *root,
67 				unsigned long start, unsigned long last,
68 				int flags);
69 /*
70  * Removed {start...last} from {root}.  The nodes removed are returned in
71  * 'removed.' The caller is responsibile for freeing memory of nodes in
72  * 'removed.'
73  */
74 void usnic_uiom_remove_interval(struct rb_root_cached *root,
75 				unsigned long start, unsigned long last,
76 				struct list_head *removed);
77 /*
78  * Returns {start...last} - {root} (relative complement of {start...last} in
79  * {root}) in diff_set sorted ascendingly
80  */
81 int usnic_uiom_get_intervals_diff(unsigned long start,
82 					unsigned long last, int flags,
83 					int flag_mask,
84 					struct rb_root_cached *root,
85 					struct list_head *diff_set);
86 /* Call this to free diff_set returned by usnic_uiom_get_intervals_diff */
87 void usnic_uiom_put_interval_set(struct list_head *intervals);
88 #endif /* USNIC_UIOM_INTERVAL_TREE_H_ */
89