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  * Always return a list with a single reference.
  93  *
  94  * If there is only one reference to list, we extend it in place.
  95  * Otherwise, we create a new LIST(EL) and copy the elements.
  96  */
  97 static __isl_give LIST(EL) *FN(LIST(EL),grow)(__isl_take LIST(EL) *list, int n)
  98 {
  99         isl_ctx *ctx;
 100         int i, new_size;
 101         LIST(EL) *res;
 102
 103         if (!list)
 104                 return NULL;
 105         if (list->ref == 1 && list->n + n <= list->size)
 106                 return list;
 107
 108         ctx = FN(LIST(EL),get_ctx)(list);
 109         new_size = ((list->n + n + 1) * 3) / 2;
 110         if (list->ref == 1) {
 111                 res = isl_realloc(ctx, list, LIST(EL),
 112                             sizeof(LIST(EL)) + (new_size - 1) * sizeof(EL *));
 113                 if (!res)
 114                         return FN(LIST(EL),free)(list);
 115                 res->size = new_size;
 116                 return res;
 117         }
 118
 119         if (list->n + n <= list->size && list->size < new_size)
 120                 new_size = list->size;
 121
 122         res = FN(LIST(EL),alloc)(ctx, new_size);
 123         if (!res)
 124                 return FN(LIST(EL),free)(list);
 125
 126         for (i = 0; i < list->n; ++i)
 127                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 128
 129         FN(LIST(EL),free)(list);
 130         return res;
 131 }
 132
 133 __isl_give LIST(EL) *FN(LIST(EL),add)(__isl_take LIST(EL) *list,
 134         __isl_take struct EL *el)
 135 {
 136         list = FN(LIST(EL),grow)(list, 1);
 137         if (!list || !el)
 138                 goto error;
 139         list->p[list->n] = el;
 140         list->n++;
 141         return list;
 142 error:
 143         FN(EL,free)(el);
 144         FN(LIST(EL),free)(list);
 145         return NULL;
 146 }
 147
 148 /* Remove the "n" elements starting at "first" from "list".
 149  */
 150 __isl_give LIST(EL) *FN(LIST(EL),drop)(__isl_take LIST(EL) *list,
 151         unsigned first, unsigned n)
 152 {
 153         int i;
 154
 155         if (!list)
 156                 return NULL;
 157         if (first + n > list->n || first + n < first)
 158                 isl_die(list->ctx, isl_error_invalid,
 159                         "index out of bounds", return FN(LIST(EL),free)(list));
 160         if (n == 0)
 161                 return list;
 162         list = FN(LIST(EL),cow)(list);
 163         if (!list)
 164                 return NULL;
 165         for (i = 0; i < n; ++i)
 166                 FN(EL,free)(list->p[first + i]);
 167         for (i = first; i + n < list->n; ++i)
 168                 list->p[i] = list->p[i + n];
 169         list->n -= n;
 170         return list;
 171 }
 172
 173 /* Insert "el" at position "pos" in "list".
 174  *
 175  * If there is only one reference to "list" and if it already has space
 176  * for one extra element, we insert it directly into "list".
 177  * Otherwise, we create a new list consisting of "el" and copied
 178  * elements from "list".
 179  */
 180 __isl_give LIST(EL) *FN(LIST(EL),insert)(__isl_take LIST(EL) *list,
 181         unsigned pos, __isl_take struct EL *el)
 182 {
 183         int i;
 184         isl_ctx *ctx;
 185         LIST(EL) *res;
 186
 187         if (!list || !el)
 188                 goto error;
 189         ctx = FN(LIST(EL),get_ctx)(list);
 190         if (pos > list->n)
 191                 isl_die(ctx, isl_error_invalid,
 192                         "index out of bounds", goto error);
 193
 194         if (list->ref == 1 && list->size > list->n) {
 195                 for (i = list->n; i > pos; --i)
 196                         list->p[i] = list->p[i - 1];
 197                 list->n++;
 198                 list->p[pos] = el;
 199                 return list;
 200         }
 201
 202         res = FN(LIST(EL),alloc)(ctx, list->n + 1);
 203         for (i = 0; i < pos; ++i)
 204                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 205         res = FN(LIST(EL),add)(res, el);
 206         for (i = pos; i < list->n; ++i)
 207                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list->p[i]));
 208         FN(LIST(EL),free)(list);
 209
 210         return res;
 211 error:
 212         FN(EL,free)(el);
 213         FN(LIST(EL),free)(list);
 214         return NULL;
 215 }
 216
 217 __isl_null LIST(EL) *FN(LIST(EL),free)(__isl_take LIST(EL) *list)
 218 {
 219         int i;
 220
 221         if (!list)
 222                 return NULL;
 223
 224         if (--list->ref > 0)
 225                 return NULL;
 226
 227         isl_ctx_deref(list->ctx);
 228         for (i = 0; i < list->n; ++i)
 229                 FN(EL,free)(list->p[i]);
 230         free(list);
 231
 232         return NULL;
 233 }
 234
 235 int FN(FN(LIST(EL),n),BASE)(__isl_keep LIST(EL) *list)
 236 {
 237         return list ? list->n : 0;
 238 }
 239
 240 __isl_give EL *FN(FN(LIST(EL),get),BASE)(__isl_keep LIST(EL) *list, int index)
 241 {
 242         if (!list)
 243                 return NULL;
 244         if (index < 0 || index >= list->n)
 245                 isl_die(list->ctx, isl_error_invalid,
 246                         "index out of bounds", return NULL);
 247         return FN(EL,copy)(list->p[index]);
 248 }
 249
 250 /* Replace the element at position "index" in "list" by "el".
 251  */
 252 __isl_give LIST(EL) *FN(FN(LIST(EL),set),BASE)(__isl_take LIST(EL) *list,
 253         int index, __isl_take EL *el)
 254 {
 255         if (!list || !el)
 256                 goto error;
 257         if (index < 0 || index >= list->n)
 258                 isl_die(list->ctx, isl_error_invalid,
 259                         "index out of bounds", goto error);
 260         if (list->p[index] == el) {
 261                 FN(EL,free)(el);
 262                 return list;
 263         }
 264         list = FN(LIST(EL),cow)(list);
 265         if (!list)
 266                 goto error;
 267         FN(EL,free)(list->p[index]);
 268         list->p[index] = el;
 269         return list;
 270 error:
 271         FN(EL,free)(el);
 272         FN(LIST(EL),free)(list);
 273         return NULL;
 274 }
 275
 276 isl_stat FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list,
 277         isl_stat (*fn)(__isl_take EL *el, void *user), void *user)
 278 {
 279         int i;
 280
 281         if (!list)
 282                 return isl_stat_error;
 283
 284         for (i = 0; i < list->n; ++i) {
 285                 EL *el = FN(EL,copy(list->p[i]));
 286                 if (!el)
 287                         return isl_stat_error;
 288                 if (fn(el, user) < 0)
 289                         return isl_stat_error;
 290         }
 291
 292         return isl_stat_ok;
 293 }
 294
 295 /* Internal data structure for isl_*_list_sort.
 296  *
 297  * "cmp" is the original comparison function.
 298  * "user" is a user provided pointer that should be passed to "cmp".
 299  */
 300 S(LIST(EL),sort_data) {
 301         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 302         void *user;
 303 };
 304
 305 /* Compare two entries of an isl_*_list based on the user provided
 306  * comparison function on pairs of isl_* objects.
 307  */
 308 static int FN(LIST(EL),cmp)(const void *a, const void *b, void *user)
 309 {
 310         S(LIST(EL),sort_data) *data = user;
 311         EL * const *el1 = a;
 312         EL * const *el2 = b;
 313
 314         return data->cmp(*el1, *el2, data->user);
 315 }
 316
 317 /* Sort the elements of "list" in ascending order according to
 318  * comparison function "cmp".
 319  */
 320 __isl_give LIST(EL) *FN(LIST(EL),sort)(__isl_take LIST(EL) *list,
 321         int (*cmp)(__isl_keep EL *a, __isl_keep EL *b, void *user), void *user)
 322 {
 323         S(LIST(EL),sort_data) data = { cmp, user };
 324
 325         if (!list)
 326                 return NULL;
 327         if (list->n <= 1)
 328                 return list;
 329         list = FN(LIST(EL),cow)(list);
 330         if (!list)
 331                 return NULL;
 332
 333         if (isl_sort(list->p, list->n, sizeof(list->p[0]),
 334                         &FN(LIST(EL),cmp), &data) < 0)
 335                 return FN(LIST(EL),free)(list);
 336
 337         return list;
 338 }
 339
 340 /* Internal data structure for isl_*_list_foreach_scc.
 341  *
 342  * "list" is the original list.
 343  * "follows" is the user provided callback that defines the edges of the graph.
 344  */
 345 S(LIST(EL),foreach_scc_data) {
 346         LIST(EL) *list;
 347         isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user);
 348         void *follows_user;
 349 };
 350
 351 /* Does element i of data->list follow element j?
 352  *
 353  * Use the user provided callback to find out.
 354  */
 355 static isl_bool FN(LIST(EL),follows)(int i, int j, void *user)
 356 {
 357         S(LIST(EL),foreach_scc_data) *data = user;
 358
 359         return data->follows(data->list->p[i], data->list->p[j],
 360                                 data->follows_user);
 361 }
 362
 363 /* Call "fn" on the sublist of "list" that consists of the elements
 364  * with indices specified by the "n" elements of "pos".
 365  */
 366 static isl_stat FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos,
 367         int n, isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *user)
 368 {
 369         int i;
 370         isl_ctx *ctx;
 371         LIST(EL) *slice;
 372
 373         ctx = FN(LIST(EL),get_ctx)(list);
 374         slice = FN(LIST(EL),alloc)(ctx, n);
 375         for (i = 0; i < n; ++i) {
 376                 EL *el;
 377
 378                 el = FN(EL,copy)(list->p[pos[i]]);
 379                 slice = FN(LIST(EL),add)(slice, el);
 380         }
 381
 382         return fn(slice, user);
 383 }
 384
 385 /* Call "fn" on each of the strongly connected components (SCCs) of
 386  * the graph with as vertices the elements of "list" and
 387  * a directed edge from node b to node a iff follows(a, b)
 388  * returns 1.  follows should return -1 on error.
 389  *
 390  * If SCC a contains a node i that follows a node j in another SCC b
 391  * (i.e., follows(i, j, user) returns 1), then fn will be called on SCC a
 392  * after being called on SCC b.
 393  *
 394  * We simply call isl_tarjan_graph_init, extract the SCCs from the result and
 395  * call fn on each of them.
 396  */
 397 isl_stat FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list,
 398         isl_bool (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user),
 399         void *follows_user,
 400         isl_stat (*fn)(__isl_take LIST(EL) *scc, void *user), void *fn_user)
 401 {
 402         S(LIST(EL),foreach_scc_data) data = { list, follows, follows_user };
 403         int i, n;
 404         isl_ctx *ctx;
 405         struct isl_tarjan_graph *g;
 406
 407         if (!list)
 408                 return isl_stat_error;
 409         if (list->n == 0)
 410                 return isl_stat_ok;
 411         if (list->n == 1)
 412                 return fn(FN(LIST(EL),copy)(list), fn_user);
 413
 414         ctx = FN(LIST(EL),get_ctx)(list);
 415         n = list->n;
 416         g = isl_tarjan_graph_init(ctx, n, &FN(LIST(EL),follows), &data);
 417         if (!g)
 418                 return isl_stat_error;
 419
 420         i = 0;
 421         do {
 422                 int first;
 423
 424                 if (g->order[i] == -1)
 425                         isl_die(ctx, isl_error_internal, "cannot happen",
 426                                 break);
 427                 first = i;
 428                 while (g->order[i] != -1) {
 429                         ++i; --n;
 430                 }
 431                 if (first == 0 && n == 0) {
 432                         isl_tarjan_graph_free(g);
 433                         return fn(FN(LIST(EL),copy)(list), fn_user);
 434                 }
 435                 if (FN(LIST(EL),call_on_scc)(list, g->order + first, i - first,
 436                                             fn, fn_user) < 0)
 437                         break;
 438                 ++i;
 439         } while (n);
 440
 441         isl_tarjan_graph_free(g);
 442
 443         return n > 0 ? isl_stat_error : isl_stat_ok;
 444 }
 445
 446 __isl_give LIST(EL) *FN(FN(LIST(EL),from),BASE)(__isl_take EL *el)
 447 {
 448         isl_ctx *ctx;
 449         LIST(EL) *list;
 450
 451         if (!el)
 452                 return NULL;
 453         ctx = FN(EL,get_ctx)(el);
 454         list = FN(LIST(EL),alloc)(ctx, 1);
 455         if (!list)
 456                 goto error;
 457         list = FN(LIST(EL),add)(list, el);
 458         return list;
 459 error:
 460         FN(EL,free)(el);
 461         return NULL;
 462 }
 463
 464 __isl_give LIST(EL) *FN(LIST(EL),concat)(__isl_take LIST(EL) *list1,
 465         __isl_take LIST(EL) *list2)
 466 {
 467         int i;
 468         isl_ctx *ctx;
 469         LIST(EL) *res;
 470
 471         if (!list1 || !list2)
 472                 goto error;
 473
 474         ctx = FN(LIST(EL),get_ctx)(list1);
 475         res = FN(LIST(EL),alloc)(ctx, list1->n + list2->n);
 476         for (i = 0; i < list1->n; ++i)
 477                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list1->p[i]));
 478         for (i = 0; i < list2->n; ++i)
 479                 res = FN(LIST(EL),add)(res, FN(EL,copy)(list2->p[i]));
 480
 481         FN(LIST(EL),free)(list1);
 482         FN(LIST(EL),free)(list2);
 483         return res;
 484 error:
 485         FN(LIST(EL),free)(list1);
 486         FN(LIST(EL),free)(list2);
 487         return NULL;
 488 }
 489
 490 __isl_give isl_printer *CAT(isl_printer_print_,LIST(BASE))(
 491         __isl_take isl_printer *p, __isl_keep LIST(EL) *list)
 492 {
 493         int i;
 494
 495         if (!p || !list)
 496                 goto error;
 497         p = isl_printer_print_str(p, "(");
 498         for (i = 0; i < list->n; ++i) {
 499                 if (i)
 500                         p = isl_printer_print_str(p, ",");
 501                 p = CAT(isl_printer_print_,BASE)(p, list->p[i]);
 502         }
 503         p = isl_printer_print_str(p, ")");
 504         return p;
 505 error:
 506         isl_printer_free(p);
 507         return NULL;
 508 }
 509
 510 void FN(LIST(EL),dump)(__isl_keep LIST(EL) *list)
 511 {
 512         isl_printer *printer;
 513
 514         if (!list)
 515                 return;
 516
 517         printer = isl_printer_to_file(FN(LIST(EL),get_ctx)(list), stderr);
 518         printer = CAT(isl_printer_print_,LIST(BASE))(printer, list);
 519         printer = isl_printer_end_line(printer);
 520
 521         isl_printer_free(printer);
 522 }