Home | History | Annotate | Line # | Download | only in dist 
      1 /*
      2  * Copyright 2008-2009 Katholieke Universiteit Leuven
      3  * Copyright 2011      Sven Verdoolaege
      4  * Copyright 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 Ecole Normale Superieure, 45 rue dUlm, 75230 Paris, France
     11  */
     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 
     18 isl_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  */
     25 uint32_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;
     52 error:
     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;
     77 error:
     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 between
     85  * 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 by
    166  * 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;
    192 error:
    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 
    249 isl_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;
    280 error:
    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;
    296 error:
    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;
    314 error:
    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  */
    321 int 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  */
    334 isl_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 
    341 isl_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;
    369 error:
    370 	isl_printer_free(printer);
    371 	return NULL;
    372 }
    373 
    374 void 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;
    420 error:
    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 
    435 void 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 element
    441  * 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;
    511 error:
    512 	isl_vec_free(vec1);
    513 	isl_vec_free(vec2);
    514 	return NULL;
    515 }
    516 
    517 static 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;
    555 error:
    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;
    583 error:
    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 moved
    612  * up or down depending on whether "dst_pos" is smaller or greater
    613  * 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" based
    659  * 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;
    681 error:
    682 	isl_vec_free(vec);
    683 	isl_reordering_free(r);
    684 	return NULL;
    685 }
    686