Blame src/tsort.c

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
}