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

/*
 * Copyright (c) 2001-2014 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 */
			/*
			 * overlap points to the entry we should insert before, or
			 * if NULL, we should insert at the end.
			 */
			MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
			range->rl_start = start;
			range->rl_end = end;
			
			/* Link in the new range: */
			if (overlap) {
				TAILQ_INSERT_BEFORE(overlap, range, rl_link);
			} else {
				TAILQ_INSERT_TAIL(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;
			};
			
			/* Check the other entries in the list: */
			range = TAILQ_NEXT(range, rl_link);
			*overlap = range;
			if (range == NULL)
				return RL_NOOVERLAP;
			
			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
	}
}


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

void rl_remove_all(struct rl_head *rangelist)
{
	struct rl_entry *r, *nextr;
	TAILQ_FOREACH_SAFE(r, rangelist, rl_link, nextr)
		FREE(r, M_TEMP);
	TAILQ_INIT(rangelist);
}

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

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

void rl_remove_all(struct rl_head *rangelist)
{
}

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