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