source/idar/genmergesort.h

/* 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)(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)(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)(type *list1, type *list2, int (*cmp)(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)(register type *list1,register type *list2, \
int (*cmp)(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(type *list, int len, int (*cmp)(type *, type *));\
\
storageclass type *name(type *list,int len, int (*cmp)(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); \
}
Revision:	1.1
Committed:	Fri Mar 28 15:37:05 2003 UTC (21 years, 9 months ago) by pajs
Content type:	text/plain
Branch:	MAIN
CVS Tags:	IDAR_1_2, IDAR_1_1, IDAR_1_0, HEAD
Log Message:	idar is a "top like" client which displays data collected by ihost. It currently displays cpu, load, pageing, mem, swap, net and disk io. There is infastructure to display much more in the future, and to be able to sort on more than just CPU. genmergesort is macro written by mtr to sort a linked list. Inital version 1.0 This compiles and works. It requires libxml2 (but it may work against libxml, but this has not been checked). It also requires ukcprog. This will not currently compile on linux (as it lacks strlcpy). Usage is idar <-d number_lines_to_display> machine_name port <"fqdn1;fqdn2;fqdn3">
#	Content
1	/* genmergesort.h - generate code to do a mergesort */
2
3	/* Copyright 1991 Mark Russell, University of Kent at Canterbury.
4	*
5	* You can do what you like with this source code as long as
6	* you don't try to make money out of it and you include an
7	* unaltered copy of this message (including the copyright).
8	*/
9
10	/* @(#)genmergesort.h 1.6 26/4/92 (UKC) */
11
12	/* GENERIC_MERGE_SORT generates the code necessary to mergesort
13	* an arbitrary linked list. The arguments are:
14	*
15	* storageclass:
16	* should be static or extern. Detrmines the storage class
17	* of the function generated.
18	*
19	* name: the name of the function to be generated
20	*
21	* type:
22	* the type of the elements of the list
23	* for a structure xxst, the type will be: struct xxst
24	*
25	* next:
26	* the name of the field linking the list
27	*
28	* As an example, consider a structure struct xxst, with a link field
29	* "struct xxst *xx_next". Then the following macro:
30	*
31	* GENERIC_MERGE_SORT(static, sortxx, struct xxst, xx_next)
32	*
33	* would generate a static function sortxx:
34	*
35	* static struct xxst *sortxx(list, len, cmp)
36	* struct xxst *list;
37	* int len, (*cmp)();
38	*
39	* where list is the head of the list to be sorted, len is the length
40	* of this list, and cmp is a comparison function, called in the style
41	*
42	* (*cmp)(xx1, xx2)
43	*
44	* This should return -1, 0 or 1 according as the first argument should
45	* be considered less than, equal to, or greater than the second.
46	*
47	* sortxx() returns a pointer to the head of the sorted list.
48	*
49	* The macro also generates the static functions split_name() and
50	* merge_name, where "name" is what you supplied to the macro.
51	* These functions are for the use of the sort routine only.
52	*/
53
54	#define GENERIC_MERGE_SORT(storageclass,name,type,next) \
55	\
56	/* Mergesort a linked list of structures of type type.
57	* List is a pointer to the head of the list, len is the number of
58	* elements in the list, and cmp is the comparison function
59	* as described above. Return a pointer to the head of the sorted list.
60	*
61	* Uses the standard recursive mergesort algorithm (see e.g. Kruse)
62	*/ \
63	\
64	static type CAT(name,_split)(type list, int len);\
65	\
66	/* split list, which has len elements at element len/2. Return
67	* a pointer to the second half of the list.
68	*/ \
69	static type CAT(name,_split)(type list,int len) \
70	{ \
71	type *prev; \
72	\
73	prev = NULL; /* to satisfy gcc */ \
74	for (; len > 0; --len) { \
75	prev = list; \
76	list = list->next; \
77	} \
78	prev->next = NULL; \
79	return(list); \
80	} \
81	\
82	static type CAT(name,_merge)(type list1, type list2, int (cmp)(type , type ));\
83	\
84	/* Merge the two lists list1 and list2, keeping the resulting
85	* list in order with respect to comparison function cmp (see
86	* above for specification of cmp.
87	* Return a pointer to the merged list.
88	*/ \
89	static type CAT(name,_merge)(register type list1,register type *list2, \
90	int (cmp)(type , type *)) \
91	{ \
92	register type list, head; \
93	\
94	if ((*cmp)(list1, list2) < 0) { \
95	list = list1; \
96	list1 = list1->next; \
97	} \
98	else { \
99	list = list2; \
100	list2 = list2->next; \
101	} \
102	head = list; \
103	while (list1 != NULL && list2 != NULL) { \
104	if ((*cmp)(list1, list2) < 0) { \
105	list->next = list1; \
106	list1 = list1->next; \
107	} \
108	else { \
109	list->next = list2; \
110	list2 = list2->next; \
111	} \
112	list = list->next; \
113	} \
114	list->next = (list1 != NULL) ? list1 : list2; \
115	return(head); \
116	} \
117	\
118	storageclass type name(type list, int len, int (cmp)(type , type *));\
119	\
120	storageclass type name(type list,int len, int (cmp)(type , type *)) \
121	{ \
122	type *list2; \
123	\
124	if (len > 1) { \
125	list2 = CAT(name,_split)(list,len/2); \
126	list = name(list,len/2,cmp); \
127	list2 = name(list2,(len+1)/2,cmp); \
128	return(CAT(name,_merge)(list,list2,cmp)); \
129	} \
130	else \
131	return(list); \
132	}