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