src/tsort.c - third_party/libgit2 - Git at Google

 /*
  * 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);
 }
	/*
	* 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);
	}