Lines Matching defs:range
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);
66 * Initialize a range list head
77 * Add a range to the list
82 struct rl_entry *range;
95 * 1) overlap == range
96 * 2) overlap contains range
97 * 3) range contains overlap
98 * 4) overlap starts before range
99 * 5) overlap ends after range
106 * new range, 'prev' points to ITS predecessor, and 'overlap' points
109 MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
110 range->rl_start = start;
111 range->rl_end = end;
113 /* Link in the new range: */
115 CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
117 CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
121 preceding range entry)
123 rl_collapse_neighbors(rangelist, range);
126 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
127 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range */
128 range = overlap; /* for debug output below */
131 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
133 * Replace the overlap with the new, larger range:
138 range = overlap; /* for debug output below */
141 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
143 * Expand the overlap area to cover the new range:
147 range = overlap; /* for debug output below */
150 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
152 * Expand the overlap area to cover the new range:
156 range = overlap; /* for debug output below */
168 * Remove a range from a range list.
170 * Generally, find the range (or an overlap to that range)
176 struct rl_entry *range, *next_range, *overlap, *splitrange;
187 range = CIRCLEQ_FIRST(rangelist);
188 while ((ovcase = rl_scan_from(rangelist, start, end, &overlap, range))) {
191 case RL_MATCHINGOVERLAP: /* 1: overlap == range */
196 case RL_OVERLAPCONTAINSRANGE: /* 2: overlap contains range: split it */
208 * Make a new range consisting of the last part of the encompassing range
216 * Now link the new entry into the range list after the range from which it was split:
221 case RL_OVERLAPISCONTAINED: /* 3: range contains overlap */
224 if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
230 range = next_range;
235 case RL_OVERLAPSTARTSBEFORE: /* 4: overlap starts before range */
240 if (CIRCLEQ_NEXT(overlap, rl_link) == overlap) panic("rl_remove: circular range list?!");
242 range = CIRCLEQ_NEXT(overlap, rl_link);
247 case RL_OVERLAPENDSAFTER: /* 5: overlap ends after range */
262 * Scan a range list for an entry in a specified range (if any):
264 * NOTE: this returns only the FIRST overlapping range.
286 * find an overlapping range (if any).
288 * NOTE: this returns only the FIRST overlapping range.
296 struct rl_entry *range)
307 *overlap = range;
315 * 1) overlap == range (RL_MATCHINGOVERLAP)
316 * 2) overlap contains range (RL_OVERLAPCONTAINSRANGE)
317 * 3) range contains overlap (RL_OVERLAPISCONTAINED)
318 * 4) overlap starts before range (RL_OVERLAPSTARTSBEFORE)
319 * 5) overlap ends after range (RL_OVERLAPENDSAFTER)
321 if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) ||
322 ((end != RL_INFINITY) && (range->rl_start > end))) {
324 if ((end != RL_INFINITY) && (range->rl_start > end)) {
329 if (range == CIRCLEQ_LAST(rangelist)) {
333 if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_scan_from: circular range list?!");
335 *overlap = range = CIRCLEQ_NEXT(range, rl_link);
339 if ((range->rl_start == start) && (range->rl_end == end)) {
344 if ((range->rl_start <= start) &&
346 ((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) {
351 if ((start <= range->rl_start) &&
353 ((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
358 if ((range->rl_start < start) &&
359 ((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) {
364 if ((range->rl_start > start) &&
366 ((range->rl_end > end) || (range->rl_end == RL_INFINITY))) {
382 rl_collapse_forwards(struct rl_head *rangelist, struct rl_entry *range) {
386 if (range == CIRCLEQ_LAST(rangelist)) return;
389 if (CIRCLEQ_NEXT(range, rl_link) == range) panic("rl_collapse_forwards: circular range list?!");
391 next_range = CIRCLEQ_NEXT(range, rl_link);
392 if ((range->rl_end != RL_INFINITY) && (range->rl_end < next_range->rl_start - 1)) return;
394 /* Expand this range to include the next range: */
395 range->rl_end = next_range->rl_end;
397 /* Remove the now covered range from the list: */
410 rl_collapse_backwards(struct rl_head *rangelist, struct rl_entry *range) {
414 if (range == CIRCLEQ_FIRST(rangelist)) return;
417 if (CIRCLEQ_PREV(range, rl_link) == range) panic("rl_collapse_backwards: circular range list?!");
419 prev_range = CIRCLEQ_PREV(range, rl_link);
420 if (prev_range->rl_end < range->rl_start - 1) {
427 /* Expand this range to include the previous range: */
428 range->rl_start = prev_range->rl_start;
430 /* Remove the now covered range from the list: */
439 rl_collapse_neighbors(struct rl_head *rangelist, struct rl_entry *range)
441 rl_collapse_forwards(rangelist, range);
442 rl_collapse_backwards(rangelist, range);