700 lines · c
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2011 INRIA Saclay4 * Copyright 2012-2013 Ecole Normale Superieure5 * Copyright 2017 Sven Verdoolaege6 *7 * Use of this software is governed by the MIT license8 *9 * Written by Sven Verdoolaege, K.U.Leuven, Departement10 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium11 * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,12 * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France13 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France14 */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 ## _ ## NAME23#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), 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 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, 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 */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, 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)(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)(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, 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 space193 * for one extra element, we insert it directly into "list".194 * Otherwise, we create a new list consisting of "el" and copied195 * 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, 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;228error:229 FN(EL,free)(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(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 */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)(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;309error:310 FN(EL,free)(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 itself325 * if there is only one reference to "list".326 * This allows the element to be modified inplace327 * if both the list and the element have only a single reference.328 * The caller is not allowed to modify "list" between329 * this call to isl_list_*_take_* and a subsequent call330 * 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 call349 * 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, pos1);367 el2 = FN(FN(LIST(EL),take),EL_BASE)(list, pos2);368 list = FN(FN(LIST(EL),restore),EL_BASE)(list, pos1, el2);369 list = FN(FN(LIST(EL),restore),EL_BASE)(list, pos2, 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, i, 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)(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, 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, 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 provided459 * 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 to471 * 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(list->p, list->n, sizeof(list->p[0]),487 &FN(LIST(EL),cmp), &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 elements517 * 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)(list->p[pos[i]]);532 slice = FN(LIST(EL),add)(slice, el);533 }534 535 return fn(slice, user);536}537 538/* Call "fn" on each of the strongly connected components (SCCs) of539 * the graph with as vertices the elements of "list" and540 * 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 b544 * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a545 * after being called on SCC b.546 *547 * We simply call isl_tarjan_graph_init, extract the SCCs from the result and548 * 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, n, &FN(LIST(EL),follows), &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, g->order + first, i - first,589 fn, 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)(el);607 list = FN(LIST(EL),alloc)(ctx, 1);608 if (!list)609 goto error;610 list = FN(LIST(EL),add)(list, el);611 return list;612error:613 FN(EL,free)(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 known626 * to have only a single reference and enough room to hold627 * 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)(list1, FN(EL,copy)(list2->p[i]));636 FN(LIST(EL),free)(list2);637 return list1;638}639 640/* Concatenate "list1" and "list2".641 * If "list1" has only one reference and has enough room642 * 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)(list1);659 res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);660 for (i = 0; i < list1->n; ++i)661 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));662 for (i = 0; i < list2->n; ++i)663 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));664 665 FN(LIST(EL),free)(list1);666 FN(LIST(EL),free)(list2);667 return res;668error:669 FN(LIST(EL),free)(list1);670 FN(LIST(EL),free)(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, "(");682 for (i = 0; i < list->n; ++i) {683 if (i)684 p = isl_printer_print_str(p, ",");685 p = CAT(isl_printer_print_,EL_BASE)(p, list->p[i]);686 }687 p = isl_printer_print_str(p, ")");688 return p;689error:690 isl_printer_free(p);691 return NULL;692}693 694#undef BASE695#define BASE LIST(EL_BASE)696 697#define PRINT_DUMP_DEFAULT 0698#include "print_templ.c"699#undef PRINT_DUMP_DEFAULT700