Revision e293c563b00f9adfff44676d7406d40194aff228 authored by Junio C Hamano on 25 June 2014, 18:43:07 UTC, committed by Junio C Hamano on 25 June 2014, 18:43:07 UTC
We used to unconditionally disable the pager in the pager process we spawn to feed out output, but that prevented people who want to run "less" within "less" from doing so. * je/pager-do-not-recurse: pager: do allow spawning pager recursively
mergesort.c
#include "cache.h"
#include "mergesort.h"
struct mergesort_sublist {
void *ptr;
unsigned long len;
};
static void *get_nth_next(void *list, unsigned long n,
void *(*get_next_fn)(const void *))
{
while (n-- && list)
list = get_next_fn(list);
return list;
}
static void *pop_item(struct mergesort_sublist *l,
void *(*get_next_fn)(const void *))
{
void *p = l->ptr;
l->ptr = get_next_fn(l->ptr);
l->len = l->ptr ? (l->len - 1) : 0;
return p;
}
void *llist_mergesort(void *list,
void *(*get_next_fn)(const void *),
void (*set_next_fn)(void *, void *),
int (*compare_fn)(const void *, const void *))
{
unsigned long l;
if (!list)
return NULL;
for (l = 1; ; l *= 2) {
void *curr;
struct mergesort_sublist p, q;
p.ptr = list;
q.ptr = get_nth_next(p.ptr, l, get_next_fn);
if (!q.ptr)
break;
p.len = q.len = l;
if (compare_fn(p.ptr, q.ptr) > 0)
list = curr = pop_item(&q, get_next_fn);
else
list = curr = pop_item(&p, get_next_fn);
while (p.ptr) {
while (p.len || q.len) {
void *prev = curr;
if (!p.len)
curr = pop_item(&q, get_next_fn);
else if (!q.len)
curr = pop_item(&p, get_next_fn);
else if (compare_fn(p.ptr, q.ptr) > 0)
curr = pop_item(&q, get_next_fn);
else
curr = pop_item(&p, get_next_fn);
set_next_fn(prev, curr);
}
p.ptr = q.ptr;
p.len = l;
q.ptr = get_nth_next(p.ptr, l, get_next_fn);
q.len = q.ptr ? l : 0;
}
set_next_fn(curr, NULL);
}
return list;
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...