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