isl_list_templ.c

   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
  31 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
  32 {
  33         return list ? list->ctx : NULL;
  34 }
  35
  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
  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
  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
  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  */
  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  */
 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
 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  */
 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  */
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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  */
 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
 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  */
 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  */
 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
 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
 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 }