1/* Copyright (c) 2000, 2010 Oracle and/or its affiliates. All rights reserved.
2
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
15
16
17/*
18things to define before including the file:
19
20#define LS_LIST_ITEM ListItem
21#define LS_COMPARE_FUNC_DECL compare_func var_name,
22#define LS_COMPARE_FUNC_CALL(list_el1, list_el2) (*var_name)(list_el1, list_el2)
23#define LS_NEXT(A) (A)->next
24#define LS_SET_NEXT(A,val) (A)->next= val
25#define LS_P_NEXT(A) &(A)->next
26#define LS_NAME plistsort
27#define LS_SCOPE static
28#define LS_STRUCT_NAME ls_struct_name
29*/
30
31typedef struct LS_STRUCT_NAME
32{
33 LS_LIST_ITEM *list1;
34 int list_len;
35 int return_point;
36} LS_STRUCT_NAME;
37
38LS_SCOPE LS_LIST_ITEM* LS_NAME(LS_COMPARE_FUNC_DECL LS_LIST_ITEM *list, int list_len)
39{
40 LS_LIST_ITEM *list_end;
41 LS_LIST_ITEM *sorted_list;
42
43 struct LS_STRUCT_NAME stack[63], *sp= stack;
44
45 if (list_len < 2)
46 return list;
47
48 sp->list_len= list_len;
49 sp->return_point= 2;
50
51recursion_point:
52
53 if (sp->list_len < 4)
54 {
55 LS_LIST_ITEM *e1, *e2;
56 sorted_list= list;
57 e1= LS_NEXT(sorted_list);
58 list_end= LS_NEXT(e1);
59 if (LS_COMPARE_FUNC_CALL(sorted_list, e1))
60 {
61 sorted_list= e1;
62 e1= list;
63 }
64 if (sp->list_len == 2)
65 {
66 LS_SET_NEXT(sorted_list, e1);
67 LS_SET_NEXT(e1, NULL);
68 goto exit_point;
69 }
70 e2= list_end;
71 list_end= LS_NEXT(e2);
72 if (LS_COMPARE_FUNC_CALL(e1, e2))
73 {
74 {
75 LS_LIST_ITEM *tmp_e= e1;
76 e1= e2;
77 e2= tmp_e;
78 }
79 if (LS_COMPARE_FUNC_CALL(sorted_list, e1))
80 {
81 LS_LIST_ITEM *tmp_e= sorted_list;
82 sorted_list= e1;
83 e1= tmp_e;
84 }
85 }
86
87 LS_SET_NEXT(sorted_list, e1);
88 LS_SET_NEXT(e1, e2);
89 LS_SET_NEXT(e2, NULL);
90 goto exit_point;
91 }
92
93 {
94 struct LS_STRUCT_NAME *sp0= sp++;
95 sp->list_len= sp0->list_len >> 1;
96 sp0->list_len-= sp->list_len;
97 sp->return_point= 0;
98 }
99 goto recursion_point;
100return_point0:
101 sp->list1= sorted_list;
102 {
103 struct LS_STRUCT_NAME *sp0= sp++;
104 list= list_end;
105 sp->list_len= sp0->list_len;
106 sp->return_point= 1;
107 }
108 goto recursion_point;
109return_point1:
110 {
111 LS_LIST_ITEM **hook= &sorted_list;
112 LS_LIST_ITEM *list1= sp->list1;
113 LS_LIST_ITEM *list2= sorted_list;
114
115 if (LS_COMPARE_FUNC_CALL(list1, list2))
116 {
117 LS_LIST_ITEM *tmp_e= list2;
118 list2= list1;
119 list1= tmp_e;
120 }
121 for (;;)
122 {
123 *hook= list1;
124 do
125 {
126 if (!(list1= *(hook= LS_P_NEXT(list1))))
127 {
128 *hook= list2;
129 goto exit_point;
130 }
131 } while (LS_COMPARE_FUNC_CALL(list2, list1));
132
133 *hook= list2;
134 do
135 {
136 if (!(list2= *(hook= LS_P_NEXT(list2))))
137 {
138 *hook= list1;
139 goto exit_point;
140 }
141 } while (LS_COMPARE_FUNC_CALL(list1, list2));
142 }
143 }
144
145exit_point:
146 switch ((sp--)->return_point)
147 {
148 case 0: goto return_point0;
149 case 1: goto return_point1;
150 default:;
151 }
152
153 return sorted_list;
154}
155
156
157#undef LS_LIST_ITEM
158#undef LS_NEXT
159#undef LS_SET_NEXT
160#undef LS_P_NEXT
161#undef LS_NAME
162#undef LS_STRUCT_NAME
163#undef LS_SCOPE
164#undef LS_COMPARE_FUNC_DECL
165#undef LS_COMPARE_FUNC_CALL
166
167