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