[apple/xnu.git] / bsd / hfs / rangelist.c

/*
 * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 * 
 * 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.
 * 
 * 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#if HFS

#include <sys/param.h>
#include <mach/boolean.h>
#include <sys/time.h>
#include <sys/malloc.h>

#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_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range);
static void rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range);
static void rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range);


#ifdef RL_DIAGNOSTIC
static void
rl_verify(struct rl_head *rangelist) {
	struct rl_entry *entry;
	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?!");
		limit = entry->rl_end;
		if (entry == CIRCLEQ_LAST(rangelist)) return;
		entry = CIRCLEQ_NEXT(entry, rl_link);
	};
}
#endif


/*
 * Initialize a range list head
 */
void
rl_init(struct rl_head *rangelist)
{
    CIRCLEQ_INIT(rangelist);
}


/*
 * Add a range to the list
 */
void
rl_add(off_t start, off_t end, struct rl_head *rangelist)
{
	struct rl_entry *range;
	struct rl_entry *overlap;
	enum rl_overlaptype ovcase;

#ifdef RL_DIAGNOSTIC
	if (end < start) panic("rl_add: end < start?!");
#endif

	ovcase = rl_scan(rangelist, start, end, &overlap);
			
	/*
	 * Six cases:
	 *	0) no overlap
	 *	1) overlap == range
	 *	2) overlap contains range
	 *	3) range contains overlap
	 *	4) overlap starts before range
	 *	5) overlap ends after range
	 */
	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:
				*/
			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);
			} else {
				CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
			}
			
			/* Check to see if any ranges can be combined (possibly including the immediately
			   preceding range entry)
			 */
			rl_collapse_neighbors(rangelist, range);
			break;

		case RL_MATCHINGOVERLAP: /* 1: overlap == range */
		case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
			range = overlap; /* for debug output below */
			break;

		case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
			/*
			 * Replace the overlap with the new, larger range:
			 */
			overlap->rl_start = start;
			overlap->rl_end = end;
			rl_collapse_neighbors(rangelist, overlap);
			range = overlap; /* for debug output below */
			break;

		case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
			/*
			 * Expand the overlap area to cover the new range:
			 */
			overlap->rl_end = end;
			rl_collapse_forwards(rangelist, overlap);
			range = overlap; /* for debug output below */
			break;

		case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
			/*
			 * Expand the overlap area to cover the new range:
			 */
			overlap->rl_start = start;
			rl_collapse_backwards(rangelist, overlap);
			range = overlap; /* for debug output below */
			break;
	}

#ifdef RL_DIAGNOSTIC
	rl_verify(rangelist);
#endif
}


/*
 * Remove a range from a range list.
 *
 * Generally, find the range (or an overlap to that range)
 * and remove it (or shrink it), then wakeup anyone we can.
 */
void
rl_remove(off_t start, off_t end, struct rl_head *rangelist)
{
	struct rl_entry *range, *next_range, *overlap, *splitrange;
	int ovcase, moretotest;

#ifdef RL_DIAGNOSTIC
	if (end < start) panic("rl_remove: end < start?!");
#endif

	if (CIRCLEQ_EMPTY(rangelist)) {
		return;
	};
        
	range = CIRCLEQ_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);
			FREE(overlap, M_TEMP);
			break;

		case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
			if (overlap->rl_start == start) {
				overlap->rl_start = end + 1;
				break;
			};
			
			if (overlap->rl_end == end) {
				overlap->rl_end = start - 1;
				break;
			};
			
			/*
			* Make a new range consisting of the last part of the encompassing range
			*/
			MALLOC(splitrange, struct rl_entry *, sizeof *splitrange, M_TEMP, M_WAITOK);
			splitrange->rl_start = end + 1;
			splitrange->rl_end = overlap->rl_end;
			overlap->rl_end = start - 1;
			
			/*
			* 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);
			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);
			FREE(overlap, M_TEMP);
			if (moretotest) {
				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);
				continue;
			};
			break;

		case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
			overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
			break;
		}
		break;
	}

#ifdef RL_DIAGNOSTIC
	rl_verify(rangelist);
#endif
}


/*
 * Scan a range list for an entry in a specified range (if any):
 *
 * NOTE: this returns only the FIRST overlapping range.
 *	     There may be more than one.
 */

