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

/*
 * Copyright (c) 2001 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * 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. 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_LICENSE_HEADER_END@
 */

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