]> git.saurik.com Git - apple/hfs.git/blob - core/rangelist.c
hfs-556.100.11.tar.gz
[apple/hfs.git] / core / rangelist.c
1 /*
2 * Copyright (c) 2001-2015 Apple Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28
29 #include <sys/param.h>
30 #include <mach/boolean.h>
31 #include <sys/time.h>
32 #include <sys/malloc.h>
33
34 #if !RANGELIST_TEST
35 #include <kern/debug.h>
36 #include "hfs.h"
37 #endif
38
39 #include "rangelist.h"
40
41 static enum rl_overlaptype rl_scan_from(struct rl_head *rangelist, off_t start, off_t end, struct rl_entry **overlap, struct rl_entry *range);
42 static void rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
43 static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
44 static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);
45
46
47 #ifdef RL_DIAGNOSTIC
48 static void
49 rl_verify(struct rl_head *rangelist) {
50 struct rl_entry *entry;
51 struct rl_entry *next;
52 off_t limit = 0;
53
54 TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) {
55 if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!");
56 if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!");
57 limit = entry->rl_end;
58 };
59 }
60 #endif
61
62
63
64 /*
65 * Initialize a range list head
66 */
67 void
68 rl_init(struct rl_head *rangelist)
69 {
70 TAILQ_INIT(rangelist);
71 }
72
73 /*
74 * Add a range to the list
75 */
76 void
77 rl_add(off_t start, off_t end, struct rl_head *rangelist)
78 {
79 struct rl_entry *range;
80 struct rl_entry *overlap;
81 enum rl_overlaptype ovcase;
82
83 #ifdef RL_DIAGNOSTIC
84 if (end < start) panic("hfs: rl_add: end < start?!");
85 #endif
86
87 ovcase = rl_scan(rangelist, start, end, &overlap);
88
89 /*
90 * Six cases:
91 * 0) no overlap
92 * 1) overlap == range
93 * 2) overlap contains range
94 * 3) range contains overlap
95 * 4) overlap starts before range
96 * 5) overlap ends after range
97 */
98 switch (ovcase) {
99 case RL_NOOVERLAP: /* 0: no overlap */
100 /*
101 * overlap points to the entry we should insert before, or
102 * if NULL, we should insert at the end.
103 */
104 range = hfs_malloc(sizeof(*range));
105 range->rl_start = start;
106 range->rl_end = end;
107
108 /* Link in the new range: */
109 if (overlap) {
110 TAILQ_INSERT_BEFORE(overlap, range, rl_link);
111 } else {
112 TAILQ_INSERT_TAIL(rangelist, range, rl_link);
113 }
114
115 /* Check to see if any ranges can be combined (possibly including the immediately
116 preceding range entry)
117 */
118 rl_collapse_neighbors(rangelist, range);
119 break;
120
121 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
122 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
123 break;
124
125 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
126 /*
127 * Replace the overlap with the new, larger range:
128 */
129 overlap->rl_start = start;
130 overlap->rl_end = end;
131 rl_collapse_neighbors(rangelist, overlap);
132 break;
133
134 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
135 /*
136 * Expand the overlap area to cover the new range:
137 */
138 overlap->rl_end = end;
139 rl_collapse_forwards(rangelist, overlap);
140 break;
141
142 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
143 /*
144 * Expand the overlap area to cover the new range:
145 */
146 overlap->rl_start = start;
147 rl_collapse_backwards(rangelist, overlap);
148 break;
149 }
150
151 #ifdef RL_DIAGNOSTIC
152 rl_verify(rangelist);
153 #endif
154 }
155
156
157
158 /*
159 * Remove a range from a range list.
160 *
161 * Generally, find the range (or an overlap to that range)
162 * and remove it (or shrink it), then wakeup anyone we can.
163 */
164 void
165 rl_remove(off_t start, off_t end, struct rl_head *rangelist)
166 {
167 struct rl_entry *range, *next_range, *overlap, *splitrange;
168 int ovcase;
169
170 #ifdef RL_DIAGNOSTIC
171 if (end < start) panic("hfs: rl_remove: end < start?!");
172 #endif
173
174 if (TAILQ_EMPTY(rangelist)) {
175 return;
176 };
177
178 range = TAILQ_FIRST(rangelist);
179 while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
180 switch (ovcase) {
181
182 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
183 TAILQ_REMOVE(rangelist, overlap, rl_link);
184 hfs_free(overlap, sizeof(*overlap));
185 break;
186
187 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
188 if (overlap->rl_start == start) {
189 overlap->rl_start = end + 1;
190 break;
191 };
192
193 if (overlap->rl_end == end) {
194 overlap->rl_end = start - 1;
195 break;
196 };
197
198 /*
199 * Make a new range consisting of the last part of the encompassing range
200 */
201 splitrange = hfs_malloc(sizeof *splitrange);
202 splitrange->rl_start = end + 1;
203 splitrange->rl_end = overlap->rl_end;
204 overlap->rl_end = start - 1;
205
206 /*
207 * Now link the new entry into the range list after the range from which it was split:
208 */
209 TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
210 break;
211
212 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
213 /* Check before discarding overlap entry */
214 next_range = TAILQ_NEXT(overlap, rl_link);
215 TAILQ_REMOVE(rangelist, overlap, rl_link);
216 hfs_free(overlap, sizeof(*overlap));
217 if (next_range) {
218 range = next_range;
219 continue;
220 };
221 break;
222
223 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
224 overlap->rl_end = start - 1;
225 range = TAILQ_NEXT(overlap, rl_link);
226 if (range) {
227 continue;
228 }
229 break;
230
231 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
232 overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
233 break;
234 }
235 break;
236 }
237
238 #ifdef RL_DIAGNOSTIC
239 rl_verify(rangelist);
240 #endif
241 }
242
243
244
245 /*
246 * Scan a range list for an entry in a specified range (if any):
247 *
248 * NOTE: this returns only the FIRST overlapping range.
249 * There may be more than one.
250 */
251
252 enum rl_overlaptype
253 rl_scan(struct rl_head *rangelist,
254 off_t start,
255 off_t end,
256 struct rl_entry **overlap) {
257
258 return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
259 }
260
261 enum rl_overlaptype
262 rl_overlap(const struct rl_entry *range, off_t start, off_t end)
263 {
264 /*
265 * OK, check for overlap
266 *
267 * Six cases:
268 * 0) no overlap (RL_NOOVERLAP)
269 * 1) overlap == range (RL_MATCHINGOVERLAP)
270 * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
271 * 3) range contains overlap (RL_OVERLAPISCONTAINED)
272 * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
273 * 5) overlap ends after range (RL_OVERLAPENDSAFTER)
274 */
275 if (start > range->rl_end || range->rl_start > end) {
276 /* Case 0 (RL_NOOVERLAP) */
277 return RL_NOOVERLAP;
278 }
279
280 if (range->rl_start == start && range->rl_end == end) {
281 /* Case 1 (RL_MATCHINGOVERLAP) */
282 return RL_MATCHINGOVERLAP;
283 }
284
285 if (range->rl_start <= start && range->rl_end >= end) {
286 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
287 return RL_OVERLAPCONTAINSRANGE;
288 }
289
290 if (start <= range->rl_start && end >= range->rl_end) {
291 /* Case 3 (RL_OVERLAPISCONTAINED) */
292 return RL_OVERLAPISCONTAINED;
293 }
294
295 if (range->rl_start < start && range->rl_end < end) {
296 /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
297 return RL_OVERLAPSTARTSBEFORE;
298 }
299
300 /* Case 5 (RL_OVERLAPENDSAFTER) */
301 // range->rl_start > start && range->rl_end > end
302 return RL_OVERLAPENDSAFTER;
303 }
304
305 /*
306 * Walk the list of ranges for an entry to
307 * find an overlapping range (if any).
308 *
309 * NOTE: this returns only the FIRST overlapping range.
310 * There may be more than one.
311 */
312 static enum rl_overlaptype
313 rl_scan_from(struct rl_head *rangelist __unused,
314 off_t start,
315 off_t end,
316 struct rl_entry **overlap,
317 struct rl_entry *range)
318 {
319 #ifdef RL_DIAGNOSTIC
320 rl_verify(rangelist);
321 #endif
322
323 while (range) {
324 enum rl_overlaptype ot = rl_overlap(range, start, end);
325
326 if (ot != RL_NOOVERLAP || range->rl_start > end) {
327 *overlap = range;
328 return ot;
329 }
330
331 range = TAILQ_NEXT(range, rl_link);
332 }
333
334 *overlap = NULL;
335 return RL_NOOVERLAP;
336 }
337
338
339 static void
340 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
341 struct rl_entry *next_range;
342
343 while ((next_range = TAILQ_NEXT(range, rl_link))) {
344 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
345
346 /* Expand this range to include the next range: */
347 range->rl_end = next_range->rl_end;
348
349 /* Remove the now covered range from the list: */
350 TAILQ_REMOVE(rangelist, next_range, rl_link);
351 hfs_free(next_range, sizeof(*next_range));
352
353 #ifdef RL_DIAGNOSTIC
354 rl_verify(rangelist);
355 #endif
356 };
357 }
358
359
360
361 static void
362 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
363 struct rl_entry *prev_range;
364
365 while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
366 if (prev_range->rl_end < range->rl_start -1) {
367 #ifdef RL_DIAGNOSTIC
368 rl_verify(rangelist);
369 #endif
370 return;
371 };
372
373 /* Expand this range to include the previous range: */
374 range->rl_start = prev_range->rl_start;
375
376 /* Remove the now covered range from the list: */
377 TAILQ_REMOVE(rangelist, prev_range, rl_link);
378 hfs_free(prev_range, sizeof(*prev_range));
379 };
380 }
381
382
383
384 static void
385 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
386 {
387 rl_collapse_forwards(rangelist, range);
388 rl_collapse_backwards(rangelist, range);
389 }
390
391 void rl_remove_all(struct rl_head *rangelist)
392 {
393 struct rl_entry *r, *nextr;
394 TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
395 hfs_free(r, sizeof(*r));
396 TAILQ_INIT(rangelist);
397 }
398
399 /*
400 * In the case where b is contained by a, we return the the largest part
401 * remaining. The result is stored in a.
402 */
403 void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
404 {
405 switch (rl_overlap(b, a->rl_start, a->rl_end)) {
406 case RL_MATCHINGOVERLAP:
407 case RL_OVERLAPCONTAINSRANGE:
408 a->rl_end = a->rl_start - 1;
409 break;
410 case RL_OVERLAPISCONTAINED:
411 // Keep the bigger part
412 if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
413 // Keep left
414 a->rl_end = b->rl_start - 1;
415 } else {
416 // Keep right
417 a->rl_start = b->rl_end + 1;
418 }
419 break;
420 case RL_OVERLAPSTARTSBEFORE:
421 a->rl_start = b->rl_end + 1;
422 break;
423 case RL_OVERLAPENDSAFTER:
424 a->rl_end = b->rl_start - 1;
425 break;
426 case RL_NOOVERLAP:
427 break;
428 }
429 }