X-Git-Url: https://git.saurik.com/apple/xnu.git/blobdiff_plain/0b4e3aa066abc0728aacb4bbeb86f53f9737156e..c18c124eaa464aaaa5549e99e5a70fc9cbb50944:/bsd/hfs/rangelist.c diff --git a/bsd/hfs/rangelist.c b/bsd/hfs/rangelist.c index cc062004f..0a1b412b6 100644 --- a/bsd/hfs/rangelist.c +++ b/bsd/hfs/rangelist.c @@ -1,25 +1,33 @@ /* - * Copyright (c) 2001 Apple Computer, Inc. All rights reserved. + * Copyright (c) 2001-2014 Apple Inc. All rights reserved. * - * @APPLE_LICENSE_HEADER_START@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_START@ * - * The contents of this file constitute Original Code as defined in and - * are subject to the Apple Public Source License Version 1.1 (the - * "License"). You may not use this file except in compliance with the - * License. Please obtain a copy of the License at - * http://www.apple.com/publicsource and read it before using this file. + * This file contains Original Code and/or Modifications of Original Code + * as defined in and that are subject to the Apple Public Source License + * Version 2.0 (the 'License'). You may not use this file except in + * compliance with the License. The rights granted to you under the License + * may not be used to create, or enable the creation or redistribution of, + * unlawful or unlicensed copies of an Apple operating system, or to + * circumvent, violate, or enable the circumvention or violation of, any + * terms of an Apple operating system software license agreement. * - * This Original Code and all software distributed under the License are - * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER + * Please obtain a copy of the License at + * http://www.opensource.apple.com/apsl/ and read it before using this file. + * + * The Original Code and all software distributed under the License are + * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the - * License for the specific language governing rights and limitations - * under the License. + * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. + * Please see the License for the specific language governing rights and + * limitations under the License. * - * @APPLE_LICENSE_HEADER_END@ + * @APPLE_OSREFERENCE_LICENSE_HEADER_END@ */ +#if HFS + #include #include #include @@ -37,17 +45,13 @@ static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *ra 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 @@ -60,7 +64,7 @@ rl_verify(struct rl_head *rangelist) { void rl_init(struct rl_head *rangelist) { - CIRCLEQ_INIT(rangelist); + TAILQ_INIT(rangelist); } @@ -76,7 +80,7 @@ rl_add(off_t start, off_t end, struct rl_head *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); @@ -93,20 +97,18 @@ rl_add(off_t start, off_t end, struct rl_head *rangelist) 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 @@ -166,22 +168,22 @@ void 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; @@ -207,33 +209,26 @@ rl_remove(off_t start, off_t end, struct rl_head *rangelist) /* * 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 */ @@ -263,12 +258,12 @@ rl_scan(struct rl_head *rangelist, 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)); } @@ -287,7 +282,7 @@ rl_scan_from(struct rl_head *rangelist, struct rl_entry **overlap, struct rl_entry *range) { - if (CIRCLEQ_EMPTY(rangelist)) { + if (TAILQ_EMPTY(rangelist)) { *overlap = NULL; return RL_NOOVERLAP; }; @@ -318,13 +313,11 @@ rl_scan_from(struct rl_head *rangelist, }; /* 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; } @@ -362,38 +355,30 @@ rl_scan_from(struct rl_head *rangelist, /* 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 - }; + }; } @@ -402,14 +387,8 @@ static void 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 @@ -420,7 +399,7 @@ rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) { 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); }; } @@ -433,3 +412,47 @@ rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range) rl_collapse_forwards(rangelist, range); 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 */ + +#include + +void rl_add(off_t start, off_t end, void *rangelist); +void rl_init(void *rangelist); +void rl_remove(off_t start, off_t end, void *rangelist); +int rl_scan(void *rangelist, off_t start, off_t end, void **overlap); + +void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist) +{ + return; +} + +void rl_init(__unused void *rangelist) +{ + return; +} + +void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist) +{ + return; +} + +int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap) +{ + return(0); +} + +void rl_remove_all(struct rl_head *rangelist) +{ +} + +#endif /* HFS */