[libgit2.git] / src / tsort.c

/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include "common.h"

/**
 * An array-of-pointers implementation of Python's Timsort
 * Based on code by Christopher Swenson under the MIT license
 *
 * Copyright (c) 2010 Christopher Swenson
 * Copyright (c) 2011 Vicent Marti
 */

#ifndef MAX
#	define MAX(x,y) (((x) > (y) ? (x) : (y)))
#endif

#ifndef MIN
#	define MIN(x,y) (((x) < (y) ? (x) : (y)))
#endif

static int binsearch(
	void **dst, const void *x, size_t size, git__sort_r_cmp cmp, void *payload)
{
	int l, c, r;
	void *lx, *cx;

	assert(size > 0);

	l = 0;
	r = (int)size - 1;
	c = r >> 1;
	lx = dst[l];

	/* check for beginning conditions */
	if (cmp(x, lx, payload) < 0)
		return 0;

	else if (cmp(x, lx, payload) == 0) {
		int i = 1;
		while (cmp(x, dst[i], payload) == 0)
			i++;
		return i;
	}

	/* guaranteed not to be >= rx */
	cx = dst[c];
	while (1) {
		const int val = cmp(x, cx, payload);
		if (val < 0) {
			if (c - l <= 1) return c;
			r = c;
		} else if (val > 0) {
			if (r - c <= 1) return c + 1;
			l = c;
			lx = cx;
		} else {
			do {
				cx = dst[++c];
			} while (cmp(x, cx, payload) == 0);
			return c;
		}
		c = l + ((r - l) >> 1);
		cx = dst[c];
	}
}

/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
static void bisort(
	void **dst, size_t start, size_t size, git__sort_r_cmp cmp, void *payload)
{
	size_t i;
	void *x;
	int location;

	for (i = start; i < size; i++) {
		int j;
		/* If this entry is already correct, just move along */
		if (cmp(dst[i - 1], dst[i], payload) <= 0)
			continue;

		/* Else we need to find the right place, shift everything over, and squeeze in */
		x = dst[i];
		location = binsearch(dst, x, i, cmp, payload);
		for (j = (int)i - 1; j >= location; j--) {
			dst[j + 1] = dst[j];
		}
		dst[location] = x;
	}
}


/* timsort implementation, based on timsort.txt */
struct tsort_run {
	ssize_t start;
	ssize_t length;
};

struct tsort_store {
	size_t alloc;
	git__sort_r_cmp cmp;
	void *payload;
	void **storage;
};

static void reverse_elements(void **dst, ssize_t start, ssize_t end)
{
	while (start < end) {
		void *tmp = dst[start];
		dst[start] = dst[end];
		dst[end] = tmp;

		start++;
		end--;
	}
}

static ssize_t count_run(
	void **dst, ssize_t start, ssize_t size, struct tsort_store *store)
{
	ssize_t curr = start + 2;

	if (size - start == 1)
		return 1;

	if (start >= size - 2) {
		if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) {
			void *tmp = dst[size - 1];
			dst[size - 1] = dst[size - 2];
			dst[size - 2] = tmp;
		}

		return 2;
	}

	if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) {
		while (curr < size - 1 &&
				store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0)
			curr++;

		return curr - start;
	} else {
		while (curr < size - 1 &&
				store->cmp(dst[curr - 1], dst[curr], store->payload) > 0)
			curr++;

		/* reverse in-place */
		reverse_elements(dst, start, curr - 1);
		return curr - start;
	}
}

static size_t compute_minrun(size_t n)
{
	int r = 0;
	while (n >= 64) {
		r |= n & 1;
		n >>= 1;
	}
	return n + r;
}

static int check_invariant(struct tsort_run *stack, ssize_t stack_curr)
{
	if (stack_curr < 2)
		return 1;

	else if (stack_curr == 2) {
		const ssize_t A = stack[stack_curr - 2].length;
		const ssize_t B = stack[stack_curr - 1].length;
		return (A > B);
	} else {
		const ssize_t A = stack[stack_curr - 3].length;
		const ssize_t B = stack[stack_curr - 2].length;
		const ssize_t C = stack[stack_curr - 1].length;
		return !((A <= B + C) || (B <= C));
	}
}