enum rl_overlaptype
rl_scan(struct rl_head *rangelist,
		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));	
}


/*
 * Walk the list of ranges for an entry to
 * find an overlapping range (if any).
 *
 * NOTE: this returns only the FIRST overlapping range.
 *	     There may be more than one.
 */
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)
{
	if (CIRCLEQ_EMPTY(rangelist)) {
		*overlap = NULL;
		return RL_NOOVERLAP;
	};
        
#ifdef RL_DIAGNOSTIC
		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;
		}

		/* Control should never reach here... */
#ifdef RL_DIAGNOSTIC
		panic("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;

        /* 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);

#ifdef RL_DIAGNOSTIC
		rl_verify(rangelist);
#endif
    };
}


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) {
#ifdef RL_DIAGNOSTIC
			rl_verify(rangelist);
#endif
        	return;
        };
        
        /* Expand this range to include the previous range: */
        range->rl_start = prev_range->rl_start;
    
        /* Remove the now covered range from the list: */
        CIRCLEQ_REMOVE(rangelist, prev_range, rl_link);
        FREE(prev_range, M_TEMP);
    };
}


static void
rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
{
    rl_collapse_forwards(rangelist, range);
    rl_collapse_backwards(rangelist, range);
}

#else /* not HFS - temp workaround until 4277828 is fixed */
/* stubs for exported routines that aren't present when we build kernel without HFS */

#include <sys/types.h>

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);
}

