]> git.saurik.com Git - apple/hfs.git/blame - livefiles_hfs_plugin/lf_hfs_rangelist.c
hfs-556.100.11.tar.gz
[apple/hfs.git] / livefiles_hfs_plugin / lf_hfs_rangelist.c
CommitLineData
de8ee011
A
1/* Copyright © 2017-2018 Apple Inc. All rights reserved.
2 *
3 * lf_hfs_rangelist.c
4 * livefiles_hfs
5 *
6 * Created by Yakov Ben Zaken on 19/03/2018.
7 */
8
9#include "lf_hfs_rangelist.h"
10#include "lf_hfs_vfsutils.h"
11
12static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
13static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
14static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
15
16/*
17 * Walk the list of ranges for an entry to
18 * find an overlapping range (if any).
19 *
20 * NOTE: this returns only the FIRST overlapping range.
21 * There may be more than one.
22 */
23static enum rl_overlaptype
24rl_scan_from(struct rl_head *rangelist __unused,
25 off_t start,
26 off_t end,
27 struct rl_entry **overlap,
28 struct rl_entry *range)
29{
30
31 while (range)
32 {
33 enum rl_overlaptype ot = rl_overlap(range, start, end);
34
35 if (ot != RL_NOOVERLAP || range->rl_start > end)
36 {
37 *overlap = range;
38 return ot;
39 }
40
41 range = TAILQ_NEXT(range, rl_link);
42 }
43
44 *overlap = NULL;
45 return RL_NOOVERLAP;
46}
47
48void
49rl_init(struct rl_head *rangelist)
50{
51 TAILQ_INIT(rangelist);
52}
53
54enum rl_overlaptype
55rl_overlap(const struct rl_entry *range, off_t start, off_t end)
56{
57 /*
58 * OK, check for overlap
59 *
60 * Six cases:
61 * 0) no overlap (RL_NOOVERLAP)
62 * 1) overlap == range (RL_MATCHINGOVERLAP)
63 * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
64 * 3) range contains overlap (RL_OVERLAPISCONTAINED)
65 * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
66 * 5) overlap ends after range (RL_OVERLAPENDSAFTER)
67 */
68 if (start > range->rl_end || range->rl_start > end)
69 {
70 /* Case 0 (RL_NOOVERLAP) */
71 return RL_NOOVERLAP;
72 }
73
74 if (range->rl_start == start && range->rl_end == end)
75 {
76 /* Case 1 (RL_MATCHINGOVERLAP) */
77 return RL_MATCHINGOVERLAP;
78 }
79
80 if (range->rl_start <= start && range->rl_end >= end)
81 {
82 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
83 return RL_OVERLAPCONTAINSRANGE;
84 }
85
86 if (start <= range->rl_start && end >= range->rl_end)
87 {
88 /* Case 3 (RL_OVERLAPISCONTAINED) */
89 return RL_OVERLAPISCONTAINED;
90 }
91
92 if (range->rl_start < start && range->rl_end < end)
93 {
94 /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
95 return RL_OVERLAPSTARTSBEFORE;
96 }
97
98 /* Case 5 (RL_OVERLAPENDSAFTER) */
99 // range->rl_start > start && range->rl_end > end
100 return RL_OVERLAPENDSAFTER;
101}
102
103/*
104 * Remove a range from a range list.
105 *
106 * Generally, find the range (or an overlap to that range)
107 * and remove it (or shrink it), then wakeup anyone we can.
108 */
109void
110rl_remove(off_t start, off_t end, struct rl_head *rangelist)
111{
112 struct rl_entry *range, *next_range, *overlap, *splitrange;
113 int ovcase;
114
115 if (TAILQ_EMPTY(rangelist))
116 {
117 return;
118 };
119
120 range = TAILQ_FIRST(rangelist);
121 while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range)))
122 {
123 switch (ovcase)
124 {
125
126 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
127 TAILQ_REMOVE(rangelist, overlap, rl_link);
128 hfs_free(overlap);
129 break;
130
131 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
132 if (overlap->rl_start == start) {
133 overlap->rl_start = end + 1;
134 break;
135 };
136
137 if (overlap->rl_end == end) {
138 overlap->rl_end = start - 1;
139 break;
140 };
141
142 /*
143 * Make a new range consisting of the last part of the encompassing range
144 */
145 splitrange = hfs_malloc(sizeof(struct rl_entry));
146 splitrange->rl_start = end + 1;
147 splitrange->rl_end = overlap->rl_end;
148 overlap->rl_end = start - 1;
149
150 /*
151 * Now link the new entry into the range list after the range from which it was split:
152 */
153 TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
154 break;
155
156 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
157 /* Check before discarding overlap entry */
158 next_range = TAILQ_NEXT(overlap, rl_link);
159 TAILQ_REMOVE(rangelist, overlap, rl_link);
160 hfs_free(overlap);
161 if (next_range)
162 {
163 range = next_range;
164 continue;
165 };
166 break;
167
168 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
169 overlap->rl_end = start - 1;
170 range = TAILQ_NEXT(overlap, rl_link);
171 if (range) {
172 continue;
173 }
174 break;
175
176 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
177 overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
178 break;
179 }
180 break;
181 }
182}
183
184off_t rl_len(const struct rl_entry *range)
185{
186 return range->rl_end - range->rl_start + 1;
187}
188
189void rl_remove_all(struct rl_head *rangelist)
190{
191 struct rl_entry *r, *nextr;
192 TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr){
193 hfs_free(r);
194 }
195 TAILQ_INIT(rangelist);
196}
197
198/*
199 * Add a range to the list
200 */
201void
202rl_add(off_t start, off_t end, struct rl_head *rangelist)
203{
204 struct rl_entry *range;
205 struct rl_entry *overlap;
206 enum rl_overlaptype ovcase;
207
208#ifdef RL_DIAGNOSTIC
209 if (end < start)
210 {
211 LFHFS_LOG(LEVEL_ERROR, "rl_add: end < start?!");
212 hfs_assert(0);
213 }
214#endif
215
216 ovcase = rl_scan(rangelist, start, end, &overlap);
217
218 /*
219 * Six cases:
220 * 0) no overlap
221 * 1) overlap == range
222 * 2) overlap contains range
223 * 3) range contains overlap
224 * 4) overlap starts before range
225 * 5) overlap ends after range
226 */
227 switch (ovcase) {
228 case RL_NOOVERLAP: /* 0: no overlap */
229 /*
230 * overlap points to the entry we should insert before, or
231 * if NULL, we should insert at the end.
232 */
233 range = hfs_mallocz(sizeof(*range));
234 range->rl_start = start;
235 range->rl_end = end;
236
237 /* Link in the new range: */
238 if (overlap) {
239 TAILQ_INSERT_BEFORE(overlap, range, rl_link);
240 } else {
241 TAILQ_INSERT_TAIL(rangelist, range, rl_link);
242 }
243
244 /* Check to see if any ranges can be combined (possibly including the immediately
245 preceding range entry)
246 */
247 rl_collapse_neighbors(rangelist, range);
248 break;
249
250 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
251 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
252 break;
253
254 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
255 /*
256 * Replace the overlap with the new, larger range:
257 */
258 overlap->rl_start = start;
259 overlap->rl_end = end;
260 rl_collapse_neighbors(rangelist, overlap);
261 break;
262
263 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
264 /*
265 * Expand the overlap area to cover the new range:
266 */
267 overlap->rl_end = end;
268 rl_collapse_forwards(rangelist, overlap);
269 break;
270
271 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
272 /*
273 * Expand the overlap area to cover the new range:
274 */
275 overlap->rl_start = start;
276 rl_collapse_backwards(rangelist, overlap);
277 break;
278 }
279
280#ifdef RL_DIAGNOSTIC
281 rl_verify(rangelist);
282#endif
283}
284
285/*
286 * Scan a range list for an entry in a specified range (if any):
287 *
288 * NOTE: this returns only the FIRST overlapping range.
289 * There may be more than one.
290 */
291
292enum rl_overlaptype
293rl_scan(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap)
294{
295 return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
296}
297
298static void
299rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
300 struct rl_entry *next_range;
301
302 while ((next_range = TAILQ_NEXT(range, rl_link))) {
303 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
304
305 /* Expand this range to include the next range: */
306 range->rl_end = next_range->rl_end;
307
308 /* Remove the now covered range from the list: */
309 TAILQ_REMOVE(rangelist, next_range, rl_link);
310 hfs_free(next_range);
311
312#ifdef RL_DIAGNOSTIC
313 rl_verify(rangelist);
314#endif
315 };
316}
317
318static void
319rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
320 struct rl_entry *prev_range;
321
322 while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
323 if (prev_range->rl_end < range->rl_start -1) {
324#ifdef RL_DIAGNOSTIC
325 rl_verify(rangelist);
326#endif
327 return;
328 };
329
330 /* Expand this range to include the previous range: */
331 range->rl_start = prev_range->rl_start;
332
333 /* Remove the now covered range from the list: */
334 TAILQ_REMOVE(rangelist, prev_range, rl_link);
335 hfs_free(prev_range);
336 };
337}
338
339static void
340rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
341{
342 rl_collapse_forwards(rangelist, range);
343 rl_collapse_backwards(rangelist, range);
344}
345
346/*
347 * In the case where b is contained by a, we return the the largest part
348 * remaining. The result is stored in a.
349 */
350void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
351{
352 switch (rl_overlap(b, a->rl_start, a->rl_end)) {
353 case RL_MATCHINGOVERLAP:
354 case RL_OVERLAPCONTAINSRANGE:
355 a->rl_end = a->rl_start - 1;
356 break;
357 case RL_OVERLAPISCONTAINED:
358 // Keep the bigger part
359 if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
360 // Keep left
361 a->rl_end = b->rl_start - 1;
362 } else {
363 // Keep right
364 a->rl_start = b->rl_end + 1;
365 }
366 break;
367 case RL_OVERLAPSTARTSBEFORE:
368 a->rl_start = b->rl_end + 1;
369 break;
370 case RL_OVERLAPENDSAFTER:
371 a->rl_end = b->rl_start - 1;
372 break;
373 case RL_NOOVERLAP:
374 break;
375 }
376}
377
378struct rl_entry rl_make(off_t start, off_t end)
379{
380 return (struct rl_entry){ .rl_start = start, .rl_end = end };
381}