static int resize(struct tsort_store *store, size_t new_size)
{
	if (store->alloc < new_size) {
		void **tempstore = git__realloc(store->storage, new_size * sizeof(void *));

		/**
		 * Do not propagate on OOM; this will abort the sort and
		 * leave the array unsorted, but no error code will be
		 * raised
		 */
		if (tempstore == NULL)
			return -1;

		store->storage = tempstore;
		store->alloc = new_size;
	}

	return 0;
}

static void merge(void **dst, const struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store)
{
	const ssize_t A = stack[stack_curr - 2].length;
	const ssize_t B = stack[stack_curr - 1].length;
	const ssize_t curr = stack[stack_curr - 2].start;

	void **storage;
	ssize_t i, j, k;

	if (resize(store, MIN(A, B)) < 0)
		return;

	storage = store->storage;

	/* left merge */
	if (A < B) {
		memcpy(storage, &dst[curr], A * sizeof(void *));
		i = 0;
		j = curr + A;

		for (k = curr; k < curr + A + B; k++) {
			if ((i < A) && (j < curr + A + B)) {
				if (store->cmp(storage[i], dst[j], store->payload) <= 0)
					dst[k] = storage[i++];
				else
					dst[k] = dst[j++];
			} else if (i < A) {
				dst[k] = storage[i++];
			} else
				dst[k] = dst[j++];
		}
	} else {
		memcpy(storage, &dst[curr + A], B * sizeof(void *));
		i = B - 1;
		j = curr + A - 1;

		for (k = curr + A + B - 1; k >= curr; k--) {
			if ((i >= 0) && (j >= curr)) {
				if (store->cmp(dst[j], storage[i], store->payload) > 0)
					dst[k] = dst[j--];
				else
					dst[k] = storage[i--];
			} else if (i >= 0)
				dst[k] = storage[i--];
			else
				dst[k] = dst[j--];
		}
	}
}

static ssize_t collapse(void **dst, struct tsort_run *stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size)
{
	ssize_t A, B, C;

	while (1) {
		/* if the stack only has one thing on it, we are done with the collapse */
		if (stack_curr <= 1)
			break;

		/* if this is the last merge, just do it */
		if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
			merge(dst, stack, stack_curr, store);
			stack[0].length += stack[1].length;
			stack_curr--;
			break;
		}

		/* check if the invariant is off for a stack of 2 elements */
		else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
			merge(dst, stack, stack_curr, store);
			stack[0].length += stack[1].length;
			stack_curr--;
			break;
		}
		else if (stack_curr == 2)
			break;

		A = stack[stack_curr - 3].length;
		B = stack[stack_curr - 2].length;
		C = stack[stack_curr - 1].length;

		/* check first invariant */
		if (A <= B + C) {
			if (A < C) {
				merge(dst, stack, stack_curr - 1, store);
				stack[stack_curr - 3].length += stack[stack_curr - 2].length;
				stack[stack_curr - 2] = stack[stack_curr - 1];
				stack_curr--;
			} else {
				merge(dst, stack, stack_curr, store);
				stack[stack_curr - 2].length += stack[stack_curr - 1].length;
				stack_curr--;
			}
		} else if (B <= C) {
			merge(dst, stack, stack_curr, store);
			stack[stack_curr - 2].length += stack[stack_curr - 1].length;
			stack_curr--;
		} else
			break;
	}

	return stack_curr;
}

