1 #include <linux/init.h>
2 #include <linux/list.h>
3 #include <linux/slab.h>
4 #include <linux/list_sort.h>
6 #include <linux/interval_tree_generic.h>
7 #include "usnic_uiom_interval_tree.h"
9 #define START(node) ((node)->start)
10 #define LAST(node) ((node)->last)
12 #define MAKE_NODE(node, start, end, ref_cnt, flags, err, err_out) \
14 node = usnic_uiom_interval_node_alloc(start, \
15 end, ref_cnt, flags); \
22 #define MARK_FOR_ADD(node, list) (list_add_tail(&node->link, list))
24 #define MAKE_NODE_AND_APPEND(node, start, end, ref_cnt, flags, err, \
27 MAKE_NODE(node, start, end, \
28 ref_cnt, flags, err, \
30 MARK_FOR_ADD(node, list); \
33 #define FLAGS_EQUAL(flags1, flags2, mask) \
34 (((flags1) & (mask)) == ((flags2) & (mask)))
36 static struct usnic_uiom_interval_node*
37 usnic_uiom_interval_node_alloc(long int start, long int last, int ref_cnt,
40 struct usnic_uiom_interval_node *interval = kzalloc(sizeof(*interval),
45 interval->start = start;
46 interval->last = last;
47 interval->flags = flags;
48 interval->ref_cnt = ref_cnt;
53 static int interval_cmp(void *priv, struct list_head *a, struct list_head *b)
55 struct usnic_uiom_interval_node *node_a, *node_b;
57 node_a = list_entry(a, struct usnic_uiom_interval_node, link);
58 node_b = list_entry(b, struct usnic_uiom_interval_node, link);
61 if (node_a->start < node_b->start)
63 else if (node_a->start > node_b->start)
70 find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
72 struct list_head *list)
74 struct usnic_uiom_interval_node *node;
78 for (node = usnic_uiom_interval_tree_iter_first(root, start, last);
80 node = usnic_uiom_interval_tree_iter_next(node, start, last))
81 list_add_tail(&node->link, list);
83 list_sort(NULL, list, interval_cmp);
86 int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,
87 int flags, int flag_mask,
89 struct list_head *diff_set)
91 struct usnic_uiom_interval_node *interval, *tmp;
93 long int pivot = start;
94 LIST_HEAD(intersection_set);
96 INIT_LIST_HEAD(diff_set);
98 find_intervals_intersection_sorted(root, start, last,
101 list_for_each_entry(interval, &intersection_set, link) {
102 if (pivot < interval->start) {
103 MAKE_NODE_AND_APPEND(tmp, pivot, interval->start - 1,
104 1, flags, err, err_out,
106 pivot = interval->start;
110 * Invariant: Set [start, pivot] is either in diff_set or root,
114 if (pivot > interval->last) {
116 } else if (pivot <= interval->last &&
117 FLAGS_EQUAL(interval->flags, flags,
119 pivot = interval->last + 1;
124 MAKE_NODE_AND_APPEND(tmp, pivot, last, 1, flags, err, err_out,
130 list_for_each_entry_safe(interval, tmp, diff_set, link) {
131 list_del(&interval->link);
138 void usnic_uiom_put_interval_set(struct list_head *intervals)
140 struct usnic_uiom_interval_node *interval, *tmp;
141 list_for_each_entry_safe(interval, tmp, intervals, link)
145 int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
146 unsigned long last, int flags)
148 struct usnic_uiom_interval_node *interval, *tmp;
149 unsigned long istart, ilast;
150 int iref_cnt, iflags;
151 unsigned long lpivot = start;
154 LIST_HEAD(intersection_set);
156 find_intervals_intersection_sorted(root, start, last,
159 list_for_each_entry(interval, &intersection_set, link) {
161 * Invariant - lpivot is the left edge of next interval to be
164 istart = interval->start;
165 ilast = interval->last;
166 iref_cnt = interval->ref_cnt;
167 iflags = interval->flags;
169 if (istart < lpivot) {
170 MAKE_NODE_AND_APPEND(tmp, istart, lpivot - 1, iref_cnt,
171 iflags, err, err_out, &to_add);
172 } else if (istart > lpivot) {
173 MAKE_NODE_AND_APPEND(tmp, lpivot, istart - 1, 1, flags,
174 err, err_out, &to_add);
181 MAKE_NODE_AND_APPEND(tmp, lpivot, last, iref_cnt + 1,
182 iflags | flags, err, err_out,
184 MAKE_NODE_AND_APPEND(tmp, last + 1, ilast, iref_cnt,
185 iflags, err, err_out, &to_add);
187 MAKE_NODE_AND_APPEND(tmp, lpivot, ilast, iref_cnt + 1,
188 iflags | flags, err, err_out,
196 MAKE_NODE_AND_APPEND(tmp, lpivot, last, 1, flags, err, err_out,
199 list_for_each_entry_safe(interval, tmp, &intersection_set, link) {
200 usnic_uiom_interval_tree_remove(interval, root);
204 list_for_each_entry(interval, &to_add, link)
205 usnic_uiom_interval_tree_insert(interval, root);
210 list_for_each_entry_safe(interval, tmp, &to_add, link)
216 void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start,
217 unsigned long last, struct list_head *removed)
219 struct usnic_uiom_interval_node *interval;
221 for (interval = usnic_uiom_interval_tree_iter_first(root, start, last);
223 interval = usnic_uiom_interval_tree_iter_next(interval,
226 if (--interval->ref_cnt == 0)
227 list_add_tail(&interval->link, removed);
230 list_for_each_entry(interval, removed, link)
231 usnic_uiom_interval_tree_remove(interval, root);
234 INTERVAL_TREE_DEFINE(struct usnic_uiom_interval_node, rb,
235 unsigned long, __subtree_last,
236 START, LAST, , usnic_uiom_interval_tree)