1 #include <linux/init.h>
2 #include <linux/list.h>
3 #include <linux/slab.h>
4 #include <linux/list_sort.h>
5 #include <linux/version.h>
7 #include <linux/interval_tree_generic.h>
8 #include "usnic_uiom_interval_tree.h"
10 #define START(node) ((node)->start)
11 #define LAST(node) ((node)->last)
13 #define MAKE_NODE(node, start, end, ref_cnt, flags, err, err_out) \
15 node = usnic_uiom_interval_node_alloc(start, \
16 end, ref_cnt, flags); \
23 #define MARK_FOR_ADD(node, list) (list_add_tail(&node->link, list))
25 #define MAKE_NODE_AND_APPEND(node, start, end, ref_cnt, flags, err, \
28 MAKE_NODE(node, start, end, \
29 ref_cnt, flags, err, \
31 MARK_FOR_ADD(node, list); \
34 #define FLAGS_EQUAL(flags1, flags2, mask) \
35 (((flags1) & (mask)) == ((flags2) & (mask)))
37 static struct usnic_uiom_interval_node*
38 usnic_uiom_interval_node_alloc(long int start, long int last, int ref_cnt,
41 struct usnic_uiom_interval_node *interval = kzalloc(sizeof(*interval),
46 interval->start = start;
47 interval->last = last;
48 interval->flags = flags;
49 interval->ref_cnt = ref_cnt;
54 static int interval_cmp(void *priv, struct list_head *a, struct list_head *b)
56 struct usnic_uiom_interval_node *node_a, *node_b;
58 node_a = list_entry(a, struct usnic_uiom_interval_node, link);
59 node_b = list_entry(b, struct usnic_uiom_interval_node, link);
62 if (node_a->start < node_b->start)
64 else if (node_a->start > node_b->start)
71 find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
73 struct list_head *list)
75 struct usnic_uiom_interval_node *node;
79 for (node = usnic_uiom_interval_tree_iter_first(root, start, last);
81 node = usnic_uiom_interval_tree_iter_next(node, start, last))
82 list_add_tail(&node->link, list);
84 list_sort(NULL, list, interval_cmp);
87 int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,
88 int flags, int flag_mask,
90 struct list_head *diff_set)
92 struct usnic_uiom_interval_node *interval, *tmp;
94 long int pivot = start;
95 LIST_HEAD(intersection_set);
97 INIT_LIST_HEAD(diff_set);
99 find_intervals_intersection_sorted(root, start, last,
102 list_for_each_entry(interval, &intersection_set, link) {
103 if (pivot < interval->start) {
104 MAKE_NODE_AND_APPEND(tmp, pivot, interval->start - 1,
105 1, flags, err, err_out,
107 pivot = interval->start;
111 * Invariant: Set [start, pivot] is either in diff_set or root,
115 if (pivot > interval->last) {
117 } else if (pivot <= interval->last &&
118 FLAGS_EQUAL(interval->flags, flags,
120 pivot = interval->last + 1;
125 MAKE_NODE_AND_APPEND(tmp, pivot, last, 1, flags, err, err_out,
131 list_for_each_entry_safe(interval, tmp, diff_set, link) {
132 list_del(&interval->link);
139 void usnic_uiom_put_interval_set(struct list_head *intervals)
141 struct usnic_uiom_interval_node *interval, *tmp;
142 list_for_each_entry_safe(interval, tmp, intervals, link)
146 int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
147 unsigned long last, int flags)
149 struct usnic_uiom_interval_node *interval, *tmp;
150 unsigned long istart, ilast;
151 int iref_cnt, iflags;
152 unsigned long lpivot = start;
155 LIST_HEAD(intersection_set);
157 find_intervals_intersection_sorted(root, start, last,
160 list_for_each_entry(interval, &intersection_set, link) {
162 * Invariant - lpivot is the left edge of next interval to be
165 istart = interval->start;
166 ilast = interval->last;
167 iref_cnt = interval->ref_cnt;
168 iflags = interval->flags;
170 if (istart < lpivot) {
171 MAKE_NODE_AND_APPEND(tmp, istart, lpivot - 1, iref_cnt,
172 iflags, err, err_out, &to_add);
173 } else if (istart > lpivot) {
174 MAKE_NODE_AND_APPEND(tmp, lpivot, istart - 1, 1, flags,
175 err, err_out, &to_add);
182 MAKE_NODE_AND_APPEND(tmp, lpivot, last, iref_cnt + 1,
183 iflags | flags, err, err_out,
185 MAKE_NODE_AND_APPEND(tmp, last + 1, ilast, iref_cnt,
186 iflags, err, err_out, &to_add);
188 MAKE_NODE_AND_APPEND(tmp, lpivot, ilast, iref_cnt + 1,
189 iflags | flags, err, err_out,
197 MAKE_NODE_AND_APPEND(tmp, lpivot, last, 1, flags, err, err_out,
200 list_for_each_entry_safe(interval, tmp, &intersection_set, link) {
201 usnic_uiom_interval_tree_remove(interval, root);
205 list_for_each_entry(interval, &to_add, link)
206 usnic_uiom_interval_tree_insert(interval, root);
211 list_for_each_entry_safe(interval, tmp, &to_add, link)
217 void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start,
218 unsigned long last, struct list_head *removed)
220 struct usnic_uiom_interval_node *interval;
222 for (interval = usnic_uiom_interval_tree_iter_first(root, start, last);
224 interval = usnic_uiom_interval_tree_iter_next(interval,
227 if (--interval->ref_cnt == 0)
228 list_add_tail(&interval->link, removed);
231 list_for_each_entry(interval, removed, link)
232 usnic_uiom_interval_tree_remove(interval, root);
235 INTERVAL_TREE_DEFINE(struct usnic_uiom_interval_node, rb,
236 unsigned long, __subtree_last,
237 START, LAST, , usnic_uiom_interval_tree)