#define PUSH_NEXT() do {\
	len = count_run(dst, curr, size, store);\
	run = minrun;\
	if (run < minrun) run = minrun;\
	if (run > (ssize_t)size - curr) run = size - curr;\
	if (run > len) {\
		bisort(&dst[curr], len, run, cmp, payload);\
		len = run;\
	}\
	run_stack[stack_curr].start = curr;\
	run_stack[stack_curr++].length = len;\
	curr += len;\
	if (curr == (ssize_t)size) {\
		/* finish up */ \
		while (stack_curr > 1) { \
			merge(dst, run_stack, stack_curr, store); \
			run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
			stack_curr--; \
		} \
		if (store->storage != NULL) {\
			git__free(store->storage);\
			store->storage = NULL;\
		}\
		return;\
	}\
}\
while (0)

void git__tsort_r(
	void **dst, size_t size, git__sort_r_cmp cmp, void *payload)
{
	struct tsort_store _store, *store = &_store;
	struct tsort_run run_stack[128];

	ssize_t stack_curr = 0;
	ssize_t len, run;
	ssize_t curr = 0;
	ssize_t minrun;

	if (size < 64) {
		bisort(dst, 1, size, cmp, payload);
		return;
	}

	/* compute the minimum run length */
	minrun = (ssize_t)compute_minrun(size);

	/* temporary storage for merges */
	store->alloc = 0;
	store->storage = NULL;
	store->cmp = cmp;
	store->payload = payload;

	PUSH_NEXT();
	PUSH_NEXT();
	PUSH_NEXT();

	while (1) {
		if (!check_invariant(run_stack, stack_curr)) {
			stack_curr = collapse(dst, run_stack, stack_curr, store, size);
			continue;
		}

		PUSH_NEXT();
	}
}

static int tsort_r_cmp(const void *a, const void *b, void *payload)
{
	return ((git__tsort_cmp)payload)(a, b);
}

void git__tsort(void **dst, size_t size, git__tsort_cmp cmp)
{
	git__tsort_r(dst, size, tsort_r_cmp, cmp);
}
Commit	Line	Data
bb742ede	1	/*
359fc2d2	2	* Copyright (C) the libgit2 contributors. All rights reserved.
bb742ede VM	3	*
	4	* This file is part of libgit2, distributed under the GNU GPL v2 with
	5	* a Linking Exception. For full terms see the included COPYING file.
	6	*/
b6817692 MS	7
b6817692 MS	8	#include "common.h"
417a581d	9
de18f276 VM	10	/**
	11	* An array-of-pointers implementation of Python's Timsort
	12	* Based on code by Christopher Swenson under the MIT license
	13	*
	14	* Copyright (c) 2010 Christopher Swenson
	15	* Copyright (c) 2011 Vicent Marti
	16	*/
	17
	18	#ifndef MAX
	19	# define MAX(x,y) (((x) > (y) ? (x) : (y)))
	20	#endif
	21
	22	#ifndef MIN
	23	# define MIN(x,y) (((x) < (y) ? (x) : (y)))
	24	#endif
	25
851ad650	26	static int binsearch(
62beacd3	27	void *dst, const void x, size_t size, git__sort_r_cmp cmp, void *payload)
de18f276 VM	28	{
de18f276 VM	29	int l, c, r;
d4cb0ee8	30	void lx, cx;
de18f276	31
44ef8b1b RB	32	assert(size > 0);
44ef8b1b RB	33
de18f276	34	l = 0;
44ef8b1b	35	r = (int)size - 1;
de18f276 VM	36	c = r >> 1;
	37	lx = dst[l];
	38
	39	/* check for beginning conditions */
851ad650	40	if (cmp(x, lx, payload) < 0)
de18f276 VM	41	return 0;
de18f276 VM	42
851ad650	43	else if (cmp(x, lx, payload) == 0) {
de18f276	44	int i = 1;
851ad650	45	while (cmp(x, dst[i], payload) == 0)
de18f276 VM	46	i++;
	47	return i;
	48	}
	49
de18f276 VM	50	/* guaranteed not to be >= rx */
	51	cx = dst[c];
	52	while (1) {
851ad650	53	const int val = cmp(x, cx, payload);
de18f276 VM	54	if (val < 0) {
	55	if (c - l <= 1) return c;
	56	r = c;
de18f276 VM	57	} else if (val > 0) {
	58	if (r - c <= 1) return c + 1;
	59	l = c;
	60	lx = cx;
	61	} else {
	62	do {
	63	cx = dst[++c];
851ad650	64	} while (cmp(x, cx, payload) == 0);
de18f276 VM	65	return c;
	66	}
	67	c = l + ((r - l) >> 1);
	68	cx = dst[c];
	69	}
	70	}
	71
