isl_vec.c

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