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 #include <isl_list_macro.h>
  21
  22 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  23 #define S(TYPE,NAME) xS(TYPE,NAME)
  24
  25 isl_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  */
  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  */
 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
 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  */
 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 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, 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
 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  */
 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  */
 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  */
 268 static __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(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  */
 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  */
 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  */
 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  */
 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
 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 /* Replace each element in "list" by the result of calling "fn"
 397  * on the element.
 398  */
 399 __isl_give LIST(EL) *FN(LIST(EL),map)(__isl_keep LIST(EL) *list,
 400         __isl_give EL *(*fn)(__isl_take EL *el, void *user), void *user)
 401 {
 402         int i, n;
 403
 404         if (!list)
 405                 return NULL;
 406
 407         n = list->n;
 408         for (i = 0; i < n; ++i) {
 409                 EL *el = FN(FN(LIST(EL),take),EL_BASE)(list, i);
 410                 if (!el)
 411                         return FN(LIST(EL),free)(list);
 412                 el = fn(el, user);
 413                 list = FN(FN(LIST(EL),restore),EL_BASE)(list, i, el);
 414         }
 415
 416         return list;
 417 }
 418
 419 /* Internal data structure for isl_*_list_sort.
 420  *
 421  * "cmp" is the original comparison function.
 422  * "user" is a user provided pointer that should be passed to "cmp".
 423  */
 424 S(LIST(EL),sort_data) {
 425         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 426         void *user;
 427 };
 428
 429 /* Compare two entries of an isl_*_list based on the user provided
 430  * comparison function on pairs of isl_* objects.
 431  */
 432 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
 433 {
 434         S(LIST(EL),sort_data) *data = user;
 435         EL * const *el1 = a;
 436         EL * const *el2 = b;
 437
 438         return data->cmp(*el1, *el2, data->user);
 439 }
 440
 441 /* Sort the elements of "list" in ascending order according to
 442  * comparison function "cmp".
 443  */
 444 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
 445         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
 446 {
 447         S(LIST(EL),sort_data) data = { cmp, user };
 448
 449         if (!list)
 450                 return NULL;
 451         if (list->n <= 1)
 452                 return list;
 453         list = FN(LIST(EL),cow)(list);
 454         if (!list)
 455                 return NULL;
 456
 457         if (isl_sort(list->p, list->n, sizeof(list->p[0]),
 458                         &FN(LIST(EL),cmp), &data) < 0)
 459                 return FN(LIST(EL),free)(list);
 460
 461         return list;
 462 }
 463
 464 /* Internal data structure for isl_*_list_foreach_scc.
 465  *
 466  * "list" is the original list.
 467  * "follows" is the user provided callback that defines the edges of the graph.
 468  */
 469 S(LIST(EL),foreach_scc_data) {
 470         LIST(EL) *list;
 471         isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 472         void *follows_user;
 473 };
 474
 475 /* Does element i of data->list follow element j?
 476  *
 477  * Use the user provided callback to find out.
 478  */
 479 static isl_bool FN(LIST(EL),follows)(int i, int j, void *user)
 480 {
 481         S(LIST(EL),foreach_scc_data) *data = user;
 482
 483         return data->follows(data->list->p[i], data->list->p[j],
 484                                 data->follows_user);
 485 }
 486
 487 /* Call "fn" on the sublist of "list" that consists of the elements
 488  * with indices specified by the "n" elements of "pos".
 489  */
 490 static isl_stat FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos,
 491         int n, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
 492 {
 493         int i;
 494         isl_ctx *ctx;
 495         LIST(EL) *slice;
 496
 497         ctx = FN(LIST(EL),get_ctx)(list);
 498         slice = FN(LIST(EL),alloc)(ctx, n);
 499         for (i = 0; i < n; ++i) {
 500                 EL *el;
 501
 502                 el = FN(EL,copy)(list->p[pos[i]]);
 503                 slice = FN(LIST(EL),add)(slice, el);
 504         }
 505
 506         return fn(slice, user);
 507 }
 508
 509 /* Call "fn" on each of the strongly connected components (SCCs) of
 510  * the graph with as vertices the elements of "list" and
 511  * a directed edge from node b to node a iff follows(a, b)
 512  * returns 1.  follows should return -1 on error.
 513  *
 514  * If SCC a contains a node i that follows a node j in another SCC b
 515  * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
 516  * after being called on SCC b.
 517  *
 518  * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
 519  * call fn on each of them.
 520  */
 521 isl_stat FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
 522         isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
 523         void *follows_user,
 524         isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
 525 {
 526         S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
 527         int i, n;
 528         isl_ctx *ctx;
 529         struct isl_tarjan_graph *g;
 530
 531         if (!list)
 532                 return isl_stat_error;
 533         if (list->n == 0)
 534                 return isl_stat_ok;
 535         if (list->n == 1)
 536                 return fn(FN(LIST(EL),copy)(list), fn_user);
 537
 538         ctx = FN(LIST(EL),get_ctx)(list);
 539         n = list->n;
 540         g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
 541         if (!g)
 542                 return isl_stat_error;
 543
 544         i = 0;
 545         do {
 546                 int first;
 547
 548                 if (g->order[i] == -1)
 549                         isl_die(ctx, isl_error_internal, "cannot happen",
 550                                 break);
 551                 first = i;
 552                 while (g->order[i] != -1) {
 553                         ++i; --n;
 554                 }
 555                 if (first == 0 && n == 0) {
 556                         isl_tarjan_graph_free(g);
 557                         return fn(FN(LIST(EL),copy)(list), fn_user);
 558                 }
 559                 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
 560                                             fn, fn_user) < 0)
 561                         break;
 562                 ++i;
 563         } while (n);
 564
 565         isl_tarjan_graph_free(g);
 566
 567         return n > 0 ? isl_stat_error : isl_stat_ok;
 568 }
 569
 570 __isl_give LIST(EL) *FN(FN(LIST(EL),from),EL_BASE)(__isl_take EL *el)
 571 {
 572         isl_ctx *ctx;
 573         LIST(EL) *list;
 574
 575         if (!el)
 576                 return NULL;
 577         ctx = FN(EL,get_ctx)(el);
 578         list = FN(LIST(EL),alloc)(ctx, 1);
 579         if (!list)
 580                 goto error;
 581         list = FN(LIST(EL),add)(list, el);
 582         return list;
 583 error:
 584         FN(EL,free)(el);
 585         return NULL;
 586 }
 587
 588 /* Append the elements of "list2" to "list1", where "list1" is known
 589  * to have only a single reference and enough room to hold
 590  * the extra elements.
 591  */
 592 static __isl_give LIST(EL) *FN(LIST(EL),concat_inplace)(
 593         __isl_take LIST(EL) *list1, __isl_take LIST(EL) *list2)
 594 {
 595         int i;
 596
 597         for (i = 0; i < list2->n; ++i)
 598                 list1 = FN(LIST(EL),add)(list1, FN(EL,copy)(list2->p[i]));
 599         FN(LIST(EL),free)(list2);
 600         return list1;
 601 }
 602
 603 /* Concatenate "list1" and "list2".
 604  * If "list1" has only one reference and has enough room
 605  * for the elements of "list2", the add the elements to "list1" itself.
 606  * Otherwise, create a new list to store the result.
 607  */
 608 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
 609         __isl_take LIST(EL) *list2)
 610 {
 611         int i;
 612         isl_ctx *ctx;
 613         LIST(EL) *res;
 614
 615         if (!list1 || !list2)
 616                 goto error;
 617
 618         if (list1->ref == 1 && list1->n + list2->n <= list1->size)
 619                 return FN(LIST(EL),concat_inplace)(list1, list2);
 620
 621         ctx = FN(LIST(EL),get_ctx)(list1);
 622         res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
 623         for (i = 0; i < list1->n; ++i)
 624                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
 625         for (i = 0; i < list2->n; ++i)
 626                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
 627
 628         FN(LIST(EL),free)(list1);
 629         FN(LIST(EL),free)(list2);
 630         return res;
 631 error:
 632         FN(LIST(EL),free)(list1);
 633         FN(LIST(EL),free)(list2);
 634         return NULL;
 635 }
 636
 637 __isl_give isl_printer *CAT(isl_printer_print_,LIST(EL_BASE))(
 638         __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
 639 {
 640         int i;
 641
 642         if (!p || !list)
 643                 goto error;
 644         p = isl_printer_print_str(p, "(");
 645         for (i = 0; i < list->n; ++i) {
 646                 if (i)
 647                         p = isl_printer_print_str(p, ",");
 648                 p = CAT(isl_printer_print_,EL_BASE)(p, list->p[i]);
 649         }
 650         p = isl_printer_print_str(p, ")");
 651         return p;
 652 error:
 653         isl_printer_free(p);
 654         return NULL;
 655 }
 656
 657 #undef BASE
 658 #define BASE LIST(EL_BASE)
 659
 660 #define PRINT_DUMP_DEFAULT      0
 661 #include "print_templ.c"
 662 #undef PRINT_DUMP_DEFAULT