gvsig-raster / libjni-potrace / trunk / libjni-potrace / src / main / native / jpotrace / lists.h @ 1780
History | View | Annotate | Download (10.9 KB)
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 147 2007-04-09 00:44:09Z selinger $ */
|
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 |
|