src/trace/potrace/lists.h

   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. */
   4
   5 /* $Id$ */
   6
   7 #ifndef _PS_LISTS_H
   8 #define _PS_LISTS_H
   9
  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. */
  21
  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    "_". */
  28
  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. */
  34
  35 #define MACRO_BEGIN do {
  36 #define MACRO_END   } 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) break; MACRO_END
  48
  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)
  52
  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
  56
  57 /* same, except only use hook. */
  58 #define _list_forall_hook(list, hook) \
  59   for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
  60
  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
  64
  65 /* insert element after hook */
  66 #define list_insert_athook(elt, hook) \
  67   MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
  68
  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
  72
  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
  79
  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
  88
  89 /* prepend elt to list */
  90 #define list_prepend(list, elt) \
  91   MACRO_BEGIN elt->next = list; list = elt; MACRO_END
  92
  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
 100
 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
 108
 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
 116
 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
 124
 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
 133
 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
 146
 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
 155
 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)
 159
 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
 168
 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
 186
 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
 201
 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. */
 206
 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
 225
 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
 249
 250 /* ---------------------------------------------------------------------- */
 251 /* macros for doubly-linked lists */
 252
 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
 264
 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)
 268
 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
 284
 285 #endif /* _PS_LISTS_H */
 286