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 29isl_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 */ 97static __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; 142error: 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 - 1; i >= pos; --i) 196 list->p[i + 1] = list->p[i]; 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; 211error: 212 FN(EL,free)(el); 213 FN(LIST(EL),free)(list); 214 return NULL; 215} 216 217void *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 235int 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; 270error: 271 FN(EL,free)(el); 272 FN(LIST(EL),free)(list); 273 return NULL; 274} 275 276int FN(LIST(EL),foreach)(__isl_keep LIST(EL) *list, 277 int (*fn)(__isl_take EL *el, void *user), void *user) 278{ 279 int i; 280 281 if (!list) 282 return -1; 283 284 for (i = 0; i < list->n; ++i) { 285 EL *el = FN(EL,copy(list->p[i])); 286 if (!el) 287 return -1; 288 if (fn(el, user) < 0) 289 return -1; 290 } 291 292 return 0; 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 */ 300S(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 */ 308static 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 */ 345S(LIST(EL),foreach_scc_data) { 346 LIST(EL) *list; 347 int (*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 */ 355static int 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 */ 366static int FN(LIST(EL),call_on_scc)(__isl_keep LIST(EL) *list, int *pos, int n, 367 int (*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 */ 397int FN(LIST(EL),foreach_scc)(__isl_keep LIST(EL) *list, 398 int (*follows)(__isl_keep EL *a, __isl_keep EL *b, void *user), 399 void *follows_user, 400 int (*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 -1; 409 if (list->n == 0) 410 return 0; 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 -1; 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 ? -1 : 0; 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; 459error: 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; 484error: 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; 505error: 506 isl_printer_free(p); 507 return NULL; 508} 509 510void 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} 523