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

/*
 * Copyright (c) 2001, 2006-2008 Apple 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;
	struct rl_entry *next;
	off_t limit = 0;
	
	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;
	};
}
#endif


/*
 * Initialize a range list head
 */
void
rl_init(struct rl_head *rangelist)
{
    TAILQ_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("hfs: 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) {
				TAILQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
			} else {
				TAILQ_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;

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

	if (TAILQ_EMPTY(rangelist)) {
		return;
	};
        
	range = TAILQ_FIRST(rangelist);
	while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
		switch (ovcase) {

		case RL_MATCHINGOVERLAP: /* 1: overlap == range */
			TAILQ_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:
			*/
			TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
			break;

		case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
			/* Check before discarding overlap entry */
			next_range = TAILQ_NEXT(overlap, rl_link);
			TAILQ_REMOVE(rangelist, overlap, rl_link);
			FREE(overlap, M_TEMP);
			if (next_range) {
				range = next_range;
				continue;
			};
			break;

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