87d9869f	72	/* Binary insertion sort, but knowing that the first "start" entries are sorted. Used in timsort. */
851ad650	73	static void bisort(
62beacd3	74	void *dst, size_t start, size_t size, git__sort_r_cmp cmp, void payload)
de18f276 VM	75	{
de18f276 VM	76	size_t i;
bdcc4611	77	void *x;
bdcc4611	78	int location;
de18f276 VM	79
	80	for (i = start; i < size; i++) {
	81	int j;
	82	/* If this entry is already correct, just move along */
851ad650	83	if (cmp(dst[i - 1], dst[i], payload) <= 0)
de18f276 VM	84	continue;
	85
	86	/* Else we need to find the right place, shift everything over, and squeeze in */
bdcc4611	87	x = dst[i];
851ad650	88	location = binsearch(dst, x, i, cmp, payload);
44ef8b1b	89	for (j = (int)i - 1; j >= location; j--) {
de18f276 VM	90	dst[j + 1] = dst[j];
	91	}
	92	dst[location] = x;
	93	}
	94	}
	95
	96
	97	/* timsort implementation, based on timsort.txt */
	98	struct tsort_run {
	99	ssize_t start;
	100	ssize_t length;
	101	};
	102
	103	struct tsort_store {
	104	size_t alloc;
62beacd3	105	git__sort_r_cmp cmp;
851ad650	106	void *payload;
de18f276 VM	107	void **storage;
	108	};
	109
44ef8b1b	110	static void reverse_elements(void **dst, ssize_t start, ssize_t end)
de18f276 VM	111	{
	112	while (start < end) {
	113	void *tmp = dst[start];
	114	dst[start] = dst[end];
	115	dst[end] = tmp;
	116
	117	start++;
	118	end--;
	119	}
	120	}
	121
851ad650 RB	122	static ssize_t count_run(
851ad650 RB	123	void *dst, ssize_t start, ssize_t size, struct tsort_store store)
de18f276 VM	124	{
	125	ssize_t curr = start + 2;
	126
	127	if (size - start == 1)
	128	return 1;
	129
	130	if (start >= size - 2) {
851ad650	131	if (store->cmp(dst[size - 2], dst[size - 1], store->payload) > 0) {
de18f276 VM	132	void *tmp = dst[size - 1];
	133	dst[size - 1] = dst[size - 2];
	134	dst[size - 2] = tmp;
	135	}
	136
	137	return 2;
	138	}
	139
851ad650 RB	140	if (store->cmp(dst[start], dst[start + 1], store->payload) <= 0) {
	141	while (curr < size - 1 &&
	142	store->cmp(dst[curr - 1], dst[curr], store->payload) <= 0)
de18f276 VM	143	curr++;
	144
	145	return curr - start;
	146	} else {
851ad650 RB	147	while (curr < size - 1 &&
851ad650 RB	148	store->cmp(dst[curr - 1], dst[curr], store->payload) > 0)
de18f276 VM	149	curr++;
	150
	151	/* reverse in-place */
	152	reverse_elements(dst, start, curr - 1);
	153	return curr - start;
	154	}
	155	}
	156
44ef8b1b	157	static size_t compute_minrun(size_t n)
de18f276 VM	158	{
	159	int r = 0;
	160	while (n >= 64) {
	161	r \|= n & 1;
	162	n >>= 1;
	163	}
	164	return n + r;
	165	}
	166
