usnic_uiom_interval_tree.c revision a384b20e417ae0f5f1f359600b4bdcc34265b256 
1#include <linux/init.h>
2#include <linux/list.h>
3#include <linux/slab.h>
4#include <linux/list_sort.h>
5
6#include <linux/interval_tree_generic.h>
7#include "usnic_uiom_interval_tree.h"
8
9#define START(node) ((node)->start)
10#define LAST(node) ((node)->last)
11
12#define MAKE_NODE(node, start, end, ref_cnt, flags, err, err_out)	\
13		do {							\
14			node = usnic_uiom_interval_node_alloc(start,	\
15					end, ref_cnt, flags);		\
16				if (!node) {				\
17					err = -ENOMEM;			\
18					goto err_out;			\
19				}					\
20		} while (0)
21
22#define MARK_FOR_ADD(node, list) (list_add_tail(&node->link, list))
23
24#define MAKE_NODE_AND_APPEND(node, start, end, ref_cnt, flags, err,	\
25				err_out, list)				\
26				do {					\
27					MAKE_NODE(node, start, end,	\
28						ref_cnt, flags, err,	\
29						err_out);		\
30					MARK_FOR_ADD(node, list);	\
31				} while (0)
32
33#define FLAGS_EQUAL(flags1, flags2, mask)				\
34			(((flags1) & (mask)) == ((flags2) & (mask)))
35
36static struct usnic_uiom_interval_node*
37usnic_uiom_interval_node_alloc(long int start, long int last, int ref_cnt,
38				int flags)
39{
40	struct usnic_uiom_interval_node *interval = kzalloc(sizeof(*interval),
41								GFP_ATOMIC);
42	if (!interval)
43		return NULL;
44
45	interval->start = start;
46	interval->last = last;
47	interval->flags = flags;
48	interval->ref_cnt = ref_cnt;
49
50	return interval;
51}
52
53static int interval_cmp(void *priv, struct list_head *a, struct list_head *b)
54{
55	struct usnic_uiom_interval_node *node_a, *node_b;
56
57	node_a = list_entry(a, struct usnic_uiom_interval_node, link);
58	node_b = list_entry(b, struct usnic_uiom_interval_node, link);
59
60	/* long to int */
61	if (node_a->start < node_b->start)
62		return -1;
63	else if (node_a->start > node_b->start)
64		return 1;
65
66	return 0;
67}
68
69static void
70find_intervals_intersection_sorted(struct rb_root *root, unsigned long start,
71					unsigned long last,
72					struct list_head *list)
73{
74	struct usnic_uiom_interval_node *node;
75
76	INIT_LIST_HEAD(list);
77
78	for (node = usnic_uiom_interval_tree_iter_first(root, start, last);
79		node;
80		node = usnic_uiom_interval_tree_iter_next(node, start, last))
81		list_add_tail(&node->link, list);
82
83	list_sort(NULL, list, interval_cmp);
84}
85
86int usnic_uiom_get_intervals_diff(unsigned long start, unsigned long last,
87					int flags, int flag_mask,
88					struct rb_root *root,
89					struct list_head *diff_set)
90{
91	struct usnic_uiom_interval_node *interval, *tmp;
92	int err = 0;
93	long int pivot = start;
94	LIST_HEAD(intersection_set);
95
96	INIT_LIST_HEAD(diff_set);
97
98	find_intervals_intersection_sorted(root, start, last,
99						&intersection_set);
100
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,
105						diff_set);
106			pivot = interval->start;
107		}
108
109		/*
110		 * Invariant: Set [start, pivot] is either in diff_set or root,
111		 * but not in both.
112		 */
113
114		if (pivot > interval->last) {
115			continue;
116		} else if (pivot <= interval->last &&
117				FLAGS_EQUAL(interval->flags, flags,
118				flag_mask)) {
119			pivot = interval->last + 1;
120		}
121	}
122
123	if (pivot <= last)
124		MAKE_NODE_AND_APPEND(tmp, pivot, last, 1, flags, err, err_out,
125					diff_set);
126
127	return 0;
128
129err_out:
130	list_for_each_entry_safe(interval, tmp, diff_set, link) {
131		list_del(&interval->link);
132		kfree(interval);
133	}
134
135	return err;
136}
137
138void usnic_uiom_put_interval_set(struct list_head *intervals)
139{
140	struct usnic_uiom_interval_node *interval, *tmp;
141	list_for_each_entry_safe(interval, tmp, intervals, link)
142		kfree(interval);
143}
144
145int usnic_uiom_insert_interval(struct rb_root *root, unsigned long start,
146				unsigned long last, int flags)
147{
148	struct usnic_uiom_interval_node *interval, *tmp;
149	unsigned long istart, ilast;
150	int iref_cnt, iflags;
151	unsigned long lpivot = start;
152	int err = 0;
153	LIST_HEAD(to_add);
154	LIST_HEAD(intersection_set);
155
156	find_intervals_intersection_sorted(root, start, last,
157						&intersection_set);
158
159	list_for_each_entry(interval, &intersection_set, link) {
160		/*
161		 * Invariant - lpivot is the left edge of next interval to be
162		 * inserted
163		 */
164		istart = interval->start;
165		ilast = interval->last;
166		iref_cnt = interval->ref_cnt;
167		iflags = interval->flags;
168
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);
175			lpivot = istart;
176		} else {
177			lpivot = istart;
178		}
179
180		if (ilast > last) {
181			MAKE_NODE_AND_APPEND(tmp, lpivot, last, iref_cnt + 1,
182						iflags | flags, err, err_out,
183						&to_add);
184			MAKE_NODE_AND_APPEND(tmp, last + 1, ilast, iref_cnt,
185						iflags, err, err_out, &to_add);
186		} else {
187			MAKE_NODE_AND_APPEND(tmp, lpivot, ilast, iref_cnt + 1,
188						iflags | flags, err, err_out,
189						&to_add);
190		}
191
192		lpivot = ilast + 1;
193	}
194
195	if (lpivot <= last)
196		MAKE_NODE_AND_APPEND(tmp, lpivot, last, 1, flags, err, err_out,
197					&to_add);
198
199	list_for_each_entry_safe(interval, tmp, &intersection_set, link) {
200		usnic_uiom_interval_tree_remove(interval, root);
201		kfree(interval);
202	}
203
204	list_for_each_entry(interval, &to_add, link)
205		usnic_uiom_interval_tree_insert(interval, root);
206
207	return 0;
208
209err_out:
210	list_for_each_entry_safe(interval, tmp, &to_add, link)
211		kfree(interval);
212
213	return err;
214}
215
216void usnic_uiom_remove_interval(struct rb_root *root, unsigned long start,
217				unsigned long last, struct list_head *removed)
218{
219	struct usnic_uiom_interval_node *interval;
220
221	for (interval = usnic_uiom_interval_tree_iter_first(root, start, last);
222			interval;
223			interval = usnic_uiom_interval_tree_iter_next(interval,
224									start,
225									last)) {
226		if (--interval->ref_cnt == 0)
227			list_add_tail(&interval->link, removed);
228	}
229
230	list_for_each_entry(interval, removed, link)
231		usnic_uiom_interval_tree_remove(interval, root);
232}
233
234INTERVAL_TREE_DEFINE(struct usnic_uiom_interval_node, rb,
235			unsigned long, __subtree_last,
236			START, LAST, , usnic_uiom_interval_tree)
237