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  *
   6  * Use of this software is governed by the MIT license
   7  *
   8  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   9  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
  10  * and INRIA Saclay - Ile-de-France, Parc Club Orsay Universite,
  11  * ZAC des vignes, 4 rue Jacques Monod, 91893 Orsay, France
  12  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  13  */
  14
  15 #include <isl_sort.h>
  16 #include <isl_tarjan.h>
  17
  18 #define xCAT(A,B) A ## B
  19 #define CAT(A,B) xCAT(A,B)
  20 #undef EL
  21 #define EL CAT(isl_,BASE)
  22 #define xFN(TYPE,NAME) TYPE ## _ ## NAME
  23 #define FN(TYPE,NAME) xFN(TYPE,NAME)
  24 #define xLIST(EL) EL ## _list
  25 #define LIST(EL) xLIST(EL)
  26 #define xS(TYPE,NAME) struct TYPE ## _ ## NAME
  27 #define S(TYPE,NAME) xS(TYPE,NAME)
  28
  29 isl_ctx *FN(LIST(EL),get_ctx)(__isl_keep LIST(EL) *list)
  30 {
  31         return list ? list->ctx : NULL;
  32 }
  33
  34 __isl_give LIST(EL) *FN(LIST(EL),alloc)(isl_ctx *ctx, int n)
  35 {
  36         LIST(EL) *list;
  37
  38         if (n < 0)
  39                 isl_die(ctx, isl_error_invalid,
  40                         "cannot create list of negative length",
  41                         return NULL);
  42         list = isl_alloc(ctx, LIST(EL),
  43                          sizeof(LIST(EL)) + (n - 1) * sizeof(struct EL *));
  44         if (!list)
  45                 return NULL;
  46
  47         list->ctx = ctx;
  48         isl_ctx_ref(ctx);
  49         list->ref = 1;
  50         list->size = n;
  51         list->n = 0;
  52         return list;
  53 }
  54
  55 __isl_give LIST(EL) *FN(LIST(EL),copy)(__isl_keep LIST(EL) *list)
  56 {
  57         if (!list)
  58                 return NULL;
  59
  60         list->ref++;
  61         return list;
  62 }
  63
  64 __isl_give LIST(EL) *FN(LIST(EL),dup)(__isl_keep LIST(EL) *list)
  65 {
  66         int i;
  67         LIST(EL) *dup;
  68
  69         if (!list)
  70                 return NULL;
  71
  72         dup = FN(LIST(EL),alloc)(FN(LIST(EL),get_ctx)(list), list->n);
  73         if (!dup)
  74                 return NULL;
  75         for (i = 0; i < list->n; ++i)
  76                 dup = FN(LIST(EL),add)(dup, FN(EL,copy)(list->p[i]));
  77         return dup;
  78 }
  79
  80 __isl_give LIST(EL) *FN(LIST(EL),cow)(__isl_take LIST(EL) *list)
  81 {
  82         if (!list)
  83                 return NULL;
  84
  85         if (list->ref == 1)
  86                 return list;
  87         list->ref--;
  88         return FN(LIST(EL),dup)(list);
  89 }
  90
  91 /* Make sure "list" has room for at least "n" more pieces.
  92  *
  93  * If there is only one reference to list, we extend it in place.
  94  * Otherwise, we create a new LIST(EL) and copy the elements.
  95  */
  96 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
  97 {
  98         isl_ctx *ctx;
  99         int i, new_size;
 100         LIST(EL) *res;
 101
 102         if (!list)
 103                 return NULL;
 104         if (list->n + n <= list->size)
 105                 return list;
 106
 107         ctx = FN(LIST(EL),get_ctx)(list);
 108         new_size = ((list->n + n + 1) * 3) / 2;
 109         if (list->ref == 1) {
 110                 res = isl_realloc(ctx, list, LIST(EL),
 111                             sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
 112                 if (!res)
 113                         return FN(LIST(EL),free)(list);
 114                 res->size = new_size;
 115                 return res;
 116         }
 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 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
 130         __isl_take struct EL *el)
 131 {
 132         list = FN(LIST(EL),grow)(list, 1);
 133         if (!list || !el)
 134                 goto error;
 135         list->p[list->n] = el;
 136         list->n++;
 137         return list;
 138 error:
 139         FN(EL,free)(el);
 140         FN(LIST(EL),free)(list);
 141         return NULL;
 142 }
 143
 144 /* Remove the "n" elements starting at "first" from "list".
 145  */
 146 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
 147         unsigned first, unsigned n)
 148 {
 149         int i;
 150
 151         if (!list)
 152                 return NULL;
 153         if (first + n > list->n || first + n < first)
 154                 isl_die(list->ctx, isl_error_invalid,
 155                         "index out of bounds", return FN(LIST(EL),free)(list));
 156         if (n == 0)
 157                 return list;
 158         list = FN(LIST(EL),cow)(list);
 159         if (!list)
 160                 return NULL;
 161         for (i = 0; i < n; ++i)
 162                 FN(EL,free)(list->p[first + i]);
 163         for (i = first; i + n < list->n; ++i)
 164                 list->p[i] = list->p[i + n];
 165         list->n -= n;
 166         return list;
 167 }
 168
 169 /* Insert "el" at position "pos" in "list".
 170  *
 171  * If there is only one reference to "list" and if it already has space
 172  * for one extra element, we insert it directly into "list".
 173  * Otherwise, we create a new list consisting of "el" and copied
 174  * elements from "list".
 175  */
 176 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
 177         unsigned pos, __isl_take struct EL *el)
 178 {
 179         int i;
 180         isl_ctx *ctx;
 181         LIST(EL) *res;
 182
 183         if (!list || !el)
 184                 goto error;
 185         ctx = FN(LIST(EL),get_ctx)(list);
 186         if (pos > list->n)
 187                 isl_die(ctx, isl_error_invalid,
 188                         "index out of bounds", goto error);
 189
 190         if (list->ref == 1 && list->size > list->n) {
 191                 for (i = list->n - 1; i >= pos; --i)
 192                         list->p[i + 1] = list->p[i];
 193                 list->n++;
 194                 list->p[pos] = el;
 195                 return list;
 196         }
 197
 198         res = FN(LIST(EL),alloc)(ctx, list->n + 1);
 199         for (i = 0; i < pos; ++i)
 200                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 201         res = FN(LIST(EL),add)(res, el);
 202         for (i = pos; i < list->n; ++i)
 203                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 204         FN(LIST(EL),free)(list);
 205
 206         return res;
 207 error:
 208         FN(EL,free)(el);
 209         FN(LIST(EL),free)(list);
 210         return NULL;
 211 }
 212
 213 void *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
 214 {
 215         int i;
 216
 217         if (!list)
 218                 return NULL;
 219
 220         if (--list->ref > 0)
 221                 return NULL;
 222
 223         isl_ctx_deref(list->ctx);
 224         for (i = 0; i < list->n; ++i)
 225                 FN(EL,free)(list->p[i]);
 226         free(list);
 227
 228         return NULL;
 229 }
 230
 231 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
 232 {
 233         return list ? list->n : 0;
 234 }
 235
 236 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
 237 {
 238         if (!list)
 239                 return NULL;
 240         if (index < 0 || index >= list->n)
 241                 isl_die(list->ctx, isl_error_invalid,
 242                         "index out of bounds", return NULL);
 243         return FN(EL,copy)(list->p[index]);
 244 }
 245
 246 /* Replace the element at position "index" in "list" by "el".
 247  */
 248 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
 249         int index, __isl_take EL *el)
 250 {
 251         if (!list || !el)
 252                 goto error;
 253         if (index < 0 || index >= list->n)
 254                 isl_die(list->ctx, isl_error_invalid,
 255                         "index out of bounds", goto error);
 256         if (list->p[index] == el) {
 257                 FN(EL,free)(el);
 258                 return list;
 259         }
 260         list = FN(LIST(EL),cow)(list);
 261         if (!list)
 262                 goto error;
 263         FN(EL,free)(list->p[index]);
 264         list->p[index] = el;
 265         return list;
 266 error:
 267         FN(EL,free)(el);
 268         FN(LIST(EL),free)(list);
 269         return NULL;
 270 }
 271
 272 int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
 273         int (*fn)(__isl_take EL *el, void *user), void *user)
 274 {
 275         int i;
 276
 277         if (!list)
 278                 return -1;
 279
 280         for (i = 0; i < list->n; ++i) {
 281                 EL *el = FN(EL,copy(list->p[i]));
 282                 if (!el)
 283                         return -1;
 284                 if (fn(el, user) < 0)
 285                         return -1;
 286         }
 287
 288         return 0;
 289 }
 290
 291 /* Internal data structure for isl_*_list_sort.
 292  *
 293  * "cmp" is the original comparison function.
 294  * "user" is a user provided pointer that should be passed to "cmp".
 295  */
 296 S(LIST(EL),sort_data) {
 297         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 298         void *user;
 299 };
 300
 301 /* Compare two entries of an isl_*_list based on the user provided
 302  * comparison function on pairs of isl_* objects.
 303  */
 304 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
 305 {
 306         S(LIST(EL),sort_data) *data = user;
 307         EL * const *el1 = a;
 308         EL * const *el2 = b;
 309
 310         return data->cmp(*el1, *el2, data->user);
 311 }
 312
 313 /* Sort the elements of "list" in ascending order according to
 314  * comparison function "cmp".
 315  */
 316 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
 317         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
 318 {
 319         S(LIST(EL),sort_data) data = { cmp, user };
 320
 321         if (!list)
 322                 return NULL;
 323         if (list->n <= 1)
 324                 return list;
 325         list = FN(LIST(EL),cow)(list);
 326         if (!list)
 327                 return NULL;
 328
 329         if (isl_sort(list->p, list->n, sizeof(list->p[0]),
 330                         &FN(LIST(EL),cmp), &data) < 0)
 331                 return FN(LIST(EL),free)(list);
 332
 333         return list;
 334 }
 335
 336 /* Internal data structure for isl_*_list_foreach_scc.
 337  *
 338  * "list" is the original list.
 339  * "follows" is the user provided callback that defines the edges of the graph.
 340  */
 341 S(LIST(EL),foreach_scc_data) {
 342         LIST(EL) *list;
 343         int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 344         void *follows_user;
 345 };
 346
 347 /* Does element i of data->list follow element j?
 348  *
 349  * Use the user provided callback to find out.
 350  */
 351 static int FN(LIST(EL),follows)(int i, int j, void *user)
 352 {
 353         S(LIST(EL),foreach_scc_data) *data = user;
 354
 355         return data->follows(data->list->p[i], data->list->p[j],
 356                                 data->follows_user);
 357 }
 358
 359 /* Call "fn" on the sublist of "list" that consists of the elements
 360  * with indices specified by the "n" elements of "pos".
 361  */
 362 static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n,
 363         int (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
 364 {
 365         int i;
 366         isl_ctx *ctx;
 367         LIST(EL) *slice;
 368
 369         ctx = FN(LIST(EL),get_ctx)(list);
 370         slice = FN(LIST(EL),alloc)(ctx, n);
 371         for (i = 0; i < n; ++i) {
 372                 EL *el;
 373
 374                 el = FN(EL,copy)(list->p[pos[i]]);
 375                 slice = FN(LIST(EL),add)(slice, el);
 376         }
 377
 378         return fn(slice, user);
 379 }
 380
 381 /* Call "fn" on each of the strongly connected components (SCCs) of
 382  * the graph with as vertices the elements of "list" and
 383  * a directed edge from node b to node a iff follows(a, b)
 384  * returns 1.  follows should return -1 on error.
 385  *
 386  * If SCC a contains a node i that follows a node j in another SCC b
 387  * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
 388  * after being called on SCC b.
 389  *
 390  * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
 391  * call fn on each of them.
 392  */
 393 int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
 394         int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
 395         void *follows_user,
 396         int (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
 397 {
 398         S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
 399         int i, n;
 400         isl_ctx *ctx;
 401         struct isl_tarjan_graph *g;
 402
 403         if (!list)
 404                 return -1;
 405         if (list->n == 0)
 406                 return 0;
 407         if (list->n == 1)
 408                 return fn(FN(LIST(EL),copy)(list), fn_user);
 409
 410         ctx = FN(LIST(EL),get_ctx)(list);
 411         n = list->n;
 412         g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
 413         if (!g)
 414                 return -1;
 415
 416         i = 0;
 417         do {
 418                 int first;
 419
 420                 if (g->order[i] == -1)
 421                         isl_die(ctx, isl_error_internal, "cannot happen",
 422                                 break);
 423                 first = i;
 424                 while (g->order[i] != -1) {
 425                         ++i; --n;
 426                 }
 427                 if (first == 0 && n == 0) {
 428                         isl_tarjan_graph_free(g);
 429                         return fn(FN(LIST(EL),copy)(list), fn_user);
 430                 }
 431                 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
 432                                             fn, fn_user) < 0)
 433                         break;
 434                 ++i;
 435         } while (n);
 436
 437         isl_tarjan_graph_free(g);
 438
 439         return n > 0 ? -1 : 0;
 440 }
 441
 442 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
 443 {
 444         isl_ctx *ctx;
 445         LIST(EL) *list;
 446
 447         if (!el)
 448                 return NULL;
 449         ctx = FN(EL,get_ctx)(el);
 450         list = FN(LIST(EL),alloc)(ctx, 1);
 451         if (!list)
 452                 goto error;
 453         list = FN(LIST(EL),add)(list, el);
 454         return list;
 455 error:
 456         FN(EL,free)(el);
 457         return NULL;
 458 }
 459
 460 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
 461         __isl_take LIST(EL) *list2)
 462 {
 463         int i;
 464         isl_ctx *ctx;
 465         LIST(EL) *res;
 466
 467         if (!list1 || !list2)
 468                 goto error;
 469
 470         ctx = FN(LIST(EL),get_ctx)(list1);
 471         res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
 472         for (i = 0; i < list1->n; ++i)
 473                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
 474         for (i = 0; i < list2->n; ++i)
 475                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
 476
 477         FN(LIST(EL),free)(list1);
 478         FN(LIST(EL),free)(list2);
 479         return res;
 480 error:
 481         FN(LIST(EL),free)(list1);
 482         FN(LIST(EL),free)(list2);
 483         return NULL;
 484 }
 485
 486 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
 487         __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
 488 {
 489         int i;
 490
 491         if (!p || !list)
 492                 goto error;
 493         p = isl_printer_print_str(p, "(");
 494         for (i = 0; i < list->n; ++i) {
 495                 if (i)
 496                         p = isl_printer_print_str(p, ",");
 497                 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
 498         }
 499         p = isl_printer_print_str(p, ")");
 500         return p;
 501 error:
 502         isl_printer_free(p);
 503         return NULL;
 504 }
 505
 506 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
 507 {
 508         isl_printer *printer;
 509
 510         if (!list)
 511                 return;
 512
 513         printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
 514         printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
 515         printer = isl_printer_end_line(printer);
 516
 517         isl_printer_free(printer);
 518 }