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 */ 334