/*
- * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2001-2014 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
#include <sys/time.h>
#include <sys/malloc.h>
+#if !RANGELIST_TEST
+#include <kern/debug.h>
+#endif
+
#include "rangelist.h"
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);
static void
rl_verify(struct rl_head *rangelist) {
struct rl_entry *entry;
+ struct rl_entry *next;
off_t limit = 0;
- if (CIRCLEQ_EMPTY(rangelist)) return;
- entry = CIRCLEQ_FIRST(rangelist);
- while (1) {
- if (CIRCLEQ_NEXT(entry, rl_link) == entry) panic("rl_verify: circular rangelist?!");
- if ((limit > 0) && (entry->rl_start <= limit)) panic("rl_verify: bad entry start?!");
- if (entry->rl_end < entry->rl_start) panic("rl_verify: bad entry end?!");
+ TAILQ_FOREACH_SAFE(rangelist, entry, rl_link, next) {
+ if ((limit > 0) && (entry->rl_start <= limit)) panic("hfs: rl_verify: bad entry start?!");
+ if (entry->rl_end < entry->rl_start) panic("hfs: rl_verify: bad entry end?!");
limit = entry->rl_end;
- if (entry == CIRCLEQ_LAST(rangelist)) return;
- entry = CIRCLEQ_NEXT(entry, rl_link);
};
}
#endif
void
rl_init(struct rl_head *rangelist)
{
- CIRCLEQ_INIT(rangelist);
+ TAILQ_INIT(rangelist);
}
-
-
/*
* Add a range to the list
*/
enum rl_overlaptype ovcase;
#ifdef RL_DIAGNOSTIC
- if (end < start) panic("rl_add: end < start?!");
+ if (end < start) panic("hfs: rl_add: end < start?!");
#endif
ovcase = rl_scan(rangelist, start, end, &overlap);
switch (ovcase) {
case RL_NOOVERLAP: /* 0: no overlap */
/*
- * If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
- * if the search hit a non-overlapping entry PAST the start of the
- * new range, 'prev' points to ITS predecessor, and 'overlap' points
- * to that entry:
- */
+ * overlap points to the entry we should insert before, or
+ * if NULL, we should insert at the end.
+ */
MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
range->rl_start = start;
range->rl_end = end;
/* Link in the new range: */
if (overlap) {
- CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
+ TAILQ_INSERT_BEFORE(overlap, range, rl_link);
} else {
- CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
+ TAILQ_INSERT_TAIL(rangelist, range, rl_link);
}
/* Check to see if any ranges can be combined (possibly including the immediately
rl_remove(off_t start, off_t end, struct rl_head *rangelist)
{
struct rl_entry *range, *next_range, *overlap, *splitrange;
- int ovcase, moretotest;
+ int ovcase;
#ifdef RL_DIAGNOSTIC
- if (end < start) panic("rl_remove: end < start?!");
+ if (end < start) panic("hfs: rl_remove: end < start?!");
#endif
- if (CIRCLEQ_EMPTY(rangelist)) {
+ if (TAILQ_EMPTY(rangelist)) {
return;
};
-
- range = CIRCLEQ_FIRST(rangelist);
+
+ range = TAILQ_FIRST(rangelist);
while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
switch (ovcase) {
case RL_MATCHINGOVERLAP: /* 1: overlap == range */
- CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
+ TAILQ_REMOVE(rangelist, overlap, rl_link);
FREE(overlap, M_TEMP);
break;
/*
* Now link the new entry into the range list after the range from which it was split:
*/
- CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
+ TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
break;
case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
- moretotest = (overlap != CIRCLEQ_LAST(rangelist));
-#ifdef RL_DIAGNOSTIC
- if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
-#endif
- next_range = CIRCLEQ_NEXT(overlap, rl_link); /* Check before discarding overlap entry */
- CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
+ /* Check before discarding overlap entry */
+ next_range = TAILQ_NEXT(overlap, rl_link);
+ TAILQ_REMOVE(rangelist, overlap, rl_link);
FREE(overlap, M_TEMP);
- if (moretotest) {
+ if (next_range) {
range = next_range;
continue;
};
break;
case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
- moretotest = (overlap != CIRCLEQ_LAST(rangelist));
overlap->rl_end = start - 1;
- if (moretotest) {
-#ifdef RL_DIAGNOSTIC
- if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
-#endif
- range = CIRCLEQ_NEXT(overlap, rl_link);
+ range = TAILQ_NEXT(overlap, rl_link);
+ if (range) {
continue;
- };
+ }
break;
case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
off_t start,
off_t end,
struct rl_entry **overlap) {
-
- if (CIRCLEQ_EMPTY(rangelist)) {
- *overlap = NULL;
- return RL_NOOVERLAP;
- };
-
- return rl_scan_from(rangelist, start, end, overlap, CIRCLEQ_FIRST(rangelist));
+
+ return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
}
+enum rl_overlaptype
+rl_overlap(const struct rl_entry *range, off_t start, off_t end)
+{
+ /*
+ * OK, check for overlap
+ *
+ * Six cases:
+ * 0) no overlap (RL_NOOVERLAP)
+ * 1) overlap == range (RL_MATCHINGOVERLAP)
+ * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
+ * 3) range contains overlap (RL_OVERLAPISCONTAINED)
+ * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
+ * 5) overlap ends after range (RL_OVERLAPENDSAFTER)
+ */
+ if (start > range->rl_end || range->rl_start > end) {
+ /* Case 0 (RL_NOOVERLAP) */
+ return RL_NOOVERLAP;
+ }
+
+ if (range->rl_start == start && range->rl_end == end) {
+ /* Case 1 (RL_MATCHINGOVERLAP) */
+ return RL_MATCHINGOVERLAP;
+ }
+
+ if (range->rl_start <= start && range->rl_end >= end) {
+ /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
+ return RL_OVERLAPCONTAINSRANGE;
+ }
+ if (start <= range->rl_start && end >= range->rl_end) {
+ /* Case 3 (RL_OVERLAPISCONTAINED) */
+ return RL_OVERLAPISCONTAINED;
+ }
+
+ if (range->rl_start < start && range->rl_end < end) {
+ /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
+ return RL_OVERLAPSTARTSBEFORE;
+ }
+
+ /* Case 5 (RL_OVERLAPENDSAFTER) */
+ // range->rl_start > start && range->rl_end > end
+ return RL_OVERLAPENDSAFTER;
+}
/*
* Walk the list of ranges for an entry to
* There may be more than one.
*/
static enum rl_overlaptype
-rl_scan_from(struct rl_head *rangelist,
+rl_scan_from(struct rl_head *rangelist __unused,
off_t start,
off_t end,
struct rl_entry **overlap,
- struct rl_entry *range)
+ struct rl_entry *range)
{
- if (CIRCLEQ_EMPTY(rangelist)) {
- *overlap = NULL;
- return RL_NOOVERLAP;
- };
-
#ifdef RL_DIAGNOSTIC
- rl_verify(rangelist);
+ rl_verify(rangelist);
#endif
- *overlap = range;
-
- while (1) {
- /*
- * OK, check for overlap
- *
- * Six cases:
- * 0) no overlap (RL_NOOVERLAP)
- * 1) overlap == range (RL_MATCHINGOVERLAP)
- * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
- * 3) range contains overlap (RL_OVERLAPISCONTAINED)
- * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
- * 5) overlap ends after range (RL_OVERLAPENDSAFTER)
- */
- if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) ||
- ((end != RL_INFINITY) && (range->rl_start > end))) {
- /* Case 0 (RL_NOOVERLAP), at least with the current entry: */
- if ((end != RL_INFINITY) && (range->rl_start > end)) {
- return RL_NOOVERLAP;
- };
-
- /* Check the other entries in the list: */
- if (range == CIRCLEQ_LAST(rangelist)) {
- return RL_NOOVERLAP;
- };
-#ifdef RL_DIAGNOSTIC
- if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!");
-#endif
- *overlap = range = CIRCLEQ_NEXT(range, rl_link);
- continue;
- }
-
- if ((range->rl_start == start) && (range->rl_end == end)) {
- /* Case 1 (RL_MATCHINGOVERLAP) */
- return RL_MATCHINGOVERLAP;
- }
-
- if ((range->rl_start <= start) &&
- (end != RL_INFINITY) &&
- ((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) {
- /* Case 2 (RL_OVERLAPCONTAINSRANGE) */
- return RL_OVERLAPCONTAINSRANGE;
- }
-
- if ((start <= range->rl_start) &&
- ((end == RL_INFINITY) ||
- ((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
- /* Case 3 (RL_OVERLAPISCONTAINED) */
- return RL_OVERLAPISCONTAINED;
- }
-
- if ((range->rl_start < start) &&
- ((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) {
- /* Case 4 (RL_OVERLAPSTARTSBEFORE) */
- return RL_OVERLAPSTARTSBEFORE;
- }
-
- if ((range->rl_start > start) &&
- (end != RL_INFINITY) &&
- ((range->rl_end > end) || (range->rl_end == RL_INFINITY))) {
- /* Case 5 (RL_OVERLAPENDSAFTER) */
- return RL_OVERLAPENDSAFTER;
+ while (range) {
+ enum rl_overlaptype ot = rl_overlap(range, start, end);
+
+ if (ot != RL_NOOVERLAP || range->rl_start > end) {
+ *overlap = range;
+ return ot;
}
- /* Control should never reach here... */
-#ifdef RL_DIAGNOSTIC
- panic("rl_scan_from: unhandled overlap condition?!");
-#endif
+ range = TAILQ_NEXT(range, rl_link);
}
-
+
+ *overlap = NULL;
return RL_NOOVERLAP;
}
static void
rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
- struct rl_entry *next_range;
-
- while (1) {
- if (range == CIRCLEQ_LAST(rangelist)) return;
-
-#ifdef RL_DIAGNOSTIC
- if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!");
-#endif
- next_range = CIRCLEQ_NEXT(range, rl_link);
- if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
+ struct rl_entry *next_range;
+
+ while ((next_range = TAILQ_NEXT(range, rl_link))) {
+ if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
- /* Expand this range to include the next range: */
- range->rl_end = next_range->rl_end;
-
- /* Remove the now covered range from the list: */
- CIRCLEQ_REMOVE(rangelist, next_range, rl_link);
- FREE(next_range, M_TEMP);
+ /* Expand this range to include the next range: */
+ range->rl_end = next_range->rl_end;
+
+ /* Remove the now covered range from the list: */
+ TAILQ_REMOVE(rangelist, next_range, rl_link);
+ FREE(next_range, M_TEMP);
#ifdef RL_DIAGNOSTIC
rl_verify(rangelist);
#endif
- };
+ };
}
rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
struct rl_entry *prev_range;
- while (1) {
- if (range == CIRCLEQ_FIRST(rangelist)) return;
-
-#ifdef RL_DIAGNOSTIC
- if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!");
-#endif
- prev_range = CIRCLEQ_PREV(range, rl_link);
- if (prev_range->rl_end < range->rl_start - 1) {
+ while ((prev_range = TAILQ_PREV(range, rl_head, rl_link))) {
+ if (prev_range->rl_end < range->rl_start -1) {
#ifdef RL_DIAGNOSTIC
rl_verify(rangelist);
#endif
range->rl_start = prev_range->rl_start;
/* Remove the now covered range from the list: */
- CIRCLEQ_REMOVE(rangelist, prev_range, rl_link);
+ TAILQ_REMOVE(rangelist, prev_range, rl_link);
FREE(prev_range, M_TEMP);
};
}
rl_collapse_backwards(rangelist, range);
}
+void rl_remove_all(struct rl_head *rangelist)
+{
+ struct rl_entry *r, *nextr;
+ TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
+ FREE(r, M_TEMP);
+ TAILQ_INIT(rangelist);
+}
+
+/*
+ * In the case where b is contained by a, we return the the largest part
+ * remaining. The result is stored in a.
+ */
+void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
+{
+ switch (rl_overlap(b, a->rl_start, a->rl_end)) {
+ case RL_MATCHINGOVERLAP:
+ case RL_OVERLAPCONTAINSRANGE:
+ a->rl_end = a->rl_start - 1;
+ break;
+ case RL_OVERLAPISCONTAINED:
+ // Keep the bigger part
+ if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
+ // Keep left
+ a->rl_end = b->rl_start - 1;
+ } else {
+ // Keep right
+ a->rl_start = b->rl_end + 1;
+ }
+ break;
+ case RL_OVERLAPSTARTSBEFORE:
+ a->rl_start = b->rl_end + 1;
+ break;
+ case RL_OVERLAPENDSAFTER:
+ a->rl_end = b->rl_start - 1;
+ break;
+ case RL_NOOVERLAP:
+ break;
+ }
+}
+
#else /* not HFS - temp workaround until 4277828 is fixed */
/* stubs for exported routines that aren't present when we build kernel without HFS */
return(0);
}
+void rl_remove_all(struct rl_head *rangelist)
+{
+}
+
#endif /* HFS */
projects / apple / xnu.git / blobdiff