#endif /* HFS */
Commit	Line	Data
0b4e3aa0 A	1	/*
	2	* Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
	3	*
2d21ac55	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
0b4e3aa0	5	*
2d21ac55 A	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.
8f6c56a5	14	*
2d21ac55 A	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
8f6c56a5 A	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
8f6c56a5 A	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
2d21ac55 A	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.
8f6c56a5	25	*
2d21ac55	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
0b4e3aa0 A	27	*/
0b4e3aa0 A	28
2d21ac55 A	29	#if HFS
2d21ac55 A	30
0b4e3aa0 A	31	#include <sys/param.h>
	32	#include <mach/boolean.h>
	33	#include <sys/time.h>
	34	#include <sys/malloc.h>
	35
	36	#include "rangelist.h"
	37
	38	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);
	39	static void rl_collapse_forwards(struct rl_head rangelist, struct rl_entry range);
	40	static void rl_collapse_backwards(struct rl_head rangelist, struct rl_entry range);
	41	static void rl_collapse_neighbors(struct rl_head rangelist, struct rl_entry range);
	42
	43
	44	#ifdef RL_DIAGNOSTIC
	45	static void
	46	rl_verify(struct rl_head *rangelist) {
	47	struct rl_entry *entry;
	48	off_t limit = 0;
	49
	50	if (CIRCLEQ_EMPTY(rangelist)) return;
	51	entry = CIRCLEQ_FIRST(rangelist);
	52	while (1) {
	53	if (CIRCLEQ_NEXT(entry, rl_link) == entry) panic("rl_verify: circular rangelist?!");
	54	if ((limit > 0) && (entry->rl_start <= limit)) panic("rl_verify: bad entry start?!");
	55	if (entry->rl_end < entry->rl_start) panic("rl_verify: bad entry end?!");
	56	limit = entry->rl_end;
	57	if (entry == CIRCLEQ_LAST(rangelist)) return;
	58	entry = CIRCLEQ_NEXT(entry, rl_link);
	59	};
	60	}
	61	#endif
	62
	63
	64
	65	/*
	66	* Initialize a range list head
	67	*/
	68	void
	69	rl_init(struct rl_head *rangelist)
	70	{
	71	CIRCLEQ_INIT(rangelist);
	72	}
	73
	74
	75
	76	/*
	77	* Add a range to the list
	78	*/
	79	void
	80	rl_add(off_t start, off_t end, struct rl_head *rangelist)
	81	{
	82	struct rl_entry *range;
	83	struct rl_entry *overlap;
	84	enum rl_overlaptype ovcase;
	85
	86	#ifdef RL_DIAGNOSTIC
	87	if (end < start) panic("rl_add: end < start?!");
	88	#endif
	89
	90	ovcase = rl_scan(rangelist, start, end, &overlap);
	91
	92	/*
	93	* Six cases:
	94	* 0) no overlap
95	* 1) overlap == range
96	* 2) overlap contains range
97	* 3) range contains overlap
98	* 4) overlap starts before range
99	* 5) overlap ends after range
100	*/
101	switch (ovcase) {
102	case RL_NOOVERLAP: /* 0: no overlap */
103	/*
104	* If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
105	* if the search hit a non-overlapping entry PAST the start of the
106	* new range, 'prev' points to ITS predecessor, and 'overlap' points
107	* to that entry:
108	*/
109	MALLOC(range, struct rl_entry , sizeof(range), M_TEMP, M_WAITOK);
110	range->rl_start = start;
111	range->rl_end = end;
112
113	/* Link in the new range: */
114	if (overlap) {
115	CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
116	} else {
117	CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
118	}
119
120	/* Check to see if any ranges can be combined (possibly including the immediately
121	preceding range entry)
122	*/
123	rl_collapse_neighbors(rangelist, range);
124	break;
125
126	case RL_MATCHINGOVERLAP: /* 1: overlap == range */
127	case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
128	range = overlap; /* for debug output below */
129	break;
130
131	case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
132	/*
133	* Replace the overlap with the new, larger range:
134	*/
135	overlap->rl_start = start;
136	overlap->rl_end = end;
137	rl_collapse_neighbors(rangelist, overlap);
138	range = overlap; /* for debug output below */
139	break;
140
141	case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
142	/*
143	* Expand the overlap area to cover the new range:
144	*/
145	overlap->rl_end = end;
146	rl_collapse_forwards(rangelist, overlap);
147	range = overlap; /* for debug output below */
148	break;
149
150	case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
151	/*
152	* Expand the overlap area to cover the new range:
153	*/
154	overlap->rl_start = start;
155	rl_collapse_backwards(rangelist, overlap);
156	range = overlap; /* for debug output below */
157	break;
158	}
159
160	#ifdef RL_DIAGNOSTIC
161	rl_verify(rangelist);
162	#endif
163	}
164
165
166
167	/*
168	* Remove a range from a range list.
169	*
170	* Generally, find the range (or an overlap to that range)
171	* and remove it (or shrink it), then wakeup anyone we can.
172	*/
173	void
174	rl_remove(off_t start, off_t end, struct rl_head *rangelist)
175	{
176	struct rl_entry range, next_range, overlap, splitrange;
177	int ovcase, moretotest;
178
179	#ifdef RL_DIAGNOSTIC
180	if (end < start) panic("rl_remove: end < start?!");
181	#endif
182
183	if (CIRCLEQ_EMPTY(rangelist)) {
184	return;
185	};
186
187	range = CIRCLEQ_FIRST(rangelist);
188	while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
189	switch (ovcase) {
190
191	case RL_MATCHINGOVERLAP: /* 1: overlap == range */
192	CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
193	FREE(overlap, M_TEMP);
194	break;
195
196	case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
197	if (overlap->rl_start == start) {
198	overlap->rl_start = end + 1;
199	break;
200	};
201
202	if (overlap->rl_end == end) {
203	overlap->rl_end = start - 1;
204	break;
205	};
206
207	/*
208	* Make a new range consisting of the last part of the encompassing range
209	*/
210	MALLOC(splitrange, struct rl_entry , sizeof splitrange, M_TEMP, M_WAITOK);
211	splitrange->rl_start = end + 1;
212	splitrange->rl_end = overlap->rl_end;
213	overlap->rl_end = start - 1;
214
215	/*
216	* Now link the new entry into the range list after the range from which it was split:
217	*/
218	CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
219	break;
220
221	case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
222	moretotest = (overlap != CIRCLEQ_LAST(rangelist));
223	#ifdef RL_DIAGNOSTIC
224	if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
225	#endif
226	next_range = CIRCLEQ_NEXT(overlap, rl_link); /* Check before discarding overlap entry */
227	CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
228	FREE(overlap, M_TEMP);
229	if (moretotest) {
230	range = next_range;
231	continue;
232	};
233	break;
234
235	case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
236	moretotest = (overlap != CIRCLEQ_LAST(rangelist));
237	overlap->rl_end = start - 1;
238	if (moretotest) {
239	#ifdef RL_DIAGNOSTIC
240	if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
241	#endif
242	range = CIRCLEQ_NEXT(overlap, rl_link);
243	continue;
244	};
245	break;
246
247	case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
248	overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
249	break;
250	}
251	break;
252	}
253
254	#ifdef RL_DIAGNOSTIC
255	rl_verify(rangelist);
256	#endif
257	}
258
259
260
261	/*
262	* Scan a range list for an entry in a specified range (if any):
263	*
264	* NOTE: this returns only the FIRST overlapping range.
265	* There may be more than one.
266	*/
267
268	enum rl_overlaptype
269	rl_scan(struct rl_head *rangelist,
270	off_t start,
271	off_t end,
272	struct rl_entry **overlap) {
273
274	if (CIRCLEQ_EMPTY(rangelist)) {
275	*overlap = NULL;
276	return RL_NOOVERLAP;
277	};
278
279	return rl_scan_from(rangelist, start, end, overlap, CIRCLEQ_FIRST(rangelist));
280	}
281
282
283
284	/*
285	* Walk the list of ranges for an entry to
286	* find an overlapping range (if any).
287	*
288	* NOTE: this returns only the FIRST overlapping range.
289	* There may be more than one.
290	*/
291	static enum rl_overlaptype
292	rl_scan_from(struct rl_head *rangelist,
293	off_t start,
294	off_t end,
295	struct rl_entry **overlap,
296	struct rl_entry *range)
297	{
298	if (CIRCLEQ_EMPTY(rangelist)) {
299	*overlap = NULL;
300	return RL_NOOVERLAP;
301	};
302
303	#ifdef RL_DIAGNOSTIC
304	rl_verify(rangelist);
305	#endif
306
307	*overlap = range;
308
309	while (1) {
310	/*
311	* OK, check for overlap
312	*
313	* Six cases:
314	* 0) no overlap (RL_NOOVERLAP)
315	* 1) overlap == range (RL_MATCHINGOVERLAP)
316	* 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
317	* 3) range contains overlap (RL_OVERLAPISCONTAINED)
318	* 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
319	* 5) overlap ends after range (RL_OVERLAPENDSAFTER)
320	*/
321	if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) \|\|
322	((end != RL_INFINITY) && (range->rl_start > end))) {
323	/* Case 0 (RL_NOOVERLAP), at least with the current entry: */
324	if ((end != RL_INFINITY) && (range->rl_start > end)) {
325	return RL_NOOVERLAP;
326	};
327
328	/* Check the other entries in the list: */
329	if (range == CIRCLEQ_LAST(rangelist)) {
330	return RL_NOOVERLAP;
331	};
332	#ifdef RL_DIAGNOSTIC
333	if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!");
334	#endif
335	*overlap = range = CIRCLEQ_NEXT(range, rl_link);
336	continue;
337	}
338
339	if ((range->rl_start == start) && (range->rl_end == end)) {
340	/* Case 1 (RL_MATCHINGOVERLAP) */
341	return RL_MATCHINGOVERLAP;
342	}
343
344	if ((range->rl_start <= start) &&
345	(end != RL_INFINITY) &&
346	((range->rl_end >= end) \|\| (range->rl_end == RL_INFINITY))) {
347	/* Case 2 (RL_OVERLAPCONTAINSRANGE) */
348	return RL_OVERLAPCONTAINSRANGE;
349	}
350
351	if ((start <= range->rl_start) &&
352	((end == RL_INFINITY) \|\|
353	((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
354	/* Case 3 (RL_OVERLAPISCONTAINED) */
355	return RL_OVERLAPISCONTAINED;
356	}
357
358	if ((range->rl_start < start) &&
359	((range->rl_end >= start) \|\| (range->rl_end == RL_INFINITY))) {
360	/* Case 4 (RL_OVERLAPSTARTSBEFORE) */
361	return RL_OVERLAPSTARTSBEFORE;
362	}
363
364	if ((range->rl_start > start) &&
365	(end != RL_INFINITY) &&
366	((range->rl_end > end) \|\| (range->rl_end == RL_INFINITY))) {
367	/* Case 5 (RL_OVERLAPENDSAFTER) */
368	return RL_OVERLAPENDSAFTER;
369	}
370
371	/* Control should never reach here... */
372	#ifdef RL_DIAGNOSTIC
373	panic("rl_scan_from: unhandled overlap condition?!");
374	#endif
375	}
376
377	return RL_NOOVERLAP;
378	}
379
380
381	static void
382	rl_collapse_forwards(struct rl_head rangelist, struct rl_entry range) {
383	struct rl_entry *next_range;
384
385	while (1) {
386	if (range == CIRCLEQ_LAST(rangelist)) return;
387
388	#ifdef RL_DIAGNOSTIC
389	if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!");
390	#endif
391	next_range = CIRCLEQ_NEXT(range, rl_link);
392	if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
393
394	/* Expand this range to include the next range: */
395	range->rl_end = next_range->rl_end;
396
397	/* Remove the now covered range from the list: */
398	CIRCLEQ_REMOVE(rangelist, next_range, rl_link);
399	FREE(next_range, M_TEMP);
400
401	#ifdef RL_DIAGNOSTIC
402	rl_verify(rangelist);
403	#endif
404	};
405	}
406
407
408
409	static void
410	rl_collapse_backwards(struct rl_head rangelist, struct rl_entry range) {
411	struct rl_entry *prev_range;
412
413	while (1) {
414	if (range == CIRCLEQ_FIRST(rangelist)) return;
415
416	#ifdef RL_DIAGNOSTIC
417	if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!");
418	#endif
419	prev_range = CIRCLEQ_PREV(range, rl_link);
420	if (prev_range->rl_end < range->rl_start - 1) {
421	#ifdef RL_DIAGNOSTIC
422	rl_verify(rangelist);
423	#endif
424	return;
425	};
426
427	/* Expand this range to include the previous range: */
428	range->rl_start = prev_range->rl_start;
429
430	/* Remove the now covered range from the list: */
431	CIRCLEQ_REMOVE(rangelist, prev_range, rl_link);
432	FREE(prev_range, M_TEMP);
433	};
434	}
435
436
437
438	static void
439	rl_collapse_neighbors(struct rl_head rangelist, struct rl_entry range)
440	{
441	rl_collapse_forwards(rangelist, range);
442	rl_collapse_backwards(rangelist, range);
443	}
2d21ac55 A	444
	445	#else /* not HFS - temp workaround until 4277828 is fixed */
	446	/* stubs for exported routines that aren't present when we build kernel without HFS */
	447
	448	#include <sys/types.h>
	449
	450	void rl_add(off_t start, off_t end, void *rangelist);
	451	void rl_init(void *rangelist);
	452	void rl_remove(off_t start, off_t end, void *rangelist);
	453	int rl_scan(void rangelist, off_t start, off_t end, void *overlap);
	454
	455	void rl_add(__unused off_t start, __unused off_t end, __unused void *rangelist)
	456	{
	457	return;
	458	}
	459
	460	void rl_init(__unused void *rangelist)
	461	{
	462	return;
	463	}
	464
	465	void rl_remove(__unused off_t start, __unused off_t end, __unused void *rangelist)
	466	{
	467	return;
	468	}
	469
	470	int rl_scan(__unused void rangelist, __unused off_t start, __unused off_t end, __unused void *overlap)
	471	{
	472	return(0);
	473	}
	474
	475	#endif /* HFS */