#if HFS
#include <sys/param.h>
#include <mach/boolean.h>
#include <sys/time.h>
#include <sys/malloc.h>
#if !RANGELIST_TEST
#include <kern/debug.h>
#endif
#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
void
rl_init(struct rl_head *rangelist)
{
TAILQ_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("hfs: 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) {
TAILQ_INSERT_BEFORE(overlap, range, rl_link);
} else {
TAILQ_INSERT_TAIL(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;
#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:
TAILQ_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;
TAILQ_INSERT_AFTER(rangelist, overlap, splitrange, rl_link);
break;
case RL_OVERLAPISCONTAINED:
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:
overlap->rl_end = start - 1;
range = TAILQ_NEXT(overlap, rl_link);
if (range) {
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) {
return rl_scan_from(rangelist, start, end, overlap, TAILQ_FIRST(rangelist));
}
enum rl_overlaptype
rl_overlap(const struct rl_entry *range, off_t start, off_t end)
{
if (start > range->rl_end || range->rl_start > end) {
return RL_NOOVERLAP;
}
if (range->rl_start == start && range->rl_end == end) {
return RL_MATCHINGOVERLAP;
}
if (range->rl_start <= start && range->rl_end >= end) {
return RL_OVERLAPCONTAINSRANGE;
}
if (start <= range->rl_start && end >= range->rl_end) {
return RL_OVERLAPISCONTAINED;
}
if (range->rl_start < start && range->rl_end < end) {
return RL_OVERLAPSTARTSBEFORE;
}
return RL_OVERLAPENDSAFTER;
}
static enum rl_overlaptype
rl_scan_from(struct rl_head *rangelist __unused,
off_t start,
off_t end,
struct rl_entry **overlap,
struct rl_entry *range)
{
#ifdef RL_DIAGNOSTIC
rl_verify(rangelist);
#endif
while (range) {
enum rl_overlaptype ot = rl_overlap(range, start, end);
if (ot != RL_NOOVERLAP || range->rl_start > end) {
*overlap = range;
return ot;
}
range = TAILQ_NEXT(range, rl_link);
}
*overlap = NULL;
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;
range->rl_end = next_range->rl_end;
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;
};
range->rl_start = prev_range->rl_start;
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);
}
void rl_subtract(struct rl_entry *a, const struct rl_entry *b)
{
switch (rl_overlap(b, a->rl_start, a->rl_end)) {
case RL_MATCHINGOVERLAP:
case RL_OVERLAPCONTAINSRANGE:
a->rl_end = a->rl_start - 1;
break;
case RL_OVERLAPISCONTAINED:
if (b->rl_start - a->rl_start >= a->rl_end - b->rl_end) {
a->rl_end = b->rl_start - 1;
} else {
a->rl_start = b->rl_end + 1;
}
break;
case RL_OVERLAPSTARTSBEFORE:
a->rl_start = b->rl_end + 1;
break;
case RL_OVERLAPENDSAFTER:
a->rl_end = b->rl_start - 1;
break;
case RL_NOOVERLAP:
break;
}
}
#else
#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