1 /*
2 * Copyright 2008-2009 Katholieke Universiteit Leuven
3 * Copyright 2011 INRIA Saclay
4 * Copyright 2012-2013 Ecole Normale Superieure
5 * Copyright 2017 Sven Verdoolaege
6 *
7 * Use of this software is governed by the MIT license
8 *
9 * Written by Sven Verdoolaege, K.U.Leuven, Departement
10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
14 */
15
16 #include <isl_sort.h>
17 #include <isl_tarjan.h>
18 #include <isl/printer.h>
19
20 #define xCAT(A,B) A ## B
21 #define CAT(A,B) xCAT(A,B)
22 #undef EL
23 #define EL CAT(isl_,BASE)
24 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
25 #define FN(TYPE,NAME) xFN(TYPE,NAME)
26 #define xLIST(EL) EL ## _list
27 #define LIST(EL) xLIST(EL)
28 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
29 #define S(TYPE,NAME) xS(TYPE,NAME)
30
FN(LIST (EL),get_ctx)31 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
32 {
33 return list ? list->ctx : NULL;
34 }
35
LIST(EL)36 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
37 {
38 LIST(EL) *list;
39
40 if (n < 0)
41 isl_die(ctx, isl_error_invalid,
42 "cannot create list of negative length",
43 return NULL);
44 list = isl_alloc(ctx, LIST(EL),
45 sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
46 if (!list)
47 return NULL;
48
49 list->ctx = ctx;
50 isl_ctx_ref(ctx);
51 list->ref = 1;
52 list->size = n;
53 list->n = 0;
54 return list;
55 }
56
LIST(EL)57 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
58 {
59 if (!list)
60 return NULL;
61
62 list->ref++;
63 return list;
64 }
65
LIST(EL)66 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
67 {
68 int i;
69 LIST(EL) *dup;
70
71 if (!list)
72 return NULL;
73
74 dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
75 if (!dup)
76 return NULL;
77 for (i = 0; i < list->n; ++i)
78 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
79 return dup;
80 }
81
LIST(EL)82 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
83 {
84 if (!list)
85 return NULL;
86
87 if (list->ref == 1)
88 return list;
89 list->ref--;
90 return FN(LIST(EL),dup)(list);
91 }
92
93 /* Make sure "list" has room for at least "n" more pieces.
94 * Always return a list with a single reference.
95 *
96 * If there is only one reference to list, we extend it in place.
97 * Otherwise, we create a new LIST(EL) and copy the elements.
98 */
LIST(EL)99 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
100 {
101 isl_ctx *ctx;
102 int i, new_size;
103 LIST(EL) *res;
104
105 if (!list)
106 return NULL;
107 if (list->ref == 1 && list->n + n <= list->size)
108 return list;
109
110 ctx = FN(LIST(EL),get_ctx)(list);
111 new_size = ((list->n + n + 1) * 3) / 2;
112 if (list->ref == 1) {
113 res = isl_realloc(ctx, list, LIST(EL),
114 sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
115 if (!res)
116 return FN(LIST(EL),free)(list);
117 res->size = new_size;
118 return res;
119 }
120
121 if (list->n + n <= list->size && list->size < new_size)
122 new_size = list->size;
123
124 res = FN(LIST(EL),alloc)(ctx, new_size);
125 if (!res)
126 return FN(LIST(EL),free)(list);
127
128 for (i = 0; i < list->n; ++i)
129 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
130
131 FN(LIST(EL),free)(list);
132 return res;
133 }
134
135 /* Check that "index" is a valid position in "list".
136 */
FN(LIST (EL),check_index)137 static isl_stat FN(LIST(EL),check_index)(__isl_keep LIST(EL) *list, int index)
138 {
139 if (!list)
140 return isl_stat_error;
141 if (index < 0 || index >= list->n)
142 isl_die(FN(LIST(EL),get_ctx)(list), isl_error_invalid,
143 "index out of bounds", return isl_stat_error);
144 return isl_stat_ok;
145 }
146
LIST(EL)147 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
148 __isl_take struct EL *el)
149 {
150 list = FN(LIST(EL),grow)(list, 1);
151 if (!list || !el)
152 goto error;
153 list->p[list->n] = el;
154 list->n++;
155 return list;
156 error:
157 FN(EL,free)(el);
158 FN(LIST(EL),free)(list);
159 return NULL;
160 }
161
162 /* Remove the "n" elements starting at "first" from "list".
163 */
LIST(EL)164 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
165 unsigned first, unsigned n)
166 {
167 int i;
168
169 if (!list)
170 return NULL;
171 if (first + n > list->n || first + n < first)
172 isl_die(list->ctx, isl_error_invalid,
173 "index out of bounds", return FN(LIST(EL),free)(list));
174 if (n == 0)
175 return list;
176 list = FN(LIST(EL),cow)(list);
177 if (!list)
178 return NULL;
179 for (i = 0; i < n; ++i)
180 FN(EL,free)(list->p[first + i]);
181 for (i = first; i + n < list->n; ++i)
182 list->p[i] = list->p[i + n];
183 list->n -= n;
184 return list;
185 }
186
187 /* Insert "el" at position "pos" in "list".
188 *
189 * If there is only one reference to "list" and if it already has space
190 * for one extra element, we insert it directly into "list".
191 * Otherwise, we create a new list consisting of "el" and copied
192 * elements from "list".
193 */
LIST(EL)194 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
195 unsigned pos, __isl_take struct EL *el)
196 {
197 int i;
198 isl_ctx *ctx;
199 LIST(EL) *res;
200
201 if (!list || !el)
202 goto error;
203 ctx = FN(LIST(EL),get_ctx)(list);
204 if (pos > list->n)
205 isl_die(ctx, isl_error_invalid,
206 "index out of bounds", goto error);
207
208 if (list->ref == 1 && list->size > list->n) {
209 for (i = list->n; i > pos; --i)
210 list->p[i] = list->p[i - 1];
211 list->n++;
212 list->p[pos] = el;
213 return list;
214 }
215
216 res = FN(LIST(EL),alloc)(ctx, list->n + 1);
217 for (i = 0; i < pos; ++i)
218 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
219 res = FN(LIST(EL),add)(res, el);
220 for (i = pos; i < list->n; ++i)
221 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
222 FN(LIST(EL),free)(list);
223
224 return res;
225 error:
226 FN(EL,free)(el);
227 FN(LIST(EL),free)(list);
228 return NULL;
229 }
230
LIST(EL)231 __isl_null LIST(EL) *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
232 {
233 int i;
234
235 if (!list)
236 return NULL;
237
238 if (--list->ref > 0)
239 return NULL;
240
241 isl_ctx_deref(list->ctx);
242 for (i = 0; i < list->n; ++i)
243 FN(EL,free)(list->p[i]);
244 free(list);
245
246 return NULL;
247 }
248
249 /* Return the number of elements in "list".
250 */
FN(LIST (EL),size)251 int FN(LIST(EL),size)(__isl_keep LIST(EL) *list)
252 {
253 return list ? list->n : 0;
254 }
255
256 /* This is an alternative name for the function above.
257 */
FN(FN (LIST (EL),n),BASE)258 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
259 {
260 return FN(LIST(EL),size)(list);
261 }
262
263 /* Return the element at position "index" in "list".
264 */
FN(LIST (EL),peek)265 static __isl_keep EL *FN(LIST(EL),peek)(__isl_keep LIST(EL) *list, int index)
266 {
267 if (FN(LIST(EL),check_index)(list, index) < 0)
268 return NULL;
269 return list->p[index];
270 }
271
272 /* Return a copy of the element at position "index" in "list".
273 */
FN(LIST (EL),get_at)274 __isl_give EL *FN(LIST(EL),get_at)(__isl_keep LIST(EL) *list, int index)
275 {
276 return FN(EL,copy)(FN(LIST(EL),peek)(list, index));
277 }
278
279 /* This is an alternative name for the function above.
280 */
FN(FN (LIST (EL),get),BASE)281 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
282 {
283 return FN(LIST(EL),get_at)(list, index);
284 }
285
286 /* Replace the element at position "index" in "list" by "el".
287 */
LIST(EL)288 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
289 int index, __isl_take EL *el)
290 {
291 if (!list || !el)
292 goto error;
293 if (FN(LIST(EL),check_index)(list, index) < 0)
294 goto error;
295 if (list->p[index] == el) {
296 FN(EL,free)(el);
297 return list;
298 }
299 list = FN(LIST(EL),cow)(list);
300 if (!list)
301 goto error;
302 FN(EL,free)(list->p[index]);
303 list->p[index] = el;
304 return list;
305 error:
306 FN(EL,free)(el);
307 FN(LIST(EL),free)(list);
308 return NULL;
309 }
310
311 /* Return the element at position "index" of "list".
312 * This may be either a copy or the element itself
313 * if there is only one reference to "list".
314 * This allows the element to be modified inplace
315 * if both the list and the element have only a single reference.
316 * The caller is not allowed to modify "list" between
317 * this call to isl_list_*_take_* and a subsequent call
318 * to isl_list_*_restore_*.
319 * The only exception is that isl_list_*_free can be called instead.
320 */
FN(FN (LIST (EL),take),BASE)321 static __isl_give EL *FN(FN(LIST(EL),take),BASE)(__isl_keep LIST(EL) *list,
322 int index)
323 {
324 EL *el;
325
326 if (FN(LIST(EL),check_index)(list, index) < 0)
327 return NULL;
328 if (list->ref != 1)
329 return FN(FN(LIST(EL),get),BASE)(list, index);
330 el = list->p[index];
331 list->p[index] = NULL;
332 return el;
333 }
334
335 /* Set the element at position "index" of "list" to "el",
336 * where the position may be empty due to a previous call
337 * to isl_list_*_take_*.
338 */
LIST(EL)339 static __isl_give LIST(EL) *FN(FN(LIST(EL),restore),BASE)(
340 __isl_take LIST(EL) *list, int index, __isl_take EL *el)
341 {
342 return FN(FN(LIST(EL),set),BASE)(list, index, el);
343 }
344
345 /* Swap the elements of "list" in positions "pos1" and "pos2".
346 */
LIST(EL)347 __isl_give LIST(EL) *FN(LIST(EL),swap)(__isl_take LIST(EL) *list,
348 unsigned pos1, unsigned pos2)
349 {
350 EL *el1, *el2;
351
352 if (pos1 == pos2)
353 return list;
354 el1 = FN(FN(LIST(EL),take),BASE)(list, pos1);
355 el2 = FN(FN(LIST(EL),take),BASE)(list, pos2);
356 list = FN(FN(LIST(EL),restore),BASE)(list, pos1, el2);
357 list = FN(FN(LIST(EL),restore),BASE)(list, pos2, el1);
358 return list;
359 }
360
361 /* Reverse the elements of "list".
362 */
LIST(EL)363 __isl_give LIST(EL) *FN(LIST(EL),reverse)(__isl_take LIST(EL) *list)
364 {
365 int i, n;
366
367 n = FN(LIST(EL),size)(list);
368 for (i = 0; i < n - 1 - i; ++i)
369 list = FN(LIST(EL),swap)(list, i, n - 1 - i);
370 return list;
371 }
372
FN(LIST (EL),foreach)373 isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
374 isl_stat (*fn)(__isl_take EL *el, void *user), void *user)
375 {
376 int i;
377
378 if (!list)
379 return isl_stat_error;
380
381 for (i = 0; i < list->n; ++i) {
382 EL *el = FN(EL,copy)(list->p[i]);
383 if (!el)
384 return isl_stat_error;
385 if (fn(el, user) < 0)
386 return isl_stat_error;
387 }
388
389 return isl_stat_ok;
390 }
391
392 /* Replace each element in "list" by the result of calling "fn"
393 * on the element.
394 */
LIST(EL)395 __isl_give LIST(EL) *FN(LIST(EL),map)(__isl_keep LIST(EL) *list,
396 __isl_give EL *(*fn)(__isl_take EL *el, void *user), void *user)
397 {
398 int i, n;
399
400 if (!list)
401 return NULL;
402
403 n = list->n;
404 for (i = 0; i < n; ++i) {
405 EL *el = FN(FN(LIST(EL),take),BASE)(list, i);
406 if (!el)
407 return FN(LIST(EL),free)(list);
408 el = fn(el, user);
409 list = FN(FN(LIST(EL),restore),BASE)(list, i, el);
410 }
411
412 return list;
413 }
414
415 /* Internal data structure for isl_*_list_sort.
416 *
417 * "cmp" is the original comparison function.
418 * "user" is a user provided pointer that should be passed to "cmp".
419 */
S(LIST (EL),sort_data)420 S(LIST(EL),sort_data) {
421 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
422 void *user;
423 };
424
425 /* Compare two entries of an isl_*_list based on the user provided
426 * comparison function on pairs of isl_* objects.
427 */
FN(LIST (EL),cmp)428 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
429 {
430 S(LIST(EL),sort_data) *data = user;
431 EL * const *el1 = a;
432 EL * const *el2 = b;
433
434 return data->cmp(*el1, *el2, data->user);
435 }
436
437 /* Sort the elements of "list" in ascending order according to
438 * comparison function "cmp".
439 */
LIST(EL)440 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
441 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
442 {
443 S(LIST(EL),sort_data) data = { cmp, user };
444
445 if (!list)
446 return NULL;
447 if (list->n <= 1)
448 return list;
449 list = FN(LIST(EL),cow)(list);
450 if (!list)
451 return NULL;
452
453 if (isl_sort(list->p, list->n, sizeof(list->p[0]),
454 &FN(LIST(EL),cmp), &data) < 0)
455 return FN(LIST(EL),free)(list);
456
457 return list;
458 }
459
460 /* Internal data structure for isl_*_list_foreach_scc.
461 *
462 * "list" is the original list.
463 * "follows" is the user provided callback that defines the edges of the graph.
464 */
S(LIST (EL),foreach_scc_data)465 S(LIST(EL),foreach_scc_data) {
466 LIST(EL) *list;
467 isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
468 void *follows_user;
469 };
470
471 /* Does element i of data->list follow element j?
472 *
473 * Use the user provided callback to find out.
474 */
FN(LIST (EL),follows)475 static isl_bool FN(LIST(EL),follows)(int i, int j, void *user)
476 {
477 S(LIST(EL),foreach_scc_data) *data = user;
478
479 return data->follows(data->list->p[i], data->list->p[j],
480 data->follows_user);
481 }
482
483 /* Call "fn" on the sublist of "list" that consists of the elements
484 * with indices specified by the "n" elements of "pos".
485 */
FN(LIST (EL),call_on_scc)486 static isl_stat FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos,
487 int n, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
488 {
489 int i;
490 isl_ctx *ctx;
491 LIST(EL) *slice;
492
493 ctx = FN(LIST(EL),get_ctx)(list);
494 slice = FN(LIST(EL),alloc)(ctx, n);
495 for (i = 0; i < n; ++i) {
496 EL *el;
497
498 el = FN(EL,copy)(list->p[pos[i]]);
499 slice = FN(LIST(EL),add)(slice, el);
500 }
501
502 return fn(slice, user);
503 }
504
505 /* Call "fn" on each of the strongly connected components (SCCs) of
506 * the graph with as vertices the elements of "list" and
507 * a directed edge from node b to node a iff follows(a, b)
508 * returns 1. follows should return -1 on error.
509 *
510 * If SCC a contains a node i that follows a node j in another SCC b
511 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
512 * after being called on SCC b.
513 *
514 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
515 * call fn on each of them.
516 */
FN(LIST (EL),foreach_scc)517 isl_stat FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
518 isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
519 void *follows_user,
520 isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
521 {
522 S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
523 int i, n;
524 isl_ctx *ctx;
525 struct isl_tarjan_graph *g;
526
527 if (!list)
528 return isl_stat_error;
529 if (list->n == 0)
530 return isl_stat_ok;
531 if (list->n == 1)
532 return fn(FN(LIST(EL),copy)(list), fn_user);
533
534 ctx = FN(LIST(EL),get_ctx)(list);
535 n = list->n;
536 g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
537 if (!g)
538 return isl_stat_error;
539
540 i = 0;
541 do {
542 int first;
543
544 if (g->order[i] == -1)
545 isl_die(ctx, isl_error_internal, "cannot happen",
546 break);
547 first = i;
548 while (g->order[i] != -1) {
549 ++i; --n;
550 }
551 if (first == 0 && n == 0) {
552 isl_tarjan_graph_free(g);
553 return fn(FN(LIST(EL),copy)(list), fn_user);
554 }
555 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
556 fn, fn_user) < 0)
557 break;
558 ++i;
559 } while (n);
560
561 isl_tarjan_graph_free(g);
562
563 return n > 0 ? isl_stat_error : isl_stat_ok;
564 }
565
LIST(EL)566 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
567 {
568 isl_ctx *ctx;
569 LIST(EL) *list;
570
571 if (!el)
572 return NULL;
573 ctx = FN(EL,get_ctx)(el);
574 list = FN(LIST(EL),alloc)(ctx, 1);
575 if (!list)
576 goto error;
577 list = FN(LIST(EL),add)(list, el);
578 return list;
579 error:
580 FN(EL,free)(el);
581 return NULL;
582 }
583
584 /* Append the elements of "list2" to "list1", where "list1" is known
585 * to have only a single reference and enough room to hold
586 * the extra elements.
587 */
LIST(EL)588 static __isl_give LIST(EL) *FN(LIST(EL),concat_inplace)(
589 __isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2)
590 {
591 int i;
592
593 for (i = 0; i < list2->n; ++i)
594 list1 = FN(LIST(EL),add)(list1, FN(EL,copy)(list2->p[i]));
595 FN(LIST(EL),free)(list2);
596 return list1;
597 }
598
599 /* Concatenate "list1" and "list2".
600 * If "list1" has only one reference and has enough room
601 * for the elements of "list2", the add the elements to "list1" itself.
602 * Otherwise, create a new list to store the result.
603 */
LIST(EL)604 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
605 __isl_take LIST(EL) *list2)
606 {
607 int i;
608 isl_ctx *ctx;
609 LIST(EL) *res;
610
611 if (!list1 || !list2)
612 goto error;
613
614 if (list1->ref == 1 && list1->n + list2->n <= list1->size)
615 return FN(LIST(EL),concat_inplace)(list1, list2);
616
617 ctx = FN(LIST(EL),get_ctx)(list1);
618 res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
619 for (i = 0; i < list1->n; ++i)
620 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
621 for (i = 0; i < list2->n; ++i)
622 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
623
624 FN(LIST(EL),free)(list1);
625 FN(LIST(EL),free)(list2);
626 return res;
627 error:
628 FN(LIST(EL),free)(list1);
629 FN(LIST(EL),free)(list2);
630 return NULL;
631 }
632
CAT(isl_printer_print_,LIST (BASE))633 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
634 __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
635 {
636 int i;
637
638 if (!p || !list)
639 goto error;
640 p = isl_printer_print_str(p, "(");
641 for (i = 0; i < list->n; ++i) {
642 if (i)
643 p = isl_printer_print_str(p, ",");
644 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
645 }
646 p = isl_printer_print_str(p, ")");
647 return p;
648 error:
649 isl_printer_free(p);
650 return NULL;
651 }
652
FN(LIST (EL),dump)653 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
654 {
655 isl_printer *printer;
656
657 if (!list)
658 return;
659
660 printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
661 printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
662 printer = isl_printer_end_line(printer);
663
664 isl_printer_free(printer);
665 }
666