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 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 } while (0) 36 37 /* ---------------------------------------------------------------------- */ 38 /* macros for singly-linked lists */ 39 40 /* traverse list. At the end, elt is set to NULL. */ 41 #define list_forall(elt, list) for (elt=list; elt!=NULL; elt=elt->next) 42 43 /* set elt to the first element of list satisfying boolean condition 44 c, or NULL if not found */ 45 #define list_find(elt, list, c) \ 46 MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END 47 48 /* like forall, except also set hook for elt. */ 49 #define list_forall2(elt, list, hook) \ 50 for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next) 51 52 /* same as list_find, except also set hook for elt. */ 53 #define list_find2(elt, list, c, hook) \ 54 MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END 55 56 /* same, except only use hook. */ 57 #define _list_forall_hook(list, hook) \ 58 for (hook=&list; *hook!=NULL; hook=&(*hook)->next) 59 60 /* same, except only use hook. Note: c may only refer to *hook, not elt. */ 61 #define _list_find_hook(list, c, hook) \ 62 MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END 63 64 /* insert element after hook */ 65 #define list_insert_athook(elt, hook) \ 66 MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END 67 68 /* insert element before hook */ 69 #define list_insert_beforehook(elt, hook) \ 70 MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END 71 72 /* unlink element after hook, let elt be unlinked element, or NULL. 73 hook remains. */ 74 #define list_unlink_athook(list, elt, hook) \ 75 MACRO_BEGIN \ 76 elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\ 77 MACRO_END 78 79 /* unlink the specific element, if it is in the list. Otherwise, set 80 elt to NULL */ 81 #define list_unlink(listtype, list, elt) \ 82 MACRO_BEGIN \ 83 listtype **_hook; \ 84 _list_find_hook(list, *_hook==elt, _hook); \ 85 list_unlink_athook(list, elt, _hook); \ 86 MACRO_END 87 88 /* prepend elt to list */ 89 #define list_prepend(list, elt) \ 90 MACRO_BEGIN elt->next = list; list = elt; MACRO_END 91 92 /* append elt to list. */ 93 #define list_append(listtype, list, elt) \ 94 MACRO_BEGIN \ 95 listtype **_hook; \ 96 _list_forall_hook(list, _hook) {} \ 97 list_insert_athook(elt, _hook); \ 98 MACRO_END 99 100 /* unlink the first element that satisfies the condition. */ 101 #define list_unlink_cond(listtype, list, elt, c) \ 102 MACRO_BEGIN \ 103 listtype **_hook; \ 104 list_find2(elt, list, c, _hook); \ 105 list_unlink_athook(list, elt, _hook); \ 106 MACRO_END 107 108 /* let elt be the nth element of the list, starting to count from 0. 109 Return NULL if out of bounds. */ 110 #define list_nth(elt, list, n) \ 111 MACRO_BEGIN \ 112 int _x; /* only evaluate n once */ \ 113 for (_x=(n), elt=list; _x && elt; _x--, elt=elt->next) {} \ 114 MACRO_END 115 116 /* let elt be the nth element of the list, starting to count from 0. 117 Return NULL if out of bounds. */ 118 #define list_nth_hook(elt, list, n, hook) \ 119 MACRO_BEGIN \ 120 int _x; /* only evaluate n once */ \ 121 for (_x=(n), elt=list, hook=&list; _x && elt; _x--, hook=&elt->next, elt=elt->next) {} \ 122 MACRO_END 123 124 /* set n to the length of the list */ 125 #define list_length(listtype, list, n) \ 126 MACRO_BEGIN \ 127 listtype *_elt; \ 128 n=0; \ 129 list_forall(_elt, list) \ 130 n++; \ 131 MACRO_END 132 133 /* set n to the index of the first element satisfying cond, or -1 if 134 none found. Also set elt to the element, or NULL if none found. */ 135 #define list_index(list, n, elt, c) \ 136 MACRO_BEGIN \ 137 n=0; \ 138 list_forall(elt, list) { \ 139 if (c) break; \ 140 n++; \ 141 } \ 142 if (!elt) \ 143 n=-1; \ 144 MACRO_END 145 146 /* set n to the number of elements in the list that satisfy condition c */ 147 #define list_count(list, n, elt, c) \ 148 MACRO_BEGIN \ 149 n=0; \ 150 list_forall(elt, list) { \ 151 if (c) n++; \ 152 } \ 153 MACRO_END 154 155 /* let elt be each element of the list, unlinked. At the end, set list=NULL. */ 156 #define list_forall_unlink(elt, list) \ 157 for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list) 158 159 /* reverse a list (efficient) */ 160 #define list_reverse(listtype, list) \ 161 MACRO_BEGIN \ 162 listtype *_list1=NULL, *elt; \ 163 list_forall_unlink(elt, list) \ 164 list_prepend(_list1, elt); \ 165 list = _list1; \ 166 MACRO_END 167 168 /* insert the element ELT just before the first element TMP of the 169 list for which COND holds. Here COND must be a condition of ELT and 170 TMP. Typical usage is to insert an element into an ordered list: 171 for instance, list_insert_ordered(listtype, list, elt, tmp, 172 elt->size <= tmp->size). Note: if we give a "less than or equal" 173 condition, the new element will be inserted just before a sequence 174 of equal elements. If we give a "less than" condition, the new 175 element will be inserted just after a list of equal elements. 176 Note: it is much more efficient to construct a list with 177 list_prepend and then order it with list_merge_sort, than to 178 construct it with list_insert_ordered. */ 179 #define list_insert_ordered(listtype, list, elt, tmp, cond) \ 180 MACRO_BEGIN \ 181 listtype **_hook; \ 182 _list_find_hook(list, (tmp=*_hook, (cond)), _hook); \ 183 list_insert_athook(elt, _hook); \ 184 MACRO_END 185 186 /* sort the given list, according to the comparison condition. 187 Typical usage is list_sort(listtype, list, a, b, a->size < 188 b->size). Note: if we give "less than or equal" condition, each 189 segment of equal elements will be reversed in order. If we give a 190 "less than" condition, each segment of equal elements will retain 191 the original order. The latter is slower but sometimes 192 prettier. Average running time: n*n/2. */ 193 #define list_sort(listtype, list, a, b, cond) \ 194 MACRO_BEGIN \ 195 listtype *_newlist=NULL; \ 196 list_forall_unlink(a, list) \ 197 list_insert_ordered(listtype, _newlist, a, b, cond); \ 198 list = _newlist; \ 199 MACRO_END 200 201 /* a much faster sort algorithm (merge sort, n log n worst case). It 202 is required that the list type has an additional, unused next1 203 component. Note there is no curious reversal of order of equal 204 elements as for list_sort. */ 205 206 #define list_mergesort(listtype, list, a, b, cond) \ 207 MACRO_BEGIN \ 208 listtype *_elt, **_hook1; \ 209 \ 210 for (_elt=list; _elt; _elt=_elt->next1) { \ 211 _elt->next1 = _elt->next; \ 212 _elt->next = NULL; \ 213 } \ 214 do { \ 215 _hook1 = &(list); \ 216 while ((a = *_hook1) != NULL && (b = a->next1) != NULL ) { \ 217 _elt = b->next1; \ 218 _list_merge_cond(listtype, a, b, cond, *_hook1); \ 219 _hook1 = &((*_hook1)->next1); \ 220 *_hook1 = _elt; \ 221 } \ 222 } while (_hook1 != &(list)); \ 223 MACRO_END 224 225 /* merge two sorted lists. Store result at &result */ 226 #define _list_merge_cond(listtype, a, b, cond, result) \ 227 MACRO_BEGIN \ 228 listtype **_hook; \ 229 _hook = &(result); \ 230 while (1) { \ 231 if (a==NULL) { \ 232 *_hook = b; \ 233 break; \ 234 } else if (b==NULL) { \ 235 *_hook = a; \ 236 break; \ 237 } else if (cond) { \ 238 *_hook = a; \ 239 _hook = &(a->next); \ 240 a = a->next; \ 241 } else { \ 242 *_hook = b; \ 243 _hook = &(b->next); \ 244 b = b->next; \ 245 } \ 246 } \ 247 MACRO_END 248 249 /* ---------------------------------------------------------------------- */ 250 /* macros for doubly-linked lists */ 251 252 #define dlist_append(head, end, elt) \ 253 MACRO_BEGIN \ 254 elt->prev = end; \ 255 elt->next = NULL; \ 256 if (end) { \ 257 end->next = elt; \ 258 } else { \ 259 head = elt; \ 260 } \ 261 end = elt; \ 262 MACRO_END 263 264 /* let elt be each element of the list, unlinked. At the end, set list=NULL. */ 265 #define dlist_forall_unlink(elt, head, end) \ 266 for (elt=head; elt ? (head=elt->next, elt->next=NULL, elt->prev=NULL), 1 : (end=NULL, 0); elt=head) 267 268 /* unlink the first element of the list */ 269 #define dlist_unlink_first(head, end, elt) \ 270 MACRO_BEGIN \ 271 elt = head; \ 272 if (head) { \ 273 head = head->next; \ 274 if (head) { \ 275 head->prev = NULL; \ 276 } else { \ 277 end = NULL; \ 278 } \ 279 elt->prev = NULL; \ 280 elt->next = NULL; \ 281 } \ 282 MACRO_END 283 284 #endif /* _PS_LISTS_H */ 285 286