← Back to branch summary

~valavanisalex/ubuntu/precise/inkscape/fix-943984

« back to all changes in this revision

Viewing changes to inkscape-0.47pre1/src/trace/potrace/lists.h

  • Committer: Bazaar Package Importer
  • Author(s): Bryce Harrington
  • Date: 2009-07-02 17:09:45 UTC
  • mfrom: (1.1.9 upstream)
  • Revision ID: james.westby@ubuntu.com-20090702170945-nn6d6zswovbwju1t
Tags: 0.47~pre1-0ubuntu1
https://launchpad.net/bugs/348842
https://launchpad.net/bugs/391149
* New upstream release.
  - Don't constrain maximization on small resolution devices (pre0)
    (LP: #348842)
  - Fixes segfault on startup (pre0)
    (LP: #391149)

Show diffs side-by-side

added added

removed removed

Lines of Context:
inkscape-0.47pre1/src/trace/potrace/lists.h
 
1
/* Copyright (C) 2001-2007 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: lists.h 16345 2007-10-26 21:01:30Z ishmal $ */
 
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