1 | /* |
---|
2 | * $Id: lsort.h,v 1.6 2005/04/15 23:23:47 fabio Exp $ |
---|
3 | * |
---|
4 | */ |
---|
5 | /* |
---|
6 | * Generic linked-list sorting package |
---|
7 | * Richard Rudell, UC Berkeley, 4/1/87 |
---|
8 | * |
---|
9 | * Use: |
---|
10 | * #define TYPE the linked-list type (a struct or typedef) |
---|
11 | * #define SORT sorting routine (see below) |
---|
12 | * #include "lsort.h" |
---|
13 | * |
---|
14 | * Optional: |
---|
15 | * #define NEXT 'next' field name in the linked-list structure |
---|
16 | * #define DECL_SORT 'static' or undefined |
---|
17 | * #define DECL_SORT1 'static' or undefined |
---|
18 | * #define SORT1 optional sorting routine interface |
---|
19 | * #define FIELD select subfield of the structure for compare |
---|
20 | * #define DIRECT_COMPARE in-line expand the compare routine |
---|
21 | * |
---|
22 | * This defines up to two routines: |
---|
23 | * DECL_SORT TYPE * |
---|
24 | * SORT1(list, compare) |
---|
25 | * TYPE *list; |
---|
26 | * int (*compare)(TYPE *x, TYPE *y); |
---|
27 | * sort the linked list 'list' according to the compare function |
---|
28 | * 'compare' |
---|
29 | * |
---|
30 | * DECL_SORT1 TYPE * |
---|
31 | * SORT(list, compare, length) |
---|
32 | * TYPE *list; |
---|
33 | * int (*compare)(TYPE *x, TYPE *y); |
---|
34 | * int length; |
---|
35 | * sort the linked list 'list' according to the compare function |
---|
36 | * 'compare'. length is the length of the linked list. |
---|
37 | * |
---|
38 | * Both routines gracefully handle length == 0 (in which case, list == 0 |
---|
39 | * is also allowed). |
---|
40 | * |
---|
41 | * NEXT defines the name of the next field in the linked list. If not |
---|
42 | * given, 'next' is assumed. |
---|
43 | * |
---|
44 | * By default, both routines are declared 'static'. This can be changed |
---|
45 | * using '#define DECL_SORT' or '#define DECL_SORT1'. |
---|
46 | * |
---|
47 | * If FIELD is used, then a pointer to the particular field is passed |
---|
48 | * to the comparison function (rather than a TYPE *). In this case, |
---|
49 | * the compare function is called with: |
---|
50 | * |
---|
51 | * if ((*compare)(x->FIELD, y->FIELD)) { |
---|
52 | * |
---|
53 | * If DIRECT_COMPARE is used, then the 'FIELD' items are compared using |
---|
54 | * a simple '>' (useful for scalars to save subroutine overhead) |
---|
55 | */ |
---|
56 | |
---|
57 | #ifndef NEXT |
---|
58 | #define NEXT next |
---|
59 | #endif |
---|
60 | |
---|
61 | #ifndef DECL_SORT1 |
---|
62 | #define DECL_SORT1 static |
---|
63 | #endif |
---|
64 | |
---|
65 | #ifndef DECL_SORT |
---|
66 | #define DECL_SORT static |
---|
67 | #endif |
---|
68 | |
---|
69 | #ifdef FIELD |
---|
70 | #define COMPTYPE void * |
---|
71 | #else |
---|
72 | #define COMPTYPE TYPE |
---|
73 | #endif |
---|
74 | |
---|
75 | DECL_SORT TYPE *SORT(TYPE *list_in, |
---|
76 | int (*compare)(COMPTYPE, COMPTYPE), int cnt); |
---|
77 | |
---|
78 | |
---|
79 | #ifdef SORT1 |
---|
80 | |
---|
81 | DECL_SORT1 TYPE * |
---|
82 | SORT1(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE)) |
---|
83 | { |
---|
84 | register int cnt; |
---|
85 | register TYPE *p; |
---|
86 | |
---|
87 | /* Find the length of the list */ |
---|
88 | for(p = list_in, cnt = 0; p != 0; p = p->NEXT, cnt++) |
---|
89 | ; |
---|
90 | return SORT(list_in, compare, cnt); |
---|
91 | } |
---|
92 | |
---|
93 | #endif |
---|
94 | |
---|
95 | DECL_SORT TYPE * |
---|
96 | SORT(TYPE *list_in, int (*compare)(COMPTYPE, COMPTYPE), int cnt) |
---|
97 | { |
---|
98 | register TYPE *p, **plast, *list1, *list2; |
---|
99 | register int i; |
---|
100 | |
---|
101 | if (cnt > 1) { |
---|
102 | /* break the list in half */ |
---|
103 | for(p = list_in, i = cnt/2-1; i > 0; p = p->NEXT, i--) |
---|
104 | ; |
---|
105 | list1 = list_in; |
---|
106 | list2 = p->NEXT; |
---|
107 | p->NEXT = 0; |
---|
108 | |
---|
109 | /* Recursively sort the sub-lists (unless only 1 element) */ |
---|
110 | if ((i = cnt/2) > 1) { |
---|
111 | list1 = SORT(list1, compare, i); |
---|
112 | } |
---|
113 | if ((i = cnt - i) > 1) { |
---|
114 | list2 = SORT(list2, compare, i); |
---|
115 | } |
---|
116 | |
---|
117 | /* Merge the two sorted sub-lists */ |
---|
118 | plast = &list_in; |
---|
119 | for(;;) { |
---|
120 | #ifdef FIELD |
---|
121 | #ifdef DIRECT_COMPARE |
---|
122 | if (list1->FIELD < list2->FIELD) { |
---|
123 | #else |
---|
124 | if ((*compare)(list1->FIELD, list2->FIELD) <= 0) { |
---|
125 | #endif |
---|
126 | #else |
---|
127 | if ((*compare)(list1, list2) <= 0) { |
---|
128 | #endif |
---|
129 | *plast = list1; |
---|
130 | plast = &(list1->NEXT); |
---|
131 | if ((list1 = list1->NEXT) == 0) { |
---|
132 | *plast = list2; |
---|
133 | break; |
---|
134 | } |
---|
135 | } else { |
---|
136 | *plast = list2; |
---|
137 | plast = &(list2->NEXT); |
---|
138 | if ((list2 = list2->NEXT) == 0) { |
---|
139 | *plast = list1; |
---|
140 | break; |
---|
141 | } |
---|
142 | } |
---|
143 | } |
---|
144 | } |
---|
145 | |
---|
146 | return list_in; |
---|
147 | } |
---|
148 | |
---|
149 | #undef TYPE |
---|
150 | #undef SORT |
---|
151 | #undef SORT1 |
---|
152 | #undef DECL_SORT |
---|
153 | #undef DECL_SORT1 |
---|
154 | #undef FIELD |
---|
155 | #undef DIRECT_COMPARE |
---|
156 | #undef NEXT |
---|