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