1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
|
/* Copyright (C) 2001-2007 Peter Selinger.
* This file is part of Potrace. It is free software and it is covered
* by the GNU General Public License. See the file COPYING for details. */
/* $Id: lists.h 147 2007-04-09 00:44:09Z selinger $ */
#ifndef _PS_LISTS_H
#define _PS_LISTS_H
/* here we define some general list macros. Because they are macros,
* they should work on any datatype with a "->next" component. Some of
* them use a "hook". If elt and list are of type t* then hook is of
* type t**. A hook stands for an insertion point in the list, i.e.,
* either before the first element, or between two elements, or after
* the last element. If an operation "sets the hook" for an element,
* then the hook is set to just before the element. One can insert
* something at a hook. One can also unlink at a hook: this means,
* unlink the element just after the hook. By "to unlink", we mean the
* element is removed from the list, but not deleted. Thus, it and its
* components still need to be freed. */
/* Note: these macros are somewhat experimental. Only the ones that
* are actually *used* have been tested. So be careful to test any
* that you use. Looking at the output of the preprocessor, "gcc -E"
* (possibly piped though "indent"), might help too. Also: these
* macros define some internal (local) variables that start with
* "_". */
/* we enclose macro definitions whose body consists of more than one
* statement in MACRO_BEGIN and MACRO_END, rather than '{' and '}'. The
* reason is that we want to be able to use the macro in a context
* such as "if (...) macro(...); else ...". If we didn't use this obscure
* trick, we'd have to omit the ";" in such cases. */
#define MACRO_BEGIN do {
#define MACRO_END } while( 0 )
/* ---------------------------------------------------------------------- */
/* macros for singly-linked lists */
/* traverse list. At the end, elt is set to NULL. */
#define list_forall( elt, list ) for( elt = list; elt!=NULL; elt = elt->next )
/* set elt to the first element of list satisfying boolean condition
* c, or NULL if not found */
#define list_find( elt, list, c ) \
MACRO_BEGIN list_forall( elt, list ) if( c ) \
break;MACRO_END
/* like forall, except also set hook for elt. */
#define list_forall2( elt, list, hook ) \
for( elt = list, hook = &list; elt!=NULL; hook = &elt->next, elt = elt->next )
/* same as list_find, except also set hook for elt. */
#define list_find2( elt, list, c, hook ) \
MACRO_BEGIN list_forall2( elt, list, hook ) if( c ) \
break;MACRO_END
/* same, except only use hook. */
#define _list_forall_hook( list, hook ) \
for( hook = &list; *hook!=NULL; hook = &(*hook)->next )
/* same, except only use hook. Note: c may only refer to *hook, not elt. */
#define _list_find_hook( list, c, hook ) \
MACRO_BEGIN _list_forall_hook( list, hook ) if( c ) \
break;MACRO_END
/* insert element after hook */
#define list_insert_athook( elt, hook ) \
MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
/* insert element before hook */
#define list_insert_beforehook( elt, hook ) \
MACRO_BEGIN elt->next = *hook; *hook = elt; hook = &elt->next; MACRO_END
/* unlink element after hook, let elt be unlinked element, or NULL.
* hook remains. */
#define list_unlink_athook( list, elt, hook ) \
MACRO_BEGIN \
elt = hook ? *hook : NULL; if( elt ) { *hook = elt->next; elt->next = NULL; } \
MACRO_END
/* unlink the specific element, if it is in the list. Otherwise, set
* elt to NULL */
#define list_unlink( listtype, list, elt ) \
MACRO_BEGIN \
listtype * *_hook; \
_list_find_hook( list, *_hook==elt, _hook ); \
list_unlink_athook( list, elt, _hook ); \
MACRO_END
/* prepend elt to list */
#define list_prepend( list, elt ) \
MACRO_BEGIN elt->next = list; list = elt; MACRO_END
/* append elt to list. */
#define list_append( listtype, list, elt ) \
MACRO_BEGIN \
listtype * *_hook; \
_list_forall_hook( list, _hook ) {} \
list_insert_athook( elt, _hook ); \
MACRO_END
/* unlink the first element that satisfies the condition. */
#define list_unlink_cond( listtype, list, elt, c ) \
MACRO_BEGIN \
listtype * *_hook; \
list_find2( elt, list, c, _hook ); \
list_unlink_athook( list, elt, _hook ); \
MACRO_END
/* let elt be the nth element of the list, starting to count from 0.
* Return NULL if out of bounds. */
#define list_nth( elt, list, n ) \
MACRO_BEGIN \
int _x; /* only evaluate n once */ \
for( _x = (n), elt = list; _x && elt; _x--, elt = elt->next ) {} \
MACRO_END
/* let elt be the nth element of the list, starting to count from 0.
* Return NULL if out of bounds. */
#define list_nth_hook( elt, list, n, hook ) \
MACRO_BEGIN \
int _x; /* only evaluate n once */ \
for( _x = (n), elt = list, hook = &list; _x && elt; _x--, hook = &elt->next, elt =\
elt->next ) {} \
MACRO_END
/* set n to the length of the list */
#define list_length( listtype, list, n ) \
MACRO_BEGIN \
listtype * _elt; \
n = 0; \
list_forall( _elt, list ) \
n++; \
MACRO_END
/* set n to the index of the first element satisfying cond, or -1 if
* none found. Also set elt to the element, or NULL if none found. */
#define list_index( list, n, elt, c ) \
MACRO_BEGIN \
n = 0; \
list_forall( elt, list ) { \
if( c ) \
break;\
n++; \
} \
if( !elt ) \
n = -1;\
MACRO_END
/* set n to the number of elements in the list that satisfy condition c */
#define list_count( list, n, elt, c ) \
MACRO_BEGIN \
n = 0; \
list_forall( elt, list ) { \
if( c ) \
n++;\
} \
MACRO_END
/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
#define list_forall_unlink( elt, list ) \
for( elt = list; elt ? (list = elt->next, elt->next = NULL), 1 : 0; elt = list )
/* reverse a list (efficient) */
#define list_reverse( listtype, list ) \
MACRO_BEGIN \
listtype * _list1 = NULL, *elt; \
list_forall_unlink( elt, list ) \
list_prepend( _list1, elt ); \
list = _list1; \
MACRO_END
/* insert the element ELT just before the first element TMP of the
* list for which COND holds. Here COND must be a condition of ELT and
* TMP. Typical usage is to insert an element into an ordered list:
* for instance, list_insert_ordered(listtype, list, elt, tmp,
* elt->size <= tmp->size). Note: if we give a "less than or equal"
* condition, the new element will be inserted just before a sequence
* of equal elements. If we give a "less than" condition, the new
* element will be inserted just after a list of equal elements.
* Note: it is much more efficient to construct a list with
* list_prepend and then order it with list_merge_sort, than to
* construct it with list_insert_ordered. */
#define list_insert_ordered( listtype, list, elt, tmp, cond ) \
MACRO_BEGIN \
listtype * *_hook; \
_list_find_hook( list, ( tmp = *_hook, (cond) ), _hook ); \
list_insert_athook( elt, _hook ); \
MACRO_END
/* sort the given list, according to the comparison condition.
* Typical usage is list_sort(listtype, list, a, b, a->size <
* b->size). Note: if we give "less than or equal" condition, each
* segment of equal elements will be reversed in order. If we give a
* "less than" condition, each segment of equal elements will retain
* the original order. The latter is slower but sometimes
* prettier. Average running time: n*n/2. */
#define list_sort( listtype, list, a, b, cond ) \
MACRO_BEGIN \
listtype * _newlist = NULL; \
list_forall_unlink( a, list ) \
list_insert_ordered( listtype, _newlist, a, b, cond ); \
list = _newlist; \
MACRO_END
/* a much faster sort algorithm (merge sort, n log n worst case). It
* is required that the list type has an additional, unused next1
* component. Note there is no curious reversal of order of equal
* elements as for list_sort. */
#define list_mergesort( listtype, list, a, b, cond ) \
MACRO_BEGIN \
listtype * _elt, **_hook1; \
\
for( _elt = list; _elt; _elt = _elt->next1 ) { \
_elt->next1 = _elt->next; \
_elt->next = NULL; \
} \
do { \
_hook1 = &(list); \
while( (a = *_hook1) != NULL && (b = a->next1) != NULL ) { \
_elt = b->next1; \
_list_merge_cond( listtype, a, b, cond, *_hook1 ); \
_hook1 = &( (*_hook1)->next1 ); \
*_hook1 = _elt; \
} \
} while( _hook1 != &(list) ); \
MACRO_END
/* merge two sorted lists. Store result at &result */
#define _list_merge_cond( listtype, a, b, cond, result ) \
MACRO_BEGIN \
listtype * *_hook; \
_hook = &(result); \
while( 1 ) { \
if( a==NULL ) { \
*_hook = b; \
break; \
} else if( b==NULL ) { \
*_hook = a; \
break; \
} else if( cond ) { \
*_hook = a; \
_hook = &(a->next); \
a = a->next; \
} else { \
*_hook = b; \
_hook = &(b->next); \
b = b->next; \
} \
} \
MACRO_END
/* ---------------------------------------------------------------------- */
/* macros for doubly-linked lists */
#define dlist_append( head, end, elt ) \
MACRO_BEGIN \
elt->prev = end; \
elt->next = NULL; \
if( end ) { \
end->next = elt; \
} else { \
head = elt; \
} \
end = elt; \
MACRO_END
/* let elt be each element of the list, unlinked. At the end, set list=NULL. */
#define dlist_forall_unlink( elt, head, end ) \
for( elt = head;\
elt ? (head = elt->next, elt->next = NULL, elt->prev = NULL), 1 : (end = NULL, 0); \
elt = head )
/* unlink the first element of the list */
#define dlist_unlink_first( head, end, elt ) \
MACRO_BEGIN \
elt = head; \
if( head ) { \
head = head->next; \
if( head ) { \
head->prev = NULL; \
} else { \
end = NULL; \
} \
elt->prev = NULL; \
elt->next = NULL; \
} \
MACRO_END
#endif /* _PS_LISTS_H */
|
