|
Packit Service |
20376f |
/*
|
|
Packit Service |
20376f |
* Copyright (C) the libgit2 contributors. All rights reserved.
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* This file is part of libgit2, distributed under the GNU GPL v2 with
|
|
Packit Service |
20376f |
* a Linking Exception. For full terms see the included COPYING file.
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#include "common.h"
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/**
|
|
Packit Service |
20376f |
* An array-of-pointers implementation of Python's Timsort
|
|
Packit Service |
20376f |
* Based on code by Christopher Swenson under the MIT license
|
|
Packit Service |
20376f |
*
|
|
Packit Service |
20376f |
* Copyright (c) 2010 Christopher Swenson
|
|
Packit Service |
20376f |
* Copyright (c) 2011 Vicent Marti
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#ifndef MAX
|
|
Packit Service |
20376f |
# define MAX(x,y) (((x) > (y) ? (x) : (y)))
|
|
Packit Service |
20376f |
#endif
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#ifndef MIN
|
|
Packit Service |
20376f |
# define MIN(x,y) (((x) < (y) ? (x) : (y)))
|
|
Packit Service |
20376f |
#endif
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int binsearch(
|
|
Packit Service |
20376f |
void **dst, const void *x, size_t size, git__sort_r_cmp cmp, void *payload)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
int l, c, r;
|
|
Packit Service |
20376f |
void *lx, *cx;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
assert(size > 0);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
l = 0;
|
|
Packit Service |
20376f |
r = (int)size - 1;
|
|
Packit Service |
20376f |
c = r >> 1;
|
|
Packit Service |
20376f |
lx = dst[l];
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* check for beginning conditions */
|
|
Packit Service |
20376f |
if (cmp(x, lx, payload) < 0)
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
else if (cmp(x, lx, payload) == 0) {
|
|
Packit Service |
20376f |
int i = 1;
|
|
Packit Service |
20376f |
while (cmp(x, dst[i], payload) == 0)
|
|
Packit Service |
20376f |
i++;
|
|
Packit Service |
20376f |
return i;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* guaranteed not to be >= rx */
|
|
Packit Service |
20376f |
cx = dst[c];
|
|
Packit Service |
20376f |
while (1) {
|
|
Packit Service |
20376f |
const int val = cmp(x, cx, payload);
|
|
Packit Service |
20376f |
if (val < 0) {
|
|
Packit Service |
20376f |
if (c - l <= 1) return c;
|
|
Packit Service |
20376f |
r = c;
|
|
Packit Service |
20376f |
} else if (val > 0) {
|
|
Packit Service |
20376f |
if (r - c <= 1) return c + 1;
|
|
Packit Service |
20376f |
l = c;
|
|
Packit Service |
20376f |
lx = cx;
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
do {
|
|
Packit Service |
20376f |
cx = dst[++c];
|
|
Packit Service |
20376f |
} while (cmp(x, cx, payload) == 0);
|
|
Packit Service |
20376f |
return c;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
c = l + ((r - l) >> 1);
|
|
Packit Service |
20376f |
cx = dst[c];
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
|
|
Packit Service |
20376f |
static void bisort(
|
|
Packit Service |
20376f |
void **dst, size_t start, size_t size, git__sort_r_cmp cmp, void *payload)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
size_t i;
|
|
Packit Service |
20376f |
void *x;
|
|
Packit Service |
20376f |
int location;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (i = start; i < size; i++) {
|
|
Packit Service |
20376f |
int j;
|
|
Packit Service |
20376f |
/* If this entry is already correct, just move along */
|
|
Packit Service |
20376f |
if (cmp(dst[i - 1], dst[i], payload) <= 0)
|
|
Packit Service |
20376f |
continue;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* Else we need to find the right place, shift everything over, and squeeze in */
|
|
Packit Service |
20376f |
x = dst[i];
|
|
Packit Service |
20376f |
location = binsearch(dst, x, i, cmp, payload);
|
|
Packit Service |
20376f |
for (j = (int)i - 1; j >= location; j--) {
|
|
Packit Service |
20376f |
dst[j + 1] = dst[j];
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
dst[location] = x;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* timsort implementation, based on timsort.txt */
|
|
Packit Service |
20376f |
struct tsort_run {
|
|
Packit Service |
20376f |
ssize_t start;
|
|
Packit Service |
20376f |
ssize_t length;
|
|
Packit Service |
20376f |
};
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
struct tsort_store {
|
|
Packit Service |
20376f |
size_t alloc;
|
|
Packit Service |
20376f |
git__sort_r_cmp cmp;
|
|
Packit Service |
20376f |
void *payload;
|
|
Packit Service |
20376f |
void **storage;
|
|
Packit Service |
20376f |
};
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static void reverse_elements(void **dst, ssize_t start, ssize_t end)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
while (start < end) {
|
|
Packit Service |
20376f |
void *tmp = dst[start];
|
|
Packit Service |
20376f |
dst[start] = dst[end];
|
|
Packit Service |
20376f |
dst[end] = tmp;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
start++;
|
|
Packit Service |
20376f |
end--;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static ssize_t count_run(
|
|
Packit Service |
20376f |
void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
ssize_t curr = start + 2;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (size - start == 1)
|
|
Packit Service |
20376f |
return 1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (start >= size - 2) {
|
|
Packit Service |
20376f |
if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) {
|
|
Packit Service |
20376f |
void *tmp = dst[size - 1];
|
|
Packit Service |
20376f |
dst[size - 1] = dst[size - 2];
|
|
Packit Service |
20376f |
dst[size - 2] = tmp;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 2;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) {
|
|
Packit Service |
20376f |
while (curr < size - 1 &&
|
|
Packit Service |
20376f |
store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0)
|
|
Packit Service |
20376f |
curr++;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return curr - start;
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
while (curr < size - 1 &&
|
|
Packit Service |
20376f |
store->cmp(dst[curr - 1], dst[curr], store->payload) > 0)
|
|
Packit Service |
20376f |
curr++;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* reverse in-place */
|
|
Packit Service |
20376f |
reverse_elements(dst, start, curr - 1);
|
|
Packit Service |
20376f |
return curr - start;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static size_t compute_minrun(size_t n)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
int r = 0;
|
|
Packit Service |
20376f |
while (n >= 64) {
|
|
Packit Service |
20376f |
r |= n & 1;
|
|
Packit Service |
20376f |
n >>= 1;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
return n + r;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int check_invariant(struct tsort_run *stack, ssize_t stack_curr)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
if (stack_curr < 2)
|
|
Packit Service |
20376f |
return 1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
else if (stack_curr == 2) {
|
|
Packit Service |
20376f |
const ssize_t A = stack[stack_curr - 2].length;
|
|
Packit Service |
20376f |
const ssize_t B = stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
return (A > B);
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
const ssize_t A = stack[stack_curr - 3].length;
|
|
Packit Service |
20376f |
const ssize_t B = stack[stack_curr - 2].length;
|
|
Packit Service |
20376f |
const ssize_t C = stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
return !((A <= B + C) || (B <= C));
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int resize(struct tsort_store *store, size_t new_size)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
if (store->alloc < new_size) {
|
|
Packit Service |
20376f |
void **tempstore;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
tempstore = git__reallocarray(store->storage, new_size, sizeof(void *));
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/**
|
|
Packit Service |
20376f |
* Do not propagate on OOM; this will abort the sort and
|
|
Packit Service |
20376f |
* leave the array unsorted, but no error code will be
|
|
Packit Service |
20376f |
* raised
|
|
Packit Service |
20376f |
*/
|
|
Packit Service |
20376f |
if (tempstore == NULL)
|
|
Packit Service |
20376f |
return -1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
store->storage = tempstore;
|
|
Packit Service |
20376f |
store->alloc = new_size;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return 0;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
const ssize_t A = stack[stack_curr - 2].length;
|
|
Packit Service |
20376f |
const ssize_t B = stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
const ssize_t curr = stack[stack_curr - 2].start;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void **storage;
|
|
Packit Service |
20376f |
ssize_t i, j, k;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (resize(store, MIN(A, B)) < 0)
|
|
Packit Service |
20376f |
return;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
storage = store->storage;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* left merge */
|
|
Packit Service |
20376f |
if (A < B) {
|
|
Packit Service |
20376f |
memcpy(storage, &dst[curr], A * sizeof(void *));
|
|
Packit Service |
20376f |
i = 0;
|
|
Packit Service |
20376f |
j = curr + A;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (k = curr; k < curr + A + B; k++) {
|
|
Packit Service |
20376f |
if ((i < A) && (j < curr + A + B)) {
|
|
Packit Service |
20376f |
if (store->cmp(storage[i], dst[j], store->payload) <= 0)
|
|
Packit Service |
20376f |
dst[k] = storage[i++];
|
|
Packit Service |
20376f |
else
|
|
Packit Service |
20376f |
dst[k] = dst[j++];
|
|
Packit Service |
20376f |
} else if (i < A) {
|
|
Packit Service |
20376f |
dst[k] = storage[i++];
|
|
Packit Service |
20376f |
} else
|
|
Packit Service |
20376f |
dst[k] = dst[j++];
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
memcpy(storage, &dst[curr + A], B * sizeof(void *));
|
|
Packit Service |
20376f |
i = B - 1;
|
|
Packit Service |
20376f |
j = curr + A - 1;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
for (k = curr + A + B - 1; k >= curr; k--) {
|
|
Packit Service |
20376f |
if ((i >= 0) && (j >= curr)) {
|
|
Packit Service |
20376f |
if (store->cmp(dst[j], storage[i], store->payload) > 0)
|
|
Packit Service |
20376f |
dst[k] = dst[j--];
|
|
Packit Service |
20376f |
else
|
|
Packit Service |
20376f |
dst[k] = storage[i--];
|
|
Packit Service |
20376f |
} else if (i >= 0)
|
|
Packit Service |
20376f |
dst[k] = storage[i--];
|
|
Packit Service |
20376f |
else
|
|
Packit Service |
20376f |
dst[k] = dst[j--];
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
ssize_t A, B, C;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
while (1) {
|
|
Packit Service |
20376f |
/* if the stack only has one thing on it, we are done with the collapse */
|
|
Packit Service |
20376f |
if (stack_curr <= 1)
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* if this is the last merge, just do it */
|
|
Packit Service |
20376f |
if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
|
|
Packit Service |
20376f |
merge(dst, stack, stack_curr, store);
|
|
Packit Service |
20376f |
stack[0].length += stack[1].length;
|
|
Packit Service |
20376f |
stack_curr--;
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* check if the invariant is off for a stack of 2 elements */
|
|
Packit Service |
20376f |
else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
|
|
Packit Service |
20376f |
merge(dst, stack, stack_curr, store);
|
|
Packit Service |
20376f |
stack[0].length += stack[1].length;
|
|
Packit Service |
20376f |
stack_curr--;
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
else if (stack_curr == 2)
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
A = stack[stack_curr - 3].length;
|
|
Packit Service |
20376f |
B = stack[stack_curr - 2].length;
|
|
Packit Service |
20376f |
C = stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* check first invariant */
|
|
Packit Service |
20376f |
if (A <= B + C) {
|
|
Packit Service |
20376f |
if (A < C) {
|
|
Packit Service |
20376f |
merge(dst, stack, stack_curr - 1, store);
|
|
Packit Service |
20376f |
stack[stack_curr - 3].length += stack[stack_curr - 2].length;
|
|
Packit Service |
20376f |
stack[stack_curr - 2] = stack[stack_curr - 1];
|
|
Packit Service |
20376f |
stack_curr--;
|
|
Packit Service |
20376f |
} else {
|
|
Packit Service |
20376f |
merge(dst, stack, stack_curr, store);
|
|
Packit Service |
20376f |
stack[stack_curr - 2].length += stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
stack_curr--;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
} else if (B <= C) {
|
|
Packit Service |
20376f |
merge(dst, stack, stack_curr, store);
|
|
Packit Service |
20376f |
stack[stack_curr - 2].length += stack[stack_curr - 1].length;
|
|
Packit Service |
20376f |
stack_curr--;
|
|
Packit Service |
20376f |
} else
|
|
Packit Service |
20376f |
break;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
return stack_curr;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
#define PUSH_NEXT() do {\
|
|
Packit Service |
20376f |
len = count_run(dst, curr, size, store);\
|
|
Packit Service |
20376f |
run = minrun;\
|
|
Packit Service |
20376f |
if (run < minrun) run = minrun;\
|
|
Packit Service |
20376f |
if (run > (ssize_t)size - curr) run = size - curr;\
|
|
Packit Service |
20376f |
if (run > len) {\
|
|
Packit Service |
20376f |
bisort(&dst[curr], len, run, cmp, payload);\
|
|
Packit Service |
20376f |
len = run;\
|
|
Packit Service |
20376f |
}\
|
|
Packit Service |
20376f |
run_stack[stack_curr].start = curr;\
|
|
Packit Service |
20376f |
run_stack[stack_curr++].length = len;\
|
|
Packit Service |
20376f |
curr += len;\
|
|
Packit Service |
20376f |
if (curr == (ssize_t)size) {\
|
|
Packit Service |
20376f |
/* finish up */ \
|
|
Packit Service |
20376f |
while (stack_curr > 1) { \
|
|
Packit Service |
20376f |
merge(dst, run_stack, stack_curr, store); \
|
|
Packit Service |
20376f |
run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
|
|
Packit Service |
20376f |
stack_curr--; \
|
|
Packit Service |
20376f |
} \
|
|
Packit Service |
20376f |
if (store->storage != NULL) {\
|
|
Packit Service |
20376f |
git__free(store->storage);\
|
|
Packit Service |
20376f |
store->storage = NULL;\
|
|
Packit Service |
20376f |
}\
|
|
Packit Service |
20376f |
return;\
|
|
Packit Service |
20376f |
}\
|
|
Packit Service |
20376f |
}\
|
|
Packit Service |
20376f |
while (0)
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git__tsort_r(
|
|
Packit Service |
20376f |
void **dst, size_t size, git__sort_r_cmp cmp, void *payload)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
struct tsort_store _store, *store = &_store;
|
|
Packit Service |
20376f |
struct tsort_run run_stack[128];
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
ssize_t stack_curr = 0;
|
|
Packit Service |
20376f |
ssize_t len, run;
|
|
Packit Service |
20376f |
ssize_t curr = 0;
|
|
Packit Service |
20376f |
ssize_t minrun;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
if (size < 64) {
|
|
Packit Service |
20376f |
bisort(dst, 1, size, cmp, payload);
|
|
Packit Service |
20376f |
return;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* compute the minimum run length */
|
|
Packit Service |
20376f |
minrun = (ssize_t)compute_minrun(size);
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
/* temporary storage for merges */
|
|
Packit Service |
20376f |
store->alloc = 0;
|
|
Packit Service |
20376f |
store->storage = NULL;
|
|
Packit Service |
20376f |
store->cmp = cmp;
|
|
Packit Service |
20376f |
store->payload = payload;
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
PUSH_NEXT();
|
|
Packit Service |
20376f |
PUSH_NEXT();
|
|
Packit Service |
20376f |
PUSH_NEXT();
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
while (1) {
|
|
Packit Service |
20376f |
if (!check_invariant(run_stack, stack_curr)) {
|
|
Packit Service |
20376f |
stack_curr = collapse(dst, run_stack, stack_curr, store, size);
|
|
Packit Service |
20376f |
continue;
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
PUSH_NEXT();
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
static int tsort_r_cmp(const void *a, const void *b, void *payload)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
return ((git__tsort_cmp)payload)(a, b);
|
|
Packit Service |
20376f |
}
|
|
Packit Service |
20376f |
|
|
Packit Service |
20376f |
void git__tsort(void **dst, size_t size, git__tsort_cmp cmp)
|
|
Packit Service |
20376f |
{
|
|
Packit Service |
20376f |
git__tsort_r(dst, size, tsort_r_cmp, cmp);
|
|
Packit Service |
20376f |
}
|