#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
void
rl_init(struct rl_head *rangelist)
{
CIRCLEQ_INIT(rangelist);
}
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);
switch (ovcase) {
case RL_NOOVERLAP:
MALLOC(range, struct rl_entry *, sizeof(*range), M_TEMP, M_WAITOK);
range->rl_start = start;
range->rl_end = end;
if (overlap) {
CIRCLEQ_INSERT_AFTER(rangelist, overlap, range, rl_link);
} else {
CIRCLEQ_INSERT_HEAD(rangelist, range, rl_link);
}
rl_collapse_neighbors(rangelist, range);
break;
case RL_MATCHINGOVERLAP:
case RL_OVERLAPCONTAINSRANGE:
range = overlap;
break;
case RL_OVERLAPISCONTAINED:
overlap->rl_start = start;
overlap->rl_end = end;
rl_collapse_neighbors(rangelist, overlap);
range = overlap;
break;
case RL_OVERLAPSTARTSBEFORE:
overlap->rl_end = end;
rl_collapse_forwards(rangelist, overlap);
range = overlap;
break;
case RL_OVERLAPENDSAFTER:
overlap->rl_start = start;
rl_collapse_backwards(rangelist, overlap);
range = overlap;
break;
}
#ifdef RL_DIAGNOSTIC
rl_verify(rangelist);
#endif
}
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:
CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
FREE(overlap, M_TEMP);
break;
case RL_OVERLAPCONTAINSRANGE:
if (overlap->rl_start == start) {
overlap->rl_start = end + 1;
break;
};
if (overlap->rl_end == end) {
overlap->rl_end = start - 1;
break;
};
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;
CIRCLEQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
break;
case RL_OVERLAPISCONTAINED:
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);
CIRCLEQ_REMOVE(rangelist, overlap, rl_link);
FREE(overlap, M_TEMP);
if (moretotest) {
range = next_range;
continue;
};
break;
case RL_OVERLAPSTARTSBEFORE:
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:
overlap->rl_start = (end == RL_INFINITY ? RL_INFINITY : end + 1);
break;
}
break;
}
#ifdef RL_DIAGNOSTIC
rl_verify(rangelist);
#endif
}
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));
}
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) {
if (((range->rl_end != RL_INFINITY) && (start > range->rl_end)) ||
((end != RL_INFINITY) && (range->rl_start > end))) {
if ((end != RL_INFINITY) && (range->rl_start > end)) {
return RL_NOOVERLAP;
};
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)) {
return RL_MATCHINGOVERLAP;
}
if ((range->rl_start <= start) &&
(end != RL_INFINITY) &&
((range->rl_end >= end) || (range->rl_end == RL_INFINITY))) {
return RL_OVERLAPCONTAINSRANGE;
}
if ((start <= range->rl_start) &&
((end == RL_INFINITY) ||
((range->rl_end != RL_INFINITY) && (end >= range->rl_end)))) {
return RL_OVERLAPISCONTAINED;
}
if ((range->rl_start < start) &&
((range->rl_end >= start) || (range->rl_end == RL_INFINITY))) {
return RL_OVERLAPSTARTSBEFORE;
}
if ((range->rl_start > start) &&
(end != RL_INFINITY) &&
((range->rl_end > end) || (range->rl_end == RL_INFINITY))) {
return RL_OVERLAPENDSAFTER;
}
#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;
range->rl_end = next_range->rl_end;
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;
};
range->rl_start = prev_range->rl_start;
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);
}