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
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(p: vec->el, len: 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, n: size);
42 if (isl_blk_is_error(block: 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, block: vec->block);
54 free(ptr: 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(ctx: vec->ctx, block: vec->block, new_n: 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 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, size: 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(p: vec->el, len: 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(p: vec->el + size - extra, len: 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(vec: vec2);
176 return vec1;
177 }
178
179 if (vec1->size == 0) {
180 isl_vec_free(vec: vec1);
181 return vec2;
182 }
183
184 vec1 = isl_vec_extend(vec: vec1, size: vec1->size + vec2->size);
185 if (!vec1)
186 goto error;
187
188 isl_seq_cpy(dst: vec1->el + vec1->size - vec2->size, src: vec2->el, len: vec2->size);
189
190 isl_vec_free(vec: vec2);
191 return vec1;
192error:
193 isl_vec_free(vec: vec1);
194 isl_vec_free(vec: 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(ctx: vec->ctx, size: vec->size);
214 if (!vec2)
215 return NULL;
216 isl_seq_cpy(dst: vec2->el, src: vec->el, len: 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(ctx: vec->ctx);
243 isl_blk_free(ctx: vec->ctx, block: vec->block);
244 free(ptr: 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, n: 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: 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(b: isl_seq_first_non_zero(p: vec->el, len: 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(b: isl_seq_eq(p1: vec1->el, p2: vec2->el, len: 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(p: printer, s: "[");
361 for (i = 0; i < vec->size; ++i) {
362 if (i)
363 printer = isl_printer_print_str(p: printer, s: ",");
364 printer = isl_printer_print_isl_int(p: printer, i: vec->el[i]);
365 }
366 printer = isl_printer_print_str(p: printer, s: "]");
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(ctx: vec->ctx, stderr);
382 printer = isl_printer_print_vec(printer, vec);
383 printer = isl_printer_end_line(p: 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(p: vec->el, v, len: 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(p: vec->el, v, len: 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(p: vec->el, v: v->n, len: 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(p: vec->el, len: vec->size);
432 return vec;
433}
434
435void isl_vec_lcm(__isl_keep isl_vec *vec, isl_int *lcm)
436{
437 isl_seq_lcm(p: vec->block.data, len: 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(dst: vec->el + 1, src: vec->el + 1, m: vec->el[0], len: 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(ctx: vec->ctx, p: vec->el, len: 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(dst: vec->el, src: vec->el, len: 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(dst: vec->el, src: vec->el, f: m, len: 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(dst: vec->el, src: vec->el, m, len: 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(vec: 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(dst: vec1->el, m1: vec1->ctx->one, src1: vec1->el,
507 m2: vec1->ctx->one, src2: vec2->el, len: vec1->size);
508
509 isl_vec_free(vec: vec2);
510 return vec1;
511error:
512 isl_vec_free(vec: vec1);
513 isl_vec_free(vec: 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(base: vec->el, nmemb: vec->size, size: sizeof(*vec->el), compar: &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(dst: vec->el + pos, src: vec->el + pos + n,
550 len: 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(ctx: vec->ctx, size: vec->size + n);
575 if (!ext)
576 goto error;
577
578 isl_seq_cpy(dst: ext->el, src: vec->el, len: pos);
579 isl_seq_cpy(dst: ext->el + pos + n, src: vec->el + pos, len: vec->size - pos);
580
581 isl_vec_free(vec);
582 return ext;
583error:
584 isl_vec_free(vec);
585 isl_vec_free(vec: 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, pos: 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(p: vec->el + pos, len: 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(ctx: vec->ctx, size: vec->size);
635 if (!res)
636 return isl_vec_free(vec);
637
638 if (dst_pos < src_pos) {
639 isl_seq_cpy(dst: res->el, src: vec->el, len: dst_pos);
640 isl_seq_cpy(dst: res->el + dst_pos, src: vec->el + src_pos, len: n);
641 isl_seq_cpy(dst: res->el + dst_pos + n,
642 src: vec->el + dst_pos, len: src_pos - dst_pos);
643 isl_seq_cpy(dst: res->el + src_pos + n,
644 src: vec->el + src_pos + n, len: res->size - src_pos - n);
645 } else {
646 isl_seq_cpy(dst: res->el, src: vec->el, len: src_pos);
647 isl_seq_cpy(dst: res->el + src_pos,
648 src: vec->el + src_pos + n, len: dst_pos - src_pos);
649 isl_seq_cpy(dst: res->el + dst_pos, src: vec->el + src_pos, len: n);
650 isl_seq_cpy(dst: res->el + dst_pos + n,
651 src: vec->el + dst_pos + n, len: 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(ctx: vec->ctx, size: offset + r->dst_len);
671 if (!res)
672 goto error;
673 isl_seq_cpy(dst: res->el, src: vec->el, len: offset);
674 isl_seq_clr(p: res->el + offset, len: 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(exp: r);
679 isl_vec_free(vec);
680 return res;
681error:
682 isl_vec_free(vec);
683 isl_reordering_free(exp: r);
684 return NULL;
685}
686

source code of polly/lib/External/isl/isl_vec.c