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

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