[libgit2.git] / src / tsort.c


#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

typedef int (*cmp_ptr_t)(const void *, const void *);

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

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

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

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

	/* guaranteed not to be >= rx */
	cx = dst[c];
	while (1) {
		const int val = cmp(x, cx);
		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) == 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, cmp_ptr_t cmp)
{
	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]) <= 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);
		for (j = 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;
	cmp_ptr_t cmp;
	void **storage;
};

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

		start++;
		end--;
	}
}

static int 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]) > 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]) <= 0) {
		while (curr < size - 1 && store->cmp(dst[curr - 1], dst[curr]) <= 0)
			curr++;

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

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

static int 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, int stack_curr)
{
	if (stack_curr < 2)
		return 1;

	else if (stack_curr == 2) {
		const int A = stack[stack_curr - 2].length;
		const int B = stack[stack_curr - 1].length;
		return (A > B);
	} else {
		const int A = stack[stack_curr - 3].length;
		const int B = stack[stack_curr - 2].length;
		const int 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 = 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, int 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]) <= 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]) > 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);\
		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) {\
			free(store->storage);\
			store->storage = NULL;\
		}\
		return;\
	}\
}\
while (0)

void git__tsort(void **dst, size_t size, cmp_ptr_t cmp)
{
	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);
		return;
	}

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

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

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