44ef8b1b	167	static int check_invariant(struct tsort_run *stack, ssize_t stack_curr)
de18f276 VM	168	{
	169	if (stack_curr < 2)
	170	return 1;
	171
	172	else if (stack_curr == 2) {
44ef8b1b RB	173	const ssize_t A = stack[stack_curr - 2].length;
44ef8b1b RB	174	const ssize_t B = stack[stack_curr - 1].length;
de18f276 VM	175	return (A > B);
de18f276 VM	176	} else {
44ef8b1b RB	177	const ssize_t A = stack[stack_curr - 3].length;
	178	const ssize_t B = stack[stack_curr - 2].length;
	179	const ssize_t C = stack[stack_curr - 1].length;
de18f276 VM	180	return !((A <= B + C) \|\| (B <= C));
	181	}
	182	}
	183
	184	static int resize(struct tsort_store *store, size_t new_size)
	185	{
	186	if (store->alloc < new_size) {
3286c408	187	void *tempstore = git__realloc(store->storage, new_size sizeof(void *));
de18f276 VM	188
	189	/**
	190	* Do not propagate on OOM; this will abort the sort and
	191	* leave the array unsorted, but no error code will be
	192	* raised
	193	*/
	194	if (tempstore == NULL)
	195	return -1;
	196
	197	store->storage = tempstore;
	198	store->alloc = new_size;
	199	}
	200
	201	return 0;
	202	}
	203
44ef8b1b	204	static void merge(void *dst, const struct tsort_run stack, ssize_t stack_curr, struct tsort_store *store)
de18f276 VM	205	{
	206	const ssize_t A = stack[stack_curr - 2].length;
	207	const ssize_t B = stack[stack_curr - 1].length;
	208	const ssize_t curr = stack[stack_curr - 2].start;
	209
	210	void **storage;
	211	ssize_t i, j, k;
	212
	213	if (resize(store, MIN(A, B)) < 0)
	214	return;
	215
87d9869f	216	storage = store->storage;
de18f276 VM	217
	218	/* left merge */
	219	if (A < B) {
	220	memcpy(storage, &dst[curr], A * sizeof(void *));
	221	i = 0;
	222	j = curr + A;
	223
	224	for (k = curr; k < curr + A + B; k++) {
	225	if ((i < A) && (j < curr + A + B)) {
851ad650	226	if (store->cmp(storage[i], dst[j], store->payload) <= 0)
de18f276 VM	227	dst[k] = storage[i++];
	228	else
	229	dst[k] = dst[j++];
	230	} else if (i < A) {
	231	dst[k] = storage[i++];
	232	} else
	233	dst[k] = dst[j++];
	234	}
	235	} else {
	236	memcpy(storage, &dst[curr + A], B * sizeof(void *));
	237	i = B - 1;
	238	j = curr + A - 1;
	239
	240	for (k = curr + A + B - 1; k >= curr; k--) {
	241	if ((i >= 0) && (j >= curr)) {
851ad650	242	if (store->cmp(dst[j], storage[i], store->payload) > 0)
de18f276 VM	243	dst[k] = dst[j--];
	244	else
	245	dst[k] = storage[i--];
	246	} else if (i >= 0)
	247	dst[k] = storage[i--];
	248	else
	249	dst[k] = dst[j--];
	250	}
	251	}
	252	}
	253
	254	static ssize_t collapse(void *dst, struct tsort_run stack, ssize_t stack_curr, struct tsort_store *store, ssize_t size)
	255	{
	256	ssize_t A, B, C;
	257
	258	while (1) {
	259	/* if the stack only has one thing on it, we are done with the collapse */
	260	if (stack_curr <= 1)
	261	break;
	262
	263	/* if this is the last merge, just do it */
	264	if ((stack_curr == 2) && (stack[0].length + stack[1].length == size)) {
	265	merge(dst, stack, stack_curr, store);
	266	stack[0].length += stack[1].length;
	267	stack_curr--;
	268	break;
	269	}
	270
	271	/* check if the invariant is off for a stack of 2 elements */
	272	else if ((stack_curr == 2) && (stack[0].length <= stack[1].length)) {
	273	merge(dst, stack, stack_curr, store);
	274	stack[0].length += stack[1].length;
	275	stack_curr--;
	276	break;
	277	}
	278	else if (stack_curr == 2)
	279	break;
	280
	281	A = stack[stack_curr - 3].length;
	282	B = stack[stack_curr - 2].length;
	283	C = stack[stack_curr - 1].length;
	284
	285	/* check first invariant */
	286	if (A <= B + C) {
	287	if (A < C) {
	288	merge(dst, stack, stack_curr - 1, store);
	289	stack[stack_curr - 3].length += stack[stack_curr - 2].length;
	290	stack[stack_curr - 2] = stack[stack_curr - 1];
	291	stack_curr--;
	292	} else {
	293	merge(dst, stack, stack_curr, store);
	294	stack[stack_curr - 2].length += stack[stack_curr - 1].length;
	295	stack_curr--;
	296	}
	297	} else if (B <= C) {
	298	merge(dst, stack, stack_curr, store);
	299	stack[stack_curr - 2].length += stack[stack_curr - 1].length;
	300	stack_curr--;
	301	} else
	302	break;
	303	}
	304
	305	return stack_curr;
	306	}
