view release on metacpan or  search on metacpan

src/sparse-0.4.4/sort.c  view on Meta::CPAN

/*
 * sort_list: a stable sort for lists.
 *
 * Time complexity: O(n*log n)
 *   [assuming limited zero-element fragments]
 *
 * Space complexity: O(1).
 *
 * Stable: yes.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "lib.h"
#include "allocate.h"

#undef PARANOIA
#undef COVERAGE

#ifdef PARANOIA
#include <assert.h>
#else
#ifndef assert
#define assert(x)
#endif
#endif

#ifdef COVERAGE
static unsigned char been_there[256];
#define BEEN_THERE(_c)					\
  do {							\
	if (!been_there[_c]) {				\
		been_there[_c] = 1;			\
		printf ("Been there: %c\n", _c);	\
	}						\
  } while (0)
#else
#define BEEN_THERE(_c) do { } while (0)
#endif

// Sort one fragment.  LIST_NODE_NR (==29) is a bit too high for my
// taste for something this simple.  But, hey, it's O(1).
//
// I would use libc qsort for this, but its comparison function
// gets a pointer indirection extra.
static void array_sort(SCTX_ void **ptr, int nr, int (*cmp)(SCTX_ const void *, const void *))
{
	int i;
	for (i = 1; i < nr; i++) {
		void *p = ptr[i];
		if (cmp(sctx_ ptr[i-1],p) > 0) {
			int j = i;
			do {
				ptr[j] = ptr[j-1];
				if (!--j)
					break;
			} while (cmp(sctx_ ptr[j-1], p) > 0);
			ptr[j] = p;
		}
	}
}

#ifdef PARANOIA
static void verify_seq_sorted (struct ptr_list *l, int n,
			       int (*cmp)(const void *, const void *))
{
	int i = 0;
	const void *a;
	struct ptr_list *head = l;

	while (l->nr == 0) {
		l = l->next;
		if (--n == 0)
			return;
		assert (l != head);
	}

	a = l->list[0];
	while (n > 0) {
		const void *b;
		if (++i >= l->nr) {
			i = 0;
			l = l->next;
			n--;
			assert (l != head || n == 0);
			continue;
		}
		b = l->list[i];
		assert (cmp (a, b) <= 0);
		a = b;
	}
}
#endif


#define FLUSH_TO(b)						\
  do {								\
	int nr = (b)->nr;					\
	assert (nbuf >= nr);					\
	memcpy ((b)->list, buffer, nr * sizeof (void *));	\
	nbuf -= nr;						\