686 lines · c
1/*2 * Copyright 2008-2009 Katholieke Universiteit Leuven3 * Copyright 2011 Sven Verdoolaege4 * Copyright 2013 Ecole Normale Superieure5 *6 * Use of this software is governed by the MIT license7 *8 * Written by Sven Verdoolaege, K.U.Leuven, Departement9 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France11 */12 13#include <isl_ctx_private.h>14#include <isl_seq.h>15#include <isl_val_private.h>16#include <isl_vec_private.h>17 18isl_ctx *isl_vec_get_ctx(__isl_keep isl_vec *vec)19{20 return vec ? vec->ctx : NULL;21}22 23/* Return a hash value that digests "vec".24 */25uint32_t isl_vec_get_hash(__isl_keep isl_vec *vec)26{27 if (!vec)28 return 0;29 30 return isl_seq_get_hash(vec->el, vec->size);31}32 33__isl_give isl_vec *isl_vec_alloc(struct isl_ctx *ctx, unsigned size)34{35 struct isl_vec *vec;36 37 vec = isl_alloc_type(ctx, struct isl_vec);38 if (!vec)39 return NULL;40 41 vec->block = isl_blk_alloc(ctx, size);42 if (isl_blk_is_error(vec->block))43 goto error;44 45 vec->ctx = ctx;46 isl_ctx_ref(ctx);47 vec->ref = 1;48 vec->size = size;49 vec->el = vec->block.data;50 51 return vec;52error:53 isl_blk_free(ctx, vec->block);54 free(vec);55 return NULL;56}57 58__isl_give isl_vec *isl_vec_extend(__isl_take isl_vec *vec, unsigned size)59{60 if (!vec)61 return NULL;62 if (size <= vec->size)63 return vec;64 65 vec = isl_vec_cow(vec);66 if (!vec)67 return NULL;68 69 vec->block = isl_blk_extend(vec->ctx, vec->block, size);70 if (!vec->block.data)71 goto error;72 73 vec->size = size;74 vec->el = vec->block.data;75 76 return vec;77error:78 isl_vec_free(vec);79 return NULL;80}81 82/* Apply the expansion specified by "exp" to the "n" elements starting at "pos".83 * "expanded" it the number of elements that need to replace those "n"84 * elements. The entries in "exp" have increasing values between85 * 0 and "expanded".86 */87__isl_give isl_vec *isl_vec_expand(__isl_take isl_vec *vec, int pos, int n,88 int *exp, int expanded)89{90 int i, j;91 int old_size, extra;92 93 if (!vec)94 return NULL;95 if (expanded < n)96 isl_die(isl_vec_get_ctx(vec), isl_error_invalid,97 "not an expansion", return isl_vec_free(vec));98 if (expanded == n)99 return vec;100 if (pos < 0 || n < 0 || pos + n > vec->size)101 isl_die(isl_vec_get_ctx(vec), isl_error_invalid,102 "position out of bounds", return isl_vec_free(vec));103 104 old_size = vec->size;105 extra = expanded - n;106 vec = isl_vec_extend(vec, old_size + extra);107 vec = isl_vec_cow(vec);108 if (!vec)109 return NULL;110 111 for (i = old_size - 1; i >= pos + n; --i)112 isl_int_set(vec->el[i + extra], vec->el[i]);113 114 j = n - 1;115 for (i = expanded - 1; i >= 0; --i) {116 if (j >= 0 && exp[j] == i) {117 if (i != j)118 isl_int_swap(vec->el[pos + i],119 vec->el[pos + j]);120 j--;121 } else {122 isl_int_set_si(vec->el[pos + i], 0);123 }124 }125 126 return vec;127}128 129/* Create a vector of size "size" with zero-valued elements.130 */131__isl_give isl_vec *isl_vec_zero(isl_ctx *ctx, unsigned size)132{133 isl_vec *vec;134 135 vec = isl_vec_alloc(ctx, size);136 if (!vec)137 return NULL;138 isl_seq_clr(vec->el, size);139 return vec;140}141 142__isl_give isl_vec *isl_vec_zero_extend(__isl_take isl_vec *vec, unsigned size)143{144 int extra;145 146 if (!vec)147 return NULL;148 if (size <= vec->size)149 return vec;150 151 vec = isl_vec_cow(vec);152 if (!vec)153 return NULL;154 155 extra = size - vec->size;156 vec = isl_vec_extend(vec, size);157 if (!vec)158 return NULL;159 160 isl_seq_clr(vec->el + size - extra, extra);161 162 return vec;163}164 165/* Return a vector containing the elements of "vec1" followed by166 * those of "vec2".167 */168__isl_give isl_vec *isl_vec_concat(__isl_take isl_vec *vec1,169 __isl_take isl_vec *vec2)170{171 if (!vec1 || !vec2)172 goto error;173 174 if (vec2->size == 0) {175 isl_vec_free(vec2);176 return vec1;177 }178 179 if (vec1->size == 0) {180 isl_vec_free(vec1);181 return vec2;182 }183 184 vec1 = isl_vec_extend(vec1, vec1->size + vec2->size);185 if (!vec1)186 goto error;187 188 isl_seq_cpy(vec1->el + vec1->size - vec2->size, vec2->el, vec2->size);189 190 isl_vec_free(vec2);191 return vec1;192error:193 isl_vec_free(vec1);194 isl_vec_free(vec2);195 return NULL;196}197 198__isl_give isl_vec *isl_vec_copy(__isl_keep isl_vec *vec)199{200 if (!vec)201 return NULL;202 203 vec->ref++;204 return vec;205}206 207__isl_give isl_vec *isl_vec_dup(__isl_keep isl_vec *vec)208{209 struct isl_vec *vec2;210 211 if (!vec)212 return NULL;213 vec2 = isl_vec_alloc(vec->ctx, vec->size);214 if (!vec2)215 return NULL;216 isl_seq_cpy(vec2->el, vec->el, vec->size);217 return vec2;218}219 220__isl_give isl_vec *isl_vec_cow(__isl_take isl_vec *vec)221{222 struct isl_vec *vec2;223 if (!vec)224 return NULL;225 226 if (vec->ref == 1)227 return vec;228 229 vec2 = isl_vec_dup(vec);230 isl_vec_free(vec);231 return vec2;232}233 234__isl_null isl_vec *isl_vec_free(__isl_take isl_vec *vec)235{236 if (!vec)237 return NULL;238 239 if (--vec->ref > 0)240 return NULL;241 242 isl_ctx_deref(vec->ctx);243 isl_blk_free(vec->ctx, vec->block);244 free(vec);245 246 return NULL;247}248 249isl_size isl_vec_size(__isl_keep isl_vec *vec)250{251 return vec ? vec->size : isl_size_error;252}253 254/* Extract the element at position "pos" of "vec".255 */256__isl_give isl_val *isl_vec_get_element_val(__isl_keep isl_vec *vec, int pos)257{258 isl_ctx *ctx;259 260 if (!vec)261 return NULL;262 ctx = isl_vec_get_ctx(vec);263 if (pos < 0 || pos >= vec->size)264 isl_die(ctx, isl_error_invalid, "position out of range",265 return NULL);266 return isl_val_int_from_isl_int(ctx, vec->el[pos]);267}268 269__isl_give isl_vec *isl_vec_set_element(__isl_take isl_vec *vec,270 int pos, isl_int v)271{272 vec = isl_vec_cow(vec);273 if (!vec)274 return NULL;275 if (pos < 0 || pos >= vec->size)276 isl_die(vec->ctx, isl_error_invalid, "position out of range",277 goto error);278 isl_int_set(vec->el[pos], v);279 return vec;280error:281 isl_vec_free(vec);282 return NULL;283}284 285__isl_give isl_vec *isl_vec_set_element_si(__isl_take isl_vec *vec,286 int pos, int v)287{288 vec = isl_vec_cow(vec);289 if (!vec)290 return NULL;291 if (pos < 0 || pos >= vec->size)292 isl_die(vec->ctx, isl_error_invalid, "position out of range",293 goto error);294 isl_int_set_si(vec->el[pos], v);295 return vec;296error:297 isl_vec_free(vec);298 return NULL;299}300 301/* Replace the element at position "pos" of "vec" by "v".302 */303__isl_give isl_vec *isl_vec_set_element_val(__isl_take isl_vec *vec,304 int pos, __isl_take isl_val *v)305{306 if (!v)307 return isl_vec_free(vec);308 if (!isl_val_is_int(v))309 isl_die(isl_val_get_ctx(v), isl_error_invalid,310 "expecting integer value", goto error);311 vec = isl_vec_set_element(vec, pos, v->n);312 isl_val_free(v);313 return vec;314error:315 isl_val_free(v);316 return isl_vec_free(vec);317}318 319/* Compare the elements of "vec1" and "vec2" at position "pos".320 */321int isl_vec_cmp_element(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2,322 int pos)323{324 if (!vec1 || !vec2)325 return 0;326 if (pos < 0 || pos >= vec1->size || pos >= vec2->size)327 isl_die(isl_vec_get_ctx(vec1), isl_error_invalid,328 "position out of range", return 0);329 return isl_int_cmp(vec1->el[pos], vec2->el[pos]);330}331 332/* Does "vec" contain only zero elements?333 */334isl_bool isl_vec_is_zero(__isl_keep isl_vec *vec)335{336 if (!vec)337 return isl_bool_error;338 return isl_bool_ok(isl_seq_first_non_zero(vec->el, vec->size) < 0);339}340 341isl_bool isl_vec_is_equal(__isl_keep isl_vec *vec1, __isl_keep isl_vec *vec2)342{343 if (!vec1 || !vec2)344 return isl_bool_error;345 346 if (vec1->size != vec2->size)347 return isl_bool_false;348 349 return isl_bool_ok(isl_seq_eq(vec1->el, vec2->el, vec1->size));350}351 352__isl_give isl_printer *isl_printer_print_vec(__isl_take isl_printer *printer,353 __isl_keep isl_vec *vec)354{355 int i;356 357 if (!printer || !vec)358 goto error;359 360 printer = isl_printer_print_str(printer, "[");361 for (i = 0; i < vec->size; ++i) {362 if (i)363 printer = isl_printer_print_str(printer, ",");364 printer = isl_printer_print_isl_int(printer, vec->el[i]);365 }366 printer = isl_printer_print_str(printer, "]");367 368 return printer;369error:370 isl_printer_free(printer);371 return NULL;372}373 374void isl_vec_dump(__isl_keep isl_vec *vec)375{376 isl_printer *printer;377 378 if (!vec)379 return;380 381 printer = isl_printer_to_file(vec->ctx, stderr);382 printer = isl_printer_print_vec(printer, vec);383 printer = isl_printer_end_line(printer);384 385 isl_printer_free(printer);386}387 388__isl_give isl_vec *isl_vec_set(__isl_take isl_vec *vec, isl_int v)389{390 vec = isl_vec_cow(vec);391 if (!vec)392 return NULL;393 isl_seq_set(vec->el, v, vec->size);394 return vec;395}396 397__isl_give isl_vec *isl_vec_set_si(__isl_take isl_vec *vec, int v)398{399 vec = isl_vec_cow(vec);400 if (!vec)401 return NULL;402 isl_seq_set_si(vec->el, v, vec->size);403 return vec;404}405 406/* Replace all elements of "vec" by "v".407 */408__isl_give isl_vec *isl_vec_set_val(__isl_take isl_vec *vec,409 __isl_take isl_val *v)410{411 vec = isl_vec_cow(vec);412 if (!vec || !v)413 goto error;414 if (!isl_val_is_int(v))415 isl_die(isl_val_get_ctx(v), isl_error_invalid,416 "expecting integer value", goto error);417 isl_seq_set(vec->el, v->n, vec->size);418 isl_val_free(v);419 return vec;420error:421 isl_vec_free(vec);422 isl_val_free(v);423 return NULL;424}425 426__isl_give isl_vec *isl_vec_clr(__isl_take isl_vec *vec)427{428 vec = isl_vec_cow(vec);429 if (!vec)430 return NULL;431 isl_seq_clr(vec->el, vec->size);432 return vec;433}434 435void isl_vec_lcm(__isl_keep isl_vec *vec, isl_int *lcm)436{437 isl_seq_lcm(vec->block.data, vec->size, lcm);438}439 440/* Given a rational vector, with the denominator in the first element441 * of the vector, round up all coordinates.442 */443__isl_give isl_vec *isl_vec_ceil(__isl_take isl_vec *vec)444{445 vec = isl_vec_cow(vec);446 if (!vec)447 return NULL;448 449 isl_seq_cdiv_q(vec->el + 1, vec->el + 1, vec->el[0], vec->size - 1);450 451 isl_int_set_si(vec->el[0], 1);452 453 return vec;454}455 456__isl_give isl_vec *isl_vec_normalize(__isl_take isl_vec *vec)457{458 if (!vec)459 return NULL;460 isl_seq_normalize(vec->ctx, vec->el, vec->size);461 return vec;462}463 464__isl_give isl_vec *isl_vec_neg(__isl_take isl_vec *vec)465{466 vec = isl_vec_cow(vec);467 if (!vec)468 return NULL;469 isl_seq_neg(vec->el, vec->el, vec->size);470 return vec;471}472 473__isl_give isl_vec *isl_vec_scale(__isl_take isl_vec *vec, isl_int m)474{475 if (isl_int_is_one(m))476 return vec;477 vec = isl_vec_cow(vec);478 if (!vec)479 return NULL;480 isl_seq_scale(vec->el, vec->el, m, vec->size);481 return vec;482}483 484/* Reduce the elements of "vec" modulo "m".485 */486__isl_give isl_vec *isl_vec_fdiv_r(__isl_take isl_vec *vec, isl_int m)487{488 vec = isl_vec_cow(vec);489 if (!vec)490 return NULL;491 492 isl_seq_fdiv_r(vec->el, vec->el, m, vec->size);493 494 return vec;495}496 497__isl_give isl_vec *isl_vec_add(__isl_take isl_vec *vec1,498 __isl_take isl_vec *vec2)499{500 vec1 = isl_vec_cow(vec1);501 if (!vec1 || !vec2)502 goto error;503 504 isl_assert(vec1->ctx, vec1->size == vec2->size, goto error);505 506 isl_seq_combine(vec1->el, vec1->ctx->one, vec1->el,507 vec1->ctx->one, vec2->el, vec1->size);508 509 isl_vec_free(vec2);510 return vec1;511error:512 isl_vec_free(vec1);513 isl_vec_free(vec2);514 return NULL;515}516 517static int qsort_int_cmp(const void *p1, const void *p2)518{519 const isl_int *i1 = (const isl_int *) p1;520 const isl_int *i2 = (const isl_int *) p2;521 522 return isl_int_cmp(*i1, *i2);523}524 525__isl_give isl_vec *isl_vec_sort(__isl_take isl_vec *vec)526{527 if (!vec)528 return NULL;529 530 qsort(vec->el, vec->size, sizeof(*vec->el), &qsort_int_cmp);531 532 return vec;533}534 535__isl_give isl_vec *isl_vec_drop_els(__isl_take isl_vec *vec,536 unsigned pos, unsigned n)537{538 if (n == 0)539 return vec;540 vec = isl_vec_cow(vec);541 if (!vec)542 return NULL;543 544 if (pos + n > vec->size)545 isl_die(vec->ctx, isl_error_invalid,546 "range out of bounds", goto error);547 548 if (pos + n != vec->size)549 isl_seq_cpy(vec->el + pos, vec->el + pos + n,550 vec->size - pos - n);551 552 vec->size -= n;553 554 return vec;555error:556 isl_vec_free(vec);557 return NULL;558}559 560__isl_give isl_vec *isl_vec_insert_els(__isl_take isl_vec *vec,561 unsigned pos, unsigned n)562{563 isl_vec *ext = NULL;564 565 if (n == 0)566 return vec;567 if (!vec)568 return NULL;569 570 if (pos > vec->size)571 isl_die(vec->ctx, isl_error_invalid,572 "position out of bounds", goto error);573 574 ext = isl_vec_alloc(vec->ctx, vec->size + n);575 if (!ext)576 goto error;577 578 isl_seq_cpy(ext->el, vec->el, pos);579 isl_seq_cpy(ext->el + pos + n, vec->el + pos, vec->size - pos);580 581 isl_vec_free(vec);582 return ext;583error:584 isl_vec_free(vec);585 isl_vec_free(ext);586 return NULL;587}588 589/* Add "n" elements at the end of "vec".590 */591__isl_give isl_vec *isl_vec_add_els(__isl_take isl_vec *vec, unsigned n)592{593 if (!vec)594 return NULL;595 return isl_vec_insert_els(vec, vec->size, n);596}597 598__isl_give isl_vec *isl_vec_insert_zero_els(__isl_take isl_vec *vec,599 unsigned pos, unsigned n)600{601 vec = isl_vec_insert_els(vec, pos, n);602 if (!vec)603 return NULL;604 605 isl_seq_clr(vec->el + pos, n);606 607 return vec;608}609 610/* Move the "n" elements starting as "src_pos" of "vec"611 * to "dst_pos". The elements originally at "dst_pos" are moved612 * up or down depending on whether "dst_pos" is smaller or greater613 * than "src_pos".614 */615__isl_give isl_vec *isl_vec_move_els(__isl_take isl_vec *vec,616 unsigned dst_pos, unsigned src_pos, unsigned n)617{618 isl_vec *res;619 620 if (!vec)621 return NULL;622 623 if (src_pos + n > vec->size)624 isl_die(vec->ctx, isl_error_invalid,625 "source range out of bounds", return isl_vec_free(vec));626 if (dst_pos + n > vec->size)627 isl_die(vec->ctx, isl_error_invalid,628 "destination range out of bounds",629 return isl_vec_free(vec));630 631 if (n == 0 || dst_pos == src_pos)632 return vec;633 634 res = isl_vec_alloc(vec->ctx, vec->size);635 if (!res)636 return isl_vec_free(vec);637 638 if (dst_pos < src_pos) {639 isl_seq_cpy(res->el, vec->el, dst_pos);640 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);641 isl_seq_cpy(res->el + dst_pos + n,642 vec->el + dst_pos, src_pos - dst_pos);643 isl_seq_cpy(res->el + src_pos + n,644 vec->el + src_pos + n, res->size - src_pos - n);645 } else {646 isl_seq_cpy(res->el, vec->el, src_pos);647 isl_seq_cpy(res->el + src_pos,648 vec->el + src_pos + n, dst_pos - src_pos);649 isl_seq_cpy(res->el + dst_pos, vec->el + src_pos, n);650 isl_seq_cpy(res->el + dst_pos + n,651 vec->el + dst_pos + n, res->size - dst_pos - n);652 }653 654 isl_vec_free(vec);655 return res;656}657 658/* Reorder the elements of "vec" starting at "offset" based659 * on the given reordering.660 */661__isl_give isl_vec *isl_vec_reorder(__isl_take isl_vec *vec,662 unsigned offset, __isl_take isl_reordering *r)663{664 isl_vec *res;665 int i;666 667 if (!vec || !r)668 goto error;669 670 res = isl_vec_alloc(vec->ctx, offset + r->dst_len);671 if (!res)672 goto error;673 isl_seq_cpy(res->el, vec->el, offset);674 isl_seq_clr(res->el + offset, res->size - offset);675 for (i = 0; i < r->src_len; ++i)676 isl_int_set(res->el[offset + r->pos[i]], vec->el[offset + i]);677 678 isl_reordering_free(r);679 isl_vec_free(vec);680 return res;681error:682 isl_vec_free(vec);683 isl_reordering_free(r);684 return NULL;685}686