307
308	#define PUSH_NEXT() do {\
309	len = count_run(dst, curr, size, store);\
310	run = minrun;\
311	if (run < minrun) run = minrun;\
312	if (run > (ssize_t)size - curr) run = size - curr;\
313	if (run > len) {\
851ad650	314	bisort(&dst[curr], len, run, cmp, payload);\
de18f276 VM	315	len = run;\
de18f276 VM	316	}\
bdcc4611	317	run_stack[stack_curr].start = curr;\
bdcc4611	318	run_stack[stack_curr++].length = len;\
de18f276 VM	319	curr += len;\
	320	if (curr == (ssize_t)size) {\
	321	/* finish up */ \
	322	while (stack_curr > 1) { \
	323	merge(dst, run_stack, stack_curr, store); \
	324	run_stack[stack_curr - 2].length += run_stack[stack_curr - 1].length; \
	325	stack_curr--; \
	326	} \
	327	if (store->storage != NULL) {\
3286c408	328	git__free(store->storage);\
de18f276 VM	329	store->storage = NULL;\
	330	}\
	331	return;\
	332	}\
	333	}\
	334	while (0)
	335
851ad650	336	void git__tsort_r(
62beacd3	337	void *dst, size_t size, git__sort_r_cmp cmp, void payload)
de18f276 VM	338	{
	339	struct tsort_store _store, *store = &_store;
	340	struct tsort_run run_stack[128];
	341
	342	ssize_t stack_curr = 0;
	343	ssize_t len, run;
	344	ssize_t curr = 0;
	345	ssize_t minrun;
	346
	347	if (size < 64) {
851ad650	348	bisort(dst, 1, size, cmp, payload);
de18f276 VM	349	return;
	350	}
	351
	352	/* compute the minimum run length */
44ef8b1b	353	minrun = (ssize_t)compute_minrun(size);
de18f276 VM	354
	355	/* temporary storage for merges */
	356	store->alloc = 0;
	357	store->storage = NULL;
	358	store->cmp = cmp;
851ad650	359	store->payload = payload;
de18f276 VM	360
	361	PUSH_NEXT();
	362	PUSH_NEXT();
	363	PUSH_NEXT();
	364
	365	while (1) {
	366	if (!check_invariant(run_stack, stack_curr)) {
	367	stack_curr = collapse(dst, run_stack, stack_curr, store, size);
	368	continue;
	369	}
	370
	371	PUSH_NEXT();
	372	}
	373	}
851ad650 RB	374
	375	static int tsort_r_cmp(const void a, const void b, void *payload)
	376	{
	377	return ((git__tsort_cmp)payload)(a, b);
	378	}
	379
	380	void git__tsort(void **dst, size_t size, git__tsort_cmp cmp)
	381	{
	382	git__tsort_r(dst, size, tsort_r_cmp, cmp);
	383	}