/*
- * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 2001-2014 Apple Inc. All rights reserved.
*
* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
*
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);
}
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 end,
struct rl_entry **overlap) {
- if (CIRCLEQ_EMPTY(rangelist)) {
+ if (TAILQ_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));
}
struct rl_entry **overlap,
struct rl_entry *range)
{
- if (CIRCLEQ_EMPTY(rangelist)) {
+ if (TAILQ_EMPTY(rangelist)) {
*overlap = NULL;
return RL_NOOVERLAP;
};
};
/* Check the other entries in the list: */
- if (range == CIRCLEQ_LAST(rangelist)) {
+ range = TAILQ_NEXT(range, rl_link);
+ *overlap = range;
+ if (range == NULL)
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;
}
/* Control should never reach here... */
#ifdef RL_DIAGNOSTIC
- panic("rl_scan_from: unhandled overlap condition?!");
+ panic("hfs: rl_scan_from: unhandled overlap condition?!");
#endif
}
-
- 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);
+}
+
#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