/* genmergesort.h - generate code to do a mergesort */

/*  Copyright 1991 Mark Russell, University of Kent at Canterbury.
 *
 *  You can do what you like with this source code as long as
 *  you don't try to make money out of it and you include an
 *  unaltered copy of this message (including the copyright).
 */

/* @(#)genmergesort.h	1.6 26/4/92 (UKC) */

/*  GENERIC_MERGE_SORT generates the code necessary to mergesort
 *  an arbitrary linked list. The arguments are:
 *
 *	storageclass:
 *		should be static or extern. Detrmines the storage class
 *		of the function generated.
 *
 *	name:	the name of the function to be generated
 *
 *	type:	
 *		the type of the elements of the list
 *		for a structure xxst, the type will be: struct xxst
 *
 *	next:
 *		the name of the field linking the list
 *
 *  As an example, consider a structure struct xxst, with a link field
 *  "struct xxst *xx_next".  Then the following macro:
 *
 *	GENERIC_MERGE_SORT(static, sortxx, struct xxst, xx_next)
 *
 *  would generate a static function sortxx:
 *
 *	static struct xxst *sortxx(list, len, cmp)
 *	struct xxst *list;
 *	int len, (*cmp)();
 *
 *  where list is the head of the list to be sorted, len is the length
 *  of this list, and cmp is a comparison function, called in the style
 *
 *	(*cmp)(xx1, xx2)
 *
 *  This should return -1, 0 or 1 according as the first argument should
 *  be considered less than, equal to, or greater than the second.
 *
 *  sortxx() returns a pointer to the head of the sorted list.
 *
 *  The macro also generates the static functions split_name() and
 *  merge_name, where "name" is what you supplied to the macro.
 *  These functions are for the use of the sort routine only.
 */		

#define GENERIC_MERGE_SORT(storageclass,name,type,next) \
\
/*  Mergesort a linked list of structures of type type.
 *  List is a pointer to the head of the list, len is the number of
 *  elements in the list, and cmp is the comparison function
 *  as described above. Return a pointer to the head of the sorted list.
 *
 *  Uses the standard recursive mergesort algorithm (see e.g. Kruse)
 */ \
\
static type *CAT(name,_split) PROTO((type *list, int len));\
\
/*  split list, which has len elements at element len/2. Return
 *  a pointer to the second half of the list.
 */ \
static type *CAT(name,_split)(list,len) \
type *list; \
int len; \
{ \
	type *prev; \
	 \
	prev = NULL;	/* to satisfy gcc */ \
	for (; len > 0; --len) { \
		prev = list; \
		list = list->next; \
	} \
	prev->next = NULL; \
	return(list); \
} \
\
static type *CAT(name,_merge) PROTO((type *list1, type *list2, int (*cmp)PROTO((type *, type *))));\
\
/*  Merge the two lists list1 and list2, keeping the resulting
 *  list in order with respect to comparison function cmp (see
 *  above for specification of cmp.
 *  Return a pointer to the merged list.
 */ \
static type *CAT(name,_merge)(list1,list2,cmp) \
register type *list1, *list2; \
int (*cmp)PROTO((type *, type *)); \
{ \
	register type *list, *head; \
	 \
	if ((*cmp)(list1, list2) < 0) { \
		list = list1; \
		list1 = list1->next; \
	} \
	else { \
		list = list2; \
		list2 = list2->next; \
	} \
	head = list; \
	while (list1 != NULL && list2 != NULL) { \
		if ((*cmp)(list1, list2) < 0) { \
			list->next = list1; \
			list1 = list1->next; \
		} \
		else { \
			list->next = list2; \
			list2 = list2->next; \
		} \
		list = list->next; \
	} \
	list->next = (list1 != NULL) ? list1 : list2; \
	return(head); \
} \
\
storageclass type *name PROTO((type *list, int len, int (*cmp)PROTO((type *, type *))));\
\
storageclass type *name(list,len,cmp) \
type *list; \
int len, (*cmp)PROTO((type *, type *)); \
{ \
	type *list2; \
	 \
	if (len > 1) { \
		list2 = CAT(name,_split)(list,len/2); \
		list = name(list,len/2,cmp); \
		list2 = name(list2,(len+1)/2,cmp); \
		return(CAT(name,_merge)(list,list2,cmp)); \
	} \
	else \
		return(list); \
}