]>
git.saurik.com Git - apple/hfs.git/blob - core/rangelist.c
2 * Copyright (c) 2001-2015 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
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.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
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.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
29 #include <sys/param.h>
30 #include <mach/boolean.h>
32 #include <sys/malloc.h>
35 #include <kern/debug.h>
39 #include "rangelist.h"
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
);
49 rl_verify(struct rl_head
*rangelist
) {
50 struct rl_entry
*entry
;
51 struct rl_entry
*next
;
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
;
65 * Initialize a range list head
68 rl_init(struct rl_head
*rangelist
)
70 TAILQ_INIT(rangelist
);
74 * Add a range to the list
77 rl_add(off_t start
, off_t end
, struct rl_head
*rangelist
)
79 struct rl_entry
*range
;
80 struct rl_entry
*overlap
;
81 enum rl_overlaptype ovcase
;
84 if (end
< start
) panic("hfs: rl_add: end < start?!");
87 ovcase
= rl_scan(rangelist
, start
, end
, &overlap
);
93 * 2) overlap contains range
94 * 3) range contains overlap
95 * 4) overlap starts before range
96 * 5) overlap ends after range
99 case RL_NOOVERLAP
: /* 0: no overlap */
101 * overlap points to the entry we should insert before, or
102 * if NULL, we should insert at the end.
104 range
= hfs_malloc(sizeof(*range
));
105 range
->rl_start
= start
;
108 /* Link in the new range: */
110 TAILQ_INSERT_BEFORE(overlap
, range
, rl_link
);
112 TAILQ_INSERT_TAIL(rangelist
, range
, rl_link
);
115 /* Check to see if any ranges can be combined (possibly including the immediately
116 preceding range entry)
118 rl_collapse_neighbors(rangelist
, range
);
121 case RL_MATCHINGOVERLAP
: /* 1: overlap == range */
122 case RL_OVERLAPCONTAINSRANGE
: /* 2: overlap contains range */
125 case RL_OVERLAPISCONTAINED
: /* 3: range contains overlap */
127 * Replace the overlap with the new, larger range:
129 overlap
->rl_start
= start
;
130 overlap
->rl_end
= end
;
131 rl_collapse_neighbors(rangelist
, overlap
);
134 case RL_OVERLAPSTARTSBEFORE
: /* 4: overlap starts before range */
136 * Expand the overlap area to cover the new range:
138 overlap
->rl_end
= end
;
139 rl_collapse_forwards(rangelist
, overlap
);
142 case RL_OVERLAPENDSAFTER
: /* 5: overlap ends after range */
144 * Expand the overlap area to cover the new range:
146 overlap
->rl_start
= start
;
147 rl_collapse_backwards(rangelist
, overlap
);
152 rl_verify(rangelist
);
159 * Remove a range from a range list.
161 * Generally, find the range (or an overlap to that range)
162 * and remove it (or shrink it), then wakeup anyone we can.
165 rl_remove(off_t start
, off_t end
, struct rl_head
*rangelist
)
167 struct rl_entry
*range
, *next_range
, *overlap
, *splitrange
;
171 if (end
< start
) panic("hfs: rl_remove: end < start?!");
174 if (TAILQ_EMPTY(rangelist
)) {
178 range
= TAILQ_FIRST(rangelist
);
179 while ((ovcase
= rl_scan_from(rangelist
, start
, end
, &overlap
, range
))) {
182 case RL_MATCHINGOVERLAP
: /* 1: overlap == range */
183 TAILQ_REMOVE(rangelist
, overlap
, rl_link
);
184 hfs_free(overlap
, sizeof(*overlap
));
187 case RL_OVERLAPCONTAINSRANGE
: /* 2: overlap contains range: split it */
188 if (overlap
->rl_start
== start
) {
189 overlap
->rl_start
= end
+ 1;
193 if (overlap
->rl_end
== end
) {
194 overlap
->rl_end
= start
- 1;
199 * Make a new range consisting of the last part of the encompassing range
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;
207 * Now link the new entry into the range list after the range from which it was split:
209 TAILQ_INSERT_AFTER(rangelist
, overlap
, splitrange
, rl_link
);
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
));
223 case RL_OVERLAPSTARTSBEFORE
: /* 4: overlap starts before range */
224 overlap
->rl_end
= start
- 1;
225 range
= TAILQ_NEXT(overlap
, rl_link
);
231 case RL_OVERLAPENDSAFTER
: /* 5: overlap ends after range */
232 overlap
->rl_start
= (end
== RL_INFINITY
? RL_INFINITY
: end
+ 1);
239 rl_verify(rangelist
);
246 * Scan a range list for an entry in a specified range (if any):
248 * NOTE: this returns only the FIRST overlapping range.
249 * There may be more than one.
253 rl_scan(struct rl_head
*rangelist
,
256 struct rl_entry
**overlap
) {
258 return rl_scan_from(rangelist
, start
, end
, overlap
, TAILQ_FIRST(rangelist
));
262 rl_overlap(const struct rl_entry
*range
, off_t start
, off_t end
)
265 * OK, check for overlap
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)
275 if (start
> range
->rl_end
|| range
->rl_start
> end
) {
276 /* Case 0 (RL_NOOVERLAP) */
280 if (range
->rl_start
== start
&& range
->rl_end
== end
) {
281 /* Case 1 (RL_MATCHINGOVERLAP) */
282 return RL_MATCHINGOVERLAP
;
285 if (range
->rl_start
<= start
&& range
->rl_end
>= end
) {
286 /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
287 return RL_OVERLAPCONTAINSRANGE
;
290 if (start
<= range
->rl_start
&& end
>= range
->rl_end
) {
291 /* Case 3 (RL_OVERLAPISCONTAINED) */
292 return RL_OVERLAPISCONTAINED
;
295 if (range
->rl_start
< start
&& range
->rl_end
< end
) {
296 /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
297 return RL_OVERLAPSTARTSBEFORE
;
300 /* Case 5 (RL_OVERLAPENDSAFTER) */
301 // range->rl_start > start && range->rl_end > end
302 return RL_OVERLAPENDSAFTER
;
306 * Walk the list of ranges for an entry to
307 * find an overlapping range (if any).
309 * NOTE: this returns only the FIRST overlapping range.
310 * There may be more than one.
312 static enum rl_overlaptype
313 rl_scan_from(struct rl_head
*rangelist __unused
,
316 struct rl_entry
**overlap
,
317 struct rl_entry
*range
)
320 rl_verify(rangelist
);
324 enum rl_overlaptype ot
= rl_overlap(range
, start
, end
);
326 if (ot
!= RL_NOOVERLAP
|| range
->rl_start
> end
) {
331 range
= TAILQ_NEXT(range
, rl_link
);
340 rl_collapse_forwards(struct rl_head
*rangelist
, struct rl_entry
*range
) {
341 struct rl_entry
*next_range
;
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;
346 /* Expand this range to include the next range: */
347 range
->rl_end
= next_range
->rl_end
;
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
));
354 rl_verify(rangelist
);
362 rl_collapse_backwards(struct rl_head
*rangelist
, struct rl_entry
*range
) {
363 struct rl_entry
*prev_range
;
365 while ((prev_range
= TAILQ_PREV(range
, rl_head
, rl_link
))) {
366 if (prev_range
->rl_end
< range
->rl_start
-1) {
368 rl_verify(rangelist
);
373 /* Expand this range to include the previous range: */
374 range
->rl_start
= prev_range
->rl_start
;
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
));
385 rl_collapse_neighbors(struct rl_head
*rangelist
, struct rl_entry
*range
)
387 rl_collapse_forwards(rangelist
, range
);
388 rl_collapse_backwards(rangelist
, range
);
391 void rl_remove_all(struct rl_head
*rangelist
)
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
);
400 * In the case where b is contained by a, we return the the largest part
401 * remaining. The result is stored in a.
403 void rl_subtract(struct rl_entry
*a
, const struct rl_entry
*b
)
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;
410 case RL_OVERLAPISCONTAINED
:
411 // Keep the bigger part
412 if (b
->rl_start
- a
->rl_start
>= a
->rl_end
- b
->rl_end
) {
414 a
->rl_end
= b
->rl_start
- 1;
417 a
->rl_start
= b
->rl_end
+ 1;
420 case RL_OVERLAPSTARTSBEFORE
:
421 a
->rl_start
= b
->rl_end
+ 1;
423 case RL_OVERLAPENDSAFTER
:
424 a
->rl_end
= b
->rl_start
- 1;