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
25isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
26{
27 return list ? list->ctx : NULL;
28}
29
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
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
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), n: list->n);
69 if (!dup)
70 return NULL;
71 for (i = 0; i < list->n; ++i)
72 dup = FN(LIST(EL),add)(list: dup, FN(EL,copy)(bmap: list->p[i]));
73 return dup;
74}
75
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 */
93static __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, n: 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)(list: res, FN(EL,copy)(bmap: 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 */
131static 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
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, n: 1);
145 if (!list || !el)
146 goto error;
147 list->p[list->n] = el;
148 list->n++;
149 return list;
150error:
151 FN(EL,free)(bmap: el);
152 FN(LIST(EL),free)(list);
153 return NULL;
154}
155
156/* Remove the "n" elements starting at "first" from "list".
157 */
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)(bmap: 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 */
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, first: 0, n: 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 */
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, n: list->n + 1);
220 for (i = 0; i < pos; ++i)
221 res = FN(LIST(EL),add)(list: res, FN(EL,copy)(bmap: list->p[i]));
222 res = FN(LIST(EL),add)(list: res, el);
223 for (i = pos; i < list->n; ++i)
224 res = FN(LIST(EL),add)(list: res, FN(EL,copy)(bmap: list->p[i]));
225 FN(LIST(EL),free)(list);
226
227 return res;
228error:
229 FN(EL,free)(bmap: el);
230 FN(LIST(EL),free)(list);
231 return NULL;
232}
233
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(ctx: list->ctx);
245 for (i = 0; i < list->n; ++i)
246 FN(EL,free)(bmap: list->p[i]);
247 free(ptr: list);
248
249 return NULL;
250}
251
252/* Return the number of elements in "list".
253 */
254isl_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 */
261isl_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 */
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 */
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 */
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 */
292__isl_give LIST(EL) *FN(LIST(EL),set_at)(__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)(bmap: el);
301 return list;
302 }
303 list = FN(LIST(EL),cow)(list);
304 if (!list)
305 goto error;
306 FN(EL,free)(bmap: list->p[index]);
307 list->p[index] = el;
308 return list;
309error:
310 FN(EL,free)(bmap: el);
311 FN(LIST(EL),free)(list);
312 return NULL;
313}
314
315/* This is an alternative name for the function above.
316 */
317__isl_give LIST(EL) *FN(FN(LIST(EL),set),EL_BASE)(__isl_take LIST(EL) *list,
318 int index, __isl_take EL *el)
319{
320 return FN(LIST(EL),set_at)(list, index, el);
321}
322
323/* Return the element at position "index" of "list".
324 * This may be either a copy or the element itself
325 * if there is only one reference to "list".
326 * This allows the element to be modified inplace
327 * if both the list and the element have only a single reference.
328 * The caller is not allowed to modify "list" between
329 * this call to isl_list_*_take_* and a subsequent call
330 * to isl_list_*_restore_*.
331 * The only exception is that isl_list_*_free can be called instead.
332 */
333static __isl_give EL *FN(FN(LIST(EL),take),EL_BASE)(__isl_keep LIST(EL) *list,
334 int index)
335{
336 EL *el;
337
338 if (FN(LIST(EL),check_index)(list, index) < 0)
339 return NULL;
340 if (list->ref != 1)
341 return FN(FN(LIST(EL),get),EL_BASE)(list, index);
342 el = list->p[index];
343 list->p[index] = NULL;
344 return el;
345}
346
347/* Set the element at position "index" of "list" to "el",
348 * where the position may be empty due to a previous call
349 * to isl_list_*_take_*.
350 */
351static __isl_give LIST(EL) *FN(FN(LIST(EL),restore),EL_BASE)(
352 __isl_take LIST(EL) *list, int index, __isl_take EL *el)
353{
354 return FN(FN(LIST(EL),set),EL_BASE)(list, index, el);
355}
356
357/* Swap the elements of "list" in positions "pos1" and "pos2".
358 */
359__isl_give LIST(EL) *FN(LIST(EL),swap)(__isl_take LIST(EL) *list,
360 unsigned pos1, unsigned pos2)
361{
362 EL *el1, *el2;
363
364 if (pos1 == pos2)
365 return list;
366 el1 = FN(FN(LIST(EL),take),EL_BASE)(list, index: pos1);
367 el2 = FN(FN(LIST(EL),take),EL_BASE)(list, index: pos2);
368 list = FN(FN(LIST(EL),restore),EL_BASE)(list, index: pos1, el: el2);
369 list = FN(FN(LIST(EL),restore),EL_BASE)(list, index: pos2, el: el1);
370 return list;
371}
372
373/* Reverse the elements of "list".
374 */
375__isl_give LIST(EL) *FN(LIST(EL),reverse)(__isl_take LIST(EL) *list)
376{
377 int i, n;
378
379 n = FN(LIST(EL),size)(list);
380 for (i = 0; i < n - 1 - i; ++i)
381 list = FN(LIST(EL),swap)(list, pos1: i, pos2: n - 1 - i);
382 return list;
383}
384
385isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
386 isl_stat (*fn)(__isl_take EL *el, void *user), void *user)
387{
388 int i;
389
390 if (!list)
391 return isl_stat_error;
392
393 for (i = 0; i < list->n; ++i) {
394 EL *el = FN(EL,copy)(bmap: list->p[i]);
395 if (!el)
396 return isl_stat_error;
397 if (fn(el, user) < 0)
398 return isl_stat_error;
399 }
400
401 return isl_stat_ok;
402}
403
404/* Does "test" succeed on every element of "list"?
405 */
406isl_bool FN(LIST(EL),every)(__isl_keep LIST(EL) *list,
407 isl_bool (*test)(__isl_keep EL *el, void *user), void *user)
408{
409 int i;
410
411 if (!list)
412 return isl_bool_error;
413
414 for (i = 0; i < list->n; ++i) {
415 isl_bool r;
416
417 r = test(list->p[i], user);
418 if (r < 0 || !r)
419 return r;
420 }
421
422 return isl_bool_true;
423}
424
425/* Replace each element in "list" by the result of calling "fn"
426 * on the element.
427 */
428__isl_give LIST(EL) *FN(LIST(EL),map)(__isl_keep LIST(EL) *list,
429 __isl_give EL *(*fn)(__isl_take EL *el, void *user), void *user)
430{
431 int i, n;
432
433 if (!list)
434 return NULL;
435
436 n = list->n;
437 for (i = 0; i < n; ++i) {
438 EL *el = FN(FN(LIST(EL),take),EL_BASE)(list, index: i);
439 if (!el)
440 return FN(LIST(EL),free)(list);
441 el = fn(el, user);
442 list = FN(FN(LIST(EL),restore),EL_BASE)(list, index: i, el);
443 }
444
445 return list;
446}
447
448/* Internal data structure for isl_*_list_sort.
449 *
450 * "cmp" is the original comparison function.
451 * "user" is a user provided pointer that should be passed to "cmp".
452 */
453S(LIST(EL),sort_data) {
454 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
455 void *user;
456};
457
458/* Compare two entries of an isl_*_list based on the user provided
459 * comparison function on pairs of isl_* objects.
460 */
461static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
462{
463 S(LIST(EL),sort_data) *data = user;
464 EL * const *el1 = a;
465 EL * const *el2 = b;
466
467 return data->cmp(*el1, *el2, data->user);
468}
469
470/* Sort the elements of "list" in ascending order according to
471 * comparison function "cmp".
472 */
473__isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
474 int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
475{
476 S(LIST(EL),sort_data) data = { cmp, user };
477
478 if (!list)
479 return NULL;
480 if (list->n <= 1)
481 return list;
482 list = FN(LIST(EL),cow)(list);
483 if (!list)
484 return NULL;
485
486 if (isl_sort(pbase: list->p, total_elems: list->n, size: sizeof(list->p[0]),
487 cmp: &FN(LIST(EL),cmp), arg: &data) < 0)
488 return FN(LIST(EL),free)(list);
489
490 return list;
491}
492
493/* Internal data structure for isl_*_list_foreach_scc.
494 *
495 * "list" is the original list.
496 * "follows" is the user provided callback that defines the edges of the graph.
497 */
498S(LIST(EL),foreach_scc_data) {
499 LIST(EL) *list;
500 isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
501 void *follows_user;
502};
503
504/* Does element i of data->list follow element j?
505 *
506 * Use the user provided callback to find out.
507 */
508static isl_bool FN(LIST(EL),follows)(int i, int j, void *user)
509{
510 S(LIST(EL),foreach_scc_data) *data = user;
511
512 return data->follows(data->list->p[i], data->list->p[j],
513 data->follows_user);
514}
515
516/* Call "fn" on the sublist of "list" that consists of the elements
517 * with indices specified by the "n" elements of "pos".
518 */
519static isl_stat FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos,
520 int n, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
521{
522 int i;
523 isl_ctx *ctx;
524 LIST(EL) *slice;
525
526 ctx = FN(LIST(EL),get_ctx)(list);
527 slice = FN(LIST(EL),alloc)(ctx, n);
528 for (i = 0; i < n; ++i) {
529 EL *el;
530
531 el = FN(EL,copy)(bmap: list->p[pos[i]]);
532 slice = FN(LIST(EL),add)(list: slice, el);
533 }
534
535 return fn(slice, user);
536}
537
538/* Call "fn" on each of the strongly connected components (SCCs) of
539 * the graph with as vertices the elements of "list" and
540 * a directed edge from node b to node a iff follows(a, b)
541 * returns 1. follows should return -1 on error.
542 *
543 * If SCC a contains a node i that follows a node j in another SCC b
544 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
545 * after being called on SCC b.
546 *
547 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
548 * call fn on each of them.
549 */
550isl_stat FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
551 isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
552 void *follows_user,
553 isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
554{
555 S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
556 int i, n;
557 isl_ctx *ctx;
558 struct isl_tarjan_graph *g;
559
560 if (!list)
561 return isl_stat_error;
562 if (list->n == 0)
563 return isl_stat_ok;
564 if (list->n == 1)
565 return fn(FN(LIST(EL),copy)(list), fn_user);
566
567 ctx = FN(LIST(EL),get_ctx)(list);
568 n = list->n;
569 g = isl_tarjan_graph_init(ctx, len: n, follows: &FN(LIST(EL),follows), user: &data);
570 if (!g)
571 return isl_stat_error;
572
573 i = 0;
574 do {
575 int first;
576
577 if (g->order[i] == -1)
578 isl_die(ctx, isl_error_internal, "cannot happen",
579 break);
580 first = i;
581 while (g->order[i] != -1) {
582 ++i; --n;
583 }
584 if (first == 0 && n == 0) {
585 isl_tarjan_graph_free(g);
586 return fn(FN(LIST(EL),copy)(list), fn_user);
587 }
588 if (FN(LIST(EL),call_on_scc)(list, pos: g->order + first, n: i - first,
589 fn, user: fn_user) < 0)
590 break;
591 ++i;
592 } while (n);
593
594 isl_tarjan_graph_free(g);
595
596 return n > 0 ? isl_stat_error : isl_stat_ok;
597}
598
599__isl_give LIST(EL) *FN(FN(LIST(EL),from),EL_BASE)(__isl_take EL *el)
600{
601 isl_ctx *ctx;
602 LIST(EL) *list;
603
604 if (!el)
605 return NULL;
606 ctx = FN(EL,get_ctx)(bmap: el);
607 list = FN(LIST(EL),alloc)(ctx, n: 1);
608 if (!list)
609 goto error;
610 list = FN(LIST(EL),add)(list, el);
611 return list;
612error:
613 FN(EL,free)(bmap: el);
614 return NULL;
615}
616
617/* This function performs the same operation as isl_*_list_from_*,
618 * but is considered as a function on the element when exported.
619 */
620__isl_give LIST(EL) *FN(EL,to_list)(__isl_take EL *el)
621{
622 return FN(FN(LIST(EL),from),EL_BASE)(el);
623}
624
625/* Append the elements of "list2" to "list1", where "list1" is known
626 * to have only a single reference and enough room to hold
627 * the extra elements.
628 */
629static __isl_give LIST(EL) *FN(LIST(EL),concat_inplace)(
630 __isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2)
631{
632 int i;
633
634 for (i = 0; i < list2->n; ++i)
635 list1 = FN(LIST(EL),add)(list: list1, FN(EL,copy)(bmap: list2->p[i]));
636 FN(LIST(EL),free)(list: list2);
637 return list1;
638}
639
640/* Concatenate "list1" and "list2".
641 * If "list1" has only one reference and has enough room
642 * for the elements of "list2", the add the elements to "list1" itself.
643 * Otherwise, create a new list to store the result.
644 */
645__isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
646 __isl_take LIST(EL) *list2)
647{
648 int i;
649 isl_ctx *ctx;
650 LIST(EL) *res;
651
652 if (!list1 || !list2)
653 goto error;
654
655 if (list1->ref == 1 && list1->n + list2->n <= list1->size)
656 return FN(LIST(EL),concat_inplace)(list1, list2);
657
658 ctx = FN(LIST(EL),get_ctx)(list: list1);
659 res = FN(LIST(EL),alloc)(ctx, n: list1->n + list2->n);
660 for (i = 0; i < list1->n; ++i)
661 res = FN(LIST(EL),add)(list: res, FN(EL,copy)(bmap: list1->p[i]));
662 for (i = 0; i < list2->n; ++i)
663 res = FN(LIST(EL),add)(list: res, FN(EL,copy)(bmap: list2->p[i]));
664
665 FN(LIST(EL),free)(list: list1);
666 FN(LIST(EL),free)(list: list2);
667 return res;
668error:
669 FN(LIST(EL),free)(list: list1);
670 FN(LIST(EL),free)(list: list2);
671 return NULL;
672}
673
674__isl_give isl_printer *CAT(isl_printer_print_,LIST(EL_BASE))(
675 __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
676{
677 int i;
678
679 if (!p || !list)
680 goto error;
681 p = isl_printer_print_str(p, s: "(");
682 for (i = 0; i < list->n; ++i) {
683 if (i)
684 p = isl_printer_print_str(p, s: ",");
685 p = CAT(isl_printer_print_,EL_BASE)(printer: p, bmap: list->p[i]);
686 }
687 p = isl_printer_print_str(p, s: ")");
688 return p;
689error:
690 isl_printer_free(printer: p);
691 return NULL;
692}
693
694#undef BASE
695#define BASE LIST(EL_BASE)
696
697#define PRINT_DUMP_DEFAULT 0
698#include "print_templ.c"
699#undef PRINT_DUMP_DEFAULT
700

source code of polly/lib/External/isl/isl_list_templ.c