/*

 * 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;

		tempstore = git__reallocarray(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);

}