isl_vec.c

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