?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
isl_map_subtract.c: map_is_singleton_subset: fix typo in comment
[isl.git] / isl_list_templ.c
blobbee624835a24460db7129f71206d3427d629201e
1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 *
6 * Use of this software is governed by the MIT license
7 *
8 * Written by Sven Verdoolaege, K.U.Leuven, Departement
9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
10 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
11 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
12 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
13 */
14
15 #include <isl_sort.h>
16 #include <isl_tarjan.h>
17
18 #define xCAT(A,B) A ## B
19 #define CAT(A,B) xCAT(A,B)
20 #undef EL
21 #define EL CAT(isl_,BASE)
22 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
23 #define FN(TYPE,NAME) xFN(TYPE,NAME)
24 #define xLIST(EL) EL ## _list
25 #define LIST(EL) xLIST(EL)
26 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
27 #define S(TYPE,NAME) xS(TYPE,NAME)
28
29 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
30 {
31 return list ? list->ctx : NULL;
32 }
33
34 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
35 {
36 LIST(EL) *list;
37
38 if (n < 0)
39 isl_die(ctx, isl_error_invalid,
40 "cannot create list of negative length",
41 return NULL);
42 list = isl_alloc(ctx, LIST(EL),
43 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
44 if (!list)
45 return NULL;
46
47 list->ctx = ctx;
48 isl_ctx_ref(ctx);
49 list->ref = 1;
50 list->size = n;
51 list->n = 0;
52 return list;
53 }
54
55 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
56 {
57 if (!list)
58 return NULL;
59
60 list->ref++;
61 return list;
62 }
63
64 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
65 {
66 int i;
67 LIST(EL) *dup;
68
69 if (!list)
70 return NULL;
71
72 dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
73 if (!dup)
74 return NULL;
75 for (i = 0; i < list->n; ++i)
76 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
77 return dup;
78 }
79
80 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
81 {
82 if (!list)
83 return NULL;
84
85 if (list->ref == 1)
86 return list;
87 list->ref--;
88 return FN(LIST(EL),dup)(list);
89 }
90
91 /* Make sure "list" has room for at least "n" more pieces.
92 * Always return a list with a single reference.
93 *
94 * If there is only one reference to list, we extend it in place.
95 * Otherwise, we create a new LIST(EL) and copy the elements.
96 */
97 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
98 {
99 isl_ctx *ctx;
100 int i, new_size;
101 LIST(EL) *res;
102
103 if (!list)
104 return NULL;
105 if (list->ref == 1 && list->n + n <= list->size)
106 return list;
107
108 ctx = FN(LIST(EL),get_ctx)(list);
109 new_size = ((list->n + n + 1) * 3) / 2;
110 if (list->ref == 1) {
111 res = isl_realloc(ctx, list, LIST(EL),
112 sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
113 if (!res)
114 return FN(LIST(EL),free)(list);
115 res->size = new_size;
116 return res;
117 }
118
119 if (list->n + n <= list->size && list->size < new_size)
120 new_size = list->size;
121
122 res = FN(LIST(EL),alloc)(ctx, new_size);
123 if (!res)
124 return FN(LIST(EL),free)(list);
125
126 for (i = 0; i < list->n; ++i)
127 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
128
129 FN(LIST(EL),free)(list);
130 return res;
131 }
132
133 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
134 __isl_take struct EL *el)
135 {
136 list = FN(LIST(EL),grow)(list, 1);
137 if (!list || !el)
138 goto error;
139 list->p[list->n] = el;
140 list->n++;
141 return list;
142 error:
143 FN(EL,free)(el);
144 FN(LIST(EL),free)(list);
145 return NULL;
146 }
147
148 /* Remove the "n" elements starting at "first" from "list".
149 */
150 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
151 unsigned first, unsigned n)
152 {
153 int i;
154
155 if (!list)
156 return NULL;
157 if (first + n > list->n || first + n < first)
158 isl_die(list->ctx, isl_error_invalid,
159 "index out of bounds", return FN(LIST(EL),free)(list));
160 if (n == 0)
161 return list;
162 list = FN(LIST(EL),cow)(list);
163 if (!list)
164 return NULL;
165 for (i = 0; i < n; ++i)
166 FN(EL,free)(list->p[first + i]);
167 for (i = first; i + n < list->n; ++i)
168 list->p[i] = list->p[i + n];
169 list->n -= n;
170 return list;
171 }
172
173 /* Insert "el" at position "pos" in "list".
174 *
175 * If there is only one reference to "list" and if it already has space
176 * for one extra element, we insert it directly into "list".
177 * Otherwise, we create a new list consisting of "el" and copied
178 * elements from "list".
179 */
180 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
181 unsigned pos, __isl_take struct EL *el)
182 {
183 int i;
184 isl_ctx *ctx;
185 LIST(EL) *res;
186
187 if (!list || !el)
188 goto error;
189 ctx = FN(LIST(EL),get_ctx)(list);
190 if (pos > list->n)
191 isl_die(ctx, isl_error_invalid,
192 "index out of bounds", goto error);
193
194 if (list->ref == 1 && list->size > list->n) {
195 for (i = list->n - 1; i >= pos; --i)
196 list->p[i + 1] = list->p[i];
197 list->n++;
198 list->p[pos] = el;
199 return list;
200 }
201
202 res = FN(LIST(EL),alloc)(ctx, list->n + 1);
203 for (i = 0; i < pos; ++i)
204 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
205 res = FN(LIST(EL),add)(res, el);
206 for (i = pos; i < list->n; ++i)
207 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
208 FN(LIST(EL),free)(list);
209
210 return res;
211 error:
212 FN(EL,free)(el);
213 FN(LIST(EL),free)(list);
214 return NULL;
215 }
216
217 __isl_null LIST(EL) *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
218 {
219 int i;
220
221 if (!list)
222 return NULL;
223
224 if (--list->ref > 0)
225 return NULL;
226
227 isl_ctx_deref(list->ctx);
228 for (i = 0; i < list->n; ++i)
229 FN(EL,free)(list->p[i]);
230 free(list);
231
232 return NULL;
233 }
234
235 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
236 {
237 return list ? list->n : 0;
238 }
239
240 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
241 {
242 if (!list)
243 return NULL;
244 if (index < 0 || index >= list->n)
245 isl_die(list->ctx, isl_error_invalid,
246 "index out of bounds", return NULL);
247 return FN(EL,copy)(list->p[index]);
248 }
249
250 /* Replace the element at position "index" in "list" by "el".
251 */
252 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
253 int index, __isl_take EL *el)
254 {
255 if (!list || !el)
256 goto error;
257 if (index < 0 || index >= list->n)
258 isl_die(list->ctx, isl_error_invalid,
259 "index out of bounds", goto error);
260 if (list->p[index] == el) {
261 FN(EL,free)(el);
262 return list;
263 }
264 list = FN(LIST(EL),cow)(list);
265 if (!list)
266 goto error;
267 FN(EL,free)(list->p[index]);
268 list->p[index] = el;
269 return list;
270 error:
271 FN(EL,free)(el);
272 FN(LIST(EL),free)(list);
273 return NULL;
274 }
275
276 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
277 int (*fn)(__isl_take EL *el, void *user), void *user)
278 {
279 int i;
280
281 if (!list)
282 return -1;
283
284 for (i = 0; i < list->n; ++i) {
285 EL *el = FN(EL,copy(list->p[i]));
286 if (!el)
287 return -1;
288 if (fn(el, user) < 0)
289 return -1;
290 }
291
292 return 0;
293 }
294
295 /* Internal data structure for isl_*_list_sort.
296 *
297 * "cmp" is the original comparison function.
298 * "user" is a user provided pointer that should be passed to "cmp".
299 */
300 S(LIST(EL),sort_data) {
301 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
302 void *user;
303 };
304
305 /* Compare two entries of an isl_*_list based on the user provided
306 * comparison function on pairs of isl_* objects.
307 */
308 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
309 {
310 S(LIST(EL),sort_data) *data = user;
311 EL * const *el1 = a;
312 EL * const *el2 = b;
313
314 return data->cmp(*el1, *el2, data->user);
315 }
316
317 /* Sort the elements of "list" in ascending order according to
318 * comparison function "cmp".
319 */
320 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
321 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
322 {
323 S(LIST(EL),sort_data) data = { cmp, user };
324
325 if (!list)
326 return NULL;
327 if (list->n <= 1)
328 return list;
329 list = FN(LIST(EL),cow)(list);
330 if (!list)
331 return NULL;
332
333 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
334 &FN(LIST(EL),cmp), &data) < 0)
335 return FN(LIST(EL),free)(list);
336
337 return list;
338 }
339
340 /* Internal data structure for isl_*_list_foreach_scc.
341 *
342 * "list" is the original list.
343 * "follows" is the user provided callback that defines the edges of the graph.
344 */
345 S(LIST(EL),foreach_scc_data) {
346 LIST(EL) *list;
347 int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
348 void *follows_user;
349 };
350
351 /* Does element i of data->list follow element j?
352 *
353 * Use the user provided callback to find out.
354 */
355 static int FN(LIST(EL),follows)(int i, int j, void *user)
356 {
357 S(LIST(EL),foreach_scc_data) *data = user;
358
359 return data->follows(data->list->p[i], data->list->p[j],
360 data->follows_user);
361 }
362
363 /* Call "fn" on the sublist of "list" that consists of the elements
364 * with indices specified by the "n" elements of "pos".
365 */
366 static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n,
367 int (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
368 {
369 int i;
370 isl_ctx *ctx;
371 LIST(EL) *slice;
372
373 ctx = FN(LIST(EL),get_ctx)(list);
374 slice = FN(LIST(EL),alloc)(ctx, n);
375 for (i = 0; i < n; ++i) {
376 EL *el;
377
378 el = FN(EL,copy)(list->p[pos[i]]);
379 slice = FN(LIST(EL),add)(slice, el);
380 }
381
382 return fn(slice, user);
383 }
384
385 /* Call "fn" on each of the strongly connected components (SCCs) of
386 * the graph with as vertices the elements of "list" and
387 * a directed edge from node b to node a iff follows(a, b)
388 * returns 1. follows should return -1 on error.
389 *
390 * If SCC a contains a node i that follows a node j in another SCC b
391 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
392 * after being called on SCC b.
393 *
394 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
395 * call fn on each of them.
396 */
397 int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
398 int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
399 void *follows_user,
400 int (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
401 {
402 S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
403 int i, n;
404 isl_ctx *ctx;
405 struct isl_tarjan_graph *g;
406
407 if (!list)
408 return -1;
409 if (list->n == 0)
410 return 0;
411 if (list->n == 1)
412 return fn(FN(LIST(EL),copy)(list), fn_user);
413
414 ctx = FN(LIST(EL),get_ctx)(list);
415 n = list->n;
416 g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
417 if (!g)
418 return -1;
419
420 i = 0;
421 do {
422 int first;
423
424 if (g->order[i] == -1)
425 isl_die(ctx, isl_error_internal, "cannot happen",
426 break);
427 first = i;
428 while (g->order[i] != -1) {
429 ++i; --n;
430 }
431 if (first == 0 && n == 0) {
432 isl_tarjan_graph_free(g);
433 return fn(FN(LIST(EL),copy)(list), fn_user);
434 }
435 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
436 fn, fn_user) < 0)
437 break;
438 ++i;
439 } while (n);
440
441 isl_tarjan_graph_free(g);
442
443 return n > 0 ? -1 : 0;
444 }
445
446 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
447 {
448 isl_ctx *ctx;
449 LIST(EL) *list;
450
451 if (!el)
452 return NULL;
453 ctx = FN(EL,get_ctx)(el);
454 list = FN(LIST(EL),alloc)(ctx, 1);
455 if (!list)
456 goto error;
457 list = FN(LIST(EL),add)(list, el);
458 return list;
459 error:
460 FN(EL,free)(el);
461 return NULL;
462 }
463
464 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
465 __isl_take LIST(EL) *list2)
466 {
467 int i;
468 isl_ctx *ctx;
469 LIST(EL) *res;
470
471 if (!list1 || !list2)
472 goto error;
473
474 ctx = FN(LIST(EL),get_ctx)(list1);
475 res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
476 for (i = 0; i < list1->n; ++i)
477 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
478 for (i = 0; i < list2->n; ++i)
479 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
480
481 FN(LIST(EL),free)(list1);
482 FN(LIST(EL),free)(list2);
483 return res;
484 error:
485 FN(LIST(EL),free)(list1);
486 FN(LIST(EL),free)(list2);
487 return NULL;
488 }
489
490 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
491 __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
492 {
493 int i;
494
495 if (!p || !list)
496 goto error;
497 p = isl_printer_print_str(p, "(");
498 for (i = 0; i < list->n; ++i) {
499 if (i)
500 p = isl_printer_print_str(p, ",");
501 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
502 }
503 p = isl_printer_print_str(p, ")");
504 return p;
505 error:
506 isl_printer_free(p);
507 return NULL;
508 }
509
510 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
511 {
512 isl_printer *printer;
513
514 if (!list)
515 return;
516
517 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
518 printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
519 printer = isl_printer_end_line(printer);
520
521 isl_printer_free(printer);
522 }
Integer set library