#include "git-compat-util.h"
#include "line-range.h"
#include "cache.h"
#include "tag.h"
#include "blob.h"
#include "tree.h"
#include "diff.h"
#include "commit.h"
#include "decorate.h"
#include "revision.h"
#include "xdiff-interface.h"
#include "strbuf.h"
#include "log-tree.h"
#include "graph.h"
#include "userdiff.h"
#include "line-log.h"
#include "argv-array.h"
static void range_set_grow(struct range_set *rs, size_t extra)
{
ALLOC_GROW(rs->ranges, rs->nr + extra, rs->alloc);
}
/* Either initialization would be fine */
#define RANGE_SET_INIT {0}
void range_set_init(struct range_set *rs, size_t prealloc)
{
rs->alloc = rs->nr = 0;
rs->ranges = NULL;
if (prealloc)
range_set_grow(rs, prealloc);
}
void range_set_release(struct range_set *rs)
{
FREE_AND_NULL(rs->ranges);
rs->alloc = rs->nr = 0;
}
/* dst must be uninitialized! */
static void range_set_copy(struct range_set *dst, struct range_set *src)
{
range_set_init(dst, src->nr);
COPY_ARRAY(dst->ranges, src->ranges, src->nr);
dst->nr = src->nr;
}
static void range_set_move(struct range_set *dst, struct range_set *src)
{
range_set_release(dst);
dst->ranges = src->ranges;
dst->nr = src->nr;
dst->alloc = src->alloc;
src->ranges = NULL;
src->alloc = src->nr = 0;
}
/* tack on a _new_ range _at the end_ */
void range_set_append_unsafe(struct range_set *rs, long a, long b)
{
assert(a <= b);
range_set_grow(rs, 1);
rs->ranges[rs->nr].start = a;
rs->ranges[rs->nr].end = b;
rs->nr++;
}
void range_set_append(struct range_set *rs, long a, long b)
{
assert(rs->nr == 0 || rs->ranges[rs->nr-1].end <= a);
range_set_append_unsafe(rs, a, b);
}
static int range_cmp(const void *_r, const void *_s)
{
const struct range *r = _r;
const struct range *s = _s;
/* this could be simply 'return r.start-s.start', but for the types */
if (r->start == s->start)
return 0;
if (r->start < s->start)
return -1;
return 1;
}
/*
* Check that the ranges are non-empty, sorted and non-overlapping
*/
static void range_set_check_invariants(struct range_set *rs)
{
unsigned int i;
if (!rs)
return;
if (rs->nr)
assert(rs->ranges[0].start < rs->ranges[0].end);
for (i = 1; i < rs->nr; i++) {
assert(rs->ranges[i-1].end < rs->ranges[i].start);
assert(rs->ranges[i].start < rs->ranges[i].end);
}
}
/*
* In-place pass of sorting and merging the ranges in the range set,
* to establish the invariants when we get the ranges from the user
*/
void sort_and_merge_range_set(struct range_set *rs)
{
unsigned int i;
unsigned int o = 0; /* output cursor */
QSORT(rs->ranges, rs->nr, range_cmp);
for (i = 0; i < rs->nr; i++) {
if (rs->ranges[i].start == rs->ranges[i].end)
continue;
if (o > 0 && rs->ranges[i].start <= rs->ranges[o-1].end) {
if (rs->ranges[o-1].end < rs->ranges[i].end)
rs->ranges[o-1].end = rs->ranges[i].end;
} else {
rs->ranges[o].start = rs->ranges[i].start;
rs->ranges[o].end = rs->ranges[i].end;
o++;
}
}
assert(o <= rs->nr);
rs->nr = o;
range_set_check_invariants(rs);
}
/*
* Union of range sets (i.e., sets of line numbers). Used to merge
* them when searches meet at a common ancestor.
*
* This is also where the ranges are consolidated into canonical form:
* overlapping and adjacent ranges are merged, and empty ranges are
* removed.
*/
static void
|