lists.h
Go to the documentation of this file.
00001 /* Copyright (C) 2001-2007 Peter Selinger.
00002    This file is part of Potrace. It is free software and it is covered
00003    by the GNU General Public License. See the file COPYING for details. */
00004 
00005 /* $Id: lists.h 147 2007-04-09 00:44:09Z selinger $ */
00006 
00007 #ifndef _PS_LISTS_H
00008 #define _PS_LISTS_H
00009 
00010 /* here we define some general list macros. Because they are macros,
00011    they should work on any datatype with a "->next" component. Some of
00012    them use a "hook". If elt and list are of type t* then hook is of
00013    type t**. A hook stands for an insertion point in the list, i.e.,
00014    either before the first element, or between two elements, or after
00015    the last element. If an operation "sets the hook" for an element,
00016    then the hook is set to just before the element. One can insert
00017    something at a hook. One can also unlink at a hook: this means,
00018    unlink the element just after the hook. By "to unlink", we mean the
00019    element is removed from the list, but not deleted. Thus, it and its
00020    components still need to be freed. */
00021 
00022 /* Note: these macros are somewhat experimental. Only the ones that
00023    are actually *used* have been tested. So be careful to test any
00024    that you use. Looking at the output of the preprocessor, "gcc -E"
00025    (possibly piped though "indent"), might help too. Also: these
00026    macros define some internal (local) variables that start with
00027    "_". */
00028 
00029 /* we enclose macro definitions whose body consists of more than one
00030    statement in MACRO_BEGIN and MACRO_END, rather than '{' and '}'.  The
00031    reason is that we want to be able to use the macro in a context
00032    such as "if (...) macro(...); else ...". If we didn't use this obscure
00033    trick, we'd have to omit the ";" in such cases. */
00034 
00035 #define MACRO_BEGIN do {
00036 #define MACRO_END   } while (0)
00037 
00038 /* ---------------------------------------------------------------------- */
00039 /* macros for singly-linked lists */
00040 
00041 /* traverse list. At the end, elt is set to NULL. */
00042 #define list_forall(elt, list)   for (elt=list; elt!=NULL; elt=elt->next)
00043 
00044 /* set elt to the first element of list satisfying boolean condition
00045    c, or NULL if not found */
00046 #define list_find(elt, list, c) \
00047   MACRO_BEGIN list_forall(elt, list) if (c) break; MACRO_END
00048 
00049 /* like forall, except also set hook for elt. */
00050 #define list_forall2(elt, list, hook) \
00051   for (elt=list, hook=&list; elt!=NULL; hook=&elt->next, elt=elt->next)
00052 
00053 /* same as list_find, except also set hook for elt. */
00054 #define list_find2(elt, list, c, hook) \
00055   MACRO_BEGIN list_forall2(elt, list, hook) if (c) break; MACRO_END
00056 
00057 /* same, except only use hook. */
00058 #define _list_forall_hook(list, hook) \
00059   for (hook=&list; *hook!=NULL; hook=&(*hook)->next)
00060 
00061 /* same, except only use hook. Note: c may only refer to *hook, not elt. */
00062 #define _list_find_hook(list, c, hook) \
00063   MACRO_BEGIN _list_forall_hook(list, hook) if (c) break; MACRO_END
00064 
00065 /* insert element after hook */
00066 #define list_insert_athook(elt, hook) \
00067   MACRO_BEGIN elt->next = *hook; *hook = elt; MACRO_END
00068 
00069 /* insert element before hook */
00070 #define list_insert_beforehook(elt, hook) \
00071   MACRO_BEGIN elt->next = *hook; *hook = elt; hook=&elt->next; MACRO_END
00072 
00073 /* unlink element after hook, let elt be unlinked element, or NULL.
00074    hook remains. */
00075 #define list_unlink_athook(list, elt, hook) \
00076   MACRO_BEGIN \
00077   elt = hook ? *hook : NULL; if (elt) { *hook = elt->next; elt->next = NULL; }\
00078   MACRO_END
00079 
00080 /* unlink the specific element, if it is in the list. Otherwise, set
00081    elt to NULL */
00082 #define list_unlink(listtype, list, elt)      \
00083   MACRO_BEGIN                                 \
00084   listtype **_hook;                           \
00085   _list_find_hook(list, *_hook==elt, _hook);  \
00086   list_unlink_athook(list, elt, _hook);       \
00087   MACRO_END
00088 
00089 /* prepend elt to list */
00090 #define list_prepend(list, elt) \
00091   MACRO_BEGIN elt->next = list; list = elt; MACRO_END
00092 
00093 /* append elt to list. */
00094 #define list_append(listtype, list, elt)     \
00095   MACRO_BEGIN                                \
00096   listtype **_hook;                          \
00097   _list_forall_hook(list, _hook) {}          \
00098   list_insert_athook(elt, _hook);            \
00099   MACRO_END
00100 
00101 /* unlink the first element that satisfies the condition. */
00102 #define list_unlink_cond(listtype, list, elt, c)     \
00103   MACRO_BEGIN                                        \
00104   listtype **_hook;                                  \
00105   list_find2(elt, list, c, _hook);                   \
00106   list_unlink_athook(list, elt, _hook);              \
00107   MACRO_END
00108 
00109 /* let elt be the nth element of the list, starting to count from 0.
00110    Return NULL if out of bounds.   */
00111 #define list_nth(elt, list, n)                                \
00112   MACRO_BEGIN                                                 \
00113   int _x;  /* only evaluate n once */                         \
00114   for (_x=(n), elt=list; _x && elt; _x--, elt=elt->next) {}   \
00115   MACRO_END
00116 
00117 /* let elt be the nth element of the list, starting to count from 0.
00118    Return NULL if out of bounds.   */
00119 #define list_nth_hook(elt, list, n, hook)                     \
00120   MACRO_BEGIN                                                 \
00121   int _x;  /* only evaluate n once */                         \
00122   for (_x=(n), elt=list, hook=&list; _x && elt; _x--, hook=&elt->next, elt=elt->next) {}   \
00123   MACRO_END
00124 
00125 /* set n to the length of the list */
00126 #define list_length(listtype, list, n)                   \
00127   MACRO_BEGIN                                            \
00128   listtype *_elt;                                        \
00129   n=0;                                                   \
00130   list_forall(_elt, list)                                \
00131     n++;                                                 \
00132   MACRO_END
00133 
00134 /* set n to the index of the first element satisfying cond, or -1 if
00135    none found. Also set elt to the element, or NULL if none found. */
00136 #define list_index(list, n, elt, c)                      \
00137   MACRO_BEGIN                                            \
00138   n=0;                                                   \
00139   list_forall(elt, list) {                               \
00140     if (c) break;                                        \
00141     n++;                                                 \
00142   }                                                      \
00143   if (!elt)                                              \
00144     n=-1;                                                \
00145   MACRO_END
00146 
00147 /* set n to the number of elements in the list that satisfy condition c */
00148 #define list_count(list, n, elt, c)                      \
00149   MACRO_BEGIN                                            \
00150   n=0;                                                   \
00151   list_forall(elt, list) {                               \
00152     if (c) n++;                                          \
00153   }                                                      \
00154   MACRO_END
00155 
00156 /* let elt be each element of the list, unlinked. At the end, set list=NULL. */
00157 #define list_forall_unlink(elt, list) \
00158   for (elt=list; elt ? (list=elt->next, elt->next=NULL), 1 : 0; elt=list)
00159 
00160 /* reverse a list (efficient) */
00161 #define list_reverse(listtype, list)            \
00162   MACRO_BEGIN                                   \
00163   listtype *_list1=NULL, *elt;                  \
00164   list_forall_unlink(elt, list)                 \
00165     list_prepend(_list1, elt);                  \
00166   list = _list1;                                \
00167   MACRO_END
00168 
00169 /* insert the element ELT just before the first element TMP of the
00170    list for which COND holds. Here COND must be a condition of ELT and
00171    TMP.  Typical usage is to insert an element into an ordered list:
00172    for instance, list_insert_ordered(listtype, list, elt, tmp,
00173    elt->size <= tmp->size).  Note: if we give a "less than or equal"
00174    condition, the new element will be inserted just before a sequence
00175    of equal elements. If we give a "less than" condition, the new
00176    element will be inserted just after a list of equal elements.
00177    Note: it is much more efficient to construct a list with
00178    list_prepend and then order it with list_merge_sort, than to
00179    construct it with list_insert_ordered. */
00180 #define list_insert_ordered(listtype, list, elt, tmp, cond) \
00181   MACRO_BEGIN                                               \
00182   listtype **_hook;                                         \
00183   _list_find_hook(list, (tmp=*_hook, (cond)), _hook);       \
00184   list_insert_athook(elt, _hook);                           \
00185   MACRO_END
00186 
00187 /* sort the given list, according to the comparison condition.
00188    Typical usage is list_sort(listtype, list, a, b, a->size <
00189    b->size).  Note: if we give "less than or equal" condition, each
00190    segment of equal elements will be reversed in order. If we give a
00191    "less than" condition, each segment of equal elements will retain
00192    the original order. The latter is slower but sometimes
00193    prettier. Average running time: n*n/2. */
00194 #define list_sort(listtype, list, a, b, cond)            \
00195   MACRO_BEGIN                                            \
00196   listtype *_newlist=NULL;                               \
00197   list_forall_unlink(a, list)                            \
00198     list_insert_ordered(listtype, _newlist, a, b, cond); \
00199   list = _newlist;                                       \
00200   MACRO_END
00201 
00202 /* a much faster sort algorithm (merge sort, n log n worst case). It
00203    is required that the list type has an additional, unused next1
00204    component. Note there is no curious reversal of order of equal
00205    elements as for list_sort. */
00206 
00207 #define list_mergesort(listtype, list, a, b, cond)              \
00208   MACRO_BEGIN                                                   \
00209   listtype *_elt, **_hook1;                                     \
00210                                                                 \
00211   for (_elt=list; _elt; _elt=_elt->next1) {                     \
00212     _elt->next1 = _elt->next;                                   \
00213     _elt->next = NULL;                                          \
00214   }                                                             \
00215   do {                                                          \
00216     _hook1 = &(list);                                           \
00217     while ((a = *_hook1) != NULL && (b = a->next1) != NULL ) {  \
00218       _elt = b->next1;                                          \
00219       _list_merge_cond(listtype, a, b, cond, *_hook1);          \
00220       _hook1 = &((*_hook1)->next1);                             \
00221       *_hook1 = _elt;                                           \
00222     }                                                           \
00223   } while (_hook1 != &(list));                                  \
00224   MACRO_END
00225 
00226 /* merge two sorted lists. Store result at &result */
00227 #define _list_merge_cond(listtype, a, b, cond, result)   \
00228   MACRO_BEGIN                                            \
00229   listtype **_hook;                                      \
00230   _hook = &(result);                                     \
00231   while (1) {                                            \
00232      if (a==NULL) {                                      \
00233        *_hook = b;                                       \
00234        break;                                            \
00235      } else if (b==NULL) {                               \
00236        *_hook = a;                                       \
00237        break;                                            \
00238      } else if (cond) {                                  \
00239        *_hook = a;                                       \
00240        _hook = &(a->next);                               \
00241        a = a->next;                                      \
00242      } else {                                            \
00243        *_hook = b;                                       \
00244        _hook = &(b->next);                               \
00245        b = b->next;                                      \
00246      }                                                   \
00247   }                                                      \
00248   MACRO_END
00249 
00250 /* ---------------------------------------------------------------------- */
00251 /* macros for doubly-linked lists */
00252 
00253 #define dlist_append(head, end, elt)                    \
00254   MACRO_BEGIN                                            \
00255   elt->prev = end;                                       \
00256   elt->next = NULL;                                      \
00257   if (end) {                                             \
00258     end->next = elt;                                     \
00259   } else {                                               \
00260     head = elt;                                          \
00261   }                                                      \
00262   end = elt;                                             \
00263   MACRO_END
00264 
00265 /* let elt be each element of the list, unlinked. At the end, set list=NULL. */
00266 #define dlist_forall_unlink(elt, head, end) \
00267   for (elt=head; elt ? (head=elt->next, elt->next=NULL, elt->prev=NULL), 1 : (end=NULL, 0); elt=head)
00268 
00269 /* unlink the first element of the list */
00270 #define dlist_unlink_first(head, end, elt)               \
00271   MACRO_BEGIN                                            \
00272   elt = head;                                            \
00273   if (head) {                                            \
00274     head = head->next;                                   \
00275     if (head) {                                          \
00276       head->prev = NULL;                                 \
00277     } else {                                             \
00278       end = NULL;                                        \
00279     }                                                    \
00280     elt->prev = NULL;                                    \
00281     elt->next = NULL;                                    \
00282   }                                                      \
00283   MACRO_END
00284 
00285 #endif /* _PS_LISTS_H */
00286 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines


portrait_painter
Author(s): Niklas Meinzer, Ina Baumgarten
autogenerated on Wed Dec 26 2012 16:00:43