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 d’Ulm, 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
isl_vec_get_ctx(__isl_keep isl_vec * vec)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 */
isl_vec_get_hash(__isl_keep isl_vec * vec)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
isl_vec_alloc(struct isl_ctx * ctx,unsigned size)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
isl_vec_extend(__isl_take isl_vec * vec,unsigned size)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 */
isl_vec_expand(__isl_take isl_vec * vec,int pos,int n,int * exp,int expanded)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 */
isl_vec_zero(isl_ctx * ctx,unsigned size)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
isl_vec_zero_extend(__isl_take isl_vec * vec,unsigned size)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 */
isl_vec_concat(__isl_take isl_vec * vec1,__isl_take isl_vec * vec2)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
isl_vec_copy(__isl_keep isl_vec * vec)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
isl_vec_dup(__isl_keep isl_vec * vec)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
isl_vec_cow(__isl_take isl_vec * vec)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
isl_vec_free(__isl_take isl_vec * vec)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
isl_vec_size(__isl_keep isl_vec * vec)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 */
isl_vec_get_element_val(__isl_keep isl_vec * vec,int pos)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
isl_vec_set_element(__isl_take isl_vec * vec,int pos,isl_int v)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
isl_vec_set_element_si(__isl_take isl_vec * vec,int pos,int v)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 */
isl_vec_set_element_val(__isl_take isl_vec * vec,int pos,__isl_take isl_val * v)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 */
isl_vec_cmp_element(__isl_keep isl_vec * vec1,__isl_keep isl_vec * vec2,int pos)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 */
isl_vec_is_zero(__isl_keep isl_vec * vec)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
isl_vec_is_equal(__isl_keep isl_vec * vec1,__isl_keep isl_vec * vec2)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
isl_printer_print_vec(__isl_take isl_printer * printer,__isl_keep isl_vec * vec)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
isl_vec_dump(__isl_keep isl_vec * vec)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
isl_vec_set(__isl_take isl_vec * vec,isl_int v)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
isl_vec_set_si(__isl_take isl_vec * vec,int v)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 */
isl_vec_set_val(__isl_take isl_vec * vec,__isl_take isl_val * v)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
isl_vec_clr(__isl_take isl_vec * vec)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
isl_vec_lcm(__isl_keep isl_vec * vec,isl_int * lcm)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 */
isl_vec_ceil(__isl_take isl_vec * vec)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
isl_vec_normalize(__isl_take isl_vec * vec)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
isl_vec_neg(__isl_take isl_vec * vec)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
isl_vec_scale(__isl_take isl_vec * vec,isl_int m)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 */
isl_vec_fdiv_r(__isl_take isl_vec * vec,isl_int m)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
isl_vec_add(__isl_take isl_vec * vec1,__isl_take isl_vec * vec2)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
qsort_int_cmp(const void * p1,const void * p2)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
isl_vec_sort(__isl_take isl_vec * vec)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
isl_vec_drop_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)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
isl_vec_insert_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)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 */
isl_vec_add_els(__isl_take isl_vec * vec,unsigned n)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
isl_vec_insert_zero_els(__isl_take isl_vec * vec,unsigned pos,unsigned n)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 */
isl_vec_move_els(__isl_take isl_vec * vec,unsigned dst_pos,unsigned src_pos,unsigned n)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 */
isl_vec_reorder(__isl_take isl_vec * vec,unsigned offset,__isl_take isl_reordering * r)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