bsd/hfs/rangelist.c

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);
79 	struct rl_entry *overlap;
86 	ovcase = rl_scan(rangelist, start, end, &overlap);
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
98 		case RL_NOOVERLAP: /* 0: no overlap */
100 				* If the list was empty 'prev' is undisturbed and 'overlap' == NULL;
102 				* new range, 'prev' points to ITS predecessor, and 'overlap' points
110 			if (overlap) {
111 				TAILQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
122 		case RL_MATCHINGOVERLAP: /* 1: overlap == range */
123 		case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
124 			range = overlap; /* for debug output below */
127 		case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
129 			 * Replace the overlap with the new, larger range:
131 			overlap->rl_start = start;
132 			overlap->rl_end = end;
133 			rl_collapse_neighbors(rangelist, overlap);
134 			range = overlap; /* for debug output below */
137 		case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
139 			 * Expand the overlap area to cover the new range:
141 			overlap->rl_end = end;
142 			rl_collapse_forwards(rangelist, overlap);
143 			range = overlap; /* for debug output below */
146 		case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
148 			 * Expand the overlap area to cover the new range:
150 			overlap->rl_start = start;
151 			rl_collapse_backwards(rangelist, overlap);
152 			range = overlap; /* for debug output below */
166  * Generally, find the range (or an overlap to that range)
172 	struct rl_entry *range, *next_range, *overlap, *splitrange;
184 	while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
187 		case RL_MATCHINGOVERLAP: /* 1: overlap == range */
188 			TAILQ_REMOVE(rangelist, overlap, rl_link);
189 			FREE(overlap, M_TEMP);
192 		case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
193 			if (overlap->rl_start == start) {
194 				overlap->rl_start = end + 1;
198 			if (overlap->rl_end == end) {
199 				overlap->rl_end = start - 1;
208 			splitrange->rl_end = overlap->rl_end;
209 			overlap->rl_end = start - 1;
214 			TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
217 		case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
218 			/* Check before discarding overlap entry */
219 			next_range = TAILQ_NEXT(overlap, rl_link);
220 			TAILQ_REMOVE(rangelist, overlap, rl_link);
221 			FREE(overlap, M_TEMP);
228 		case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
229 			overlap->rl_end = start - 1;
230 			range = TAILQ_NEXT(overlap, rl_link);
236 		case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
237 			overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
261 		struct rl_entry **overlap) {
264 		*overlap = NULL;
268 	return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
284 			 struct rl_entry **overlap,
288 		*overlap = NULL;
296 	*overlap = range;
300 		 * OK, check for overlap
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)
323 			*overlap = range;
361 		panic("hfs: rl_scan_from: unhandled overlap condition?!");
429 int rl_scan(void *rangelist, off_t start, off_t end, void **overlap);
446 int rl_scan(__unused void *rangelist, __unused off_t start, __unused off_t end, __unused void **overlap)